Graph: Nitin Upadhyay March 01, 2006 Bits-pilani Goa Campus

Graph Nitin Upadhyay March 01, 2006 Bits-Pilani Goa campus

Discussion  Counting

Path Example  Connectedness  Cut Vertices and Cut Edges  General Graphs  Planar Graphs  Planar Embedding  Plane Graph Regions  Plane Graph Degree

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 1 to 5 in the graph? e1

1 e6 e5 4

3

2 e3 e2

e4

5

Adjacency Matrix 2 3

4

5

1 0 2 1 3 0

1

0

1

0

0

1

0

1

1

0

1

1

4 1

0

1

0

0

5 0

1

1

0

0

1

e6 e5 4

1

e1

1

3

The number of paths of length 4 from a to d is the (1, 5)th entry of A4. Since

2 e3 e2

e4

5

The (1, 5)th entry of A4 is 6, indicating that there are six different paths of length 4 between 1 and 5.

2

3

4

5

1:{1-4-1-2-5} 2:{1-2-1-2-5}

1 9 2 3 3 11

3

11

1

6

15

7

11

8

3:{1-4-3-2-5}

7

15

3

8

4:{1-2-5-2-5}

4

1

11

3

9

6

5

6

8

8

6

8

5:{1-2-3-2-5} 6:{1-2-5-3-5}

Counting Paths Example 



How many paths of length 4 are there from a to d in the right graph? The adjacency matrix of the graph is

0 1  A = 1  0  

1

1

0 0 1

0 0 1

0 1  1  0  

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

8

8

8 0

8 0

0 0  8

a

b

d

c

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

Connectedness 





An undirected graph is connected iff there is a path between every pair of distinct vertices in the graph. E.g., Graph G1 is connected, since for every pair of distinct vertices, there is a path between them. However, G2 is not connected. E.g., no path in G2 between vertices a and c.

a

b

c

d

e

f

a

b

c

d

e

f

Connectedness  Theorem:

There is a simple path between every pair of distinct vertices of a connected undirected graph.  Connected component: A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph.

Connected Component Example 

The graph H is the union of three disjoint connected subgraph H1, H2, and H3. These three subgraphs are the connected components of H.

H2 d

H1

e H3

a f H

b

c

h

g

Cut Vertices and Cut Edges 



A cut vertex or cut edge separates 1 connected component into 2 if removed. E.g., The cut vertices of G are b, c, and e, since removing one of these vertices (and its adjacent edges) disconnects the graph. The cut edges are [a, b] and [c, e].

a

d

f

g

b

c

e

h

Directed Connectedness A

directed graph is strongly connected iff there is a directed path from any vertex to any other vertex in the graph.

 It

is weakly connected iff the underlying undirected graph (i.e., with edge directions removed) is connected.

Directed Connectedness Example 

Are the directed graphs G and H strongly connected or weakly connected? a

a

b

b

c d

e

G

c d

e

H

Directed Connectedness Example 

G is strongly connected since there is a directed path between any two vertices. Hence, G is also weakly connected. H is not strongly connected since, for instance, there’s no directed path from a to b. H is however weakly connected since there is a path between any two vertices with all directions removed.

a

a

b

b

c d

e

G

c d

e

H

General Graphs  Generally

graphs drawn on a piece of paper permit edges to intersect at points other than vertices.  These points of intersection are called crossovers.  And the intersecting edges are said to cross over each other.

Example Crossovers  Here

this graph exhibits three crossovers:  {b, e} crosses over {a, d} and {a, c}.  {b, d} crosses over {a, c} d

e a

c

b

Planar Graphs A

Graph G is said to be planar if it can be drawn on a plane without any crossovers.

A

graph is non planar if there is no way to convert it into planar.

Example conversion  Non

d

planar to planar

d

e

e a

a c

b

c

b

Planar embedding  Graphs

can be represented such that no two edges of the graph intersect except possibly at a vertex to which they both incident.  A drawing of a geometric representation of a graph on any surface such that no edges intersect is called embedding.  An graph G is planar if there exists a graph isomorphic to G that is embedded in a plane.

Plane Graph Regions A

plane graph G can be thought of as dividing the plane into regions or faces.

 The

regions are the connected portions of the plane remaining after all the curves and points of the plane corresponding, respectively, to edges and vertices of G have been deleted.

Plane Graph Regions A

plane graph partitions the plane into regions of G.

 There

is exactly one region whose area is infinite, known as exterior or infinite region.

 Every

other region is an interior region.

Plane Graph Regions  The

boundary of a region is the subgraph formed by the vertices and edges encompassing that region.

 If

the boundary of the exterior region of a plane graph is a cycle, that cycle is known as the maximal cycle of the graph.

Plane Graph Regions  The

degree of a region is the number of edges in a (closed) walk encloses it.  A bridge belongs to the boundary of only one region, thus it contributes to the size of the boundary twice.  The sum of the degrees of all the regions in a plane graph is twice the size if the graph.

Region Example  Graph

has six interior regions and one exterior regions. a b

c

g e

f

d

h

j

i

Interior regions- 1:{a-b-c-a} 3:{a-c-d-e-a} 5:{g-h-j-g} 6:{g-h-i-f-g} 2:{b-c-d-b} 4:{j-h-i-j} Exterior region- 1:{a-b-d-e-f-i-j-g-f-e-a}

Degree example  In

the graph there exists four interior regions of degree 3 and two interior regions of degree 4.The degree of exterior region is 10. a b

c d

g e

f

h i

j

Degree example  The

sum of the degrees (of the regions) is 30, and the graph has 15 edges. a b

c d

g e

f

h i

j

Example 1  Find

out the interior and exterior regions, degree of each region and total degree of the planar graph G. Interior regions: a

b

c

d

1:{a-b-g-h-a} 2:{b-c-f-g-b} 3:{c-d-e-f-c} degree: {4} Exterior region 1: {a-b-c-d-e-f-g-h-a}

h

g

f

e

Degree: {8} Total degree: 8 + (4 * 3) = 20 Number of edges: 20/2 = 10

Example 2  Find

out the interior and exterior regions, degree of each region and total degree of the planar graph G. Interior regions: 1:{b-d-c-b} 2:{e-f-g-e}

a b

f d

Exterior region

e

1: {a-b-c-d-e-f-g-e-d-b-a}

g c

degree: {3}

Degree: {10} Total degree: 10 + (2 * 3) = 16

Questions

Questions ?