Eulerian circuits. If a graph represents transportation
routes in a city or across a nation, for example, then
seeking Eulerian circuits for the graph can have important practical use.
In 1857 WILLIAM ROWAN HAMILTON explored the
issue of finding paths through graphs that do not necessarily trace each edge, but instead visit each vertex in
the graph once, and only once. Today such a path is
called a Hamiltonian path, or a Hamiltonian circuit if
it is a path that returns to the starting vertex. Although
mathematicians have developed some theorems that
give conditions under which Hamiltonian paths will
exist, no one to this day knows a simple algorithm that
enables us to find them. Each graph must still be examined individually, and finding a Hamiltonian path—if
one exists—is usually a matter of inspired guessing.
Simple counting can lead to important results in
graph theory. For example, summing the degrees of all
the vertices in a graph counts the total numbers of ends
of edges. As every edge has two ends, we have:
In any graph, the sum of the degrees of all the
vertices equals twice the number of edges in
the graph.
In particular, the sum of all the degrees of vertices must
be an even number. Consequently, there cannot be an
odd number of odd numbers in this sum.
In any graph, the number of vertices of odd
degree is even.
This result has an amusing interpretation. Thinking
of edges in a graph as handshakes between people, we
have established the so-called HANDSHAKE LEMMA:
At any instant, the number of people on this
planet, living or deceased, who have participated in an odd number of handshakes is even.
A POLYHEDRON can be thought of as a graph drawn
on a SPHERE—each corner of the polyhedron is a vertex, and each edge of the figure is an edge of the
graph. If a polyhedron consists of only t triangular
faces, then 3t counts the number of edges of the figure
twice (each triangle has three edges, and each edge
borders two triangles). Thus 3t = 2e, where e is the
number of edges. This shows that t must be an even
number. We have:
It is impossible to cover a sphere with an odd
number of triangles.
Euler also went on to show that for any graph drawn
on a plane or a sphere (with no edges of the graph
intersecting):
v – e + r = 2
where v is the number of vertices the graph possesses, e
its number of edges, and r the number of regions
defined by the graph—including the large “outer”
region if the graph is drawn on a plane. This is called
EULER’S FORMULA. If the graph is drawn instead on a
TORUS, this formula is modified to read: v – e + r = 0.
Graph theory is a discipline under intense continued study. Its many applications vary from the purely
theoretical to the very concrete and practical. Routing
problems, information-flow problems, and electronic
circuit design, for example, can all be effectively analyzed and refined through the study of this field.
See also EULERIAN PATH/CIRCUIT; HAMILTONIAN
PATH/CIRCUIT; THREE-UTILITIES PROBLEM; TOPOLOGY;
TOURNAMENT; TRAVELING-SALESMAN PROBLEM.
greatest common divisor (greatest common factor,
highest common factor) The largest FACTOR common
to a given set of integers is called the greatest common
divisor of those integers. For example, the numbers 72,
120, and 180 have factors 1, 2, 3, 4, 6, and 12 in common, with 12 being the greatest common divisor. We
write gcd(72, 120, 180) = 12.
One can find the greatest common divisor of two
or more integers simply by listing the factors of each
integer and identifying the largest factor they have in
common. Alternatively, if the prime decompositions of
the integers are known, then their greatest common
divisor can be determined as the product of the primes
they have in common. For example, noting that:
72 = 2 × 2 × 2 × 3× 3
120 = 2 × 2 × 2 × 3× 5
180 = 2 × 2 × 3 × 3× 5
we see that these three numbers share, as prime factors,
two 2s and one 3. Their greatest common divisor is
thus gcd (72,120,180) = 2 × 2 × 3 = 12. (This second
236 greatest common divisor
routes in a city or across a nation, for example, then
seeking Eulerian circuits for the graph can have important practical use.
In 1857 WILLIAM ROWAN HAMILTON explored the
issue of finding paths through graphs that do not necessarily trace each edge, but instead visit each vertex in
the graph once, and only once. Today such a path is
called a Hamiltonian path, or a Hamiltonian circuit if
it is a path that returns to the starting vertex. Although
mathematicians have developed some theorems that
give conditions under which Hamiltonian paths will
exist, no one to this day knows a simple algorithm that
enables us to find them. Each graph must still be examined individually, and finding a Hamiltonian path—if
one exists—is usually a matter of inspired guessing.
Simple counting can lead to important results in
graph theory. For example, summing the degrees of all
the vertices in a graph counts the total numbers of ends
of edges. As every edge has two ends, we have:
In any graph, the sum of the degrees of all the
vertices equals twice the number of edges in
the graph.
In particular, the sum of all the degrees of vertices must
be an even number. Consequently, there cannot be an
odd number of odd numbers in this sum.
In any graph, the number of vertices of odd
degree is even.
This result has an amusing interpretation. Thinking
of edges in a graph as handshakes between people, we
have established the so-called HANDSHAKE LEMMA:
At any instant, the number of people on this
planet, living or deceased, who have participated in an odd number of handshakes is even.
A POLYHEDRON can be thought of as a graph drawn
on a SPHERE—each corner of the polyhedron is a vertex, and each edge of the figure is an edge of the
graph. If a polyhedron consists of only t triangular
faces, then 3t counts the number of edges of the figure
twice (each triangle has three edges, and each edge
borders two triangles). Thus 3t = 2e, where e is the
number of edges. This shows that t must be an even
number. We have:
It is impossible to cover a sphere with an odd
number of triangles.
Euler also went on to show that for any graph drawn
on a plane or a sphere (with no edges of the graph
intersecting):
v – e + r = 2
where v is the number of vertices the graph possesses, e
its number of edges, and r the number of regions
defined by the graph—including the large “outer”
region if the graph is drawn on a plane. This is called
EULER’S FORMULA. If the graph is drawn instead on a
TORUS, this formula is modified to read: v – e + r = 0.
Graph theory is a discipline under intense continued study. Its many applications vary from the purely
theoretical to the very concrete and practical. Routing
problems, information-flow problems, and electronic
circuit design, for example, can all be effectively analyzed and refined through the study of this field.
See also EULERIAN PATH/CIRCUIT; HAMILTONIAN
PATH/CIRCUIT; THREE-UTILITIES PROBLEM; TOPOLOGY;
TOURNAMENT; TRAVELING-SALESMAN PROBLEM.
greatest common divisor (greatest common factor,
highest common factor) The largest FACTOR common
to a given set of integers is called the greatest common
divisor of those integers. For example, the numbers 72,
120, and 180 have factors 1, 2, 3, 4, 6, and 12 in common, with 12 being the greatest common divisor. We
write gcd(72, 120, 180) = 12.
One can find the greatest common divisor of two
or more integers simply by listing the factors of each
integer and identifying the largest factor they have in
common. Alternatively, if the prime decompositions of
the integers are known, then their greatest common
divisor can be determined as the product of the primes
they have in common. For example, noting that:
72 = 2 × 2 × 2 × 3× 3
120 = 2 × 2 × 2 × 3× 5
180 = 2 × 2 × 3 × 3× 5
we see that these three numbers share, as prime factors,
two 2s and one 3. Their greatest common divisor is
thus gcd (72,120,180) = 2 × 2 × 3 = 12. (This second
236 greatest common divisor