Handshaking Theorem For Directed Graphs
AnnouncementsCS311H: Discrete MathematicsIntroduction to Graph TheoryInstructor: Işıl DilligInstructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph TheoryHomeworkdue now!INext HW out, due next TuesdayIMidterm 2 next Thursday!!Instructor: Işıl Dillig,1/34Directed GraphsCS311H: Discrete MathematicsIntroduction to Graph Theory2/34In-Degree and Out-Degree of Directed GraphsIAll graphs we considered so far are undirectedIIn undirected graphs, edge (u, v ) same as (v , u)IA directed edge (arc) is an ordered pair (u, v )(i.e., (u, v ) not same as (v , u))IA directed graph is a graph with directed edgesInstructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph Theory3/34v VIIPPv Vv VCS311H: Discrete MathematicsThe in-degree of a vertex v , written deg (v ), is the numberof edges going into vIdeg (a) IThe out-degree of a vertex v , written deg (v ), is the numberof edges leaving vIdeg (a) CS311H: Discrete MathematicsIntroduction to Graph Theory4/34SubgraphsLet G (V , E ) be a directed graph. Then:XXdeg (v ) deg (v ) E v VIInstructor: Işıl Dillig,Handshaking Theorem for Directed GraphsInstructor: Işıl Dillig,IIA graph G (V , E ) is a subgraph of another graphG 0 (V 0 , E 0 ) if V V 0 and E E 0IExample:IGraph G is a proper subgraph of G 0 if G 6 G 0 .deg (v ) deg (v ) Introduction to Graph Theory5/34Instructor: Işıl Dillig,1CS311H: Discrete MathematicsIntroduction to Graph Theory6/34
QuestionInduced SubgraphConsider a graph G with vertices {v1 , v2 , v3 , v4 } and edges(v1 , v3 ), (v1 , v4 ), (v2 , v3 ).IConsider a graph G (V , E ) and a set of vertices V 0 suchthat V 0 VIGraph G 0 is the induced subgraph of G with respect to V 0 if:1. G 0 contains exactly those vertices in V 0Which of the following are subgraphs of G?2. For all u, v V 0 , edge (u, v ) G 0 iff (u, v ) G1. Graph G1 with vertex v1 and edge (v1 , v3 )I2. Graph G2 with vertices {v1 , v3 } and no edgesSubgraph induced by vertices {C , D}:3. Graph G3 with vertices {v1 , v2 } and edge (v1 , v2 )Instructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph Theory7/34Instructor: Işıl Dillig,Complete GraphsIntroduction to Graph Theory8/34Bipartite graphsIICS311H: Discrete MathematicsA complete graph is a simple undirected graph in which everypair of vertices is connected by one edge.A simple undirected graph G (V , E ) is called bipartite if Vcan be partitioned into two disjoint sets V1 and V2 such thatevery edge in E connects a V1 vertex to a V2 vertexCADBIInstructor: Işıl Dillig,How many edges does a complete graph with n vertices have?CS311H: Discrete MathematicsIntroduction to Graph TheoryInstructor: Işıl Dillig,9/34Examples Bipartite and Non-Bi-partite GraphsICS311H: Discrete MathematicsIntroduction to Graph Theory10/34Questions about Bipartite GraphsIs this graph bipartite?ABIEIDoes there exist a complete graph that is also bipartite?IConsider a graph G with 5 nodes and 7 edges. Can G bebipartite?CWhat about this graph?AECDBInstructor: Işıl Dillig,CS311H: Discrete MathematicsFIntroduction to Graph Theory11/34Instructor: Işıl Dillig,2CS311H: Discrete MathematicsIntroduction to Graph Theory12/34
Graph ColoringQuestionIIIA coloring of a graph is the assignment of acolor to each vertex so that no two adjacentvertices are assigned the same color.Consider a graph G with vertices {v1 , v2 , v3 , v4 } and edges(v1 , v2 ), (v1 , v3 ), (v2 , v3 ), (v2 , v4 ).A graph is k -colorable if it is possible to color itusing k colors.Which of the following are valid colorings for G?Ie.g., graph on left is 3-colorableIIs it also 2-colorable?1. v1 red, v2 green, v3 blue2. v1 red, v2 green, v3 blue, v4 redThe chromatic number of a graph is the least number ofcolors needed to color it.I3. v1 red, v2 green, v3 red, v4 blueWhat is the chromatic number of this graph?Instructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph Theory13/34Instructor: Işıl Dillig,ExamplesCS311H: Discrete MathematicsIntroduction to Graph Theory14/34Applications of Graph ColoringIGraph coloring has lots of applications, particularly inscheduling.IExample: What’s the minimum number of time slots neededso that no student is enrolled in conflicting classes?What are the chromatic numbers for these graphs?ABABABCDCDCD311314312331429439Instructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph Theory15/34Instructor: Işıl Dillig,Bipartite Graphs and ColorabilityCS311H: Discrete MathematicsIntroduction to Graph TheoryIntroduction to Graph Theory16/34Complete graphs and ColorabilityProve that a graph G (V , E ) is bipartite if and only if it is2-colorable.Instructor: Işıl Dillig,CS311H: Discrete MathematicsProve that any complete graph Kn has chromatic number n.17/34Instructor: Işıl Dillig,3CS311H: Discrete MathematicsIntroduction to Graph Theory18/34
Degree and ColorabilityDegree and Colorability, cont.Theorem: Every simple graph G is always max degree(G) 1colorable.IRemove v and all its incident edges from G; call this G 0 .IProof is by induction on the number of vertices n.IBy the IH, G 0 is max degree(G 0 ) 1 colorable.ILet P (n) be the predicate “A simple graph G with n verticesis max-degree(G)-colorable”ILet C 0 be the coloring of G 0 : Suppose C 0 assigns colorsc1 , . . . , cp to v ’s n neighbors. Clearly, p n.IBase case: n 1. If graph has only one node, then it cannothave any edges. Hence, it is 1-colorable.INow, create coloring C for G:IInduction: Consider a graph G (V , E ) with k 1 vertices.INow consider arbitrary v V with neighnors v1 , . . . , vnInstructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph TheoryIC (v ) cp 1CS311H: Discrete MathematicsTwo possibilities: (i) cp 1 was used in C 0 , or (ii) new colorICase 1: Then, G is max degree(G 0 ) 1 colorable, andtherefore max degree(G) 1 colorable.ICase 2: Coloring C uses p 1 colors.IWe know p n, where n is num neighborsIWhat can we say about max degree(G)?IThus, p 1 max degree(G) 1Introduction to Graph Theory21/34Instructor: Işıl Dillig,Question About Star GraphsIA star graph Sn is a graph with onevertex u at the center and the only edgesare from u to each of v1 , . . . , vn 1 .IDraw S4 .IWhat is the chromatic number of Sn ?CS311H: Discrete MathematicsIntroduction to Graph Theory22/34abWhich of the following statements must be true about theresulting graph G?xTypical question: Is it possible to get fromsome node u to another node v ?IExample: Train network – if there is pathfrom u to v , possible to take train from u tov and vice versa.IIf it’s possible to get from u to v , we say uand v are connected and there is a pathbetween u and vyvd2. G is 2-colorable.3. max degree(G) max(k , m).cIntroduction to Graph TheorywIu1. The chromatic number of G is 3CS311H: Discrete Mathematics20/34Connectivity in GraphsSuppose we have two star graphs Sk and Sm . Now, pick a randomvertex from each graph and connect them with an edge.Instructor: Işıl Dillig,Introduction to Graph TheoryStar Graphs and ColorabilityICS311H: Discrete MathematicsC (v 0 ) C 0 (v 0 ) for any v 6 v 0Instructor: Işıl Dillig,19/34Degree and Colorability, cont.Instructor: Işıl Dillig,I23/34Instructor: Işıl Dillig,4CS311H: Discrete MathematicsIntroduction to Graph Theory24/34
PathsExampleIabIxwuyvA path between u and v is a sequence ofedges that starts at vertex u, moves alongadjacent edges, and ends in v .IExample: u, x , y, w is a path, but u, y, v andu, a, x are notConsider a graph with vertices {x , y, z , w } and edges(x , y), (x , w ), (x , z ), (y, z )IWhat are all the simple paths from z to w ?IWhat are all the simple paths from x to y?IHow many paths (can be non-simple) are there from x to y?ILength of a path is the number of edgestraversed, e.g., length of u, x , y, w is 3IA simple path is a path that does not repeatany edgesIu, x , y, w is a simple path but u, x , u is notdcInstructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph TheoryInstructor: Işıl Dillig,25/34ConnectednessCS311H: Discrete MathematicsIntroduction to Graph Theory26/34ExampleaIbxIA graph is connected if there is a pathbetween every pair of vertices in the graphIExample: This graph not connected; e.g., nopath from x to dIA connected component of a graph G is amaximal connected subgraph of GIwuyvdProve: Suppose graph G has exactly two vertices of odddegree, say u and v . Then G contains a path from u to v .IIIcInstructor: Işıl Dillig,CS311H: Discrete MathematicsIntroduction to Graph Theory27/34Instructor: Işıl Dillig,CircuitsIntroduction to Graph Theory28/34CyclesIabxyvA circuit is a path that begins and ends inthe same vertex.Iu, x , y, x , u and u, x , y, u are both circuitsIA simple circuit does not contain the sameedge more than onceIu, x , y, u is a simple circuit, but u, x , y, x , uis notwuabxcIIA cycle is a simple circuit with no repeatedvertices other than the first and last ones.IFor instance, u, x , a, b, x , y, u is a circuit butnot a cycleIHowever, u, x , y, u is a cyclewuyvddIInstructor: Işıl Dillig,CS311H: Discrete MathematicsLength of a circuit is the number of edges itcontains, e.g., length of u, x , y, u is 3cIn this class, we only consider circuits oflength 3 or moreCS311H: Discrete MathematicsIntroduction to Graph TheoryInstructor: Işıl Dillig,29/345CS311H: Discrete MathematicsIntroduction to Graph Theory30/34
ExampleProofIProve: If a graph has an odd length circuit, then it also has anodd length cycle.IHuh? Recall that not every circuit is a a cycle.IAccording to this theorem, if we can find an odd lengthcircuit, we can also find odd length cycle.IExample: d , c, a, b, c, d is an odd length circuit, but graphalso contains odd length cycleProve: If a graph has an odd length circuit, then it also has an oddlength cycle.IProof by strong induction on the length of the circuit.IBase case: Length of circuit 3.IOnly circuit of length 3 is a triangle, which is also a cycleaabbccInstructor: Işıl Dillig,CS311H: Discrete MathematicsdIntroduction to Graph Theory31/34Instructor: Işıl Dillig,Proof, cont.Introduction to Graph Theory32/34Proof, cont.Prove: If a graph has an odd length circuit, then it also has an oddlength cycle.ILet P (n) be the predicate “If a graph has odd length circuit oflength n, it also has an odd length cycle”IInductive step: Assume P (3), P (5), . . . , P (n) and show claimholds for P (n 2)INow, consider a circuit of length n 2. There are two cases:ICase 1: Circuit is already a cycle: done!Instructor: Işıl Dillig,CS311H: Discrete MathematicsCS311H: Discrete MathematicsIntroduction to Graph TheoryProve: If a graph has an odd length circuit, then it also has an oddlength cycle.IIIIInstructor: Işıl Dillig,33/346CS311H: Discrete MathematicsIntroduction to Graph Theory34/34
Instructor: Is l Dillig, CS311H: Discrete Mathematics Introduction to Graph Theory 11/34 Questions about Bipartite Graphs I Does there exist a complete graph that is also bipartite? I Consider a graph G with 5 nodes and 7 edges. Can G be bipartite? Instructor: Is l Dillig, CS311H: Discrete Mathemat
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
Stokes’ and Gauss’ Theorems Math 240 Stokes’ theorem Gauss’ theorem Calculating volume Stokes’ theorem Theorem (Green’s theorem) Let Dbe a closed, bounded region in R2 with boundary C @D. If F Mi Nj is a C1 vector eld on Dthen I C Mdx Ndy ZZ D @N @x @M @y dxdy: Notice that @N @x @M @y k r F: Theorem (Stokes’ theorem)
Nov 19, 2018 · Theorem 5-4 Angle Bisector Theorem Theorem If a point is on the bisector of an angle, then the point is equidistant from the sides of the angle. If. . . QS bisects PQR, 1 QP, and SR 1 QR P, S Then. SP SR You will prove Theorem 5-4 in Exercise 34. Theorem 5-5 Converse of the Angle Bisector Theorem Theorem
Triangle Sum Theorem Exterior Angle Theorem Third Angle Theorem Angle - Angle- Side Congruence Theorem non Hypotenuse- Leg Theorem the triangles are congruent Isosceles Triangle Theorem Perpendicular Bisector Theorem If a perpendicular line is
10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan
service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största
Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid
LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .
