[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 .  

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.  

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 .  

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.

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

We discuss one model for parallel computation known as the -cube or hypercube.

Figure 1.10 The 3-cube

Figure 1.12 The complete graph .

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. 

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. 

Figure 1.15 The complete bipartite graph 

Exercises  1, 2

8.2 Paths and Cycles

Start at vertex ; go along edge  to ; go along edge  to ; and so on.

Figure 2.1 A connected graph with paths  of length  and  of length .

A connected graph is a graph in which we can get from any vertex to any other vertex on a path.

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.

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.

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.  

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.  

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 .

Figure 2.10 The graph for Example 2.19.

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.

Figure 3.6 A graph with 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.

Figure 3.8 A graph for the traveling salesperson problem.

●  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

Proof We prove the theorem by induction on .

● 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

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 .

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 .

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 .

                      Dijkstra’s algorithm is  in the worst case.   

                     Exercises  13, 14, 15, 16

8.5 Representations of Graphs

Our first method of representing a graph uses the adjacency matrix.

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. 

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

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 .

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 .

,          ,          ,

,          ,          .  

                                 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

 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.

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. 

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 . 

                           Exercises  21, 22

8.7 Planar Graphs

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

                                .  

Figure 7.4  is obtained from  by a series reduction.

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. 

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 . 

, ,          , , 

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