Chapter 9
Graphs

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter9/extra_examples.html - Extra examples with solutions.

Graphs

Graphs represent mathematical connections, a way of encoding networks of relations.

Graph (map) representing the connection network of the US Interstate Highway system.

The Project Evaluation and Review Technique (PERT), is a model designed to analyze and represent the tasks involved in completing a project.

PERT network chart for a seven-month project with five milestones (10 through 50) and six activities (A through F). From Wikipedia.

 

Class dependency diagram of the Java program, Zuul. Produced by BlueJ.

Facebook friends

 

9.1 Graphs and Graph Models

Definition 1

Graph G=(V,E) V - finite set called the vertex set whose elements are called vertices E - is a binary relation on V called the edge set, whose elements are called edges

Examples

Undirected V = {1, 2, 3, 4, 5} E = {(1,2)(2,1)(1,5)(5,1)(2,5)(5,2)(4,2)(2,4)(4,5)(5,4)(4,3)(3,4)(2,3)(3,2)}   Note edge pairs: (2,5), (5,2) Question 9.1.1 Is (1, 2) an edge? Is (2, 1) an edge? Is (1, 4) an edge?

Directed V = {1, 2, 3, 4} E = {(1,2)(2,4)(3,1)(3,2)(4,3)(4,4)} Question 9.1.2 Is (1, 2) an edge? Is (2, 1) an edge?  Is (3, 3) an edge?   Is (4, 4) an edge?

Definition

Simple Graph Each edge connects two different vertices. No loops. No two different edges connect the same pair of vertices. Only one edge between.

Example

Undirected Graph Simple

Directed Graph Not simple - loop.

Question 9.2 - Which of the following graphs are simple?

a.

b.

 

Definition 2

Directed Graph The ordered pairs in E represent the direction of the edge, i.e., (tail, head) tail is source vertex and head is the target vertex

Undirected Graph The pairs in E are unordered pairs, i.e., there is no tail or head and there is no direction to the edge e.g., (u, v) ∈ E is really the same edge as (v, u)

 

Graph Models

Definition

Graph model a graph is an abstract mathematical entity modeling tool: a graph becomes a model when a graph is used to represent either a physical entity, or a conceptual entity

Example:

V (vertex set) contains city names representing cities

E (edge set) contains edges that represent the roads connecting the cities

Building a model

Need to:

• decide what the vertices represent
• decide what the edges represent
• answer the following three questions:
  
  1. Are the edges of the graph undirected or directed (or does the graph contain both types of edges)?
     
  2. Are multiple edges present that connect the the same pair of vertices?
     
  3. Are loops present?

 

Figure 1     Computer Network

Question 9.3.1 - Why is an undirected graph a good model of the network?

 

Figure 2     Highway Network with Multiple Links

Question 9.3.2 - Why multiple undirected links?

 

Figure 3     Computer Network with Diagnostic Links

Question 9.3.3 - Why loops?

 

Figure 4     Television Network with One-way Links

Question 9.3.4 - Why one-way?

 

Figure 5     Television Network with Multiple One-way Links

Question 9.3.5 - Why multiple one-way?

Question 9.3.6 - How many (Denver, Chicago)?

 

 

Figure 6     Niche Overlap Graph

Connected vertices compete. The number of vertex connections are the number of competitors.

The woodpecker competes with squirrels, opossums and shrews.

Question 9.4 - What animals does the crow compete with?

 

Figure 7     Acquaintance Graph

Question 9.5.1

1. With whom can Ching connect through one acquaintance?
   
   

2. Is Ching 4 acquaintances away from Kari?
   
   

3. Who is the most directly connected (popular) person?

 

Figure 8     Influence Graph

Linda influences no one.

Question 9.5.2 - Who influences Brian?

 

 

 

Figure 11   Precedence Graph

S₁ and S₂ can execute in parallel.

S₁ and S₃ must execute in series, S₁ first.

S₆ requires S₁, S₂, S₃ and S₄ to execute first. Consider that S₆ includes variable c computed in S₃.

Question 9.6

1. Can S₆ be executed before S₃?
   
   

2. Can S₆ be executed before or after S₅?

 

9.2 Graph Terminology and Special Types of Graphs

Basic Terminology

Definitions

