### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# GRAPH THEORY CSCI 4260

RPI

GPA 3.76

### View Full Document

## 14

## 0

## Popular in Course

## Popular in ComputerScienence

This 119 page Class Notes was uploaded by Santos Fadel on Monday October 19, 2015. The Class Notes belongs to CSCI 4260 at Rensselaer Polytechnic Institute taught by Mark Goldberg in Fall. Since its upload, it has received 14 views. For similar materials see /class/224848/csci-4260-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.

## Reviews for GRAPH THEORY

### 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: 10/19/15

1 Basic De nitions continued Let 1 d17 d2 dn be the sequence of degrees of a graph G Then 71 Z d 21 A vertex v resp an edge e in a connected graph is called an articulation point or a cut vertex resp a cut edge or a bridge if its removal disconnects the graph A non trivial graph is called nonseparable if it does not have cut vertices A block B of G is a maximal non separable subgraph of G Theorem 1 An edge e of a connected graph is a bridge i n0 cycle ofG contains e Proof An edge e u v is a bridge iff in G e the vertices u and v belong to different connected components Finish the proo f Types of Graphs Complete or Clique any two vertices are adjacent Empty no two vertices are adjacent Bipartite V V1 U V2 and any two adjacent vertices belong to different parts Complete bipartite a bipartite graph with any two vertices from different partitions are adjacent Star a tree with one vertex adjacent to all other vertices How different are these graphs De nition 1 Two graphs G V E and G V E are called isomorphic tf there ts a one to one mapptng f from V onto V such that any two oerttces 111112 E V are adjacent t fv1 and fltU2gt are adjacent Proposition 1 If GV E and HUF are tsontorphtc then 1 V WI and lEl IFI 2 the degree sequences of G and H sorted tn the non tncreastng order are tdenttcal 5 G has a cut vertex t H does 4 the lengths of the shortest cycles tn G and tn H are equal Problem 1 Which of the graphs below are isomorphic Operations on graphs The complement G of a graph G has VG as its vertex set two vertices being adjacent iff they are not adjacent in G A graph G is called selfcomplementary if G is isomorphic to G Problem Construct two non isomorphic self complementary graphs lf u and v are non adjacent G u 1 denotes the graph ltVltGgt7 139 U U7 vgt Let A denote the set ofall pairs 3 SC a E VG lfR g VXV A7 then G R VG E U R Union G U H the graph VG U VH EG U Join G H G and H are vertex disjoint graphs then G H is the graph obtained from G U H by adding all edges of the type 1 u Where 1 E VltGgt and u E The Cartesian product G D H of two graphs G and H has a vertex set WG gtlt WH and the edge set E G D H consisting of vu1 vu2 Where v E VG uhug E and 01110 v2u where 111112 E EG and u E VH The product G X H is the graph F with VltFgt VltGgt gtlt VH and 117 U1 U27 u2gtgt7 Where 111112 E EG andltu1u2 E Question HOW to represent a hypercube or an n cube Q 1 G G complement d f g d f x o 11 c o b y g d f x union G U H o b c y G H I o o o cartesian product product G x H G DH G o o o H o o o join of two disjoint graphs Theorem 2 Erdos Gdlldl 1960 Let d d17 d2 dn he the sequence of degrees of a graph G and let d1 2 d2 2 Z dn Then 2311 d ls even and k n Zd hh 1 Z rninkd fordllh12n 21 39 1 The reverse ls also true Theorem 3 Havel dnd Hdhlml 1963 Let D d17 d2 dn he a non lncredslng sequence of n0n negdtlve lntegers Denote D the sequence d2 17 7dd11 17dd127 7 Then D ls a degree sequence of a graph l D ls Proof gt If D is graphical ie is a degree sequence for some graph then take any realization G of D and add a new vertex adjacent to the vertices of D whose degrees are d2 1 dle 1 The resulting graph is a realization of D d17 d2 dn lt2 Let D be graphical and let G be its realization which satis es the following condition let v1 he a vertex of degree k E all and let v2v3vk1 he vertlces of degrees d2 d2 dkH respectlvelg then G ls selected so that the number of the nelghhors 0f v1 that are tn the set v2v3vk1 ls as large as posslhle h Examples nftwn m erent realizations nfa degree sequence Claim ln G the degrees of the vertices adjacent to 111 are d2 dkH Proof Let 112113 ukH be the vertices adjacent to 111 ordered so that degltu2 Z degltu3 Z Z deguk1 If the Claim is incorrect let 7 be the smallest integer such that Dr y ur Since Dr is a vertex of the 7quot largest degree among 1117s neighbors degltvr Z degltur Since 111 is adjacent to u and is not adjacent to UT there must be a neighbor z of Ur Which is not adjacent to ur Consider these four vertices 111 um 2 Dr The pairs Ulur and 21 are edges but the pairs urz and mu are not edges Now modify G by removing edges mu and zvr and adding edges urz and mm The degrees of all vertices are the same as before but vertex U1 is adjacent With more vertices from the set 112 v3 ka contrary to the selection of G Thus the Claim is correct To nish the proof we remove 111 from G Which yields a graph With the degree sequence D I Line graph of a given graph The line graph LG of a given graph is de ned as follows the vertices of LG are the edges E of G and two vertices of LG are adjacent iff the corresponding edges in G are incident to the same vertex of G See the Figure below G3 2 lt 4 5O 12 13 23 34 35 Edge 12 in graph G corresponds to vertex 12 in L G edge 13 in G corresponds to vertex 13 in LG and so on 1 2Connected Graphs De nition 1 A graph is connected if for any two vertices 33 E VG there is a path Whose endpoints are 13 and y A connected graph G is called 2Connected if for every vertex 3 E VG G 6 is connected A separating set or vertex cut of a connected graph G is a set S C VltGgt such that G S is disconnected The connectivity of G denoted MG is the smallest size of a vertex set S such that G S is disconnected or has only one vertex Two paths connecting two given vertices 6 and y are called inter nally disjoint if 13 and y are the only common vertices for the paths A disconnecting set of edges F is such that G F has more connected components than G does A connected graph G is called k edgeconnected if every discon necting edge set has at least k edges The edgeconnectivity of a connected graph G written HltGgt is the minimum size of a disconnecting set An edge cut is a set of edges of the form S S for some S C VG Here S S denotes the set of edges my Where a E S and y E S Theorem 1 Whttney 1927 A connected graph G wtth at least three verttces ts 2 c0nnected t for every two verttces Say E VG there ts a cycle contamth both Proving lt2 su ictent condttton If every two vertices belong to a cycle no removal of one vertex can disconnect the graph Proving gt necessary condition If G is 2 connected every two vertices belong to a cycle We will prove it by induction on the distance di5tu 1 between two vertices in the graph BASE Since the vertices are distinct the smallest distance is 1 This means that the vertices u and v are adjacent Let 2 be any vertex in G different from u and 1 Because of the removal of u resp 1 does not disconnect G there is a path P1 resp P2 which connects u resp v with z and does not contain 1 resp The cycle containing u and 1 consists of the edge u v and a path from u to 1 obtained from the walk from v to 2 using P2 followed by the reverse of the path P1 from z to u see gure below lNDUCTlVE STEP Now let the proposition be true for all pairs of vertices on the dis tance g k and let di5tuv k 1 Where k 2 0 Consider the shortest path from u to v and let to be the vertex on the path which is adjacent to 1 Since di5tu w k there is a cycle C containing u and w Furthermore since the removal of to does not disconnect u from 1 let here is a path P Which connects u With 1 but does not contain w A cycle containing u and U can be constructed from C and P the way it is illustrated in the gure below give a rigorous description 1 Problem 1 Let G be a connected graph and let G be obtained from G by adding edges Sty i distgcy 2 Prove that H is Q connected Problem 2 Let graph G satisfy the following condition for ev ery edge my there are two cycles 01 and 02 such that their in tersection is 33y Prove that G is 3 edge connected Problem 3 Prove that Petersen graph is 3 edge connected 2 Breadthfirst search BFSG gt39lt BFS traverses the vertices and the edges of the graph so that the vertices that are closer to the source 8 are visited rst BFS proceeds until all vertices reachable from s have been visited At the beginning all vertices are colored White except for 8 colored gray When a vertex is discovered it becomes gray When all neighbors of a vertex becorne gray the vertex is colored black When the program halts dm gives the distance from s to 1 and 7dr shows the parent of 1 in the breadth rst tree gt39lt 1 colors gray ds 0 7rs nil 2 insert 3 into a queue Q 3 for each vertex u E VG 8 4 colorM white dM oo 7Tunil 5 while Q y 9 6 u headQ 7 for each 1 E ad u 8 if colorM white 9 colorM gray dM 0M 1 u u 10 insert 1 into Q 11 remove u from Q 12 colorM black 3 Depth First search DFS prcn teer an MMQ for each vertex ueEVU icolorh white Wunil time O for each vertex ueEVU if colorhd white 7 DFSVisitu Q39Wrb QDPOt DFS Visitu L colorh gray 2 time ii dishd time dis is the discovery time for each vEEad u if colorh white WMM DFSVisitv colorh black finh time time fin is the time a vertex is finished S9 qgt51Qgt9 gt Edge classi cation Having applied DFS to a graph CV E de ne Tree edges the edges of the form u v the edges through which new vertices were discovered rnake Mn 1 directed from 7Tv to 1 Claim 1 If E is the set of all tree edges in G then every connected component of T V E is a directed rooted tree Back edges the edges u 1 connecting a vertex u to an ancestor v in T A vertex v is an ancestor of u u is a descendant of v if T contains a directed path from v to u Claim 2 A vertex u is an ancestor of v v is a descendant of u if at the time u was discovered by DFS there was a path connecting u with n all of whose vertices are white Forward edges non tree edges U7 1 connecting a ver tex u to a descendant v in T Cross edges all other edges Claim 3 A cross edge either connects two vertices u and v of the same depth rst tree provided none of the two is a descendant of the other or connect vertices from different trees of TV Theorem 2 Parenthesz s property In any depth rst search of a graph CV E for any two yertices u and v of G one of the following two conditions holds true 0 drew firde and disu are disjoint 0 one vertex is a descendant of the other say u is a descendant of v and dishr is contained en tirely in WSW firtM Corollary Vertex v is a proper descendant of vertex u in a depth rst forest iff dZsM lt disM lt firtM lt Theorem 3 The mom property of DFStrees m con nected undirected graphs T does not have cross edges that is every edge e E E is either a tree edge or a back edge 4 Finding Cut Vertices And Blocks Having applied the DFS denote disv the time vertex U was discovered Lv the least dis number of a vertex in the set of vertices reachable from 1 via a directed path consisting of tree edges followed by at most one back edge lowpoint of 1 Lemma 1 A vertex it which is not the root of the DFS search of a connected graph G chem gt 1 is a cut vertex iff there is a tree edge u gt U such that Lv Z chem Lemma 2 The root 7 of the DFS tree is a cut vertex of the graph iff there are at least two tree edges out of 7 To compute Lv for every vertex U which is a not the root of the DFS search modify the DFS algorithm using the following steps 0 when U is discovered set Lv disv o if v is a leaf of the DFS tree for every back edge ow Lv mmLv disw o if v is not a leaf for every DFS edge ow when the search backtracks from w to v Lv mmLv 11 Question Suppose you have a glass of water which is still Then you stir the water in the glass with a spoon without spilling it over and without adding more water in the glass Then wait till the water becomes still again and compare mentally the position of each water molecule before and after stirring What is the likelihood of the event that some molecule occupies the same position in the glass before and after the stirring Within the accu racy of the measurement still water Stirring randomly still again A B C Is there a molecule which occupies the same position in A as in C What is the probability of such an event The answer is at the end of the notes A gas lx Simpliciai and non simpliciai subdivision De nition 1 Let T be a closed triangle in the plane A subdivision of T into a nite number of triangles is called simplicial if the intersection of any two of the triangles is either empty or a vertex or an interval which is a side for both triangles Rules The three vertices of the triangle are labeled 0 1 2 Vi j E 0 1 2 the internal points of the Z j side are arbitrary labeled 2 0r j lriterrial points are arbitrary labeled 012 Is it possible to label the points so that no internal triangle is labeled 012 1 1 4V 2 0 Degrees Odd vertices and Sperner s lemma Theorem 1 Let 1 L 2 xn be a string 0f0 and 1 such that 1 0 and mm 1 Then there is an Odd number of tndtces 2 E 171 1 such that 5L Z39 y 51311 Proof Induction on the number n of entries in the string I De nition 2 Given a simplioial division of a triangle T a labeling of the vertices of the triangles of the sub division in three symbols 0 and 2 is called proper Z7 0 the three vertices of T are labeled 0 and 2 o for every ij0 g i lt j g 2 the vertices lying on the side ofT whose endpoints arei andj are also labeledi and j 0 every internal vertex is labeled with either 0 or 1 or 2 Theorem 2 Let G be ap qgraph with VG v17 vp Then p 21 degW 261 Corollary 1 Every graph contains an even number of vertices of odd degree In Theorem 3 Sperner s lemma For every proper labeling of a simplicial subdivision of T there is an odd number of triangles in the subdivisions whose ver tices are labeled with all three symbols 0 and 2 Proof Let To denote the region outside T and let T1T2 Tn be the triangles of the subdivision We de ne an auxiliary graph G as follows 71 1 vertices v0 v1 vn correspond to regions T0T1 Tn The edge set E comprises the set of pairs 1 vj such that the corresponding regions T and have a common boundary Whose labels are 0 and 1 By the lemma the degree of no is odd Therefore by the corollary there is an odd number of vertices among v1 on Whose degrees are odd Every triangle may have at most two sides With labels containing both 0 and 1 Therefore if a vertex vZz Z 1 has an odd degree then it is a vertex of degree 1 But if a triangle has just one side labeled 1 then its third vertex must have label 2 In other words the tri angles With all three labels and only them correspond to the vertices of odd degree in G This proves the theorem I Brouwer Theorem Brouwer s xedpoint theorem twodimensional case Let f be a continuous mapping of a Closed1 trian gle into itself Then there is a point z in the triangle for which fz 2 Proof If 0 1 and x2 are the corners of the triangle T then every point inside the triangle can be written as 1 050560 05111 052 Where 051392 0 012 and ozoozlozg 1 Triple 040 041 042 is the barycentric coordinates of 1 Let 1 050560 05111 ozng x 053 dim 053 We de ne three sets So 31 Sg 3 E Si if and only 1m 3 04 1A Closed gure is understood in the topological sense if a sequence of points inside the gure ap proaches77 a point in the plain7 than that point is also inside the gure in other words7 a gure is Closed if the boundary of the gure is a part of it Now select a sirnplicial subdivision of T for which every small triangle is of arbitrary small diameter We label every vertex of the subdivision by the index of Si that contains the point By Sperner s lernrna at least one triangle has all three labels Thus there are three points belonging to 5031 and SQ respectively that are arbitrary close to each other Since the sets Si are closed we conclude that they intersect a E So Sl Sg then a0 g 043 Oil 3 051 and Olg g or For barycentric coordinates this can only be true if on or for i 012 u Corollary 2 Informal The puzzle with the glass of water is solved by the generalization of the Brouwer Theorem to three dimensional case stirring is a con tinuous mapping of the class of water into itself so it has a xed point which is that molecule which stays in the same position before and after stirring 1 Trees A graph is called a tree if it is connected and has no cycles A star is a tree With one vertex adjacent to all other vertices Theorem 1 For every sirnple graph G With n 2 1 vertices the following four properties are equivalent A G is connected and has no cycles B G is connected and has n 1 edges C G has n 1 edges and no cycles lt l D For every pair a v of vertices in G there is exactly one u v path ProofAgtBgtCgtDgtA Problem 1 Let T he a tree and let P and Q be two disjoint paths of the same length in T Prove that T contains another path longer than P and longer than Q Problem 2 Let d1 2 d2 2 2 an gt 0 be it integers Prove that there is a tree T with degrees d1 an if and only if d1d2dn2n 2 2 Graceful labeling of trees De nition 1 A graph G is said to be decomposable into subgraphs H1 Hm if no Hi has an isolated vertex and EH1 EH2 is a partitioning of EltH If all are isomorphic to a graph H G is called H decomposable H 0 H dec0mp0siti0n F dec0mp0siti0n HOW to construct a T decomposition of K7 M decomposition of K7 K7 T o o o o 0 0 M 0 0 Given a labeleing gb of the vertices of a graph G for every edge M the length of M is de ned as De nition 2 Given a labeleing gb of the vertices of a graph G for every edge M the length of M is de ned as Given a tree T V E With n vertices a labeling of its vertices With integers O 1 n 1 is called graceful if 1 different vertices have different labels and 2 the lengths of the edges are distinct integers 1 2 i n 1 Conjecture 1 Ringel 1964 For any tree T with m edges m 2 O graph K2m1 is T decomposahle Theorem 2 If T is a tree with m edges which has a graceful labeling then K2m1 is decomposable into 2m 1 copies of T Proof Label the vertices of K2m1 by O122m View the vertices as placed around a circle Let gt VltTgt gt 0 1 m be a graceful labeling of T The 2m 1 copies of T are constructed by the following rule For k O 2m the vertices of km copy are k h1 h m7 Where the addition h m is understood in the modular sense 2m 1 O Vertices k i and k j in the hm copy of T are adjacent iff i and j are adjacent in the graceful labeling of T Finish the proof I Problem 3 Construct graceful labeltngs 0f the trees below H H H O O I O O H Problem 4 Construct an S decomposttton 0f K13 for the tree S below Graph Theory is a delightful playground for the exploration of proof technique in discrete math ematics and its results have applications in many areas of the computing social and natural sci ences D West Introduction to Graph Theory 1 Example of applications matching jobs and candidates CZ are candidates for jobs A line connecting 0239 With Jk indicates that candidate 0239 is appropriate for job Jk Question how to assign the candidates to the jobs so that each candidate is assigned to exactly one job and each job gets an appro priate candidate assigned to it 2 Basic De nitions A simple graph G V E consists of a set V of elements called vertices and a set E of pair of vertices called edges A null graph is a graph with V E Q a trivial graph is a graph with E Q and V 1 an empty graph is a graph with E and V Z 1 The order of a graph CV E is V the size of CV E is If both V and are nite G is called nite A graph of order p and size q is called a p q graph If e v u is an edge in G then 6 joins u and v e is incident with u and v u and v are incident with e u and v are adjacent to each other The degree of a vertex v denoted degdv or degv is the number of vertices adjacent to v or the number of edges incident With v A vertex of degree 0 is called isolated A graph is called regular if the degree of all vertices are equal A graph G is r regular if Va E VG degdr r Problem 1 Construct a 3 regular graph on 11 verttees Theorem 1 Let G be a p q graph with VG 111112 vp Then p a degltv 2g Corollary 1 Every graph contains an even number of verttees of odd degree Problem 1 has no solution A subgraph of a graph G V E is a graph HU F such that U g V and F g E G is a supergraph for H H is an induced subgraph of G if all edges of G connecting vertices in H belong to H H is a spanning subgraph of G if VH VG If G is a graph and S g VG then G S denotes the subgraph of G induced on VG S If R g EG then G R denotes graph VG EG R A walk from a vertex v to a vertex u is a sequence W of alternating vertices and edges 1117617112762 aekilavka such that 111 1 Uk u and Vi1k 1 6239 is incident with UZ39 and U 1 k 1 is called the length of W A walk without repeated edges is called a trail A walk trail with U1 vk is called closed If all vertices in W are distinct W is called a path If all vertices in a closed walk W are distinct and k 2 3 then W is called a cycle A graph is called connected if any two vertices u and v are con nected by a walk A subgraph H of G is called a connected component if H is a maximal non extensible connected subgraph of G denoted often cted components of a graph G is The number of conne MG cted Is the graph below COIme A distance distv u between two connected vertices v and u is the length of the shortest path connecting them For a connected graph G E01 rnaxmwg distv as the eccentricity of v in G DG max Ev the diameter of a G RltGgt rninq Ev the radius of G What are DltGgt and RltGgt for the graph below A graph is called a tree if it is connected and has no cycles A leaf is a vertex of degree 1 A rooted tree is a tree with a distinguished vertex called a root A level of a vertex in a rooted tree is the distance from the vertex to the root lf a vertex 1 lies on the path from the root to a vertex u then 1 is called an ancestor of u if additionally u and v are adjacent then u is a child of v and v is a parent of u A binary tree is a rooted tree in which every vertex has either two children or none Theorem 2 Every tree wtth at least two verttces has at least two leaves Proof Consider a longest path P in a given tree T note that there can be more than one longest path Let u and v be the endpoints of P Then each of these two vertices is a leaf since otherwise either T has a cycle or P is not a longest path I Theorem 3 A tree with p vertices has q p 1 edges Proof We prove the statement by induction on p BASE For p 1 every graph T has 0 p 1 edges INDUCTIVE STEP Let the statement hold for some p Z O and let T be a tree with p 1 vertices Then by Theorem 2 T has a leaf 9 T 23 must be a tree since if 23 were on a path connecting some two vertices then 13 would be of degree 2 2 ln the tree T as there are p 1 vertices and p 2 edges by induction We nish the proof noticing that removing 13 removes exactly one edge I 1 Global connectivity A vertex cut C of a connected graph CV E is a set such that G C is disconnected A u v separator for vertices u v E V is a vertex cut Which sepa rates u from v Mum denotes the minimum number of vertices in an uv separator 7ru 1 denote the maximum number of internally disjoint u 1 paths Theorem 1 Menger 1927 Let G be an undirected graph and let uv E VG be two non adjacent dtsttnet verttees Then Mu v 7ru v Proof It is obvious that Mu v 2 7ru v To prove Mu 11 S u v we use induction on number m of edges in G Denote k Mu 1 Base The smallest m for a graph with two non adjacent vertices u and 1 connected by a path is m 2 the graph is a path of length 2 For this graph obviously MG 7rG 1 0 0 0 Inductive step the theorem holds for all graphs with lt m edges gt it holds for any graph G with m edges Let G be a graph with m edges u v E VG and W be a minimal u U separator Case 1 Ev y W y Let k A strict path from u to W resp from v to W starts at u resp at 1 ends at a vertex in W and contains no other vertex from W V1 resp V2 denotes the set of all vertices covered by strict u W paths resp strict v W paths Claim 1 W V1 V2 lndeed every vertex in W belongs to a path from u to 1 since otherwise W is not a minimal separating set Thus W Q V1 V2 Furthermore if a E V1 0 V2 W then we select a MHZ path which avoids W and then 331 path which also avoids W this yields a uv path avoiding W which is not possible Form a new graph H1 by adding a new vertex 1 to the subgraph G V1 induced on V1 and making 1 adjacent to all vertices in W Similarly form a new graph H 2 by adding a new vertex 1 to the subgraph G induced on V2 making 1 adjacent to all vertices in W Claim 2 HH1111 HH2lt1 Ugt k lndeed every 11 v path in G starts with a 11 W path in in H1 so every 111 separating set in H1 is a 111J separating set in G similarly for H 2 Both H1 and H2 are smaller then G Why thus Menger7s theorem holds for both there are k internally disjoint paths from 11 to 1 and k internally disjoint paths from 1 to 1 By dropping 1 and 1 and combining the remaining paths we get k internally disjoint uv paths in G Graph H 1 Graph H 2 Case 2 Every minimal u v cut is either E or E Every minimum cut Wis either Eu or Ev There are vertices not in Eu or E v The graph consists of u v Eu and Ev lf G has a vertex 23 9 u U U U U Ev then the smallest cut of graph G SC is still h and applying Mengerls theorem to this graph we get k internally disjoint u v paths Similarly we consider the case of a E E 0 E Thus we conclude that VG u U U U U Ev and H E v Q Consider a bipartite graph B obtained from G by removing u and 1 Clearly every u v cut in G is a vertex cover of B By theorem of EgemciszKonig the size of a minimal cover is that of the maximum matching We use this matching to construct k internally disjoint paths in G H 1 Minimum Spanning Trees MST A graph HU F is a subgraph of CV E if U Q V and F g E A subgraph HU F is called spanning if U V Let G be a graph with weights assigned to the edges Then the weight of a subgraph H of the G is the sum of the weights of the edges of H A minimum spanning tree MST is a spanning tree of the minimum weight A cut V1 V V1 of a graph CV E is a partitioning of its vertioes into two subsets V1 V V1 denotes the set of edges u v of the form uEVl amp vEV Vl Machinery for constructing MST s 1 D 00 Greedy Method Initialize by coloring all edges White At every moment Comment All algorithms use the Greedy Algorithmic Strategy a tree is constructed as a sequence of steps each step is locally opti mal no step is ever reversed Main step of every algorithm an edge is colored either BLUE E accepted or RED E rejected every step is done so that the color invariant holds true El MST containing all blue edges and none of the red ones The coloring rules blue rule 0 construct a cut of the graph Without blue edges if it ex ists 0 select a shortest uncolored edge from the cut and color it blue red rule 0 construct a simple cycle Without red edges if it exists 0 select the longest uncolored edge in the cycle and color it red apply either rule until all edges are colored red or blue color invariant holds after every coloring step 2 For the method to succeed it is necessary that the Problem 1 Construct a minimum spanning tree in the network below by apply ing rst blue rules resp red rules and then applying red rules resp blue rules Problem 2 Let u v be a minimum weight edge in a graph G Show that u 1 belongs to some minimum spanning tree Problem 3 Call an edge light7 if there is a cut of G for which the edge is a minimal weight edge crossing the cut 1 Show that every edge of a minimal spanning tree is light 2 Construct an example of a weighted graph such that the set of all its light edges does not form an MST Problem 4 Let T be an MST of a graph G and let LltTgt be the sorted list of the edge weights of T Show that for any two MST7s S and T MS MT Problem 5 Let T be an MST of a graph CV E and let V g V Let T be the subgraph of T induced by V and let G be the subgraph of G induced by V Show that if T is connected then T is an MST of G Theorem 1 At every step of the red blue coloring the color invariant holds true Proof We want to prove that at every step of the coloring there is a minimum spanning tree which uses all blue edges and does not use any of the red ones lnitially no edge is colored either blue or red so the statement is correct and any minimum spanning tree would do Let T be a min imum spanning tree satisfying the color invariant and let 6 be the next colored edge Case 1 e was colored blue If e is in T already we are done Otherwise T contains a path P connecting the end points of e lf XY is the cut used to select 6 then P contains edges from the cut Because of the color invariant and the condition of the blue rule every edge which belongs to P and to X Y is uncolored Let 6 be such an edge We build a new tree T by removing e and adding 6 to P Obviously the resulting spanning tree can only be shorter than T Case 2 e was colored red If e is not in T we are done Let 6 be an edge of T and let C be the cycle using which 6 was selected Obviously at least one edge of the cycle 6 does not belong to T 4 Since T contains all blue edges 6 is not blue furthermore7 because of the color invariant it is not red By the red rule the weight of e is not less than that of 6 This proves that T e U 6 is a minimum spanning tree satisfying the required conditions 7 C is or avee wfhoufred edges XX 1 is or cuf wfhouf loue edges Remove e e Remove e i Add 9 Add e el 2 Ideas for minspan algorithms A blue tree is a tree in the forest de ned by blue edges All three algorithms below are mainly bluerule algorithms every coloring step selects a blue tree nds a minimum cost edge incident to the tree and colors it blue Kruskal7s algorithm builds blue trees according to the edge costs Prim7s algorithm builds only one non trivial tree Boruvka7s algo rithm builds blue trees uniformly througout the graph Boruvka s algorithm 1926 initialize the forest of 71 blue trees each With one vertex and no edges repeatedly consider the blue trees and for each one select the shortest incident edge color all selected edges blue Kruskal s algorithni 1956 reorder the edges in the nondecreasing order of their costs for each next edge if both ends of the edge belong to the same blue tree color the edge red else color it blue Prim s algorithrn Jarnic 1930 Prirn 1957 Dijkstra 1959 start With an arbitrary vertex 3 repeatedly if T is a blue tree containing as then select the shortest uncolored edge incident to T light blue color the edge blue After 3 steps 3 Algorithms for Minimum Spanning Trees MST KruskalGw At every moment7 the algorithm maintains a collection of treescomponents containing all vertices of G When an edge um is examined7 it is checked if the endponts of the edge belong to the same component It is done with the help of the procedure FINDSETO7 which outputs the representative of the component containing the input If the edge um passes the test7 the algorithm converges the two components containing u and 1 respectively the latter is done by procedure Unionuv A Q for each vertex 1 E VG MakeSet 1 sort the edges of E by nondecreasing weight w for each edge um E E7 in order by nondecreasing weight if FindSetu FindSetv A A U uw Unionuv 9 N WHgtP NE return A Complexity of MSTKruskalo The rst three lines initialize the components at that moment7 every component is an one vertex tree The initialization is a linear procedure done in OOH time The time to sort the edges in line 4 is lg There are operations lines 67 77 and on the disjoint set7 which in total takes log time Usual algorithms for set manipulation execute FINDSETO and UNION in lglE time in total7 but there are even faster algorithms The total running time of MST Kruscal is lg MST PRIMG w Prim7s algorithm maintains a single tree which starts with an arbitrary root vertex and grows until it spans all V At each moment a blue edge connecting A with V 7 A is added The key to an ef cient implementation of the whole algorithm is to make the selection of the new edge ef cient During the execution all vertices not in the tree are in the prioroty queue based on a key eld which is the minimal weight of an edge connecting the vertex with A The eld lll is the parent of 1 1 Q VlGl 2 for each vertex u E Q 3 keyM oo 4 keylr 0 5 Wm NIL 6 while Q 739 0 7 u Extract MinQ 8 for each 1 E adju 9 if 1 E Q and wuv lt keyM 10 lll u 11 MM wltuvgt 12 return 7T Complexity of MSTPRIMO The performance of the program depends on the implementation of the priority queue Q Using binary heaps the initialization in line 1 7 4 can be done in OOV time The loop is executed lVl times Since Extract Min requires OlglVl operations this part of the program is done in 0lVl lg time The for loop in lines 8 7 11 is executed time for each execution of the While loop Line 9 test for membership can be executed in a constant time on a RAM machine The assignment on line 11 involves rearrangement of the queue which is done in Olg time Alltogether the running time is 0lVl lg lVl lg There are implementations that run in 0lVl lg lVl time Theorem 2 Let U Q V and e be of the minimum length among the edges with one endpoint in U and the other in V 7 U Then there exists a minimum spanning tree T such that e is in T Proof Let To be a minimum spanning tree If e is not in T7 add 6 to T There is a path comprised of T edges that connects the endpoints of 6 Together with e the path forms a cycle This cycle must have at least one more edge connecting U and V 7 U Let 6 be the edge add 6 to T and remove 6 The resulting graph T is connected and is a tree the length of the new tree does not exceed that of T7 thus T is minimal Problem 6 Let G be a weighted undirected graph with all weights distinct is it true that G has a unique minimum spanning tree G o be 00 d 0 so of 0 Q G G o o g b0 00 Do QC be cc d d o o g 90 of so of so of o o 0 g g g Application to the TSP on the plane For this case of the general TSP7 the triangle inequality holds true for any three points 7 y7 and 27 MM M1172 2 10967 2 Approximate TSPG7 w 1 select a vertex 7 E VG to be the root vertex 3 construct a minimum spanning tree T for G from 7 using MST PrimG7 um 9 let L be the list of vertices visited in a preorder tree walk of T 7 use shortcuts to eliminate revisits let H be the resulting tour Cf return the cycle H Problem 7 Let L be a curcular tour of n points on the plane which intersects itself the intersection point is not one of the ls it true that the tour is not optimal How to construct a shorter tour which goes through all n points Notes on Discrete Mathematics Department of Computer Science Professor Goldberg Textbooks Introduction to the Theory of Computation by Michael Sipser Elements of the Theory of Computation by H Lewis and C Papadimitriou Discrete Mathematics with Algorithms by M Albertson and J Hutchinson These notes contain the material from Discrete Mathematics that you need to know in order to take the course in Computability and Complexity Try to solve all problems Most of them are simple their purpose is just to refresh you memory If you cannot solve many of them I would strongly recommend that you take a course in Discrete Mathematics 1 Logic Problem 1 Which of the following statements are true cats cats cats or mice eyes then sharks do not have teeth mice eyes then sharks do not have teeth Problem 2 Fill in the truth tables P Q P is true P is false P Q P is true P is false Q is true Q is true Q is false Q is false If Q then P P is true P is false true false Q is true P Q is false u P Problem 3 Write the truth table for p q q p Problem 4 Assuming that p and 7 are false and that q and 5 are true nd the truth value of the following propositions 539quot 90 2 Set theory De nition 1 A set A a07a1 empty set A is a subset of B A Q B x is an element of A x E A 2A the set of all subsets of A Cartesian product of two sets A x B a b a E Aampb E B Problem 5 Which of the following statements are true Problem 6 Prove the following identities ldempotency A U A A A m A A CommutatiVity AUBBUA A B B A AssociatiVity A U B U C A U B U C A B CA B C DistributiVity AUB QC A C39 UB C A BUCAUC BUC DeMorgan s Laws U BUC U B U C U B CU BUU C Problem 7 If X 133 and Y ab then What are X x YY x X X x X 2X De nition 2 A partition of a nonempty set A is a subset H of 2A such that is not an element of H and each element of A is in one and only one set in H Problem 8 Rephrase the de nition of a partition in a simpler language Enumerate all partitions of Y x Y for Y 1 2 Problem 9 Let S 1 234 5 a What partition of S has the most the fewest members b List all partitions of S with exactly two three members De nition 3 Binary relation R is a subset of A x B Inverse Pf1 of R if R is a binary relation between A and B then Pf1 Q B x A ba 6 PK1 i ab E R Composition QR Q Q A x C and R Q C x B is de ned by ab 6 QB i ac E Q and 01 6 R for some 0 E C Problem 10 De ne an n ary relation De nition 4 A binary relation R Q A x A is called re exive if a a E R for all a E A symmetric if a b E R whenever I a E R antisymmetric if a b E R and b a E R then a b transitive if a b and b 0 imply ac equivalence if it is re exive symmetric and transitive partial order if it is re exive antisymmetric and transitive total order if it is a partial order and Va I either a b E R or b a E R De nition 5 Function from a set A into a set B is a binary relation R on A and B such that for each element a E A El exactly one element b E B with a b E R f A gt B A is the domain of f fA Q B is the range of f A function is onetoone if for any two distinct elements a and b fa y onto if each element of B is the image of an element of A under f bijection between A and B if it is one to one and onto B De nition 6 Let D be a set 71 Z 0 and R Q D 1 be an 11 l ary relation on D Then B Q D is said to be closed under R if Vbl bn e B b1bnbn1 e R implies bn1 e B Let D be a set 71 Z 0 and f D gt D A subset B Q D is closed under fiffb1bnEBforallb17bnEB Problem 11 Fix D 5 Construct an example of a relation R Q D3 and a subset B C D which is closed under R Problem 12 Is a set closed under a function f also closed under an appropriately de ned relation R How to de ne R Problem 13 Given a set A Q D and a relation R on D is there a subset B Q D which contains A and is closed under R Problem 14 Given a set A Q D and a relation R on D is there a subset B Q D which 1 contains A 2 closed under R 3 is minimal in some natural sense Theorem 1 Let R be a relation on D and let A Q D Then there is a set B Q D such that o A Q B o B is closed under R o for any C Q D satisfying the previous two conditions B Q C De nition 7 The set B described in the previous theorem is called the closure of A under relations R1 Rn Re exive Transitive Closure of a Binary Relation De nition 8 Let A be a nite set D A x A and R Q D Let also Q and Q be a 3 ary and unary relation on D respectively given by Q ab bc ac a bc E A and Q a a a E A Then the closure of R under Q and Q is called the reflexive transitive closure of R and is denoted R Theorem 2 The re exive transitive closure PK of a binary relation R is equal to R U a b El a chain in R from a to b Problem 15 Prove theorem 217 3 Principle of Mathematical Induction Let A be a set of nonnegative integers such that LOEA 2 VnENif0nQA7thennlEA ThenAN Applying Mathematical Induction The task Given property P P01 prove that it holds for all integers n 2 0 Basis show that P0 is correct Induction assume that for some xed but arbitrary integer n 2 0 hypothesis P holds for all integers 0 1 7n Induction step prove that the induction hypothesis P01 implies that P is true of n 1 P01 gt P01 1 Conclusion using the principle of Mathematical Induction conclude that P is true for arbitrary n 2 0 Problem 16 Prove that for all n gt 10 n2 n 12 n 2lt Proof De ne property P01 by k2 k P01 Vk nkgt10 ngt10 k 2ltT 7 Then Basis for n 11 112 11 110 55 1 Notice that the base of the induction proof start with n 11 rather than with n 0 Such a shift happens often and it does not change the principle since this is nothing more than the matter of notations One can de ne a property Qm by Qm Pn 11 and consider Q for m 2 0 Induction step Suppose given 71 2 11 P holds true for all integers up n Then Pn gt n 2lt 21 gt n1 gt n1 2ltW l gt n1 2ltWsincengt10 1 lt nl27 nl72nill The last inequality is P n 1 Problem 17 Ramsey Theorem Let G be a graph A clique resp in dependent set in G is a subgraph in which any two vertices are adjacent respectively no two are adjacent Denote Rpq the smallest integer N such that every graph with N vertices either contains a clique of size p or an independent set of size q Prove that RltP7 D S Rp 161 R yq 1 Then prove that every graph with vertices either contains a clique of size n or an independent set of size 11 Problem 18 Prove that for all n 2 0 1 1 1 1 lt 1 2 3 2n 11 Problem 19 A set with an even number of elements is called even Guess a formula for the number of even subsets of a set with n elements and prove the formula by induction 4 Pigeonhole principle lst form If n pigeons y into k pigeonholes and k lt n then some pigeon hole contains at least two pigeons 2nd form If A and B are nonempty nite sets and A gt B then for any function f A gt B Ela b E A such that fa 3rd form Let f be a function from a nite set A to a nite set B let A n B m and k If k 2 1 then there are at least k values a1 ak such that fa1 ak Problem 20 Prove that every sequence of n2 1 distinct numbers has either an increasing snbsequence of length n1 or a decreasing snbsequence of length n 1 Proof Consider an arbitrary sequence S ai E 1 n2 1 of distinct numbers and de ne t to be the length of the longest increasing subsequence starting at ai If no monotone increasing subsequence S of length n 1 exists then Vi 1n21t Sn To use the Pigeonhole Principle we now de ne function F 1 n2 1 gt 1 n by Fa 25 i 12n2 1 Since the domain A of F is of size n2 1 and the range B is of size n by the Pigeonhole Principle 3 form there are at least n2 1n n 1 indices i1i2 in11 for which F takes the same value Let Fm Fag Fin1 L Clalm for every i1ig Zn1 aZj gt aZHl Indeed suppose aZj lt a l for some j E 1 2 n 1 Then every mono tone increasing subsequence R starting with aZj1 can be included into a longer monotone increasing subsequence starting with aZj by simply mak ing aZj the rst member and appending R to it If R is the longest monotone 9 increasing subsequence starting at i111 its length is L which yields a length L 1 monotone increasing subsequence starting at aij This contradicts the conclusion from the Pigeonhole Principle and thus proves the claim Finally we see that ail gt ail gt gt an1 which proves the theore I Problem 21 Prove that any subset A of a set 1 2 3 2n which has at least n1 elements contains two numbers such that one of them is a multiple of the other Proof De ne oddx to be the largest odd divisor of 05 let R be an equiva lence de ned by R a b odda oddb There are n classes of R in 1 2n and there are n 1 numbers By pigeonhole principle two of the numbers are in the same class this implies that one of them is a multiple of the other 5 Strings and languages Terminology alphabet E a nite set of symbols binary alphabet 01 string over Ea nite sequence of symbols from 2 empty string e 2 the set of all strings over an alphabet 2 length of a string the number of symbols in the string occurrences COMMITTEE position ranges from 1 to the length of the string substring COMMITTEE 7 MIT suf x pre x COMMITTEE 7 TEE COM Operations on strings Concatenation Reversal Statement Operations on languages Complement Union Concatenation MUSH o ROOM gt MUSHROOM concatenation is associative uvw uvw MUSHROOMR MOORHSUM For any two strings u and v uvR vRuR ZE A LUM LMwwuvuELvEM LkLLL Closure Kleene star L Problem 22 What is W Problem 23 What is 17 LeULUL2U LLUL2U Problem 24 Is it true that L Q M implies L Q M Problem 25 Is it true that L Q M implies L Q M7 Problem 26 Prove that wRR w Problem 27 Prove that if v is a substring of w then UR is a substring of wR Problem 28 Prove that wRR w Problem 29 Under What circumstances is IFL L e Problem 30 Prove that a b aba Proof The inclusion a7 b 2 WW A is obvious since the left part is the set of all strings in a and b The non trivial part of our task is to prove that a7 hr g aba lt13gt The left part of B consists of all strings in the alphabet a b every such a string can be written as apobqoaplbql apnilbqnil for n 2 0 and non negative integers p0 10191 ql The right part of B can be re written as follows aba e U a U a2 e U L U L2 UasLt where 515 2 0 are integers and L ba I U ba U ba2 U Thus to prove B we need to nd for every p0 10191 ql 7 integers 5 and t such that asLt contains aponOaP1b41 apnilenil Claim 5 p0 and t q0 q1 1711 are such integers aPO L 041mqn71 a bUbanaZbUbanaZbUbana2 401 bUbanaQbUbanaZbUbana2 bUbanaZbUbana2bUbana2 4717171 The rst factor gives a each next qo 1 factor gives a b the factor which follows gives bet and so on on every line the factors above the braces give I each and the last factor gives the concatenation of b and a in the corresponding degree I FINITE REPRESENTATION OF LANGUAGES THE CENTRAL ISSUE IN THE THEORY OF COMPUTATION IS THE REPRESENTATION OF LANGUAGES BY FINITE SPECIFICATIONS U the union operation 0 the concatenation operation the closure operation Regular Language informal de nition any language that can be obtained by a nite application of the three operations above to a given nite set of words Regular expression over an alphabet E is a string over the alphabet EUR 7 LAW such that the following holds 6 and each member of E is a regular expression If oz and B are regular expressions then so is a If oz and B are regular expressions then so is aU If oz is a regular expressions then so is of mybooww Only an expression which can be obtained by applying 1 through 4 is regular The class of regular languages sets over an alphabet E is the minimal collection of sets containing and the set a for every a E E and closed under the operations of union concatenation and Kleene stari Standard convention Parentheses in an expression may be omitted Problem 31 For each of the sets below give examples of strings in and not in the sets 2 a b a w for some u 6 2210 uuRu b w ww www c w for some u and v uvw wvu d w for some u www uu Problem 32 Rewrite each of the regular expressions as a simpler expression representing the same set a W Ua Ub Uan b abba C WW U WV d a U baa U b Problem 33 A regular expression is in disjunctive normal form if it is of the form a1 U a2 U an for some n 2 0 Where none of the ozz contains an occurrence of U Show that every regular language is represented by an expression in disjunctive normal form 6 Principle of Mathematical Induction Let A be a set of nonnegative integers such that IDEA 2 VnENif0nQA7thenn16A ThenAN Applying Mathematical Induction 15 The task Given property P P01 prove that it holds for all integers n 2 0 Basis show that P0 is correct Induction assume that for some xed but arbitrary integer n 2 0 hypothesis P holds for all integers 0 l n Induction step prove that the induction hypothesis P01 implies that P is true of n 1 Pn gt P01 1 Conclusion using the principle of Mathematical Induction conclude that P is true for arbitrary n 2 0 Problem 34 Prove that for all n gt 10 n2 n 2lt 12 Proof De ne property Pn by k2 k Pn Vk nkgt10 ngt10 k 2ltT Then Basis for n ll 112 11gt9 110i55i91 12 12 i 6 i 639 Notice that the base of the induction proof start with n 11 rather than with n 0 Such a shift happens often and it does not change the principle since this is nothing more than the matter of notations One can de ne a property Qm by Qm Pn 11 and consider Q for m 2 0 11 2lt Induction step Suppose given 71 Z 11 P holds true for all integers up n Then Pn gt n 2lt 21 n121ltW n127nl 27 gt n1 2lt 1 gt nl 2ltWsincengt10 The last inequality is Pn 1 Problem 35 Ramsey Theorem Let G be a graph A clique resp in dependent set in G is a subgraph in which any two vertices are adjacent respectively no two are adjacent Denote Rpq the smallest integer N such that every graph with N vertices either contains a clique of size p or an independent set of size L Prove that R 4gtSR l lR 1l Then prove that every graph with vertices either contains a clique of size n or an independent set of size 11 Problem 36 Prove that for all n 2 0 111 41lt1 7 7 7 n 2 3 2 Problem 37 A set with an even number of elements is called even Guess a formula for the number of even subsets of a set with n elements and prove the formula by induction 7 Pigeonhole principle lst form If n pigeons y into k pigeonholes and k lt n then some pigeon hole contains at least two pigeons 2nd form If A and B are nonempty nite sets and A gt B7 then for any function f A gt B Ela b E A such that fa 3rd form Let f be a function from a nite set A to a nite set B let A n B m and k If k 2 1 then there are at least k values a1 ak such that fa1 ak Problem 38 Prove that every sequence of n2 1 distinct numbers has either an increasing subsequence of length n1 or a decreasing subsequence of length n 1 Proof Consider an arbitrary sequence S ai E 1 n2 1 of distinct numbers and de ne t to be the length of the longest increasing subsequence starting at ai If no monotone increasing subsequence S of length n 1 exists then Vi 1n21t Sn To use the Pigeonhole Principle we now de ne function F 1 n2 1 gt 1 n by Since the domain A of F is of size n2 1 and the range B is of size n by the Pigeonhole Principle 3 form there are at least n2 1n n 1 indices i1i2 in1 for which F takes the same value Let m1 Fag Fi39n1 L Clalm for every i1ig Zn1 aZj gt aZHl lndeed suppose aZj lt aZH1 for some j E 1 2 n 1 Then every mono tone increasing subsequence R starting with aZj1 can be included into a longer monotone increasing subsequence starting with aZj by simply mak ing aZj the rst member and appending R to it If R is the longest monotone increasing subsequence starting at 2311 its length is L which yields a length L 1 monotone increasing subsequence starting at aZj This contradicts the conclusion from the Pigeonhole Principle and thus proves the claim Finally we see that ail gt ail gt gt an1 which proves the theore I Problem 39 Prove that any subset A of a set 1 2 3 2n which has at least n1 elements contains two numbers such that one of them is a multiple of the other Proof De ne oddx to be the largest odd divisor of 05 let R be an equiva lence de ned by R a b odda oddb There are n classes of R in 1 2n and there are n 1 numbers By pigeonhole principle two of the numbers are in the same class this implies that one of them is a multiple of the other 8 Strings and languages Terminology alphabet E a nite set of symbols binary alphabet 01 string over Ea nite sequence of symbols from 2 empty string e 2 the set of all strings over an alphabet 2 length of a string the number of symbols in the string occurrences COMMITTEE position ranges from I to the length of the string substring COMMITTEE 7 MIT suf x pre x COMMITTEE 7 TEE COM Operations on strings Concatenation MUSH o ROOM gt MUSHROOM concatenation is associative uuw uuw Reversal MUSHROOMR MOORHSUM Statement For any two strings u and V uvR vRuR Operations on languages Complement Z 2 A Union L U M Concatenation LM w w uv u 6 L71 6 M Ll LL L Closure Kleene star L L eULUL2U LLUL2U Problem 40 What is W Problem 41 What is L Problem 42 ls it true that L Q M implies L Q M Problem 43 ls it true that L Q M implies L Q M7 Problem 44 Prove that wRR w Problem 45 Prove that if v is a substring of w then UR rap is a substring of Problem 46 Under What circumstances is L L e Additional Problems in Discrete mathematics Problem 47 Let A a17a27 ap p Z 3 and let Nk denote the number of subsets ofA whose size is k k 12 719 Which of the following three statements is correct a N2 gt Npi2 N2 lt Np72739 C N2 an2 20 Problem 48 How many eight digit numbers are there that contain a 5 and a 6 9 Explain Problem 49 Proue by induction that l54n 3n2n l Problem 50 Find the smallest ualue ofn for which a 22 gt 1000 000 b nl gt 1000000 Explain Problem 51 Describe an algorithm which computes 0596 using at most seuen multiplications Problem 52 Determine whether the following is true or false a n 1 Onl b n3 0500n2 Explain Problem 53 What are the coe cients of the terms 12 in the expansion of x i where n gt 2 Explain Problem 54 The Euclidean algorithm is based on the theorem stating that the last nonzero remainder produced in the set of Euclidean equations equals gcdbc A corollary to this theorem is ifg gcdbc then there are integers x and 3 such that g 05b yc Write a formal induction proof of this Corollary Problem 55 Find pairs bc such that gcdbc equals a b239 b b3 Problem 56 Let abt be positive integers Which of the following state ments is correct Explain a gcda b lt gcdat bt b gcda b gcdat bt c gcda b gt gcdatbt Problem 57 Using the Euclidean algorithm nd the greatest common diui sor of J 1008 and 539 662 and 414 Show all stages of the algorithm in both cases Problem 58 If a7b7x7y are nonzero integers such that am by 3 is gcda b 3 Explain Problem 59 Proue by induction that FlF3F2nilFZn7 where E denotes the ith Fibonacci number Problem 60 Suppose that the sequence GZ is de ned by Go 0 G1 l Gn G714 2Gng Determine which of the following propositions are true a Gn 0012 GnG0G1Gn1 c Gnlt2n n0l Problem 61 Let E be an alphabet and L be a language ouer E Prove that 232 gL then LgL LLUL2UL3U Problem 62 Prove that for euery integer n gt 0 5 2 is diuisible by 3 Problem 63 For euery integer n 2 0 12 7 nn l2n 1 7 6 1 M N H Proue Problem 64 For euery integer n 2 0 n 1 n iilinl39 Proue Problem 65 For any n 2 4 n gt 2 22 Problem 66 For any w E 071 ifw starts with 0 and ends with 1 then it contain s a substring 01 Problem 67 For any integers a and b with 0 S a S b and every integer n 2 1 b a is divisible by b a Problem 68 For every integer n 2 1 i gt 2nn3 21 Proof We prove it by induction on n Base For n 1 the left part is 1 and the right part is 23 1 g 23 Inductive step Suppose the statement is correct for some n 2 1 we prove that it is correct for n 1 Thus Given 21 gt 2nn3 Prove 2211 gt 2n 1n 13 n1 n Zxt2 n1 1 2391 2391 Using the given inequality we evaluate the right part of 1 xn 12 2mm xn 1 2 The following sequance of equivalent inequalities completes the proof 2mm W 2 2n 1 nT13 3 2W 3 n 1 2 2n1n 1 4 211 2 2n 1n 1 5 411 2 2n 12n 1 6 4n3 2 4n2 4n1n14n3 3n1 7 0 2 3n 1 8 The last inequality holds true for any n gt 0 I Problem 69 Prove that for every n 2 1 and every m 2 1 the number of functions from 1 2 n to 1 2 m is m Problem 70 The numbers can for n 2 0 are de ned recursively as follows a0 2 a1 2 for n 2 2 an 5an21 6an22 Show that for every n 2 0 an 2 x 3 4 x 2 24 Problem 71 Let E be an alphabet Under what conditions two distinct non empty strings as y satisfy my yx Either proue it cannot occur or describe precisely the circumstances under which it can Problem 72 For a nite set S S denotes the number of elements of S s it always true that for nite languages A and B AB A gtlt B7 Either proue it or nd a counterexample Problem 73 Let L be a language ouer an alphabet 2 Under what circum stances IfL If Problem 74 Giue an example of two non empty languages L1 and L2 that satisfy the following two conditions 1 1ng LQL and 2 Neither language is a subset of the other Problem 75 Show that for any language L L L UV UV L L 9 9 Order of functions Notations N resp N set of natural resp positive natural numbers R resp R set of real resp positive real numbers Floors and ceilings Polynomials q0 qln qbnb exponentials a limnnw0 exlx2 js Logarithms lg n log n binary logarithm lnn loge n Factorials nl 123 n W lt2 3 m s W aw12gt n m x27Tn Fibonacci numbers F0 0 F1 l E FFl Tl2 If 5 HT m 161803 and 25 PT m 061803 then R Frequently occurring complexity functions 00 Linear function when the size of the input doubles the amount of work doubles N log N often arises when the algorithm breaks up the problem into N2 respi N3 2N small subproblems when the data doubles the function more than doubles but not by much Quadratic resp Cubic order doubling the data size quadruples resp increases by a factor of 8 the work Exponential order assumed to be impractical Given two functions f g 71 gt 71 gOfEEICgt0n0gt0 such that gn S Cfn for all n gt no Function 901 does not grow at a faster rate than f gQfEEICgt0n0gt0 such that gn Z Cfn for all n gt no Function gn grows at least as fast as f does 99fE9Of amp 99f 901 and grow at the same rate 0gn E V0 gt 073n1gt 0 such that Vn gt m 0 lt lt 0901 equivalently lirnrH00 0 f is growing asymptotically slower than 901 WWW 13 09n 901 is growing asymptotically faster than f Problem 76 Which of the statements below is correct and which is false n2 0mg n3 0mg 27 02 11 1 OWE if n 0m then mm 0mg if 001 then 21 02 if GLOW and 901 00501 then 00m there are two functions f and 901 such that 1 7e O9n and 901 7g 00 Problem 77 Prove that 1 9900 and 901 90471 imply 90471 2 9900 and 901 Own imply WWW 3 WWW and 901 WWW imply WWW 4 09 and 900 0hn imply WWW 5 M900 and 901 WWW imply WWW 6 GLOW 13 9 9 NW 7 ea 1x9m2 whena gt0 8 n ab 9011 a and b are constants 9 Is 2nl O2 7 Is 22 O2 7 H O n 001 n w2 lgn 9nlgn Problem 78 Prove by induction that 2th Fibonacci number satis es the equality Fz39 W gt57 Where b the golden ratio and a the conjugate of q Problem 79 Prove by induction that W gt 0 E S Problem 80 Show that quicksort s best running time is nlog Problem 81 Construct a linear algorithm for sorting n non negative integers of size 3 On for some constant C 1 Matchings in Graphs De nition 1 Two edges are called independent if they are not adjacent in the graph A set of mutually independent edges is called a matching A matching is called maximal if no other matching contains it maximum if its cardinality is maximal among all matchings perfect if every vertex of the graph is incident to an edge of the matching Given a matching M in G7 a path is called alternating if its edges are alternatively in M and not in M a vertex 1 is called weak if no edge of M is incident to 3 Are there perfect matchings in the graphs below WW The symmetric difference of two sets X and Y is the set of all ele ments that belong to one but not the other of the sets X YXUYUXHY Theorem 1 A matching M is maximum if and only if there exists no alternating path between any two distinct weak vertiees of G Proof For a proof we will try to answer the following questions 0 lf a graph M is a matching What is the maximum degree of a vertex in such a graph o If the edge set E of a graph F is the symmetric difference of two matchings M1 and M2 then What is the maximal vertex degree of F 0 Consider a component C of F above Can 0 be a path a cycle anything else o If C is a cycle of F can it have an odd length an even length De nition 2 An edge cover of graph G is a set L of edges such that every vertex is an end point of an edge in L G is the smallest size of an edge cover oG is the largest size of a matching in G Theorem 2 For every graph G Without isolated vertices oG 6 G maximum malchz39n g unsaturated vertices MG 2 719 MG Consider the minimal edge cover L and the subgraph H V L H doesnt have paths of length gt 2 since otherwise an edge in side could be removed yielding a smaller edge cover Thus every connected component of H is a star If k is the number of these stars L MG k Form a matching by picking one edge from each star l 2 Matchings in Bipartite Graphs De nition 3 A graph GltVEgt is called bipartite if V can be partitioned into two subsets V1 and V2 so that E g V1 gtlt V2 Proposition 1 A graph G is bipartite if and only if it has no cycles of odd length Proof lf G is bipartite and C is a cycle of G then the vertices of C can be labeled by O and 1 depending to which part the vertex belongs to This implies that the length of the cycle is even Let now G be a graph without cycles of odd length We want to prove that G is bipartite Obviously we may assume that G is con nected Then consider an arbitrary vertex v E VltGgt and de ne Vwm resp Vodd to be the set of all vertices whose distance from v is even resp odd lf there were an edge connecting two vertices from Amen resp two vertices from Aadd then G would have an odd cycle Thus G is bipartite and Vwem Vodd is the partition I De nition 4 Given a matching M of a bipartite graph G V1 V2 E V1M resp V2M denotes the set of vertices in V1 resp V2 incident to the edges in M De nition 5 A matching M is said to saturate a vertex v if there is an edge u w E M Theorem 3 A bipartite graph G V1 V2 E contains a match ing with V1 edges a matching saturating all V1 t VX g n W EltXgt ltgt Proof First we prove that X g Since M is a matching the sets V1M and V2M have the same cardinality For every 33 E X there is a distinct vertex y E for which 13 y is in M Applying to X V1 we get V1 g Our goal is to prove that there is a matching which saturates all vertices in V1 Suppose M0 is a matching which does not saturates all V1 We will show how to construct a new matching M with M gt M0 The idea is illustrated in the next gure D T 00000 v 0000 S Let S V1 V1M0 and T V2 V2M0 If there were an edge 3311 E E such that a E S and y E T the new matching is M0 U 33 So we assume that no vertex in S is adjacent to any vertex in T Because of for every vertex v E S there are edges incident to 7 Consider any path in G satisfying the following conditions 1 the rst vertex of the path is in S 2 the edges of the path alternate between edges not in M0 and edges in M0 Claim No path satisfying 1 and 2 contains a vertex in T lndeed if such a path had a vertex in T it would be its last vertex and the path itself would be an MO alternating path with two end vertices that are not saturated by M0 Thus the path would have been augmenting yielding a matching M1 which is larger than M0 Let U E S and D be the set of all vertices reachable from v by MO alternating paths Because of the Claim D H T Q Furthermore V1Mogt DI V2M0gt D Thus for X V1M0 DI U U EXgt V2M0gt Da which implies that EXgt X 1 This contradicts the condition on G and thus proves that S Q I De nition 6 Given a graph CV E a subset 0 g V is called vertex cover if every edge in E is incident to at least one vertex in C Question if C is a vertex cover for G What kind of graph Will be obtained if C is removed from G Theorem 4 Egemari 1931 K nig 1931 A maximum car dinality of a matching in a bipartite graph G l1l2E is equal to the minimum cardinality of a veitex cover Proof gt Let c be the smallest size of a vertex cover and m be the largest size of a matching in G Then 0 2 in since in any cover every edge in a matching must be covered by its own vertex lt Given a minimum vertex cover C construct a matching of size ICI A minimum vertex cover C yields a maximum matching M 1V M 2 DenoteS Vl QandT Vg Q ForanyX g S letX denote the set of vertices in V2 that are adjacent to vertices in X lf X gt X then X U X would be a new cover set which is smaller than Thus X g X 7 and by Hall7s theorem the bipartite graph induced by S U V2 T contains a matching Which saturates S Similarly for the bipartite graph induced by TU V1 S The union of these matchings yields a matching of size I Another proof Given a maximum matching M construct a vertex cover of size M I 1 Milk JIIIIIIIIIIIII ST X I IIIIIIIIIIIIIF 3 Dominating sets A set D of vertices in a graph CV E is called dominating if any vertex outside of D is adjacent to a vertex in D THe smallest size of a dominating set in G is called the dominating number 7G 39 3V A Theorem 5 Every graph with n vertices and minimal degree k contains a dominating set of size at most n1 lnltk 1 k 1 Proof Us the greedy algorithm which selects vertices one by one so that at every step the vertex selected is the one Which dominates the maximum new vertices Continue these selections as long as there are more then nk 1 undominated vertices left After that all remining vertices are added to the dominating set Claim Let U be the set of undominated vertices Within the pro cess Then there is a vertex Which dominates at least IU 1 n vertices in U Indeed each vertex v in U dominates set N v of size 2 k2 1 Thus 2 NVgt Z Uk1gt UEU On the other hand every verex in G appears in at most 71 of the sets N Thus there is a vertex t which dominates at least Ultk1gt tirnes Thus we proved that the sizes of U is smaller than k1 IU lt1 lt implies that lnkJ 1 n k 1 applications reduce the undorninated set to at most nk 1 Algorithm for constructing a maximum matching The algorithms is the iteration of a procedure AUGMENT which starts with a matching can be empty of a bipartite graph AUGMENT either outputs a bigger matching or a vertex cover of the size of the matching which proves that the current matching is maximum in the graph The last iteration ends with the construction of the cover set Procedure AUGMENT Input graph CVl V2 E and a matching M let M V1 resp M denote the vertices in V1 resp V2 that are saturated by M 1mm V1 then halt with M as a maximum matching and V1 as a minimum vertex cover else MUu me construct an alternating tree 7U if 7U contains vertices in V2 MUG extract an augmenting path P 111 v2 m E V1 Ml1v2 E V2 WU2 augment M else let S be the set of all vertices in V1 that are reached by 7 let T be the set of all vertices in V2 that are reached by T halt with maximum matching M and minimum vertex cover V1 S U T Nlt HHJ iJHH v V V V V X V V 2 V 1 Illustration of the algorithm for constructing a maximum matching in a bipartite graph 4 Matchings in General Graphs A factor is a spanning subgraph of a given graph A k factor is a k regular factor A 1 factor is a perfect matching For a graph H 0H denotes the number of connected components with an odd number of vertices Theorem 6 Tutte 1947 A connected graph G has a 1 faet07 W for every S g VG 00 8 g S Proving lt2 Claim 1 If G has a 1 factor then VS g VG 0G S 3 Explain Proving gt Claim 2 If VS g VG 0G S g S then MG is even lndeed apply the condition for the empty set S Q Claim 3 lfVS Q VG 0G S 3 ISI then adding an edge to G preserves the condition lndeed adding an edge doesn7t disconnect components doesn7t reduce S and occasionally may even connect two odd components making them one even component Now proceed to the heart of the proof lf contrary to the Tutte theorem G is a graph without a 1 factor but for which Tutte7s condition holds then add the maximum possible number of additional edges to G so that the resulting graph G still doesnt have a 1 factor Let U be the set of vertices in G that are adjacent to all vertices in G Then at least one connected component of G U is not a complete graph since otherwise it is straightforward to construct a 1 factor in such a G Thus there are non adjacent vertices 13 and z in one connected com ponent of G U It is easy to see that one can select such a pair so that there is a third vertex y which is adjacent to both of them Furthermore since y Z U there is a forth vertex w which is not adjacent to y Now consider G 2 and G yw Because of the Inaxiinahty of G both have 1 factors Let M1 resp M2 be a 1 factor in G 2 resp G yw Clearly M1 y M2 since M1 contains 332 but not yw While M2 contains yw but not asz Because each of M1 and M2 are 1 factors the symmetric difference M1 G9 M2 consist of even cycles and isolated vertices Symmetric difference of two matchings the union of alternating cycles of even length IIIIIIIII IIIIIIIII 0 o y 9 o o n o o o v N G Q I I o o v q o v G I q o I I o v s y 39I Q 9 0 I 039 9 l III I III II HHIIIII lllllllllll I I I I I I I i 39 o o 0 c 0 39 o o 0 o quotI 0 o o 39l I o ll 1IIII 39IIIIIIIIIIIIIIII39 ln the graphs G 2 and G yw CASE 1 2 and yw belong to different cycles then a 1 factor of G which avoids both 332 and yw is constructed by using M1 for one cycles and M2 for another See the gure below nuQ squot y z xlllll39hquot N l I39 quot391 s 39t I I I I o o o o use dot edges here use solid edges here a s G CASE 2 2 and yw belong to the same cycle of M1 G9 M2 Then construct a 1 factor of G by switching from M1 to M2 in the same cycle containing both 332 and yw See gure below The case of ltxzwygt The case of ltxzywgt Corollary 1 A 3 regular graph G without bridges has a perfect matchtng odd components of GS G1 G2 Gk Proof We prove the statement using Tutte7s theorem Let S g VltGgt and let G1 G2 Gk be odd components of G S Denote m VltG and mi the number of edges With one endpoint in S and the other in Gzr 1 Z 16936 3m 2EG mi 1 lt implies that mi is odd for every 239 Since G has no bridges mi gt 1 thus 77 gt 3 E 1 On the other hand k E doomquot 3S Z 2 ml 2 3k 2 x65 t1 Inequality 2 implies S Z k which by Tutte7s condition implies that a perfect matching exists in G H 1 Directed graphs A directed graph digraph G is a pair V E where V is a set of vertices and E is a set of ordered pairs of vertices For every edge e 33y E E SC is called the tail of e and y is called the head of e For every edge 6 it is an edge from the tail to the head The outdegree of a vertex 3 denoted 6ltgt is the number of edges for which 13 is the tail The indegree of a vertex 23 denoted 6136 is the number of edges for which 6 is the head A loop is an edges whose tail and head are the same vertices Multiple edges are edges with the same heads and tails Subgraphs Isomorphism decomposition union the same for graphs and digraphs Two digraphs G1l1E1 and G206 E2 are isomorphic if there is a one to one mapping f V1 gt V2 such that for all u and v E V1 uv E E1 iff fufv E E2 The adjacency matrix of a graph G A am Where are 11ffz jeE m i 0 else ln the case of a digraph With multiple edges am is the number of edges With tailz39 and head j Unless it is speci ed our digraphs have no multiple edges nor loops The incidence matrix MG mm of a graph G With vertices v1 1 and edges 61 em is de ned as follows 1 if vi is the tail of Q7 mm 1 if 11 is the head of Q7 0 else In an undirected graph G a walk is a list 1116111262 1461111 such that 111 vk are vertices 61 62 6k are edges and Vi1k 1e v v 1 The length of a walk is the number of edges A trail is a walk without repeated edges A path is a trail without repeated vertices A trail whose rst and last vertices are the same is called a Closed walk or a circuit A circuit without repeated vertices is called a cycle Given a digraph G its underlying graph G is obtained by re placing all directed edges with corresponding undirected edges A digraph G is weakly connected if its underlying graph is con nected The weakly connected components of digraph G are the connected components of the underlying undirected graph A directed path in a digraph G is a sequence of edges 6239 51 such that for every 139 1 p 1 the head of e is the tail of 1 A digraph G is strongly connected or strong if for every 6 and y there is a directed path starting at 13 and ending at y A subgraph H is a strongly connected component of a given digraph G if H is strong and no other strong subgraph contains H Theorem 1 Every digraph G can be partitioned into strong sub graphs with disjoint sets of vertrces An Eulerian trail in a digraph is a trail Which contains all edges Lemma 1 Let G be a digraph with the smallest outdegree 6G Z 1 Then G has a cycle Proof Starting With an arbitrary vertex 3 E VG form a sequence of vertices as follows 5171517 33 the head of an edge ezr Whose tail is 36 Terminate the sequence When the rst member seq is encountered Which is equal to a member tsp already in the sequence Clearly the sequence p pp1 eq2q1eq1ap is a cycle I Theorem 2 Let G be a digraph whose underlying graph is con neeted and has at least 2 pertiees Then G has an Enlerian circuit i for every perteri E 1 n di d i Proof lnduction on the number of edges of the digraph Since the underlying graph is connected for every vertex v E VG dv Z 1 This implies that Z Base Suppose Then dv d v 1 for every vertex v E VG This implies that G is a directed cycle Which is also the Hamiltonian cycle of the graph Inductive step Suppose the theorem holds for every graph with lt m edges and let G be a graph with m edges which satis es the condition of the Theorem Since d Z 1 for every 6 E VG by the Lemma 1 above G has a directed cycle C Consider now the graph H V E E C which is obtained from G by removing all edges of C see Figure below Let G1 G2 Gk be the connected component of H For every G E 1 k which is not an isolated vertex the conditions of the Theorem hold and each of them has fewer than m edges explain the reasons Thus by induction each such component G has an Eulerian trail 1 Then combining all Ms with C yields an Eulerian trail for G I

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.