Xem mẫu

6 Directed Graphs 6.1 Digraphs In some problems the relation between the objects is not symmetric. For these cases we need directed graphs, where the edges are oriented from one vertex to another. As an example consider a map of a small town. Can you make the streets one-way, and still be able to drive from one house to another (or exit the town)? Definitions DEFINITION. A digraph (or a directed graph) D = (V ; E ) consists of the vertices VD D D and (directed) edges (without loops ). We still write for , but note uv v vE V V (u; v ) D D D . For each pair define the inverse of as 1 . e = uv e = v u (= (v ; u))uv = v u e Note that does not imply 1 . e 2 E e 2 E D D DEFINITION. Let D be a digraph. Then A is its subdigraph, if and , V V E E A D A D induced subdigraph, , if and . E = E \ (X X ) V = X A = D [X ℄ A A D The underlying graph of a digraph DU (D ) is the graph on such that if , then V e 2 E D D the undirected edge with the same ends is in . U (D ) A digraph is an orientation of a graph , if and implies 1 . G e 2= EG = U (D ) e 2 E D D D In this case, D is said to be an oriented graph. DEFINITION. Let be a digraph. A walk ? of is a directed D U (D )W = e e : : : e : u ! v 1 2 k for all . Similarly, we define directed paths and directed cycles as e 2 E i 2 [1; k ℄ i D directed walks and closed directed walks without repetitions of vertices. The digraph is di-connected, if, for all , there exist directed paths ? and D u ! v u = v ? . The maximal induced di-connected subdigraphs are the di-components of . D v ! u 6.1 Digraphs 84 Note that a graph might be connected, although the digraph is not di-D G = U (D ) connected. DEFINITION. The indegree and the outdegree of a vertex are defined as follows I O d (v ) = jfe 2 E j e = xv gj; d (v ) = jfe 2 E j e = v xgj : D D D D We have the following handshaking lemma. (You offer and accept a handshake.) Lemma 6.1. Let be a digraph. Then D X X I O d (v ) = jE j = d (v ): D D D v 2D v 2D Directed paths The relationship between paths and directed paths is in gen-eral rather complicated. This digraph has a path of length five, but its directed paths are of length one. There is a nice connection between the lengths of directed paths and the chromatic number . (D ) = (U (D )) Theorem 6.1 (ROY (1967),GALLAI (1968)). A digraph D has a directed path of length . (D ) 1 Proof. Let A E be a minimal set of edges such that the subdigraph D A contains no D directed cycles. Let be the length of the longest directed path in . k D A For each vertex v 2 D , assign a colour (v ) = i , if a longest directed path from v has length i 1 in D A . Here 1 i k + 1. First we observe that if ( ) is any directed path ? in , then r 1 P = e e : : : e D Au ! v 1 2 r . Indeed, if , then there exists a directed path ? of length , Q : v ! w (v ) = i i 1 (u) = (v ) is a directed path, since does not contain directed cycles. Since ? , D A P Q : u ! w P Q . In particular, if , then . e = uv 2 E (u) = (v ) (u) = i = (v ) D A Consider then an edge e = v u 2 A . By the minimality of A, (D A ) + e contains a directed cycle ? , where the part ? is a directed path in , and hence D A uC : u ! v ! u ! v . This shows that is a proper colouring of , and therefore , U (D ) (D ) k + 1 (u) = (v ) that is, k (D ) 1 . ut The bound is the best possible in the following sense: (D ) 1 Theorem 6.2. Every graph has an orientation , where the longest directed paths have D G lengths (G) 1 . 6.1 Digraphs 85 Proof. Let and let be a proper -colouring of . As usual the set of colours is G kk = (G) . We orient each edge by setting , if . Clearly, the so uv 2 E (u) < (v )[1; k ℄ uv 2 E G D obtained orientation D has no directed paths of length k 1 . tu DEFINITION. An orientation of an undirected graph is acyclic, if it has no directed D G cycles. Let be the number of acyclic orientations of . G a (G) The next result is charming, since ( 1) measures the number of proper colourings of G using colours! 1G Theorem 6.3 (STANLEY (1973)). Let be a graph of order . Then the number of the acyclic n G orientations of G is n a (G) = ( 1) ( 1) ; G where is the chromatic polynomial of . G G Proof. The proof is by induction on . First, if is discrete, then n , and " (k ) = k G a (G) = G G 1 = ( 1) n ( 1) n = ( 1) n ( 1) as required. G is a polynomial that satisfies the recurrence . To (k ) (k ) = (k ) (k ) G G G e Ge prove the claim, we show that a (G) satisfies the same recurrence. Indeed, if a (G) = a (G e) + a (G e) (6.1) then, by the induction hypothesis, n n 1 n a (G) = ( 1) ( 1) + ( 1) ( 1) = ( 1) ( 1) : G e Ge G For (6.1), we observe that every acyclic orientation of gives an acyclic orientation of . G G e On the other hand, if D is an acyclic orientation of G e for e = uv , it extends to an acyclic orientation of G by putting e : u ! v or e : v ! u. Indeed, if D has no directed path 1 2 ? , we choose , and if has no directed path ? , we choose . Note that since D eu ! v v ! u e 2 1 is acyclic, it cannot have both ways ? and ? . D u ! v v ! u We conclude that , where is the number of acyclic orientations of D ba (G) = a (G e) + b that extend in both ways and . The acyclic orientations that extend in both ways D ee G e 1 2 are exactly those that contain neither u ! v nor v ! u as a directed path. (6.2) Each acyclic orientation of corresponds in a natural way to an acyclic orientation DG e of that satisfies (6.2). Therefore , and the proof is completed. G e b = a (G e) tu One-way traffic Every graph can be oriented, but the result may not be di-connected. In the one-way traffic problem the resulting orientation should be di-connected, for otherwise someone is not able to drive home. ROBBINS’ theorem solves this problem. 6.1 Digraphs 86 DEFINITION. A graph is di-orientable, if there is a di-connected oriented graph such G D that G = U (D ) . Theorem 6.4 (ROBBINS (1939)). A connected graph G is di-orientable if and only if G has no bridges. Proof. If has a bridge , then any orientation of has at least two di-components (both G Ge sides of the bridge). Suppose then that has no bridges. Hence has a cycle , and a cycle is always di-C GG orientable. Let then be maximal such that it has a di-orientation . If , then D H G H = G H we are done. Otherwise, there exists an edge such that e = v u 2 E G but (because is connected). The edge is e G v 2= Hu 2 H not a bridge and thus there exists a cycle u v e 0 P P Q ? ? 0 C = eP Q : v ! u ! w ! v w in , where is the last vertex inside . w H G In the di-orientation of there is a directed path 0 ? . Now,we orient D e : v ! P : u ! w H H and the edges of in the direction ? to obtain a directed cycle 0 ?Q eP Q : v ! u ! Q : w ! v u w ! v . In conclusion, has a di-orientation, which contradicts the maximality G[V [ V ℄ H C assumption on H . This proves the claim. tu Example 6.1. Let be a digraph. A directed Euler tour of is a directed closed walk that D ... - tailieumienphi.vn
nguon tai.lieu . vn