Adjacent Vertices - means there is an edge from u to v, i.e., (u, v) undirected graph - (u, v) means v is adjacent to u, and vice versa. Example: (2, 3) and (3, 2) are adjacent. directed graph - (u, v) means v is adjacent to u, but unless there is an edge (v, u), then u is not adjacent to v. Example: (3, 2) means 3 is adjacent to 2   but 2 is not adjacent to 3. adjacent vertices are said to be neighbors.

Undirected Graph

Directed Graph

 

Definition

Degree in an undirected graph is number of incident edges at a vertex.

Example:     Vertex 5 has degree 3.

Question 9.7

1. Degree of vertex 2?
   
   

2. Is vertex 1 adjacent to vertex 3?

Theorem 1

Handshaking Theorem G=(V,E) an undirected graph with e edges. i.e. 2 edges between adjacent vertices.

Undirected Graph with edge (1,2) and (2,1)

Question 9.7 - What is the degree summation of the above graph?

 

How many edges are there in an undirected graph with the degree sum of 14?

2e = 14

e = 7

 

Theorem 2

An undirected graph has an even number of vertices of odd degree.

Example

Vertices 4 and 5 are odd degree, 3.

Vertices 1, 2 and 3 are even degree.

Undirected Graph

 

Definition 4

Degree - the number of edges incident on a vertex undirected graph - the degree equals the number of edges incident on a vertex. vertex 2 has degree 4. directed graph in-degree, deg-(v)  equals the number of edges who have their head at a vertex, or targeting the vertex vertex 2 has in-degree 2. out-degree, deg+(v)   equals the number of edges emanating from the vertex. vertex 2 has out-degree 1.

Directed Graph Question 9.7 What is deg-(3)? What is deg+(3)? What is deg+(4)?

Undirected Graph Question 9.8 What is deg(4)?

 

Theorem 2

Let G=(V,E) be a graph with directed edges. Then

Example

Theorem says that one vertex's out-edge is another's in-edge, an edge always connects two vertices.

 

Some Special Graphs

Directed Graph G

Graphs Kn for 1 ≤ n ≤6 Models connections in fully-connected communication or multi-processor computer systems.

Complete graph on n vertices, Kn Simple graph that contains one edge between each pair of vertices.

 

Cycles - Cn, n ≥ 3, n vertices v1,v2,...,vn, and edges {v1,v2},{v2,v3},...,{vn-1,vn},{vn,v1}

Models some local area network topologies (e.g. Token-Ring, Fiber Distributed Data Interface or FDDI).

 

Wheels - Wn, add vertex to Cn, n ≥ 3, and connect to each of the n vertices

Models some multi-processor computer systems having central and neighbor connections. No more than two hops away from any other processor.

 

n-Cubes - Qn, graphs representing 2n bit strings of length n.  Q3 graph represents 23 bit strings of length 3.  Each adjacent vertex changes by only a single bit. A 4-bit representation would be a 4-dimensional n-Cube.

Only one bit changes between neighbors.

Models algorithm search-space, changing only one parameter at a time in the search, can be applied to genetic algorithms.

 

Bipartite Graphs

Can model disjoint subsets such as male and females.

Example

A graph of odd and even numbers.

Odds are only connected by an edge to an even. V₁ connected to V₆ and V₂.

Odds and evens form disjoint subsets.

Figure 7 - Showing that C₆ is bipartite

Definition 5

Bipartite is a simple graph in which the vertices can be partitioned into disjoint sets V1 and V2 Edges connect vertices of V1 and V2 No edges connect vertices of: V1 with other vertices of V1 or V2 with other vertices of V2

 

Example

G is bipartite

V₁={a, b, d} are not connected

V₂={c, e, f, g} are not connected

V = {a, b, d} U {c, e, f, g}

{a, b, d} ∩ {c, e, f, g} = ∅

all vertices in either V₁or V₂

H is not bipartite because f is connected to every vertex.

Theorem 4

A simple graph is bipartite iff it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.

Example

1. Assign 1 red.

2. Must then assign 2 and 5 blue.

3. But 2 and 5 adjacent and same color.

4. Not bipartite.

 

Example

Graph models people and software jobs suited to perform.

People are disjoint with software jobs, no connecting edges between people or between jobs.

1. Color Alvarez blue.

2. From Alvarez, color requirements, testing black.

3. From requirements, color Chen, Davis blue.

4. From testing, color Berkowitz blue.

5. From Chen, color architecture, implementation black.

6. All vertices colored.

7. Color determines membership in disjoint set.

Alvarez Chen Davis Berkowitz	blue
requirements testing architecture implementation	black

