GN Lecture 5

8/18/2019 GN Lecture 5

1/28

BITS, PILANI – K. K. BIRLA GOA CAMPUS

Dr. Tarkeshwar SinghDepartment of Mathematics


2/28

Topics to be covered

TreesEquivalent Definitions

Some ResultsSpanning TreesMinimum Spanning Tree

Kruskal’s Algorithm

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +


3/28

Trees

!TS" #!$A%! & K. K. !R$A '(A )AM#*S ,

• Definition: A graph G is said to be acyclic if it has nocycles.

• Definition: A connected acyclic graph G is called tree.

• Bridge: An edge e = uv is said to a bridge if G - e isdisconnected.

• Definition: An acyclic graph is called a forest in whicheach component is a tree.


4/28

Motivation

Kirchoff had developed theory of tress in 1847 in order tosolve the system of simultaneous linear equations whichgives the current in each branch and around each circuit of

an electrical network.n 18!7" the concept of tree was discovered by Aurther

#ayley in the very natural setting of organic chemistry" inenumeration of isomers in # n $ %n&%. $e had used the

connected graph to represent #n

$%n&%

. p ' (n&% and q ' )4n&%n&%*+% ' (n&1.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S -


5/28

Motivation contd.

,he graph corresponding to # n $ %n&% molecule is an acyclicgraph. n this case" the problem of counting structuralisomers of the given hydrocarbon becomes the problem of

counting trees with certain qualifying properties of order p and si-e q = p-1 .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S


6/28

Trees Contd.

A connected graph is said to be a minimally connected graphif removal of any edge from it disconnects the graph.

Remark:A minimally connected graph does not have any cycle.A tree is minimally connected graphA tree with ma imum number of pendent vertices is star K 1,r .

A tree with minimum number of pendent vertices is path P n.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S /


7/28

Equivalent Definitions

Theorem: /et G = (V, E) be a (p, q) 0graph. ,hefollowing statements are equivalentG is a tree.

2very pair of vertices of G are 3oined by unique path.G is connected and q = p-1 .

G is acyclic and q = p-1 .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 0


8/28

ut line of !roof

" implies #: ince G is a connected graph" then theree ists a ) u , v*0path in G.

uppose there are two paths P 1" and P 2 respectively" 3oining

u and v in G.,hen there will be some verte ui not in P 1 but in P 2 andsome verte u j in P 1 but not in P 2 where i < j. ,hen we shallget a contradiction.

o there is a unique ) u , v*0path in G.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 1


9/28

!roof Contd.

# implies $: 5rom % it is clear that G is connected. 6ow" we have to show that q = p -1 .

e shall prove this by induction on number of vertices p.asis step for p = 1 or 2" graph is trivial connected graph.

6ow" we shall assume that" the result is true for theconnected graph with less than p vertices.Assume G is graph with p vertices and let e = )u, v* is anyedge of G" then G - e is disconnected graph. ) hy9*,hen there will be at least two components say G1 and G2.,hen by induction hypothesis we can prove that q = p - 1 .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 2


10/28

!roof Contd.

$ implies %:t is clear that : is connected and q = p – 1, then we have

prove that G is acyclic.

o assume that G has a cycle of length n. 6ow" fi a verte on the cycle and consider any one of theremaining p – n vertices not lying on the cycle.#onsider the edges in the shortest path so we get q ≥ ) p - n *+ n = p. hich is a contradiction.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 34


11/28

!roof Contd.

% implies ":ince G is a cyclic and q = p – 1. ,hen we have to show

that G is tree.

o it is sufficient to prove that G is connected.e shall prove this by contradiction.

$ence" we assume G is disconnected.

,hen we shall get contradiction.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 33


12/28


13/28

Minimum &panning Trees

M&T !roblem: upp se (G , *) is ' # nne#$e%n n $rivi' , *ei&h$e% &r'ph ! r%er p 'n% size q.

here * is $he *ei&h$ !un#$i n 'ssi&ne% $ 'n e%&e' p si$ive re' nu er. r e'#h su &r'ph / *e%e!ine ' *ei&h$ ! / "

*(/) = 0 *(e), *here e ∈ E(/).

e *ish $ ini ize $he *(/). ! / % es n $ # n$'in ' #"# e $hen $he *(/) *i e' *'"s ini u .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 3,


