Chapter 8   Graph Theory


그림입니다.
원본 그림의 이름: CLP000022e80015.bmp
원본 그림의 크기: 가로 497pixel, 세로 185pixel

그림입니다.
원본 그림의 이름: CLP000022e80016.bmp
원본 그림의 크기: 가로 140pixel, 세로 232pixel

[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


그림입니다.
원본 그림의 이름: CLP000022e80018.bmp
원본 그림의 크기: 가로 227pixel, 세로 148pixel  그림입니다.
원본 그림의 이름: CLP000022e80019.bmp
원본 그림의 크기: 가로 383pixel, 세로 322pixel



그림입니다.
원본 그림의 이름: CLP000022e80017.bmp
원본 그림의 크기: 가로 557pixel, 세로 473pixel

그림입니다.
원본 그림의 이름: CLP000022e80017.bmp
원본 그림의 크기: 가로 557pixel, 세로 473pixel

그림입니다.
원본 그림의 이름: CLP000022e8001a.bmp
원본 그림의 크기: 가로 719pixel, 세로 356pixel            


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 .  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 Definition  1.1

 

그림입니다.
원본 그림의 이름: CLP000022e8001b.bmp
원본 그림의 크기: 가로 803pixel, 세로 442pixel

 

 Example  1.2

 

그림입니다.
원본 그림의 이름: CLP000022e8001c.bmp
원본 그림의 크기: 가로 800pixel, 세로 308pixel

 

 Example  1.3

 

그림입니다.
원본 그림의 이름: CLP000022e8001d.bmp
원본 그림의 크기: 가로 803pixel, 세로 108pixel

 

그림입니다.
원본 그림의 이름: CLP000022e8001e.bmp
원본 그림의 크기: 가로 179pixel, 세로 335pixel그림입니다.
원본 그림의 이름: CLP000022e8001f.bmp
원본 그림의 크기: 가로 427pixel, 세로 261pixel


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 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


그림입니다.
원본 그림의 이름: CLP00000d6c0020.bmp
원본 그림의 크기: 가로 630pixel, 세로 184pixel







 Example  1.4

 

 Since the graph of Figure has neither parallel edges nor loops, it is a simple graph.

 

 Example  1.5

 

그림입니다.
원본 그림의 이름: CLP000022e80020.bmp
원본 그림의 크기: 가로 802pixel, 세로 109pixel

 

그림입니다.
원본 그림의 이름: CLP000022e80021.bmp
원본 그림의 크기: 가로 251pixel, 세로 236pixel   그림입니다.
원본 그림의 이름: CLP000022e80022.bmp
원본 그림의 크기: 가로 267pixel, 세로 373pixel

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  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




그림입니다.
원본 그림의 이름: CLP000022e80023.bmp
원본 그림의 크기: 가로 351pixel, 세로 333pixel

 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.   그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


We next develop a graph model for Bacon numbers.

  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 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.

 

그림입니다.
원본 그림의 이름: CLP000022e80024.bmp
원본 그림의 크기: 가로 653pixel, 세로 251pixel


  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 .

,   ,    ,    그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

● 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.  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


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)

그림입니다.
원본 그림의 이름: CLP000022e80025.bmp
원본 그림의 크기: 가로 801pixel, 세로 259pixel

 


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

, , , , , , , ,

, , , , , , , .

그림입니다.
원본 그림의 이름: CLP000022e80026.bmp
원본 그림의 크기: 가로 447pixel, 세로 480pixel 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 Definition  1.9

 

그림입니다.
원본 그림의 이름: CLP000022e80027.bmp
원본 그림의 크기: 가로 802pixel, 세로 58pixel

 


 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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel








 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

 

그림입니다.
원본 그림의 이름: CLP00001fd05645.bmp
원본 그림의 크기: 가로 801pixel, 세로 150pixel

 

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


그림입니다.
원본 그림의 이름: CLP00000d6c0021.bmp
원본 그림의 크기: 가로 607pixel, 세로 168pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 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 .

 

 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

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

 

그림입니다.
원본 그림의 이름: CLP00001fd00001.bmp
원본 그림의 크기: 가로 801pixel, 세로 105pixel

 

 Example  2.9

 

