Chapter 8 Graph Theory
[References]
1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson
Chapter 8 Graph Theory
8.1 Introduction
8.2 Paths and Cycles (Graphs)
8.3 Hamiltonian Cycles and
the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity(skipped)
Graphs are discrete structures consisting of vertices and edges that connect these vertices. There are different kinds of graphs, depending on whether edges have directions, whether multiple edges can connect the same pair of vertices, and whether loops are allowed. Problems in almost every conceivable discipline can be solved using graph models.We will give examples to illustrate how graphs are used as models in a variety of areas.
8.1 Introduction
● Highway system and Road inspector
Graphs are drawn with dots and lines.
The dots are vertices.
The lines connect the vertices are edges.
The edges is , , .
We start at a vertex , travel along an edge to vertex , travel along an edge to vertex , and so on, and eventually arrive at a vertex .
Path is from to .
Definition 1.1 |
|
|
Example 1.2 |
|
|
Example 1.3 |
|
|
Edges and are both associated with the vertex pair .
Edges and are parallel edge.
Edge incident on a single vertex is a loop.
For example, edge is a loop.
Vertex is not incident on any edge is an isolated vertex.
A graph with neither loops nor parallel edges is a simple graph.
Example 1.4 |
|
Since the graph of Figure has neither parallel edges nor loops, it is a simple graph.
|
Example 1.5 |
|
|
Solution
A graph with numbers on the edges is a weight graph.
Edge is labeled The weight of edge is .
The weight of edge is .
In a weight graph, the length of a path is the sum of the weights of the edges in the path.
For example The length of a path that starts at , visits , and terminates at is .
The weight of edge is .
The weight of edge is .
The length of a path is .
Example 1.6 |
Bacon Numbers |
Actor Kevin Bacon has appeared in numerous films including Diner and Apollo . A movie stars with Kevin Bacon are Bacon number one. |
For example, Ellen Barkin has Bacon number one because she appeared with Bacon in Diner.
Bacon number two is a movie star who did not appear in Bacon but appeared with a Bacon number 1 movie star.
Higher Bacon numbers are defined similarly.
For example, Bela Lugosi has Bacon number three. Lugosi was in Black Friday with Emmertt Vogan, Vogan was in With a Song in My Heart with Robert Wagner, and Wagner was in Wild Things with Bacon.
We next develop a graph model for Bacon numbers.
Example 1.7 |
Similarity Graphs |
This example deal with the problem of grouping “like” objects into classes based on properties of the objects. For example, suppose that a particular algorithm is implemented in by a number of persons and we want to group “like” programs into classes based on certain properties of the programs. Suppose that we select as properties 1. The number of lines in the program. 2. The number of return statements in the program. 3. The number of function calls in the program. |
● Similarity Graph
A similarity graph is constructed as follows.
The vertices correspond to programs.
A vertex is , where is the value of property .
is the set of programs .
Each vertex is assigned a triple ,
where is the value of property or .
, , , ,
● Dissimilarity Function
Define a dissimilarity function as follows.
For each pair of vertices and , we set
.
is the vertex corresponding to program , we obtain
, , , ,
,
, , , , ,
, , , .
If and are vertices corresponding two programs, is a measure of how dissimilarity the programs are.
A large value of indicates dissimilarity.
A small value of indicates similarity.
For a fixed a number .
Insert an edge between vertices and if .
and are in the same class if or there is a path from to .
Figure 1.9 A similarity graph corresponding to the programs of Table 1.2 with .
In Figure 1.9 we show the graph corresponding to the programs of Table 1.2 with . In this graph, the programs are grouped into three classes , and . An appropriate value for might be selected by trial and error or the values of might be selected automatically according to some predetermined criteria.
Dissimilarity function values
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, and all other
There are three classes : , and .
Example 1.8 |
The -Cube (Hypercube) |
|
We discuss one model for parallel computation known as the -cube or hypercube.
The cube has processors,
Vertices are labeled
An edge connects two vertices if the binary representation of their labels differs in
exactly one bit
cube
cube has two processors labeled 0 and 1, and one edge
Let and be two cubes whose vertices are labeled in binary
Place an edge between each pair of vertices, one from and one from ,
provided that the vertices have identical labels.
Change the label on each vertex in to and
Change the label on each vertex in to
(a line)
has only vertices and .
has no cycle.
(a square)
has vertices labeled , , and .
A Hamilton cycle is (, , , , )
(a cube)
has vertices, edges and faces.
Vertex labels , , , , , , and .
A Hamilton cycle is (, , , , , , , , )
Figure 1.10 The 3-cube
(a hypercube)
has vertices, edges and faces.
Vertex labels
, , , , , , , ,
, , , , , , , .
Definition 1.9 |
|
|
Example 1.10 |
|
The complete graph on four vertices, , is shown in Figure 1.12. |
Figure 1.12 The complete graph .
Definition 1.11 |
|
A graph is bipartite if there exist subsets and of , each edge in is incident on one vertex in and one vertex in . |
Example 1.12 |
|
The graph in Figure 1.13 is bipartite. Since if we let and , each edges is incident on one vertex in and one vertex in . |
Figure 1.13 A bipartite graph.
is an edge in a bipartite graph, then is incident on one vertex in and one vertex in .
If and , then there is an edge between and .
The graph of Figure 1.13 is bipartite since each edge is incident on one vertex in and one vertex in .
Not all edges between vertices in and are in the graph.
For example, the edge is absent.
Example 1.13 |
|
The graph in Figure 1.14 is not bipartite. It is often easiest to prove that a graph is not bipartite by arguing by contradiction. |
Figure 1.14 A graph that is not bipartite.
The graph of Figure 1.14 is bipartite.
The vertex set can be partitioned into two subsets and .
Each edge is incident on one vertex in and one vertex in .
Consider the vertices , and .
and are adjacent one in and the other in .
is in and is in .
and are adjacent one in and the other in .
is in and is in .
and are adjacent one in and the other in .
is in and is in .
is in both and .
and are not disjoint.
The graph of Figure 1.14 is not bipartite.
Example 1.14 |
|
The complete graph on one vertex is bipartite. Let be the set containing the one vertex and be the empty set. Then each edges is incident on one vertex in and one vertex in . |
Definition 1.15 |
|
is the complete bipartite graph on and vertices. is the simple graph whose vertex set is partitioned into sets with vertices and with vertices in which the edge set consists of all edges of the from with and . |
Example 1.16 |
|
Complete bipartite graph on two and four vertices, is shown in Figure 1.15. |
Figure 1.15 The complete bipartite graph
Exercises 1, 2
8.2 Paths and Cycles
Definition 2.1 |
|
|
Start at vertex ; go along edge to ; go along edge to ; and so on.
Example 2.2 |
|
In the graph of Figure 2.1,
is a path of length from vertex to vertex . |
Figure 2.1 A connected graph with paths of length and of length .
Example 2.3 |
|
In the graph of Figure 2.1, the path consisting solely of vertex is a path of length from vertex to vertex . |
A connected graph is a graph in which we can get from any vertex to any other vertex on a path.
Definition 2.4 |
|
A graph is connected if given any vertices and in , there is a path from to . |
Example 2.5 |
|
The graph of Figure 2.1 is connected since given any vertices and in , there is a path from to . |
Example 2.6 |
|
Graph of Figure 2.2 is not connected since, there is no path from to . |
Figure 2.2 A graph that is not connected.
As we can see from Figure 2.1 and 2.2, a connected graph consist of one “piece,” which a graph that is not connected consists of two or more “piece.” These “piece” are subgraphs of the original graph and are called components. We give the formal definitions beginning with subgraph.
A subgraph of a graph is obtained by selecting certain edges and vertices from subject to the restriction that if we select an edge that is incident on vertices and , we include . The restriction is to ensure that is a actually a graph.
Definition 2.8 |
|
|
Example 2.9 |
|
|
Figure 2.3 A subgraph of the graph of Figure 2.4.
Figure 2.4 A graph, one of whose subgraphs is shown in Figure 2.3.
Example 2.10 |
|
Find all subgraphs of the graph of Figure 2.5 having at least one vertex. |
Solution
Graphs , and have not edge.
Graphs , and are a subgraph of graph .
We select the one edge .
is incident the two vertices.
Graph is a subgraph of graph .
Thus has the four subgraphs.
Figure 2.5 The graph for Example 2.10.
Figure 2.6 The four subgraphs of the graph of Figure 2.5.
Definition 2.11 |
|
|
Example 2.12 |
|
The graph of Figure 2.1 has one component, namely itself. A graph is connect it has exactly one component. |
Example 2.13 |
|
|
The component of a graph is obtained by defining a relation on the set of
vertices by the rule
path from to
is an equivalence relation on .
If , the set of vertices in the component containing is the equivalence class
.
Definition of “path” allows repetitions of vertices or edges or both.
Definition 2.14 |
|
|
Example 2.15 |
|
|
Example 2.16 |
Konigsberg Bridge Problem |
|
Konigsberg Bridge Problem
Starting and ending at the same point, is it possible to cross all seven bridges just once and return to the starting point?
This problem can represented by a graph
Edges represent bridges and each vertex represents a region.
● Degree of a Vertex
is the degree of a vertex .
is the number of degree of edges incident on .
Theorem 2.17 |
|
|
Theorem 2.18 |
|
|
Example 2.19 |
|
is the graph of Figure 2.10. Use Theorem 2.18 to verify that has an Euler cycle. Find an Euler cycle for . |
Figure 2.10 The graph for Example 2.19.
Theorem 2.21 |
|
|
Corollary 2.22 |
|
|
Theorem 2.23 |
|
|
Theorem 2.24 |
|
|
Figure 2.12 A cycle that either is a simple cycle or can be reduced to a simple cycle.
Exercises 5, 6, 8
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
● Hamilton’s puzzle
Each corner bore the name of a city and the problem was to start any city, travel along the edges, visit each city exactly one time, and return to the initial city.
A cycle in a graph contains each vertex in exactly once, except for the starting and ending vertex that appears twice, a Hamiltonian cycle.
A connected graph has a Hamiltonian cycle is a Hamiltonian graph.
Example 3.1 |
|
Cycle is a Hamiltonian cycle for the graph of Figure 3.4. |
Example 3.2 |
|
|
Figure 3.6 A graph with a Hamiltonian cycle.
Example 3.3 |
|
Show that the graph of Figure 3.7 does not contain a Hamiltonian cycle. |
Figure 3.7 A graph with no Hamiltonian cycle.
● Traveling Salesperson Problem
Given a weighted graph , find a minimum-length Hamiltonian cycle in .
Traveling salesperson problem
1. To visit every vertex of a graph G only once by a simple cycle.
2. Such a cycle is called a Hamiltonian cycle.
3. If a connected graph G has a Hamiltonian cycle, G is called a Hamiltonian graph.
Example 3.4 |
|
The cycle is a Hamiltonian cycle for the graph of Figure 3.8. Replacing any of the edges in by either of the edges labeled would increase the length of is a minimum-length Hamiltonian cycle for . Thus solves the traveling salesperson problem for . |
Figure 3.8 A graph for the traveling salesperson problem.
Example 3.5 |
Gray Codes and Hamiltonian Cycles in the Cube |
Considered a ring model for parallel computation is a simple cycle. A Gray code is a sequence such that every bit string appears somewhere in the sequence and differ in exactly one bit, And and differ in exactly one bit. |
Considered a ring model for parallel computation is a simple cycle.
● Parallel computation models
The n-cube has processors,
1. Vertices are labeled 0, 1, 2, …,
2. An edge connects two vertices if the binary representation of their labels differs in exactly one bit
3. n-cube
a. 1-cube has two processors labeled 0 and 1, and one edge
b. and be two (n-1)-cubes whose vertices are labeled in binary 0, 1, …,
c. Place an edge between each pair of vertices, one from and one from ,
provided that the vertices have identical labels.
d. Change the label L on each vertex in to 0L and
Change the label L on each vertex in to 1L
Theorem 3.6 |
Gray Codes and Hamiltonian Cycles |
|
Proof We prove the theorem by induction on .
Corollary 3.7 |
|
|
Example 3.8 |
Gray Codes and Hamiltonian Cycles |
|
● Gray Codes and Hamiltonian Cycles
is a line.
has only two vertices and .
has no cycle.
is a square.
has vertices labeled , , and
A Hamiltonian cycle is
is a cube.
has 8 vertices labeled 000, 001, 010, 011, 100, 101, 110, and 111.
A Hamiltonian cycle is .
is a hypercube.
has vertices, edges and faces
Vertex labels:
0000 0001 0010 0011
0100 0101 0110 0111
1000 1001 1010 1011
1100 1101 1110 1111
Example 3.9 |
The Knight’s Tour |
In chess, the Knight’s move consists of moving two squares horizontally or vertically and then moving one square in the perpendicular direction. For example, in Figure a Knight on the square marked can move to any of the square marked . A Knight’s tourof an board begins at some square, visits each square exactly once marking legal moves, and returns to the initial square. The problem is to determine for which a Knight’s tour exists. |
Figure 3.10 The Knight’s legal moves in chess.
Figure 3.11 A chessboard and the graph .
Exercises 9. 11
8.4 A Shortest-Path Algorithm
A weighted graph is a graph in which values are assigned to the edges.
The length of a path in a weighted graph is the sum of the weights of the edges in the path. is the weight of edge .
In weighted graphs, we often want to find a shortest path between two given vertices.
is a connected, weighted graph.
The weights are positive numbers.
Find a shortest path from vertex to vertex .
Dijkstra’s algorithm involves assigns labels to vertices.
is the label of vertex .
At any point, some vertices have temporary labels and rest have permanent labels.
is the set of vertices having temporary labels.
We will circle vertices having permanent labels.
If is the permanent label of vertex , then is the length of a shortest path from vertex to vertex .
All vertices have temporary labels.
Each iteration of the algorithm changes the status of one label from temporary to permanent; thus we may terminate the algorithm when receives a permanent label.
gives length of a shortest path from to .
Algorithm 4.1 |
Dijkstra’s Shortest-Path Algorithm |
|
Example 4.2 |
|
Show how Algorithm 4.1 finds a shortest path from to in the graph of Figure . Figure 4.2 shows the result of executing lines . |
Solution
At line , is not circled.
We proceed to line , where we select vertex , the uncircled vertex with the smallest label, and circle it. At lines and we update each of the uncircled vertices and , adjacent to .We obtain the labels
, .
At this point, we return to line . is not circled.
We proceed to line , where we select vertex , the uncircled vertex with the smallest label, and circle it. At lines and we update each of the uncircled vertices and , adjacent to . We obtain the labels show in Figure 4.4. is labeled , indicating that the length of a shortest path from to is . A shortest path is given by .
Theorem 4.3 |
|
|
Proof
We use mathematical induction on to prove that the time we arrive at line ,
is the length of a shortest path from to .
This proved, correctness of the algorithm follows since when is chosen at line ,
give the length of a shortest path from to .
Example 4.4 |
|
Find a shortest path from to and its length for the graph of Figure . |
Dijkstra’s algorithm is in the worst case.
Theorem 4.5 |
|
|
Exercises 13, 14, 15, 16
8.5 Representations of Graphs
Our first method of representing a graph uses the adjacency matrix.
Example 5.1 |
adjacency matrix |
Consider the graph of Figure 5.1. To obtain the adjacency matrix of this graph, we first select an ordering of the vertices, say , , , , . Next, we label the rows and columns of a matrix with the ordered vertices. The entry in this matrix in row , column , is the number of edges incident on and . , the entry is twice the number of loops incident on . The adjacency matrix for this graph is
|
We obtain the degree of a vertex in a graph by summing row or column in ’s adjacency matrix.
● The adjacency matrix is symmetric about the main diagonal, the information except that on the main diagonal appears twice.
Example 5.2 |
|
The adjacency matrix of the simple graph of Figure is
|
● If is the adjacency matrix of a simple graph , the powers of ,
, , ,
count the number or paths of various lengths.
The vertices of are labeled , the entry in the matrix is equal to the number of paths from to of length .
Consider the entry for row , column c in , obtained by multiplying pairwise the entries in row by the entries in column of matrix and summing:
.
This happens if there is a vertex whose entry in row is .
This happens if there is a vertex whose entry in column is . .
Such edges from a path of length from to and each path increases the sum by .
The sum is because there are two paths
,
of length from to .
In general, the entry in row and column of the matrix is the number of paths of length from vertex to vertex .
The entries on the diagonal give the degree of the vertices.
Consider vertices .
The degree of is since is incident on the three edges , and .
But each of these edges can be converted to a path of length from to
, ,
A path of length from to defines an edge incident on .
Thus the number of paths of length from to is , the degree of .
Theorem 5.3 |
|
|
We will use induction on .
Figure 5.3 The proof of Theorem .
A path from to of length whose next-to-last vertex is consists of a path of length from to followed by edge .
There are paths of length from to and is if edge exists and .
Otherwise, the sum of over all gives the number of paths of length from to .
Example 5.4 |
|
After Example 5.2, we showed that if is the matrix of the graph of Figure , then
The entry from row , column is , which means that there are six paths of length from to .
, , ,
, , .
Example 5.5 |
Incidence Matrix |
To obtain the incidence matrix of the graph, we label the rows with the vertices and columns with the edges. The entry for row and column is if is incident on and otherwise. Thus the incidence matrix for the graph of Figure 5.4.
Figure 5.4 A column such as is understood to represent a loop. |
Exercises 19, 20
8.6 Isomorphisms of Graphs
● Isomorphic Graphs
Draw and label five vertices , , , and .
Connect and , and , and , and , and .
Surely these figures define the same graph even though they appear dissimilar.
The two graphs are the same graph, but the shapes are different.
Same graphs are isomorphic.
Figure 6.1 Isomorphic graph
Definition 6.1 |
|
|
Example 6.2 |
|
An isomorphism for the and of Figure 6.1 is defined by
, , , , , , , , . |
and are isomorphic
we define a relation on a set of graphs by the rule
is an equivalence relation.
Each equivalence class consist of a set of mutually isomorphic graphs.
Theorem 6.4 |
|
|
Corollary 6.5 |
|
|
Example 6.6 |
Isomorphic and Adjacency Matrix |
|
Two simple graph and are not isomorphic.
Find a property of that does not have but that would have if and were isomorphic.
Such a property is an invariant.
A property is an invariant if whenever and are isomorphic graphs:
If has property , has property .
By Definition 6.1, if graphs and are isomorphic, there are one-to-one, onto functions from the edges of to the edges of .
and are isomorphic, then and have the same number of edges and the same number of vertices.
Therefore, if and are nonnegative integers, the properties “has edges” and “has vertices” are invariants.
Example 6.7 |
|
|
Example 6.8 |
|
Show that if is a positive integer, “has a vertex of degree ” is an invariant. |
Solution
and are isomorphic graphs.
is a one-to-one, onto function.
has a vertex of degree .
Then there are edges incident on .
By Definition 6.1, are incident on .
is one-to-one, .
Let be an edge that is incident on in .
Since is onto, there is an edge in with .
Since is incident on in , by Definition , is incident on in .
Since are the only edges in incident on , for some .
Now .
, so has a vertex, namely , of degree .
Example 6.9 |
|
|
Example 6.10 |
|
|
Exercises 21, 22
8.7 Planar Graphs
Definition 7.1 |
|
A graph is planer if it can be drawn in the plane without its edges crossing. |
If a connected, planar graph is drawn in the plane, the plane is divided into contiguous regions called faces. A face is characterized by the cycle that forms its boundary.
The face is bounded by the cycle .
The face is bounded by the cycle .
The face is bounded by the cycle .
The outer face is considered to be bounded by the cycle .
The graph of Figure 7.2 has faces, edges and vertices.
, and satisfy the equation
.
https://sagecell.sagemath.org/
Example 7.2 |
|
|
Definition 7.3 |
Edges in series: |
|
Example 7.4 |
|
In the graph of Figure the edges and are in series. The graph of Figure is obtained from by a series reduction. |
Figure 7.4 is obtained from by a series reduction.
Definition 7.5 |
|
|
Example 7.6 |
|
|
Define a relation on a set of graphs by the rule if and are homeomorphic, is an equivalence relation.
Each equivalence class consists of a set of mutually homeomorphic graphs.
Theorem 7.7 |
Kuratowski’s Theorem |
|
Example 7.8 |
|
|
Solution
The vertices , , and each have degree . In each vertex has degree ,
so let us eliminate the edges and so that all vertices have degree .
We note that if we eliminate one more edge, we will obtain two vertices of degree and we can then carry out two series reductions. The resulting graph will have nine edges; since has nine edges, this approach looks promising. Using trial and error, we finally see that if we eliminate edge and carry out the series reductions, we obtain an isomorhic copy of . Therefore, the graph of Figure 7.6 is not planar, since it containing a subgraph homeomorphic to .
Theorem 7.9 |
Euler’s Formula for Graphs |
If is a connected, planar graph with edges, vertices and faces, then (8.7.3) . |
, , , ,
Figure 7.8 The Basis Step of Theorem 7.9
Figure 7.10 The proof of Theorem 7.9 for the case that has a cycle. We delete edge in a cycle.
● Euler’s Formula for Graph
, , , , , ,
Exercises 25, 26, 27
Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).