Question 9.9

Color G to show it is bipartite, start with vertex a.

Suppose an edge means they like each other. What do the two subsets represent?

 

Some Applications of Special Types of Graphs

Example - Interconnection networks for parallel computation

Connect processors so that output of one can serve as input to another, requires communication connection.

Connections should model problem requirements

Simplest is linear connection.

Useful in linear problems that can be performed in stages.

Modeling and visualization of weather where:

P₁=collects weather data

P₂=models weather

P₃=generates graphics

P₄=presents graphics over network

 

 

Mesh models have a maximum of 4 adjacent processors, edges have fewer.

Edges can be connected to form roll (e.g. P_0,0 to P_3,0) or ball (e.g. P_0,0 to P_3,3, P_1,0 to P_3,2).

Modeling of robots moving in rank and file over terrain, much as marching soldiers would do, each need to communicate with neighbors.

 

3-dimensional hypercubes (Q₃) have 3 adjacent processors and are no more than 3 edges (communication links) from any other processor.

A connection between two on opposite corners: 111, 101, 100, 000.

 

 

A connection between two on opposite corners: P₇, P₅, P₄, P₀.

Question 9.10

Is the above graph connected as is the Q₃ cube?

 

New Graphs from Old

Definition 6

Subgraph H = (W, F) is a subgraph of G = (V, E) where W ⊆ V and F ⊆ E. H is a proper subgraph of G if H≠G.

Definition 7

Union of two simple graphs G1(V1, E1) and G2(V2, E2) is a simple graph with: V1 U V2 vertex set E1 U E2 edge set G1 U G2 graph union

 

Iso - equal

 

Morphic - form

Isomorphic graphs have same form, there is a one-to-one correspondence between vertices that preserves edges

 

G and H are isomorphic

u1→v1 u2→v4 u3→v3 u4→v2 Question 9.11 Is the above function a. one-to-one? b. onto?

 

Representing Graphs

Adjacency lists specify the vertices adjacent to another

Undirected Graph

Vertex Adjacent Vertices a b, c, e b a c a, d, e d c, e e a, c, d

Directed graph

Vertex Adjacent Vertices a b, c, d, e b b, d c a, c, e d   e b, c, d

Question 9.12

Give the adjacency list for

a.

b.

 

Adjacency Matrices

aij = 1  (vi, vj) ∈G         0  otherwise

Undirected graph

a b c d a 0 1 1 1 b 1 0 1 0 c 1 1 0 0 d 1 0 0 0

Question 9.13

Complete the adjacency matrix for the following:

1 2 3 4 5 1 0 1 0 0 1 2           3           4           5

 

Question 9.14

Draw the graph for the equivalent adjacency matrix.

	a	c	b	d
a	0	1	1	0
c	1	0	0	1
b	1	0	0	1
d	0	1	1	0

 

Example

Directed graph

1 2 3 4 1 0 1 0 0 2 0 0 0 1 3 1 1 0 0 4 0 0 1 1

Question 9.14

Complete the adjacency matrix for the following graph:

10 20 30 40 50 10 0 1 1 0 0 20           30           40           50

Example

Pseudograph with multiple undirected edges.

a b c d a 0 3 0 2 b 3 0 1 1 c 0 1 1 2 d 2 1 2 0

 

Incidence Matrices

mij = 1  when edge ej incidence with vi          0  otherwise

Example 6

e1 e2 e3 e4 e5 e6 v1 1 1 0 0 0 0 v2 0 0 1 1 0 1 v3 0 0 0 0 1 1 v4 1 0 1 0 0 0 v5 0 1 0 1 1 0

Example 7

e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 1 v5 0 0 0 0 1 1 0 0

 

Isomorphisms of Graphs

Isomorphic - Similar in form and relations

Example

Many homes have cable, phone and electric lines often sharing same homes (vertices) and right-of-ways (edges).

In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database.

 

One-to-one or injective function iff f(a) = f(b) implies a = b for all a and b in domain. ∀a∀b( f(a) = f(b)→a = b  ) One-to-one or injective function iff f(a) ≠ f(b) whenever a ≠ b. ∀a∀b( a ≠ b →f(a) ≠ f(b) )

Onto or surjective function iff every b ∈ B has a ∈ A with f(a) = b. ∀y∃x( f(x) = y )

Question 9.15

1. Which are one-to-one?
   
   
2. Which are onto?
   
   
3. Which are one-to-one and onto?