그림입니다.
원본 그림의 이름: CLP00001fd00002.bmp
원본 그림의 크기: 가로 801pixel, 세로 56pixel

 

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.  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 Definition  2.11

 

그림입니다.
원본 그림의 이름: CLP00001fd00003.bmp
원본 그림의 크기: 가로 800pixel, 세로 79pixel

 



 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

 

그림입니다.
원본 그림의 이름: CLP00001fd00004.bmp
원본 그림의 크기: 가로 801pixel, 세로 286pixel

 




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.  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 Definition  2.14

 

그림입니다.
원본 그림의 이름: CLP00001fd00005.bmp
원본 그림의 크기: 가로 800pixel, 세로 138pixel

 



 Example  2.15

 

그림입니다.
원본 그림의 이름: CLP00001fd00006.bmp
원본 그림의 크기: 가로 800pixel, 세로 266pixel

 

 Example  2.16

 Konigsberg Bridge Problem

그림입니다.
원본 그림의 이름: CLP00001fcc5894.bmp
원본 그림의 크기: 가로 800pixel, 세로 105pixel

 

그림입니다.
원본 그림의 이름: CLP00001fcc0001.bmp
원본 그림의 크기: 가로 804pixel, 세로 217pixel

그림입니다.
원본 그림의 이름: CLP00001fcc0002.bmp
원본 그림의 크기: 가로 766pixel, 세로 300pixel


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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


그림입니다.
원본 그림의 이름: CLP00000d6c0022.bmp
원본 그림의 크기: 가로 596pixel, 세로 236pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



 Degree of a Vertex

 is the degree of a vertex .

 is the number of degree of edges incident on .

 

 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 Theorem  2.17

 

그림입니다.
원본 그림의 이름: CLP000021fc5991.bmp
원본 그림의 크기: 가로 796pixel, 세로 132pixel

 

 Theorem  2.18

 

그림입니다.
원본 그림의 이름: CLP000021fc0001.bmp
원본 그림의 크기: 가로 798pixel, 세로 107pixel

 


그림입니다.
원본 그림의 이름: CLP000021fc0002.bmp
원본 그림의 크기: 가로 892pixel, 세로 479pixel


 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 .

 

그림입니다.
원본 그림의 이름: CLP000021fc0003.bmp
원본 그림의 크기: 가로 803pixel, 세로 328pixel

Figure 2.10 The graph for Example 2.19.




 Theorem  2.21

 

그림입니다.
원본 그림의 이름: CLP000021fc0004.bmp
원본 그림의 크기: 가로 797pixel, 세로 263pixel

 


 Corollary  2.22

 

그림입니다.
원본 그림의 이름: CLP000021fc0005.bmp
원본 그림의 크기: 가로 797pixel, 세로 220pixel

 


 Theorem  2.23

 

그림입니다.
원본 그림의 이름: CLP000021fc0006.bmp
원본 그림의 크기: 가로 798pixel, 세로 287pixel

 


 Theorem  2.24

 

그림입니다.
원본 그림의 이름: CLP000021fc0007.bmp
원본 그림의 크기: 가로 797pixel, 세로 313pixel

 

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.

그림입니다.
원본 그림의 이름: CLP000021fc0008.bmp
원본 그림의 크기: 가로 896pixel, 세로 314pixel

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.


그림입니다.
원본 그림의 이름: CLP00000d6c0023.bmp
원본 그림의 크기: 가로 605pixel, 세로 131pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Example 3.1

 

 Cycle  is a Hamiltonian cycle for the graph of Figure 3.4.

 

그림입니다.
원본 그림의 이름: CLP000021fc0009.bmp
원본 그림의 크기: 가로 223pixel, 세로 236pixel그림입니다.
원본 그림의 이름: CLP000017985b40.bmp
원본 그림의 크기: 가로 243pixel, 세로 216pixel




 Example  3.2

 

그림입니다.
원본 그림의 이름: CLP000017980001.bmp
원본 그림의 크기: 가로 800pixel, 세로 190pixel

 

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.

