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.

Figure 1.10 The 3-cube

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 .

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.

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.

●  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 tour of 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 .

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

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

                                . 

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