Definition 1

Isomorphism Simple graphs G1 = (V1, E1) and G2 = (V2, E2) isomorphic if there is a one-to-one and onto function f from V1 to V2. f has property that if a and b are adjacent in G1 then f(a) and f(b) are adjacent in G2.

Example

Show graphs are isomorphic.

One-to-one? Onto?

u1→v1 u2→v2 u3→v3

Constructing an identical adjacency matrix for both graphs demonstrates isomorphism. Problem is there are P(n, n) = n! possible matrices to try. Determining if two graphs with 3 vertices are isomorphic has P(3,3)=3!=6 possible   u1 u2 u3 u1 0 1 0 u2 1 0 1 u3 1 0 0   v1 v2 v3 v1 0 1 0 v2 1 0 1 v3 1 0 0 u1→v1 u2→v2 u3→v3   v1 v3 v2 v1 0 0 1 v3 1 0 0 v2 1 1 0 u1→v1 u2→v3 u3→v2   v2 v1 v3 v2 0 1 1 v1 1 0 0 v3 0 1 0 u1→v2 u2→v1 u3→v3   v2 v3 v1 v2 0 1 1 v3 1 0 0 v1 1 0 0 u1→v2 u2→v3 u3→v1   v3 v1 v2 v3 0 0 1 v1 0 0 1 v2 1 1 0 u1→v3 u2→v1 u3→v2   v3 v2 v1 v3 0 1 0 v2 1 0 1 v1 0 1 0 u1→v3 u2→v2 u3→v1

Example

Show graphs are isomorphic.

One-to-one? Onto?

u1→v1 u2→v4 u3→v3 u4→v2

Constructing an identical adjacency matrix for both graphs demonstrates isomorphism. Problem is there are P(n, n) = n! possible matrices to try. Determining if two graphs with 4 vertices are isomorphic has P(4,4)=4!=24 possible

u1 u2 u3 u4 u1 0 1 1 0 u2 1 0 0 1 u3 1 0 0 1 u4 0 1 1 0   v1 v4 v3 v2 v1 0 1 1 0 v4 1 0 0 1 v3 1 0 0 1 v2 0 1 1 0

Question 9.16.1

Which abc matrix is identical with xyz?

Is the graph of abc isomorphic with xyz?

1.   a b c a 0 0 1 b 0 0 1 c 1 1 0

2.   c b a c 0 1 1 b 1 0 0 a 1 0 0

3.   a c b a 0 1 0 c 1 0 1 b 0 1 0

x y z x 0 1 1 y 1 0 0 z 1 0 0

      

Question 9.16.2

Is:

  a®z
 

  b®y
 

  c®x

One-to-one?

Onto?

 

Graph invariant Property preserved by isomorphism. Must have same number of vertices and edges since one-to-one and onto. Must have same number of vertices of same degree.

Example

Show graphs are not isomorphic.

G H Vertices 5 5 Edges 6 6 Max degree 3 4

Question 9.16.3 - Check invariants

G H Vertices     Edges     Max degree     Degree 4 of 2 4 of 3

Example

Show graphs are isomorphic.

First, check invariants.   G H Vertices 6 6 Edges 14 14 Max degree 3 3 Degree 4 of 2 2 of 3 4 of 2 2 of 3

Invariants agree.

Find one-to-one and onto function f

u₁ and u₃ degree 2, adjacent to degree 3 vertices.

v₆ and v₄ degree 2, adjacent to degree 3 vertices.

f(u₁) = v₆ or v₄

f(u₃) = v₆ or v₄

Pick f(u₁) = v₆

then f(u₃) = v₄

u₂ adjacent to u₁

u₂ and u₄ degree 3 vertex.

v₃ or v₅ degree 3 vertex.

f(u₂) = v₃ or v₅

f(u₄) = v₃ or v₅

Pick f(u₂) = v₃

then f(u₄) = v₅

Continuing similarly, picking

f(u₅) = v₁, f(u₆) = v₂

u1 u2 u3 u4 u5 u6 u1 0 1 0 1 0 0 u2 1 0 1 0 0 1 u3 0 1 0 1 0 0 u4 1 0 1 0 1 0 u5 0 0 0 1 0 1 u6 0 1 0 0 1 0

v6 v3 v4 v5 v1 v2 v6 0 1 0 1 0 0 v3 1 0 1 0 0 1 v4 0 1 0 1 0 0 v5 1 0 1 0 1 0 v1 0 0 0 1 0 1 v2 0 1 0 0 1 0