그림입니다.
원본 그림의 이름: CLP000017980002.bmp
원본 그림의 크기: 가로 804pixel, 세로 163pixel

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

그림입니다.

그림입니다.
원본 그림의 이름: CLP00000d6c0024.bmp
원본 그림의 크기: 가로 620pixel, 세로 186pixel

그림입니다.
원본 그림의 이름: CLP00000d6c0025.bmp
원본 그림의 크기: 가로 618pixel, 세로 352pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 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

그림입니다.
원본 그림의 이름: CLP000023905c4a.bmp
원본 그림의 크기: 가로 795pixel, 세로 360pixel

 

Proof We prove the theorem by induction on .


 Corollary  3.7

 

그림입니다.
원본 그림의 이름: CLP00000d6c5c8d.bmp
원본 그림의 크기: 가로 796pixel, 세로 41pixel

 

  

 Example  3.8

 Gray Codes and Hamiltonian Cycles

그림입니다.
원본 그림의 이름: CLP00000d6c0001.bmp
원본 그림의 크기: 가로 729pixel, 세로 376pixel

 


 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

그림입니다.   그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 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 .    그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 

 Algorithm  4.1

  Dijkstra’s Shortest-Path Algorithm

그림입니다.
원본 그림의 이름: CLP00000d6c0002.bmp
원본 그림의 크기: 가로 714pixel, 세로 449pixel

 


그림입니다.
원본 그림의 이름: CLP00000d6c0026.bmp
원본 그림의 크기: 가로 594pixel, 세로 301pixel

그림입니다.
원본 그림의 이름: CLP00000d6c0027.bmp
원본 그림의 크기: 가로 589pixel, 세로 278pixel

그림입니다.
원본 그림의 이름: CLP00000d6c0028.bmp
원본 그림의 크기: 가로 534pixel, 세로 189pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel




 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 .

그림입니다.
원본 그림의 이름: CLP00000d6c0003.bmp
원본 그림의 크기: 가로 852pixel, 세로 487pixel

그림입니다.
원본 그림의 이름: CLP00000d6c0004.bmp
원본 그림의 크기: 가로 395pixel, 세로 334pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 Theorem  4.3

 

그림입니다.
원본 그림의 이름: CLP00000d6c0005.bmp
원본 그림의 크기: 가로 795pixel, 세로 181pixel

 

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 .

그림입니다.
원본 그림의 이름: CLP00000d6c0006.bmp
원본 그림의 크기: 가로 405pixel, 세로 250pixel 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 Example  4.4

 

 Find a shortest path from  to  and its length for the graph of Figure .

 

그림입니다.
원본 그림의 이름: CLP00000d6c0007.bmp
원본 그림의 크기: 가로 873pixel, 세로 474pixel

그림입니다.
원본 그림의 이름: CLP00000d6c0008.bmp
원본 그림의 크기: 가로 405pixel, 세로 315pixel

                      Dijkstra’s algorithm is  in the worst case.   그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Theorem  4.5

 

그림입니다.
원본 그림의 이름: CLP00000d6c0009.bmp
원본 그림의 크기: 가로 797pixel, 세로 187pixel

그림입니다.
원본 그림의 이름: CLP00000d6c000a.bmp
원본 그림의 크기: 가로 798pixel, 세로 136pixel

 




                     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

   그림입니다.
원본 그림의 이름: CLP00000d6c000b.bmp
원본 그림의 크기: 가로 218pixel, 세로 171pixel

 


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

그림입니다.
원본 그림의 이름: CLP00000d6c000c.bmp
원본 그림의 크기: 가로 265pixel, 세로 170pixel




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

그림입니다.
원본 그림의 이름: CLP00000d6c0029.bmp
원본 그림의 크기: 가로 611pixel, 세로 211pixel




 Theorem  5.3

 

그림입니다.
원본 그림의 이름: CLP00000d6c000d.bmp
원본 그림의 크기: 가로 798pixel, 세로 96pixel

 

 

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 .

,          ,          ,

,          ,           그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 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

 

그림입니다.
원본 그림의 이름: CLP00000d6c000e.bmp
원본 그림의 크기: 가로 807pixel, 세로 139pixel

 


 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

 

