Graph: Nitin Upadhyay March 08, 2006

Graph

Nitin Upadhyay March 08, 2006

Multigraphs  





Like simple graphs, but there may be more than one edge connecting two given nodes. A multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges (as primitive objects), and a function f from E to {{u,v}| u,v∈V ∧ u≠v}. The edges e1 and e2 are called multiple or parallel edges if f(e1) = f(e2). Parallel edges E.g., nodes are cities, edges are segments of major highways

Multiplicity matrix  It

is an natural extension of adjacency matrix.  Each entry in the matrix shows the multiplicity of edges. Find the multiplicity matrix of the following graph: C D

A B

Multiplicity matrix  matrix C D

A B A B C D

A

B

C

D

0 2 2 1

2 0 0 1

2 0 0 1

1 1 1 0

2

C

1

1

A 2

B

D 1

Euler Graphs and Circuit A graph is said to be Euler graph if it contains Euler circuit.  A multigraph is said to be Eulerian multigraph if it contains Euler circuit. Euler Circuit and path  An Euler circuit is an Euler path whose endpoints are identical.  An Euler path in a graph is a path that includes each edge of the graph at least once.  An Euler path in a multigraph is a path that includes each edge of the graph at least once and intersects each vertex of the multigraph at least once. 

Example  Following

graph is Euler graph:

Theorem

 If

G is a graph in which the degree of every vertex is at least two then G contains a cycle.

Application- De Bruijin Sequences  If

W is the set {0, 1, 2,…, p-1}, any linear arrangement using some of or all these numbers is called a word in the alphabet W.  Any word with n numbers from W is called an n-letter word in W.  The set of all n-letter words in the alphabet W with p numbers is denoted by W(p,n).

Construction- De Bruijin Digraph  Suppose

all words in W(p, k) are known for k=1, 2,….,(n-1).  The vertex set of G(p, n) is w(p, n-1).  If t is any (n-2)-letter word, and if i and j are numbers in W, draw arcs fron vertex it ti ij as j varies from 0 to p-1.  Then the arc from xt to ty represents the nletter word xty.

Example 1 Problem: Construct the de Bruijn digraph G(3,2) Solution: P = 3, n = 2 W = {0,..,p - 1} = {0, 1, 2} Vertex word = n – 1 = 1 {0 or 1 or 2} Arc = n-letter word

Example 1  De

Bruijn digraph

00

0

01 10

20 11

1 02

12 21

22

2

Example 2 Problem:  If x = 21134 is a word in W(4, 5), constructs the arcs incident from the vertex x Solution:  Take t = 1134.  Arcs can be drawn from x to t0, t1, t2, t3, and t4 to denote the five six-letter words 211340, 211341, 211342, 211343, and 211344 resp.

De Bruijn as Eulerian graph  The

outdegree of each vertex by our construction is p.

 The



indegree is also p.

Thus the graph is eulerian graph.

Questions

Questions ?