Question 9.17

We were guided by several heuristics: pick vertices with same number of edges in each graph, etc.

Suppose we used brute force, trying every permutation of f(u_i) = v_j till finding a one-to-one and onto mapping.

How many ways would we have to try to determine G and H to be isomorphic?

 

9.4 Connectivity

Path of length k from u to u' in G = (V, E) is a sequence of vertices < v0, v1, ..., vk > where u = v0 and u' = vk, and (vi -1, vi) ∈ E, for i = 1, 2, ..., k |P| = Path Length equals the number of edges in the path, always a 0-length path from u to u Circuit if begins and ends at same vertex. Simple path/circuit if does not include edge more than once.

Example 1

Simple Path of length 3 P =(a,d), (d,c), (c,f) a path start f path end Non-path (a,d), (d,b) Simple circuit of length 3 (a,d), (d,e), (e,a) Non-simple circuit of length 2 (a,d), (d,a) Non-simple Path of length 4 (a,d), (d,e), (e,d), (d,e)

Question 9.18.1

Simple paths?

1. (a, b), (b, f), (f, c)
   

2. (a, b), (b, c), (c, b)
   

3. (d, e), (e, a), (a, d), (d, e)

Question 9.18.2

Simple circuits?

1. (a, b), (b, e), (e, a)
   

2. (d, e), (e, a), (a, d)
   

3. (d, e), (e, a), (a, d), (d, e)

 

Connectedness in Undirected Graphs

Definition 2

Connected if there is a path between every pair of vertices in an undirected graph.

Example 5

G1 - connected

G2 - not connected

Example 6

H not connected but has 3 connected parts.

 

Cut vertices Vertices that when removed along with incidence edges, produces a subgraph with more connected components than original graph. Cut edges Edges that when removed along with incidence vertices, produces a subgraph with more connected components than original graph.

Example

Cut vertices are: b, c, e

Removing b produces 2 unconnected subgraphs, one with only vertex a.

Cut edges: (a, b) and (c, e)

Removing (c, e) produces 2 unconnected subgraphs.

Cut vertices Vertices that when removed along with incidence edges, produces a subgraph with more connected components than original graph. Cut edges Edges that when removed along with incidence vertices, produces a subgraph with more connected components than original graph.

Question 9.19.1

1. What are the cut vertices in G₁?
   
   

2. What are the cut edges in G₁?

 

Connectedness in Directed Graphs

Definition 4

Strongly Connected if there is a path between a and b then there is a path from b to a.

Definition 5

Weakly Connected if there is a path between every two vertices in the underlying undirected graph.

Example 9

G is strongly and weakly connected.

H is not strongly connected

(b, a) no (a, b) path

H is weakly connected

path in undirected graph

 

Question 9.19.2 - Is the graph below

1. strongly connected?
   
   

2. weakly connected?

Strongly Connected if there is a path between a and b then there is a path from b to a.

Weakly Connected if there is a path between every two vertices in the underlying undirected graph.

 

Paths and Isomorphorism

Paths and circuits can determine whether graphs are isomorphic.

Isomorphic graphs must have paths/circuits of same length.

Example 12

G and H are not isomorphic.

G H Vertices 6 6 Edges 8 8 Degree 4 of 3 2 of 2 4 of 3 2 of 2 Simple circuit Length 3 none Length 3 v1,v2,v6,v1

Example 13

G and H are isomorphic.

G H Vertices 5 5 Edges 6 6 Degree 2 of 3 3 of 2 2 of 3 3 of 2 Simple circuit Length 3 u1,u4,u3,u1 Length 5 u2,u3,u4,u1,u5,u2 Length 3 v1,v2,v3,v1 Length 5 v1,v2,v3,v4,v5,v1 One-to-one? Onto? f u1→v3 u2→v5 u3→v1 u4→v2 u5→v4 Adjacency matrices agree under f. G and H are isomorphic.

u1 u2 u3 u4 u5 u1 0 0 1 1 1 u2 0 0 1 0 1 u3 1 1 0 1 0 u4 1 0 1 0 0 u5 1 1 0 0 0   v3 v5 v1 v2 v4 v3 0 0 1 1 1 v5 0 0 1 0 1 v1 1 1 0 1 0 v2 1 0 1 0 0 v4 1 1 0 0 0

 

 

Counting Paths Between Vertices

