Graphs Lect3

Graphs

Nitin Upadhyay February 27, 2006 Bits-Pilani Goa campus

Discussion 

What is a Graph?



Applications of Graphs



Categorization



Terminology

Special Graph Structures Special cases of undirected graph structures:  Complete graphs K n 

Cycles Cn



Wheels Wn



n-Cubes Qn



Bipartite graphs Complete bipartite graphs Km,n



Graph Representations     

Adjacency-matrix representation Incidence matrix representation Edge-set representation Adjacency-set representation Adjacency List

Graph Isomorphism 

Formal definition: 

Simple graphs G1=(V1, E1) and G2=(V2, E2) are isomorphic if there is a function f:V1→V2 such that



f is one-to-one . f is onto, and ∀ a,b∈V1, a and b are adjacent in G1 iff f(a) and f(b) are adjacent in G2.

 



f is the “renaming” function that makes the two graphs identical.

Graph Invariants under Isomorphism Necessary but not sufficient conditions for G1=(V1, E1) to be isomorphic to G2=(V2, E2): 

|V1|=|V2|, |E1|=|E2|.



The number of vertices with degree n is the same in both graphs. For every proper subgraph g of one graph, there is a proper subgraph of the other graph that is isomorphic to g.



Isomorphism Example 

If isomorphic, label the 2nd graph to show the isomorphism, else identify difference. b a

d e

b

c c

f Hence, they are isomorphic!

f

d * Same # of vertices a* Same # of edges e•Same # of degrees for all vertices

Are These Isomorphic? 

If isomorphic, label the 2nd graph to show the isomorphism, else identify difference. a

b d

c

e Hence, they are NOT isomorphic!

* Same # of vertices * Same # of edges * Different # of verts of degree 2! (1 vs 3)

Subgraphs 

A subgraph of a graph G=(V, E) is a graph H=(W, F) where W⊆V and F⊆E.

G

H

Spanning Subgraph 

 

A subgraph H= (W, F) of G= (V, E) is called a spanning subgraph of G iff: W(H)=V(G) F(H) ⊆ E(G)

G

H

Connectivity 

In an undirected graph, a path of length n from u to v is a sequence of n adjacent edges going from vertex u (=x0) to vertex v (=xn).



A path is a circuit if u=v and n > 0. A path pass through the vertices x1, x2,.., xn-1, or traverses the edges e1, e2, …, en.





A path is simple if it does not contain the same edge more than once.

Path Example 

a

b

c

 



d

e

f

a, d, c, f, e is a simple path of length 4. d, e, c, a is not a path since {e, c} is not an edge. b, c, f, e, b is a circuit of length 4 since this path begins and ends at b. Path a, b, e, d, a, b is not a simple path since it contains the edge {a, b} twice.

Counting Paths and Adjacency Matrices 

Let A be the adjacency matrix of graph G.



The number of paths of length k from vi to vj is equal to (Ak)i,j. (The notation (M)i,j denotes mi,j where [mi,j] = M.)

Counting Paths Example 



How many paths of length 4 are there from a to d in the right a b graph? The adjacency matrix of the graphcis d 0 1 A = 1  0

1 0 0

1 0 0

1

1

0 1  1  0

Hence, the number 8 0 0 8 0 8 8 0 of paths ofA length  = 0 8 8 0  4 from a to d8is0 the 0 8 (1, 4)th entry of A4. Since 8 0 0 8

aa

bb

dd

cc

4

0 A4 =  0  8

8

8

8 0

8 0

0 0  8

There are 8 paths of length 4 from a to d.

Euler & Hamilton Paths 







An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in G is a simple path containing every edge of G. A Hamilton circuit is a circuit that traverses each vertex in G exactly once. A Hamilton path is a path that traverses each vertex in G exactly once.

Some Useful Theorems 





A connected multigraph has an Euler circuit iff each vertex has even degree. A connected multigraph has an Euler path (but not an Euler circuit) iff it has exactly 2 vertices of odd degree. If (but not only if) G is connected, simple, has n≥3 vertices, and ∀v deg(v)≥n/2, then G has a Hamilton circuit.s

Paths in Directed Graphs 

Same as in undirected graphs, but the path must go in the direction of the arrows.

Graph Unions 

The union G1∪G2 of two simple graphs G1=(V1, E1) and G2=(V2,E2) is the simple graph (V1∪V2, E1∪E2).

Graph Union Example 

Find the union of the graphs G1 and G2 shown below. The vertex set of the union G1∪G2 is the union of the two vertex sets, namely {a, b, c, d, e, f}. The edge set of the union is the union of the two edge set. a

b

d

e

G1

c

a

d

b

G2

c

a

b

c

f

d

e

f

G1 ∪ G2

Questions Questions ?