Paul Van Dooren Université catholique de Louvain Louvain ...

1 Graph TheoryandApplications-6pt-6ptGraph Theory andApplications-6pt-6pt1 / 112 Graph Theory and ApplicationsPaul Van DoorenUniversit catholique de LouvainLouvain-la-Neuve, BelgiumDublin, August 2009 Inspired from the course notes of V. Blondel and L. Wolsey (UCL)Appetizer-6pt-6ptAppetizer-6pt-6pt2 / 112 Graph theory started with Euler who was asked to find anice path across the seven K ningsberg bridgesThe ( eulerian ) pathshould cross overeach of the sevenbridges exactly onceAppetizer-6pt-6ptAppetizer-6pt-6pt3 / 112 Another early bird was Sir William Rowan Hamilton (1805-1865)In 1859 he developed a toy based on finding a path visiting allcities in a graph exactly once and sold it to a toy maker in never was a big / 112 But now graph theory is used for finding communities in networkswhere we want to detect hierarchies of substructuresAppetizer-6pt-6ptAppetizer- 6pt-6pt5 / 112and their sizes can become quite big ..Appetizer-6pt-6ptAppetizer-6pt-6pt6 / 112It is also used for ranking (ordering) hyperlinksAppetizer-6pt-6ptAppetizer-6pt -6pt7 / 112or by your GPS to find the shortest path home.

2 Appetizer-6pt-6ptAppetizer-6pt-6pt8 / 112or by your GPS to find the shortest path home ..Contents-6pt-6ptContents-6pt-6pt9 / 112 What we will cover in this courseIBasic theory about graphsIConnectivityIPathsITreesINetworks and flowsIEulerian and Hamiltonian graphsIColoring problemsIComplexity issuesIA number of applications (in large graphs)ILarge scale problems in graphsISimilarity of nodes in large graphsITelephony problems and graphsIRanking in large graphsIClustering of large graphsWhat aregraphs-6pt-6ptWhat are graphs-6pt-6pt10 / 112A graphG= (V,E)is a pair of vertices (or nodes)Vanda set of edgesE, assumed finite |V|=nand|E|= (G) ={v1,v2,..,v5}andE(G) ={e1,e2,..,e6}.An edgeek= (vi,vj)is incident with the simple graph has no self-loops or multiple edges like belowWhat aregraphs-6pt-6ptWhat are graphs-6pt-6pt11 / 112 Some propertiesThe degreed(v)of a vertexVis its number of incident edgesA self-loop counts for 2 in the degree isolated vertex has degree sum of the degrees of a graphG= (V,E)equals 2|E|=2m(trivial)CorollaryThe number of vertices of odd degree is even (trivial)What aregraphs-6pt-6ptWhat are graphs-6pt-6pt12 / 112 Special graphsA complete graphKnis a simple graph with allB(n,2) :=n(n 1)2possible edges, like the matrices below forn=2,3,4, graph is a simple graph with vertices of equal degreekCorollaryThe complete graphKnis(n 1)-regularWhat aregraphs-6pt-6ptWhat are graphs-6pt-6pt13 / 112A bipartite graph is one whereV=V1 V2such that there are noedges betweenV1andV2(the black and white nodes below)A complete bipartite graph is one where all edges betweenV1andV2are present ( |E|=|V1|.)

3 |V2|). It is noted asKn1, is complete bipartite graph regular ?What aregraphs-6pt-6ptWhat are graphs-6pt-6pt14 / 112 When isGbipartite ?Which graph is bipartite ?It suffices to find 2 colors that separate the edges as belowWhat aregraphs-6pt-6ptWhat are graphs-6pt-6pt15 / 112 When isGbipartite ?Which graph is bipartite ?It suffices to find 2 colors that separate the edges as belowThe second example is not bipartite because it has a triangle(to be continued)Cycles-6pt-6ptCycles-6pt-6pt16 / 112 Walking in a graphA walk of lengthkfrom nodev0to nodevkis a non-empty graphP= (V,E)of the formV={v0,v1,..,vk}E={(v0,v1),..,(vk 1,vk)}where edgejconnects nodesj 1 andj( |V|=|E|+1).A trail is a walk with all different path is a walk with all different nodes (and hence edges).A walk or trail is closed whenv0= cycle is a walk with different nodes except forv0= / 112 Try to prove the following wo (useful) lemmasPropositionA walk fromutov6=ucontains a path fromutovHint : eliminate subcyclesPropositionA closed walk of odd length contains a cycle of oddlengthHint : decompose recursively into distinct subgraphs and useinductionQuestionIs this only for simple graphs ?