Number of paths between two vertices can be determined using adjacency matrix and matrix multiplication (not Boolean product).

Theorem 2

Number of different paths of length r from vi to vj in graph G represented by adjacency matrix A is (i, j)th entry of Ar. Ignore diagonals which are loops.

Example 14

Length 1 number of paths. In A1, (a, d) = 0 A1 a b c d a 0 1 1 0 b 1 0 0 1 c 1 0 0 1 d 0 1 1 0
Length 2 number of paths. In A2, (a, d) = 2 A2 a b c d a 2 0 0 2 b 0 2 2 0 c 0 2 2 0 d 2 0 0 2	Paths of length 2 from a to d: a, b, d a, c, d Paths of length 2 from a to a: a, b, a a, c, a Note: A2 = A * A
Length 3 number of paths. In A3, (a, d) = 0 A3 a b c d a 0 4 4 0 b 4 0 0 4 c 4 0 0 4 d 0 4 4 0	A3 = A2 * A        (a, b) = 4        a, c, d, b        a, b, a, b        a, b, d, b        a, c, a, b

Question 9.20 - Find the number of length 4 paths by finding A⁴ = A³ * A.

A4 a b c d a         b         c         d

=

A3 a b c d a 0 4 4 0 b 4 0 0 4 c 4 0 0 4 d 0 4 4 0

*

A a b c d a 0 1 1 0 b 1 0 0 1 c 1 0 0 1 d 0 1 1 0

Note that (a, b), (b, a), (a, b), (b, d) is a path of length 4 from a to d.

 

9.5 Euler and Hamilton Paths

Euler Paths and Circuits

Definition

Simple circuit or path does not contain an edge more than once.

Definition 1

Euler circuit a simple circuit containing every edge of graph G. Euler path a simple path containing every edge of graph G.

Example 1

Which of the undirected graphs have an Euler circuit?

G₁ (a, e, c, d, e, b, a)

Of those that do not, which have an Euler path?

G₃ (a, c, d, e, b, d, a, b)

Example 2

Which of the directed graphs have an Euler circuit?

H₂ (e, d, f, a, g, c, b, g, e)

Of those that do not, which have an Euler path?

H₃ (c, a, b, c, d, b)

Question 9.21.1

Euler circuit? Euler path? An Euler path/circuit is useful when inspecting roads. Other applications?

Question 9.21.2

Euler circuit? Euler path?

 

Definition

Multigraphs have multiple edges connecting at least one vertex pair.

Theorem 1

Euler circuit in multigraph iff each vertex has even degree.

Theorem 2

Euler path but not Euler circuit iff multigraph has exactly two vertices of odd degree.

Question 9.21.3

Does the above multigraph have an Euler circuit by Theorem 1?

 

Hamilton Paths and Circuits

Definition

Simple circuit or path does not contain an edge more than once.

Definition 2

Hamilton circuit a simple circuit passing through every vertex of graph G exactly once. Hamilton path a simple path containing every vertex of graph G exactly once.

Example 5

Which of the undirected graphs have a Hamilton circuit?

G₁ (a, b, c, d, e, a)

Of those that do not, which have a Hamilton path?

G₂ (a, b, c, d)

Definition

No Hamilton circuit when in a graph having a vertex of degree one. All edges of vertices of degree two must be in the circuit.

Question 9.22 - Which of the undirected graphs have a

1. Hamilton circuit?
   
   

2. Hamilton path?

 

Question 9.23 - Does the directed graph have a

Hamilton circuit? Hamilton path?

 

9.6 Shortest-Path Problems

Definition

Weighted graph has numerical weights assigned to edges.

Question 9.24.1 Find length of shortest path: c to d. Start at c c→c = 0 c→b=3 or c→z=2

w a b c d e z a ∞ 4 ∞ 2 ∞ ∞ b 4 ∞ 3 ∞ 3 ∞ c ∞ 3 ∞ ∞ ∞ 2 d 2 ∞ ∞ ∞ 3 ∞ e ∞ 3 ∞ 3 ∞ 1 z ∞ ∞ 2 ∞ 1 ∞ w[vi, vj]   L a ∞       b ∞ c 0 d ∞ e ∞ z ∞ S ∅        Initial values

Question 9.24.2 - Complete steps 3 and 4 of shortest path from c to d, tracing the algorithm by updating S and L[ u ] entries.

Theorem 2

