Applied Graph Theory and Algorithms
Applied Graph Theory and Algorithms CMPE 177
Popular in Course
verified elite notetaker
Yancey "Catie" Kruger
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in Computer Engineering
This 30 page Class Notes was uploaded by Buck Ankunding on Monday September 7, 2015. The Class Notes belongs to CMPE 177 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 67 views. For similar materials see /class/182222/cmpe-177-university-of-california-santa-cruz in Computer Engineering at University of California - Santa Cruz.
Reviews for Applied Graph Theory and Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/07/15
Applied Graph Theory Class 2 Sept 29 2005 Complete Graph A complete graph is one where every vertex is connected to every other vertex Vu7vEV7u7 v HeEElpeu7v u a v ensures that we only consider discrete vertices The opposite of a complete graph is an empty graph with E g5 Bipartite Graph Bipartite graphs originate in situations where we need to use binary edges to describe relations with arity more than two7 such as the is a member of the family relation Here we are forced to create two kinds of nodes7 one representing family and the other representing family member Edges only connect nodes of different kinds VV1UV27V10V2 VeEE7peEV1 XVZUVZ XVl Note They have no self loops For the matching problem7 which is to match vertices in one set with compatible vertices in the other7 if we have a complete bipartite graph7 then the solution time is linear in the number of vertices Degree of a vertex Degree of a vertex v E V is the number of edges which have v either as their source or destination Note that self loops are counted twice dltvgt we l we W we l we W This above applies to the undirected case For directed graphs7 we make the distinction between out degree edges for which the given vertex is the source and in degree edges for which the given vertex is the destination dumb le l We Vlv dmV le l Me Vl First theorem of Graph Theory The sum of the degrees of all vertices equals twice the number of edges This applies to both directed as well as undirected graphs 26V dltvgt 2m Corollary There is an even number of odd vertices vertices with an odd degree This follows from the fact that the sum of an odd number of odd numbers is odd 2n 1 X oddNumber 2m oddNumber which is odd The usefullness of the the corollary If you know of a vertex in a graph with odd degree then there must be another vertex in that graph with odd degree For a walk on an arbitrary graph You will never stop at a node of even degree if you can take an unvisited edge to reach that node So if you start at an odd vertex you will eventually stop at an odd vertex This is very useful for proofs and is good to docket Connected graph For the undirected case there always exists a path from a node to another node in the graph For directed graphs there are two notions A weakly connected directed graph is one where the underlying undirected graph is a connected graph A strongly connected directed graph is one where there always exists a path from a node to another node in the graph Subgraph If G V E p then a subgraph of G G1 V1 E1 m l V1 Q V E1 Q E p1 p on E1 The last condition says that edges in the subgraph lead exactly where they used to in the original graph Further G1 is also a graph Note that when you pick an edge from G you pick both end points Graphs don7t have dangling edges A graph is a subgraph of itself With a slight abuse of notation if G1 Q G and G2 Q G denoting sub graphs of G then G1 U G2 and G1 0 G2 are Q G Note that G1 G2 which is a graph formed by removing all the vertices and edges that are common to G1 and G2 may not produce a graph as it may have dangling edges Strongly connected component SCC A strongly connected component in a graph is a subgraph which is a con nected graph This means that one can reach any vertex from any given vertex in that subgraph A maximal SCC is one that cannot be made larger by including anymore vertices G1 G2 Q G G1 0 G2 a Z5 and G1 G2 are strongly connected implies G1 U G2 is also strongly connected For a proof start from the result that the union is an SCC This implies there always exists a path from a node to any other node The interesting case is the existence of a path from a node in G1 to a node in G2 Since G1 is strongly connected there always exists a path from a node in G1 to a node in G1 0 G2 Similarly since G2 is strongly connected there always exists a path from a node in G1 0 G2 to G2 hence there always exists a path from any node in G1 to one in G2 and vice versa lnsight For such proofs always start from the result in this case that in the union there always exists a path from one node to another and for all interesting cases show the result using the pre conditions in this case that a path exists from any node in one SCC to any node in the other SCC Complement of a graph Given a graph G G v is a graph that results when we remove v and all the edges leading to it or leaving it Similarly G e is the graph that results when we remove edge e If U Q V the G U is the graph that results when we iteratively remove all vertices in U from G G G1 is the graph formed by removing all vertices and edges in G1 0 G from G The complement of a graph G is a graph that has edges between all vertices that are not connected in G Graphs are considered disjoint if there are no vertices in common Graphs are considered edge disjoint if there are no edges in common Walk in a graph A walk in a graph is a sequence of alternating vertices and edges of the form v0 e1 v1 e2 v2vn Walks for now are nite There are two kinds of walks Open walks where v0 a vn and closed walks where v0 V The length of a walk is the number of edges in the walk Therefore there can be walks of length zero A trail is a walk with no repeated vertices Theorem If there is a v u walk implying a walk from vertex v to vertex u then there is a v u trail If you have a path with loops then chop off the loops to get the corre sponding trail For an algorithm that does this build a stack of vertices visited as you walk the graph At each new vertex reached check if it has been encountered before already on stack If it has then clear the stack all the way to the earlier occurence of this vertex and continue walk This guarantees that loops are chopped off as soon as they are encountered The stack at the end of the walk will be the trail Each time we get rid of a loop we generate a trail pre x lVl n i a v u trail has length at most n 1 Theorem An undirected graph G is bipartite i it has no odd cycles The theorem as stated is incorrect It states that a graph is bipartite implies it has no odd cycles and a graph has no odd cycles implies that it is bipartite The latter implication should have been a graph has no odd cycles implies it is 2 colorable Proof If a graph is bipartite then in any walk the vertices are of alter nating kinds Therefore we can never close a loop using an even number of edges as we will then have an edge connecting vertices of the same kind which will make the graph not bipartite For proving the graph has no odd cycles i it is 2 colorable consider the following intuitive proof no odd cycles 2 colorable77 is the same as proving the statement not 2 colorable i there are odd cycles Consider a node v1 in conflict that has two incoming edges Along one edge we want to color the node White whereas along the other we want to color the node Black This can only happen if the immediate predecessor vertex say v2 along the latter edge is White and the immediate predecessor vertex along the former edge say V3 is Black Now if the two paths originate from the same Black node say v then the length of v V3 has to be even and the length of v v2 has to be odd This follows from the fact that even paths connect nodes of the same kind Since there is one edge from v2 to v1 and one from V3 to v1 we have a cycle of length even odd 1 1 which is odd Hence the proof Eccentricity Radius and Diameter of a vertex du v distance of u v the length of the shortest walk same as trail since shortest from u to v Eccentricity of a vertex v ev maxdu v l u E V RadiusG minev l v E V DiameterG maxev l v E V which is the same as maxdu v l u v e V Eggma C 1 41M Ionso mzm News Rama 1 Mk Algonkfhm I Slwvd td MvFA VV V Huh 0 uivp Reps l i Pl ck U chq I BFU gigW p04 UA H I m chmitz em De t k mls war by QrFRnAW Wchi 0quot9 30W I 7WW WWO Accgwal 0106 Ne bhrs 0 WE39er LMLW Hu had twat 295 en n39aly fwnqu B e quot w cv s39f V g ll bar 9 quot39 Why DU ks hA Works do 96 th 9mm 10 1 v0 j t 0 i f 1 r5 4 RH Unfit 7yl lo 10 r vm m we a fme H1 0 xivMR Pow 306 Guquot39 0 u 5 to TMquot WM aim L7 o Inc FMM vb 0 to 1 C934 ijiuj IUOgt lt 695 Vejro 0 LQquot LV 1ij lt Voirojdo TIM W Nahquot t Luau bigger 14quot uo WkJok 3 M 1 uz 61 40 r4 wM W7 RheeLed Wi U 0 um W39I blew91 neng 46 U0 Z39r ugoiuAm39m 90m V9 Vab9190 Alfemne pthlq Lo L19 w39L V0 pun A to 0 H in U sz bus 139 3H 0 d c If pen I no MH V Al I a wcxj rum V0 19 0 5 Fa 9155 bgt cw 2 o 139 1n I39 C0 VDfolda gt 605 Va odu Hvt U0 NodJ1 how1 lawn Ma sFaltemy Calch LAQ Iquot We Cir l 4 m N 9wer U w Vu AC WCUDu3 RQPM Pi39Lk X e I V H no n U V94 I WW w cl u UIZUUiuS HunWAofoJw j I For A 6 dCr Min our 1 DICu3 w qu 3 UA H UIV SIMJL la wwnf n9 M39H o n 39r M R 39 fr 695 04 D53ksml per WW OOP lVi plUlng GA 469 00 Cu I Cor U1 Uuiuzs v 97 AVmln Ed r Acugtwcw 11gt OCV JECVHH W39W gt 00 mlVl 3931th 2 C6M1tbiefAIK9a quot fatall CSKYJSK 39 l C v h litHal Hi a 539 c 4 Z cc r S 2 P0P l Z 3 QQH39AMJ m W llnlmuy4 O 09 n gt O CMmlog n 1 3 WWW queue ovHvk ME ruleaHlu MMWI 5 399 MMHY Linyuawm wke Hwr m 9 anng kun n S u as l adnly 009479Wnce 9A NAL H VCF arrkka 395 SDoge passzC 0 Ginrng axlge 39H m knewr mg graph J MHS tux g imam V V0 Va Um 3 WW lleHc be I 0 J r LP mfmeIInIIA H39Qn 0C oplls l n beau 2 Me 5 576919544 5 Chem I I wm ksanva AHst m MW Mas AKJ3gt 19 539 0 Shark3 prov Ir0 J Wk I C Van l39t 1513 9 n Mares A VI Vlj HVK LJ 9quot 1 GM 393 JK1 PW k EMRL 01quot 2 m5 ig wgAKOJ k13A 4l3 g cm rm I AW km foam MRA 1 The Algorf an VVDJUjrgzVn V0233 4039 UN 1 WC For kilo 0 14quot V551 AK39C5JJM Aquot JJAk5krdkkn53 end n mm A as i C490quot 5 0 Cm axPeMmVa J bu CAMs 0x 511911923139 Pa s M ax J Pailrs Itquot A 1W Re wlow EXPFIL9 VS Par I UI Ven39 r c gt L M SC H 33 can W 1 5403quot A 743 7 r bc 4 He39t H ff f 0r bCi CI PMstI Q xrrem 2 0 3 noJe WCI39JJ 31 19 0 3 alp mbi From I 39Io C 90 39 H 1 s LU Am So AHChan 3a 1753 tvHvk A U n CMPE 177 Fall 2002 Induction Proofs Let Pn be a propositional function de ned on the set of integers In other words P is a function P Z gt True False where Z stands for the set of integers or possibly a subset of the integers Informally this means that Pn is some statement whose truth or falsity depends on the value of an integer n Mathematical Induction is a proof technique which can be used to prove statements of the form Vn 21 Pn for all positive n Pn is true More generally we seek to prove Vn 2 n0 Pn for some integer n0 Such a proof consists of two steps 1 Base Step Prove Pno In other words prove directly that the propositionPn0 is true IIa Induction Step Prove Vn 2 n0 Pn gt Pn 1 Pick an arbitrary n 2 n0 and assume that for this n Pn is true Then show as a consequence that Pn1 is true The statement Pn is often called the induction hypothesis since it is what is assumed in the induction step When I and II are complete we conclude that Pn is true for all integers n 2 n0 Induction is sometimes explained in terms of a domino analogy Consider an infinite set of dominos which are lined up and ready to fall Let Pn be the statement the nth domino falls First prove Pl which is the first domino falls then prove Vn 21Pn gtPn1 which says if any particular domino falls then the next domino must also fall When this is done we may conclude Vn 2 1 Pn all dominos fall There are a number of variations on the induction step The first is just a reparametrization of Ila IIb Induction Step Prove Vn gt n0 Pn 1 gt Pn Let n gt n0 assume Pn 1 is true then prove Pn is true Forms Ila and 11b are said to be based on the first principle of mathematical induction Another important variation is the second principle of mathematical induction also called strong induction IIc Induction Step Prove Vn 2 n0 Vk S n Pk gt Pn 1 Let n 2 n0 assume that for all k in the range n0 S k S n Pk is true Then prove as a consequence that Pn1 is true In this case the term induction hypothesis refers to the stronger assumption Vk S n Pk The strong induction form can and often is parameterized as in IIb IId Induction Step Prove Vn gt n0 Vk lt n Pk gt Pn Let n gt n0 assume that for all k in the range n0 S k lt n Pk is true then prove as a consequence that Pn is true In this case the induction hypothesis is Vk lt n Pk Example 1 Prove that for all n 2 1 quot 2 nn12n1 6 Proof Let Pn be the boxed equation above We begin the induction at no 1 1 Base step 1 Clearly 2139 2 1 11 showing that P1 is true IIa Induction Step Let n 2 1 and assume Pn is true That is for this particular value of n the boxed equation holds Then quot1 21 1392 n12 11 11 W 71 12 by the induction hypothesis nn 12n 1 6n 12 6 bysome algebra showing that Pn 1 is true It follows from the principle of mathematical induction that Pn is true for all n 2 1 One should always state explicitly what is being assumed in the induction step ie what is the induction hypothesis One should also make note of the point in the proof at which the induction hypothesis is used Example 2 Let xe R and x 1Showthatforalln20 n1 1 n I x 2x 11 x 1 Proof Again let Pn be the boxed equation We begin the induction at no 0 1 Base step 0 Z x x0 1 x j showing that P1 is true x 10 IIb Induction Step Let n gt 0 and assume that Pn l is true ie assume for this particular 71 that I xquot l x x l39 H 3 Then l o by induction hypothesis showing that Pn is true Steps I and II prove that Pn holds for all n 2 0 Often the propositional function Pn is not a formula but some assertion concerning other types of mathematical structures Recall that a graph G is a collection of vertices and edges where each edge joins two not necessarily distinct vertices A path in G is a sequence of distinct vertices joined by edges and a cycle in G is a closed path G is called acyclic if it contains no cycles G is called connected if any two vertices are joined by a path in G A graph T is called a tree if it is both connected and acyclic The next example is a case in which strong induction is necessary Example 3 Let n 2 l and suppose T be atree on n vertices Prove that T necessarily has n l edges Proof Let Pn be the statement if T is a tree on n vertices then T contains 71 l edges We begin at n l I Base step If T has just one vertex then being acyclic it can have no edges whence Pl holds IId Induction Step Strong Induction Let 71 gt1 and assume that for all k in the range 1 S k lt n Pk is true That is for any such k all trees on k vertices contain k l edges Now let T be a tree on n vertices Pick any edge e in T and remove it The removal of e splits T into two subtrees each having fewer than n vertices Say the two subtrees have ml and n2 vertices respectively Then by our inductive hypothesis the two subtrees have n1 1 and n2 1 edges respectively Now replacing the edge e we see that T contains a total of I11 ln2 ll n1 n2 ln l edges Observe that no vertices were removed so that n1 r12 n The result now follows for all trees by induction There are many other variations on the induction technique Occasionally we must use double induction which involves a modi cation of both the base and induction steps I Base Step Prove Pno and Pn0 l II Induction Step Prove Vn 2 n0 2 Pn 2 APn l gt Pn When this is accomplished we may conclude Vn 2 n0 Pn In terms of our domino analogy we prove that I the rst two dominos fall and II if any two consecutive dominos fall then the very next domino falls From this we deduce that all dominos fall The Fibonacci numbers Fquot are de ned by the recurrence 0 if n 0 F 1 ifn1 Fquot1 FH if n 2 2 ie each term is the sum of the previous two Using this recurrence the rst few terms of the sequence are readily computed as F0 0F1 lF2 lF3 2F4 3 etc Example 4 Prove that for all n 2 0 F 15 aquot bquotl 1 43 2 SI 3 where 6112 and b Proof Let Pn denote the boxed equation above I Base Observe that PO and Pl are true since i61 b 0 F and LL b1 1 F 5 0 J3 1 II Double Induction Let n 2 2 and assume that both Pn 2 and Pn l are true ie we assume FH 2a bH and FM 2a bH Thus 1 F F71F72 aquot 2a1 bquot 2b1 n n n 5 One checks that a and b are roots of the quadratic equation x2 x l 0 Therefore a2 61 1 and b2 bl whence l 1 F anilra2bnilrb2 anbn I 1 I 1 showing that Pn is true Together steps I and II imply that Fquot i 61quot bquot for all n 2 0 J3 Often the proposition to be proved is an inequality as in the next example Example 5 De ne Tn for n e Z l by the recurrence T0 0 if n 1 TIn211 1f n22 Prove that for all n 2 5 showing that Tn Olg n Proof Let Pn be the boxed inequality above 1 Base One checks easily that T5 3 S 2 r lg5 using the recurrence and the fact that 8 S 25 so P5 holds IId Strong Induction Let n gt 5 and assume for all k in the range 5 S k lt n that Pk is true ie Tk S 21gk In particular TIn2DS 2lgn2D for k rt2 One shows easily that lgxDS l2 lgx for all x21J2 l Since 71 gt 5 2 2J2 l we have n2 21J2 l whence TIn2DS 212 lgn2 Now by the de nition of Tn Tn Tfn21 S 21 2 lgn 2 l by the above inequality 21gn showing that Pn is true Therefore Tn S 2lgn for all n 2 5 as claimed Induction Fallacies The next few examples illustrate some pitfalls in constructing induction proofs The result in Example A below was proved correctly in Example 3 We give an invalid proof of the same fact which illustrates an argument some authors have called the induction trap Example A Show that for all n 21 if T is a tree on n vertices then T has n l edges Proof Invalid Base If n 1 then Thas no edges being acyclic Induction Let n 2 l and let T be a tree on n vertices Assume that T has n l edges Add a new vertex and join it to T with a new edge The resulting graph has n1 vertices and n edges and is clearly a tree since connectedness is maintained and no cycles were created By the principle of mathematical induction all trees on n vertices have n l edges B Let us first observe that this argument does not follow the induction paradigm In this example Pn is of the form An gtBn where An is the statement T is a tree on n vertices and Bn is T has n l edges The induction step should therefore be to prove for all n 2 l Pn gt Pn 1 That is An gt Bn gt An 1 gt Bn 1 To prove this we should assume An gtBn then assume Anl then show as a consequence that Bn 1 is true In other words we should 0 Assume all trees on n vertices have n l edges 0 Assume T has 71 1 vertices 0 Show as a consequence that T has n edges The above argument did not follow this format however Instead the arguer does the following 0 Assume T has n vertices 0 Assume T has n l edges 0 Construct a new tree from T having 71 1 vertices and n edges Therefore the above argument was not a proof by induction Some students would nevertheless hold that the above argument is still valid even though it is not a true induction proof The next example shows convincingly that it cannot be valid First we introduce a few more definitions related to graphs A graph G is called simple if it contains no loops edges whose end vertices are identical and no multiple edges pairs of edges with the same end vertices Example B For all n 2 l ifG is a simple graph on n vertices then G has n l edges We notice right away that the above statement is false since the graph below provides an elementary counter example But consider the following proof in light of Example A Proof Invalid Base If n 1 then G has no edges being simple Induction Let n 2 1 and let G be a simple graph on n vertices Assume that G has n 1 edges Add a new vertex and join it to G with a new edge The resulting graph has n1 vertices and n edges and is clearly simple since no loops or multiple edges were created By the principle of mathematical induction all simple graphs on n vertices have n 1 edges Observe that Example B follows the format of Example A word for word Thus if A is valid so must B be valid But the assertion proved in B is false Therefore B cannot be a valid argument and so neither is A Another fallacy comes about by not proving the induction step for all n 2 no Example C Prove that all horses are of the same color Proof Invalid We prove that for all n 2 1 ifS is a set ofn horses then all horses in S have the same color The result follows on letting S be the set of all horses Let Pn be the boxed statement and proceed by induction on n Base Let n 1 Obviously if S is a set consisting of just one horse then all horses in S must have the same color Thus P1 is true Induction Let n gt 1 and assume that in any set of 71 horses all horses are of the same color Let S be a set of 71 1 horses say S h1 h2 h3 hn1 Then the sets Sh h35quotquothn1Sh1 and S39hlh3hn1S hz each contain exactly 71 horses and so by the induction hypothesis all horses in S are of one color and likewise for S 39 Observe that h3 e S m S 39 and that h3 can have only one color Therefore the color of the horses in S is identical to that of the horses in S Note 71 gt 1 gt 71 2 2 gt 71 1 2 3 so there is in fact a third horse and he can have only one color Since S S U S 39 it follows that all horses in S are of the same color Therefore Pn gt Pn 1 for all n gt 1 The result now follows by induction D Obviously the proposition being proved is false so there is something wrong with the proof but what The base step is certainly correct and the induction step as stated is also correct The problem is that the induction step was not quantified properly We should have proved Vn 21Pn gtPn1 Instead we proved correctly that Vn gt1 Pn gt Pn1 Indeed it is true that P2 gtP3 for instance but we never proved and it is false that P1 gt P2 Gm RQEW DQ a HMs T mm P MQ HRX 39 Ni V TaVes 1 6che 66gt wow Mad Rx when lama L 0 d 5V mew DST rpm MA mam m h1Ta4ec BOA Vva Waco Nof bard QW Bad rmd ina em E1 951 when watm space Cam be emei DVKCAA as Mask m U AT Wait DDAM WPX W JYWUT e m0 A MW 39VLV 6V 39 maxCA VDNW lusf 4g x v gt awe3 MARK 3quotva 3V CLV 3 vie erCL we came warng Memm mxi A 1 was walk Li 5 1 In CK e L quot cobv vj wWi e color CV1gtQCK u awagbh n u m e XLaLw M Qm ow claim aWM WWmce T am 3 1 30 L L QMObSQg Jars t Uw ma ox X a k KCLC 39 PxC K L Iii PMS Cw LB 39mw 50 L I PTCK QW05 9H i demWWMxL UVwL P LK wok Mwe Jf od vo Elmaa m Meai ewWCl w dew WL D F5 I 3me Maciaskquot TX L s CK Mr X a n WW 06v 9 m m r w W Mv F3 P4103 Cole FOO39339 wW i wokAC O 4613 ex f7 AQMX CL TY DIEgtvi 3 Vk 7 MCLCVB 4 abrCVo39li bT COLOCCJAB VOW V c l Ow LOWPDQ U CV01quot V aC Q 7 4 Cv gt I C Ty CM z VCL CW u I Lab r Q1mckl 3 I OCVH39WQ mcfma Msoxcenca Md I Me c1 39 6mg It epmsevx ygi a ahHow V QQVlequ I 6 66V Ver c anti R M 61 6X S MWQ A G katk at ESQ gt PAM 866MW 0L n E TWs 6an x JOK TM E wank ltVNM wc Q hoo BHAOK fexajrrm ex 3on Cwq lvk KIA1Wqu tic0x 1 Zquot L jonx Mxcq 3 NLACOK ASL Cows uo avg er were Mair sWd meec b vt A B 51gt B 75 kc a 5 13 UXNSUA A C CVCAJV Doou A D h D WWWth A6 4e 539T 9 rec QM vo mesecl COMtwat WV QL X 5W9 res mlvefs Wt FQMOVR L mlvx xmwwk mmmber 0 1665 ST W Wk xs NbKQW wt ru 3mm or mam ou vmwe 3 gtWquot 5 my ew 5 bwkg 2 an KAKWQWQC 33 ma a worM As at v a TM 0L1 HAWIS WK ecum V quot M Jags MC e VO O o j w nd Me ex ondr mlLorwome MAR R lac m ed 0 cm Sammie a gfmmms 4w rech 535 M Twp q 12lm6 beemms Pl 6 GFQPM GCE gt QvLEgt IZM V Ni quot 955 Cum3 erV Z 4 ak 2 1 h 3 39 E 2xDQampEgt gtgt 41 6V7 Equot Qquot a 2 ADCQ smch W IQ V 3 77 quot9b a 0A 6V 79 CC 3 3 fb We citch uwou th Caricaeg M r i gtka WCMTV W w LMOQT P900K 5 Commx meb W e Eam gGbC zK Q 496 L09 39 65 a veW K4 gt e 30 a x e A No PM a M No sew Imps W 6 CVIJEngt39 oxWA 622CVZJE3bz Ggt QW GZ 0J8 NSoww Alg K Q G quotWere u39 N6IXLL Wxafavt b xge ms AA 6E1 XE Z WI 130950 hVLGVlequot V7 VL OMA g quot1 1 WWW0493 quotAceA amk 5 AlAD LQZ39B 44w AMIL M CRWFerL DKO edggg Applied Graph Theory Glass 9 Oct 27 2005 Articulation Points If G is an undirected graph a vertex V E V is an articulation point if and only if G V is a disconnected graph A graph G is biconnected i it has no articulation points A graph is n connected i removing any n l or lesser number of vertices does not disconnect it lntuitive idea behind an algorithm to nd articulation points If we do a DFS since the graph we are considering is undirected we do Visit all vertices in one pass Do DFS The Root V is an articulation point i it has more than one child children are always connected by tree edges Remember that DFS builds a tree Therefore if the root has two or more Tree edges it is an articulation point For all other nodes we need to check if removing the node will separate the ancestors of the node from its children This can only happen if there are no Backedges during DFS from the children of the node to its ancestors De ne a function low V a N as follows l0wv minuevdulv Li u lowv computes the smallest arrival time over the set of all ancestors of the node V such that they are connected to the node v through paths originating at node V that have zero of more tree edges followed by a single back edge For all such ancestor vertices u E V lowv returns the smallest discovery time Therefore if we nd a child t of v having a lowt less than the discovery time of V then we have found a path originating from v leading to one of its ancestors This implies v cannot be an articulation point since it does not disconnect its ancestors from its children Therefore v is not an articulation point i v has a child t with lowt S dv the discovery time of the vertex v Using recursive DFS Assume we have computed lowwi for i 123 where w are children of v implies they are connected by tree edges We 1 Applied Graph Theory Class 7 Oct 18 2005 Reducibility Reduction is used to reduce a given problem to a known problem Say we have an e icient algorithm7 say A7 that has complexity 0n2 If we know of a reduction for a new problem in space and time Oklogk where k is the size of the new problem7 then we can solve it in time Oklogk2 Oklogk7 which has the asymptotic complexity of Oklogk2 Point to be taken Strive to cast a new problem in terms of one you know and can solve e iciently Communication network Consider a communication network with loss probabilities along edges The rst thing we do is convert all loss probablities to success probabilities This is because a packet being lost along an edge i the packet is lost along any path that starts from its destination vertex Probability of successful transmission HeeE 1 P8 The problem Given u7 v nd a sequence u uO7 uh uk v that maximizes Hf11 Pu 1L7 ui Remember that V u7 v 6 V7 Pu7 v E 07 1 Convert the product into a sum using log Transformed problem7 k mazimize logH1 7 Pu 17 2391 k mazimize Z log1 7 Pu 17 21 Since the Shortest Path SP algorithm computes the shortest path by minimizing the sum of the weights7 invert the sign of log1 Pu L7 The problem then becomes7 k minimize Z 7 log1 7 Pu 1 21 The terms above will always be positive since the domain of the log function is in the range 0 I So set wr s where r s E the set of edges to log1 Pu 1 and solve using SP Note In the above discussion for paths that don7t exist set the loss probability to 1 Interesting note on logs In general sums are better than products Even from the way we have been taught multiplication and addition in school multiplication is quadratic whereas addition is linear So when you have products try to convert them into sums logs are very useful in this regard FloydWarshall Proof that the algorithm computes the shortest path between any two vertices i and j Note that the re nement step in the algorithm where we check for a lower cost path between any two vertices i and j is given by dk1l7 mmfdevJ39LdeC 1 dkk 171 Proof We know that d0i j wi j Assume that dki j computes minimum paths At step k1 there are two cases to consider Use the node k1 since there is a path from i to k1 and from k1 to j which has a total cost less than dki j In this case since all nodes along the paths i k1 and k1 j are below k1 by induction hypothesis paths i k1 and k1 j are each minimal paths Hence their concatenation is a minimum path If we don7t use the node at k1 then dk1i j dki j which again by induction hypothesis is minimal BellmanFord Let d be a function that maps each vertex with a real number So d V a IR Now BFv d mindv Winner101 u We consider two versions of the algorithm The Strati ed version and the in place version optimized version Strati ed BellmanFord o d0u 0 if u source 00 otherwise 0 For k 0 1 2 n 1 For all u E V dk1u BFu dk 0 Output V u dnu We need to prove that the algorithm computes the shortest path between any vertex and the source We use induction to prove that at step k1 the algorithm computes the shortest path using only edges 3 k1 When we are done since we would have considered all n edges dnu will then give us the shortest path from u to the source Proof Assume that dku is the minimum weight of a path to the source from u that has at most k edges This is our induction hypothesis There are two cases to consider The rst case is when we need 3 k edges for the shortest path This means that BFu dk does not return a smaller value by using an additional edge k1 By our induction hypothesis since dk u is optimal in this case dk1u is optimal as well The second case is when there is a better path with k1 edges Then if V7 is the set of vertices that are immediate neighbours of u the cost of such a path will be minvEVdkv wv u This will be a shortest path since dk is the shortest path to v by our induction hypothesis and to this shortest path we are adding the edge with the smallest weight that leads to u so dk1u should be shortest as well In place Bellman Ford 0 du 0 if u source 00 otherwise 0 For k 0 1 2 n 1 For all u E V du BFu d 0 Output V u du We have simply dropped the subscript We need to prove that this version of the algorithm solves exactly the same problem as the Strati ed Bellman Ford described above lntuition for a proof If the vertices are traversed in the same order as their occurence in the optimal path then we need only one pass to compute the values du for all vertices along that path So the in place algorithm may work faster based on the order in which vertices are updated Euler Tours A tourof G is a closed walk which includes every edge at least once An Euler tourof G is a tour which includes every edge exactly once An Euler trail of G is a trail which includes every edge exactly once swag CMPE177 Fall 2mm A graph is Eulerian if it has an Eulertour Eulerian 2 Does it have an Eulertrail 2 swag CMPE177 Fal 2mm Thm For a connected graph G the following are equivalent 1 G is Eulerian 2All vertices of G have even degree 3The edges of G can be partitioned into cycles Thm 32 1 if and only if 2 Thm 33 1 if and only if 3 Show 1L 2L 3L 1 swag CMPE177 Fall 2mm Eulerian 2 Does it have an Eulertrail 2 swag CMPE177 Fal 2mm
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'