4 Cycles-6pt-6ptCycles-6pt-6pt18 / 112 Directed graphsIn a directed graph or digraph, each edge has a (vs,vt),vsis the source node andvtis the terminal nodevhas an in-degreedin(v)and an out-degreedout(v).A graph is balanced ifdin(v) =dout(v)for all / 112 Topological orderLet us now try to order the nodes in a a bijectionford:V {1,2,..,n}, thenford( )is atopological order for the graphG= (V,E)iffford(i)<ford(j), (i,j) EThis is apparently possible for the above is easy to see that such a graph should have no is this also sufficient ?Cycles-6pt-6ptCycles-6pt-6pt20 / 112An acyclic graph is a graph without acyclic graph contains at least one node with zero in-degreeProofBy (v)>0 for all nodes, then each nodeihas apredecessorp(i)such that(vp(i),vi) from an arbitraryv0to form a list of predecessors as belowSince|V|is bounded, one must eventually return to a node thatwas already visited; hence there is a / 112 Let us use this to find a topological orderAlgorithmFindTopOrd(G)t:=0;G0:=G;wh ile v Gt:din(v) =0doGt+1:=Gt/{v};order(v) :=t+1;t:=t+1;end whileift=nthenGis acyclic;else ift<nthenGhas a cycle;end ifend ifLet us verify this algorithm on the above / 112 The only node of in-degree 0 isv4.

5 So fort=1 we haveAfter removingv4there are two nodes of in-degree 0, we pickv3then we have fort=2 Further reductions yield the final order{v4,v3,v1,v2,v5,v6}.What is the complexity of this algorithm ?Isomorphism-6pt-6ptIsomorphism-6pt-6pt2 3 / 112 Isomorphic graphsTwo graphsG1andG2are isomorphic iff there is a bijectionbetween their respective nodes which make each edge ofG1correspond to exactly one edge ofG2, and vice must find a label numbering that makes the graphs identicalThis problem is still believed to be NP hardIsomorphism-6pt-6ptIsomorphism-6pt-6 pt24 / 112 Counting graphsHow many different simple graphs are there withnnodes ?A graph withnnodes can haveB(n,2) :=n(n 1)/2 differentedges and each of them can be present or there can be at most 2n(n 1)/2graphs only 4 of the graphs are different(omitting the isomorphic ones)Withn=4 one finds eventually 11different graphs after collapsing theisomorphic onesIsomorphism-6pt-6ptIsomorphism-6pt-6 pt25 / 112 Let there beTnnon-isomorphic (simple) graphs :=2n(n 1)/2n!

6 Tn 2n(n 1)/2 ExerciseExplain the lower boundTaking logarithms and usingn!<nnyields the boundsB(n,2) nlogn logTn B(n,2)which gives an idea of the growth ofTnn2 345678Tn2 4 11 34 156 1044 12346dLne2 239464176658 Isomorphism-6pt-6ptIsomorphism-6pt-6pt26 / 112 Bipartite revisitedLet us look again at bipartite graphsPropositionA graph is bipartite iff it has no cycles of odd lengthNecessityTrivial : color the nodes of the cycle black and Vand letf(v)be the length of a shortestpath fromutov( if there is no such path)A={v V|f(v) =odd}B={v V|f(v) =even}ThenAandBform a partition of the nodes ofVconnected then needs to show that therecan be no links between any twonodes ofAor any two nodes this would be the case, one couldconstruct a cycle of odd on each Representing graphs-6pt-6pt27 / 112 Representing graphsA graphG= (V,E)is often represented by its adjacency is ann nmatrixAwithA(i,j) =1 iff(i,j) E. For the graphsthe adjacency matrices areA1= 0 0 0 1 00 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0 A2= 0 0 1 01 0 0 00 1 0 00 1 1 0 Representinggraphs-6pt-6pt Representing graphs-6pt-6pt28 / 112A graph can also be represented by itsn mincidence an undirected graphT(i,k) =T(j,k) =1 iffek= (vi,vj).

7 For a directed graphT(i,k) = 1;T(j,k) =1 iffek= (vi,vj).For the graphsthe incidence matrices areT1= 1 0 0 0 0 00 1 1 0 0 00 0 1 1 1 01 0 0 0 1 10 1 0 1 0 1 T2= 100010101 1101 100 1 100 Representinggraphs-6pt-6pt Representing graphs-6pt-6pt29 / 112 One can also use a sparse matrix representation is in fact nothing but a list of edges, organized by that the size of the representation of a graph is thus linearin the number of edges in the graph ( inm=|E|).To be more precise, one should count the number of bits neededto represent all entries :L= (n+m)lognsince one needs lognbits to represent the vertex Representing graphs-6pt-6pt30 / 112 Counting degreesLet1be the vector of all ones, thendin=AT1anddout=A1are the vectors of in-degrees and out-degrees of the nodes ofAanddout=din=dfor undirected should we then take self-loops into account ?In an adjacency matrix of an undirected graphA(i,i) =2In an adjacency matrix of a directed graphA(i,i) =1 For an undirected graph, we haved= a directed graph one can defineTtandTsas the matricescontaining the terminal and source nodes :T=Tt TswithTt:= 0 0 0 0 10 1 0 1 01 0 1 0 00 0 0 0 0 ,Ts:= 1 0 0 0 00 0 0 0 10 0 0 1 00 1 1 0 0 Then also we havedin=Tt1anddout= Representing graphs-6pt-6pt31 / 112 Powers ofAProposition(Ak)ijis the number of walks of lengthkfromitojProofTrivial fork=1.