그림입니다.
원본 그림의 이름: CLP00000d6c000f.bmp
원본 그림의 크기: 가로 797pixel, 세로 427pixel

 


 

 Corollary  6.5

 

그림입니다.
원본 그림의 이름: CLP00000d6c0010.bmp
원본 그림의 크기: 가로 797pixel, 세로 169pixel

 



 Example  6.6 

 Isomorphic and Adjacency Matrix

그림입니다.
원본 그림의 이름: CLP00000d6c0011.bmp
원본 그림의 크기: 가로 728pixel, 세로 473pixel

 


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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 Example  6.7

 

그림입니다.
원본 그림의 이름: CLP00000d6c0012.bmp
원본 그림의 크기: 가로 803pixel, 세로 361pixel

 

그림입니다.
원본 그림의 이름: CLP00000d6c002a.bmp
원본 그림의 크기: 가로 589pixel, 세로 292pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

 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 . 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 Example  6.9

 

그림입니다.
원본 그림의 이름: CLP00000d6c0013.bmp
원본 그림의 크기: 가로 762pixel, 세로 485pixel

 

 Example  6.10

 

그림입니다.
원본 그림의 이름: CLP00000d6c0014.bmp
원본 그림의 크기: 가로 805pixel, 세로 457pixel

 


그림입니다.
원본 그림의 이름: CLP00000d6c002b.bmp
원본 그림의 크기: 가로 558pixel, 세로 245pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


                           Exercises  21, 22

8.7 Planar Graphs


그림입니다.
원본 그림의 이름: CLP00000d6c0015.bmp
원본 그림의 크기: 가로 327pixel, 세로 296pixel


 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.


그림입니다.
원본 그림의 이름: CLP00000d6c0016.bmp
원본 그림의 크기: 가로 199pixel, 세로 362pixel

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

                                .  그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


   https://sagecell.sagemath.org/




 Example  7.2

 

그림입니다.
원본 그림의 이름: CLP00000d6c0017.bmp
원본 그림의 크기: 가로 807pixel, 세로 358pixel

 


그림입니다.
원본 그림의 이름: CLP00000d6c0018.bmp
원본 그림의 크기: 가로 224pixel, 세로 161pixel

 Definition  7.3

 Edges in series:

그림입니다.
원본 그림의 이름: CLP00000d6c0019.bmp
원본 그림의 크기: 가로 803pixel, 세로 137pixel

 

       그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel


 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. 

 

그림입니다.
원본 그림의 이름: CLP00000d6c001a.bmp
원본 그림의 크기: 가로 511pixel, 세로 205pixel

Figure 7.4  is obtained from  by a series reduction.


 Definition  7.5

 

그림입니다.
원본 그림의 이름: CLP00000d6c001b.bmp
원본 그림의 크기: 가로 805pixel, 세로 59pixel

 

 Example  7.6

 

그림입니다.
원본 그림의 이름: CLP00000d6c001c.bmp
원본 그림의 크기: 가로 801pixel, 세로 317pixel

 


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. 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



 Theorem  7.7

  Kuratowski’s Theorem

그림입니다.
원본 그림의 이름: CLP00000d6c001d.bmp
원본 그림의 크기: 가로 796pixel, 세로 96pixel

 

그림입니다.          그림입니다.

                                                     


 Example  7.8

 

그림입니다.
원본 그림의 이름: CLP00000d6c001e.bmp
원본 그림의 크기: 가로 614pixel, 세로 309pixel

 

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 . 그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel

그림입니다.
원본 그림의 이름: CLP00000d6c001f.bmp
원본 그림의 크기: 가로 798pixel, 세로 390pixel


 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.


그림입니다.
원본 그림의 이름: CLP00000d6c002c.bmp
원본 그림의 크기: 가로 607pixel, 세로 372pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



 Euler’s Formula for Graph

                         

, , ,               , , , 


그림입니다.
원본 그림의 이름: CLP00000d6c002d.bmp
원본 그림의 크기: 가로 598pixel, 세로 325pixel그림입니다.
원본 그림의 이름: CLP000113980012.bmp
원본 그림의 크기: 가로 23pixel, 세로 22pixel



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