Dijkstra's Algorithm is O(n2).

 There are n-1 vertices after selecting the start vertex.

Worst-case examines all n-1 vertices in while.

Finding minimal L[u] requires examining at most n-1 vertices

for iterates at most n-1 times

2(n-1) operations inside while.

2n²-4n+2 = (n-1)*(2n-2) operations total.

2n²-4n+2 is O(n²)

while c ∉ S u := vertex not in S with L[u] minimal S := S U {u} for all vertices v not in S if L[u] + w[u,v] < L[v] then L[v] := L[u] + w[u,v]

n-1 vertices n-1 vertices   n-1 vertices

Question 9.25.1 - Complete w[v_i, v_j]

w SF Chicago Boston NY Dallas LA Denver SF ∞ 1500 ∞ ∞ ∞ 400 1000 Chicago               Boston               NY               Dallas               LA               Denver

Question 9.25.3

Denver to LA - Give the cheapest path.

Start at Denver

1. Denver→Denver = 0     
   

2. Denver→San Francisco = $1000 or
   Denver→?

  

 

Example 3 - A Javascript solution to above graph. Display length and path in reverse order.

Change weight matrix w for different minimum path problem.

Dijkstra's Algorithm, see Figure 3, p650 of Rosen.<br/> a=0, b=1, c=2, d=3, e=4, z=5<br/> <script type="text/javascript"> var w = new Array(6); for(i=0;i<6;i++) w[i]=new Array(6); for (i=0;i<6;i++)   for(j=0;j<6;j++) w[i][j]=999999999999;        // ∞ w[0][1]=4;                 // Weights w[0][3]=2; w[1][0]=4; w[1][2]=3; w[1][4]=3; w[2][1]=3; w[2][5]=2; w[3][0]=2; w[3][4]=3; w[4][1]=3; w[4][3]=3; w[4][5]=1; w[5][2]=2; w[5][4]=1; Dijkstra(0,5,w); function min(L, S) {   for (v=0; v<L.length; v++)     if(S.indexOf(v+"")==-1) {       m=v;       break;     }   for (v=0; v<L.length; v++)     if(S.indexOf(v+"")==-1)       if (L[v] < L[m]) m = v;   return m; } function Dijkstra( a, z, w) {   var L=new Array(w[0].length);   var P=new Array(w[0].length);   var S="";   for (i=0; i<w[0].length; i++) L[i]=999999999999;   L[a]=0;   while (S.indexOf(z+"") == -1) {     u = min(L, S);     S = S + u;     for (v=0; v<w[0].length; v++)       if(S.indexOf(v+"")==-1)         if ((L[u] + w[u][v]) < L[v]) {           L[v] = L[u] + w[u][v];           P[v]=u;         }   }   document.write("Path length:"+L[z]+"<br/>");   document.write("Examined:"+S+"<br/>Reverse path:"+z);   v=z;   while(v!=a) {     document.write(P[v]);     v = P[v];   } } </script>

Output: Dijkstra's Algorithm, see Figure 3, p650 of Rosen. Path length:13 Examined:021345 Reverse path:543120

 

The Traveling Salesman Problem

Make circuit of n cities, visiting each exactly once.

Used when planning bus routes, need to visit every stop (vertex) but not every connecting road (edge).

What order of visit is minimum distance?

5 cities.

Assume starts in Detroit.

P(4, 4) = 4! = 24 possible circuits to visit other 4 cities.

Because traveling a path in reverse order yields same distance, need to examine only 12.

Examination of the 12 possible circuits yields 458 as minimum

Problem

(n-1)!/2 Hamilton circuits to examine.

25 cities, 24!/2 circuits (or 23! = 310,224,200,866,619,719,680,000).

Requires 10,000,000 years to examine all if one circuit examined every 10^-9 seconds.

Solution

Approximation algorithm does not produce optimal solution but does produce one close.

W ≤ W'≤ cW

W is the optimal solution

W' is the approximation

cW is a constant factor of the optimal solution

No known polynomial time algorithm for general case approximation.

 

Question 9.26

Do each of the following have a Hamilton circuit?

An Euler circuit is not of interest in this problem since not traveling every edge but visiting every vertex.

The Traveling Salesman problem is P(n-1, n-1) = (n-1)! but can be reduced by eliminating certain cases.

P(n-1, n-1) implies graph vertices are fully connected.

Consider G₁ on how to reduce the size of the problem.

Does any circuit with (a, c) or (c, a) need to be examined?