8 By induction for element(i,j)ofAk+1=Ak Ais the sum of the walks of lengthkto nodes that are linked to nodejvia the adjacency verifies this in the following little exampleA= 0 1 00 0 11 1 0 ,A2= 0 0 11 1 00 1 1 CorollaryIn a simple undirected graph one has the identitiestr(A) =0,tr(A2)/2=|E|andtr(A3)/6 equals the number of triangles / 112 Connected componentsIn a directed graphG= (V,E),uandvare strongly connectedif there exists a walk fromutovand is an equivalence relation and hence leads to equivalenceclasses, which are called th connected components of the graph reduced to its connected components is acyclic (why ?)This shows up in many applications, in the dictionary connected components are the groups of words that use eachother in their definition (see later).Connectivity-6pt-6ptConnectivity- 6pt-6pt33 / 112 After the reduction one has an acyclic graph, which can beordered do you obtain then ? Class orderingsAn initial class hasdin(c) =0.

9 A final class hasdout(c) = other ones are / 112 Verify (strong) connectivity of a graph based on its adjacency listIdea : start from nodes, explore the graph, mark what you visitAlgorithmGenericSearch(G,s)mark(s); L:={s}whileL6= dochooseu L;if (u,v)such thatvis unmarkedthenmark(v);L:=L {v};elseL:=L\{u};end ifend whileConnectivity-6pt-6ptConnectivity-6p t-6pt35 / 112 Below we marked the chosen nodes and the discovered nodesLmark{2}2{2,1}1{2,1,5}5{2,1,5,6}6{1 ,5,6}{1,5,6,4}4{5,6,4}{5,4}{5,4,3}3{5,3} {5,3,7}7{5,3}{3}{3,8}8{3}{}This algorithm has 2nsteps : each node is added once andremoved once. Its complexity is therefore linear / 112 Because of the choices, this algorithm allows for different versionsLet us use a LIFO list forL(Last In First Out) and choose foruthelast element added toL. This is a depth first search (DFS).AlgorithmDeptFirstSearch(G,s)mark( s);L:={s};whileL6= dou:=last(L)if (u,v)such thatvis unmarkedthenchoose(u,v)withvof smallest index;mark(v);L:=L {v};elseL:=L\{u}end ifend whileConnectivity-6pt-6ptConnectivity-6p t-6pt37 / 112 Below we marked the chosen nodes and the discovered nodesLmark{2}2{2,1}1{2,1,4}4{2,1,4,3}3{2 ,1,4,3,7}7{2,1,4,3}{2,1,4,3,8}8{2,1,4,3} {2,1,4}{2,1,4,6}6{2,1,4,6,5}5{2,1,4,6}{2 ,1,4}{2,1}{2}{}This algorithm builds longer paths than the generic one (depthfirst).

10 Connectivity-6pt-6ptConnectivity-6pt-6pt 38 / 112We now use a FIFO list forL(First In First Out) and choose foruthe first element added toL. This is a breadth first search (BFS).AlgorithmBreadthFirstSearch(G,s)ma rk(s);L:={s};whileL6= dou:=first(L)if (u,v)such thatvis unmarkedthenchoose(u,v)withvof smallest index;mark(v);L:=L {v};elseL:=L\{u}end ifend whileConnectivity-6pt-6ptConnectivity-6p t-6pt39 / 112 Below we marked the chosen nodes and the discovered nodesLmark{2}2{2,1}1{2,1,5}5{1,5}{1,5,4} 4{1,5,4,6}6{5,4,6}{4,6}{4,6,3}3{6,3}{3}{ 3,7}{3,7,8}8{7,8}{8}{}This algorithm builds a wider tree (breadth first).Connectivity-6pt-6ptConnectivity- 6pt-6pt40 / 112 Testing connectivityThe exploration algorithm finds the set of all nodes that can bereached by a path from a given nodeu the graph is undirected, each node in that set can follow a pathback tou. They thus form the connected componentC(u) find all connected components, repeat this exploration on anode ofV\C(u), / 112 Testing strong connectivityPropositionLetG= (V,E)be a digraph and letu v Vthere exists a path fromutovand a path fromvtou,thenGis strongly exploration algorithm finds the set of all nodes that can bereached by a path from a given nodeu can one find the nodes from whichucan be reached ?