14/28

M&T !roblem

o this problem is equivalent to find a spanningtree with minimum weight.

t has many applications in computer ciences",elecommunications" ,ransportation 6etworks"

iology" etc. 6ow we shall discuss two Algorithms namely"

K;< KA/= A6> ?; @ which enable us tofind a minimum spanning tree from a weightedgraph G.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 3-


15/28

Kruskal=s Algorithm)1 !B*

'nput: G = (V,E,*) is a connected weightedgraph with verte set V = 1,2,3,p4 .

&tep(")'nitiali*ation+:T ← φ .5or i =1 to p do V i = i4. ⇒ 5(p)

Arrange edges in non decreasing order *(e 1 ) 6*(e 2 ) 6 3 6 *(e q ). ⇒ 5(q & q)(/e'p h r$).

) reak the ties arbitrarily*

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 3


16/28

,lgorithm contd.&tep(#: 5or j = 1 to q"do CD 5ind end vertices of e j =(u,v) )say*.

D 5ind the components of u E v say V 7 and V ( "

respectively ) 7 < *. D fV 7 8 V ( " then

do C T ← T ∪ e j 4

V ← V 7 ∪ V ( , V ( = φ F

D fV 7 = V ( " then do nothing.

F

utput: A minimum spanning tree.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 3/


17/28

,lgorithm contd.

utput: T is a minimum spanning tree withweight = *(T) .

Comple-it : ,he comple ity of thisalgorithm is 5(q & p) in the worst case.

Note: This is ' s ' &ree%" ' & ri$h .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 30


18/28

!rims ,lgorithm)"/01+

'nput: A connected weighted graph G=(V,E, *).&tep(":'nitiali*ation:

T ← φ .ei&h$ *(T) = 9.← u4

: ← V- .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 31


19/28

,lgorithm contd.

&tep(": hile : 8 φ do CD 5ind an edge e of minimum weight in ; ,

: . : 5ind the end vertices of e say e = (u,v),

where u and v :. : T ← T ∪ e j 4

D = ∪ v4: : = V- .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S 32


20/28

,lgorithm contd.

ei&h$ = *ei&h$ +*(e). 4

utput: T is a minimum spanning tree withweight = *(T) .Comple-it : ,he comple ity of this

algorithm is 5(q & p) in the worst case. Note: This is ' s ' &ree%" ' & ri$h .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +4


21/28

ther t pes of Trees

;ooted ,ree A tree is called a rooted tree if one ofits verte is identified as a root.

inary ,ree A tree is called binary if every vertehas at most two predecessor vertices.#omplete inary ,ree A binary tree is said to becomplete if every verte has e actly two

predecessor vertices.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +3


22/28

Enumeration of &panning Trees

A spanning tree in : is a subgraph of : thatincludes all the vertices of : and is also a tree. ,heedges of the trees are called branches.

e can find a spanning tree systematically byusing either of two methods.#utting down method

uilding up @ethod

!TS" #!$A%! & K. K. !R$A '(A)AM#*S ++


23/28

Cutting(do2n Method

tart choosing any cycle in :.

;emove one of cyclic edge.

;epeat this procedure until no cycles areleft.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +,


24/28

Building(up Method

elect edges of : one at a time in such away that no cycles are created.

;epeat this procedure until all vertices areincluded.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +-


25/28

3aplacian Matri-

t is the difference of the >egree >iagonal @atriand the Ad3acency matri defined as / ' l)i"3*"where the matri entries are given as

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +


26/28

Matri- Tree Theorem

e can calculate the number of labeled spanningtrees of a graph from the /aplacian matri through@atri ,ree ,heoremTheorem: Number of labelled spanning trees inany connected graph is actually the cofactor ofany of the entry in the laplacian matrix.

,he /aplacian matri is also known as Kirchhoffmatri .

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +/


27/28

,lgorithm contd.

Comple-it : #omple ity of this algorithm is5(q & p) in the worst case.

Theorem: ,he tree obtained by Kruskal=s)?rims* Algorithm is a minimum spanning tree.

!TS" #!$A%! & K. K. !R$A '(A)AM#*S +0


28/28

Thanks

+1!TS" #!$A%! & K. K. !R$A '(A )AM#*S

Documents

GN Lecture 5