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 .

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

,     .

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

.

 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