Pré-visualização50 páginas

: ; \u2018¡ 1; fn( !e)¡ \u2020 for !e = \u2c6ei, i = 0; : : : ; \u2018¡ 1; fn( !e) for e =2 W . Intuitively, fn+1 is obtained from fn by sending additional °ow of value \u2020 along W from s to t (Fig. 6.2.2). 0 1 1 2 2 1 1 3 s t 3 W Fig. 6.2.2. An \u2018augmenting path\u2019 W with increment \u2020 = 2, for constant °ow fn = 0 and capacities c = 3 128 6. Flows Clearly, fn+1 is again an integral °ow in N . Let us compute its total value jfn+1j = fn+1(s; V ). Since W contains the vertex s only once, !e0 is the only triple (e; x; y) with x = s and y 2 V whose f -value was changed. This value, and hence that of fn+1(s; V ) was raised. Therefore jfn+1j > jfnj as desired. If t =2 Sn, then (Sn; Sn) is a cut in N . By (F3) for fn, and the deflnition of Sn, we have fn( !e) = c(!e) for all !e 2 ! E(Sn; Sn), so jfnj = fn(Sn; Sn) = c(Sn; Sn) as desired. \u2044 Since the °ow constructed in the proof of Theorem 6.2.2 is integral, we have also proved the following: Corollary 6.2.3. In every network (with integral capacity function) there exists an integral °ow of maximum total value. \u2044 6.3 Group-valued °ows Let G = (V;E) be a multigraph and H an abelian group. If f and g are two H-circulations then, clearly, (f + g): !e 7! f(!e) + g(!e) andf + g ¡f : !e 7! ¡f(!e) are again H-circulations. The H-circulations on G thus¡f form a group in a natural way. A function f : ! E!H is nowhere zero if f(!e) 6= 0 for all !e 2 !E. Annowherezero H-circulation that is nowhere zero is called an H-°ow .4 Note that the set of H-°ows on G is not closed under addition: if two H-°ows addH-°ow up to zero on some edge !e, then their sum is no longer an H-°ow. By Corollary 6.1.2, a graph with an H-°ow cannot have a bridge. For flnite groupsH, the number ofH-°ows onG|and, in particular, their existence|surprisingly depends only on the order of H, not on H itself: Theorem 6.3.1. (Tutte 1954) For every multigraph G there exists a polynomial P such that, for any flnite abelian group H, the number of H-°ows on G is P ¡jHj ¡ 1¢. 4 This terminology seems simplest for our purposes but is not standard; see the notes. 6.3 Group-valued °ows 129 Proof . Let G =: (V;E); we use induction on m := jEj. Let us assume (6.1.1) flrst that all the edges of G are loops. Then, given any flnite abelian group H, every map ! E!H r f 0 g is an H-°ow on G. Since j !Ej = jEj when all edges are loops, there are ¡jHj ¡ 1¢m such maps, and P := xm is the polynomial sought. Now assume there is an edge e0 = xy 2 E that is not a loop; let e0 = xy !e0 := (e0; x; y) and E0 := Er f e0 g. We consider the multigraphs E0 G1 := G¡ e0 and G2 := G=e0 : By the induction hypothesis, there are polynomials Pi for i = 1; 2 such P1; P2 that, for any flnite abelian group H and k := jHj ¡ 1, the number of k H-°ows on Gi is Pi(k). We shall prove that the number of H-°ows on G equals P2(k)¡P1(k); then P := P2¡P1 is the desired polynomial. Let H be given, and denote the set of all H-°ows on G by F . We H are trying to show that F jF j = P2(k)¡P1(k) : (1) The H-°ows on G1 are precisely the restrictions to ! E0 of those H-circu- lations on G that are zero on e0 but nowhere else. Let us denote the set of these circulations on G by F1; then F1 P1(k) = jF1j : Our aim is to show that, likewise, the H-°ows on G2 correspond bijec- tively to those H-circulations on G that are nowhere zero except possibly on e0. The set F2 of those circulations on G then satisfles F2 P2(k) = jF2j ; and F2 is the disjoint union of F1 and F . This will prove (1), and hence the theorem. e0 v0 E0(x; y) G2 x y G Fig. 6.3.1. Contracting the edge e0 In G2, let v0 := ve0 be the vertex contracted from e0 (Fig. 6.3.1; v0 see Chapter 1.10). We are looking for a bijection f 7! g between F2 130 6. Flows and the set of H-°ows on G2. Given f , let g be the restriction of f to! E0r ! E0(y; x). (As the x{y edges e 2 E0 become loops in G2, they have on- ly the one direction (e; v0; v0) there; as its g-value, we choose f(e; x; y).) Then g is indeed an H-°ow on G2; note that (F2) holds at v0 by Propo- sition 6.1.1 for G, with X := fx; y g. It remains to show that the map f 7! g is a bijection. If we are given an H-°ow g on G2 and try to flnd an f 2 F2 with f 7! g, then f(!e) is already determined as f(!e) = g(!e) for all !e 2 ! E0r ! E0(y; x); by (F1), we further have f(!e) = ¡f(\u2c6e) for all !e 2 !E0(y; x). Thus our map f 7! g is bijective if and only if for given g there is always a unique way to deflne the remaining values of f(!e0) and f( \u2c6e0) so that f satisfles (F1) in e0 and (F2) in x and y. This is indeed the case. Let V 0 := V r fx; y g. As g satisfles (F2),V 0 the f -values flxed already are such that f(x; V 0) + f(y; V 0) = g(v0; V 0) = 0 : (2) With h := X ~e 2 ! E0(x;y) f(!e) \u2021 = X e 2E0(x;y) g(e; v0; v0) · ; (F2) for f requires 0 = f(x; V ) = f(!e0) +h+ f(x; V 0) and 0 = f(y; V ) = f(\u2c6e0)¡h+ f(y; V 0) ; so we have to set f(!e0) := ¡f(x; V 0)¡h and f(\u2c6e0) := ¡f(y; V 0) +h : Then f(!e0) + f( \u2c6e0) = 0 by (2), so f also satisfles (F1) in e0. \u2044 The polynomial P of Theorem 6.3.1 is known as the °ow polynomial°owpolynomial of G. Corollary 6.3.2. If H and H 0 are two flnite abelian groups of equal[ 6.4.5 ] order, then G has an H-°ow if and only if G has an H 0-°ow. \u2044 Corollary 6.3.2 has fundamental implications for the theory of al- gebraic °ows: it indicates that crucial di\u2013culties in existence proofs of H-°ows are unlikely to be of a group-theoretic nature. On the other hand, being able to choose a convenient group can be quite helpful; we shall see a pretty example for this in Proposition 6.4.5. 6.3 Group-valued °ows 131 Let k > 1 be an integer and G = (V;E) a multigraph. A Z-°ow f k on G such that 0 < jf(!e)j < k for all !e 2 !E is called a k-°ow . Clearly, k-°ow any k-°ow is also an \u2018-°ow for all \u2018 > k. Thus, we may ask which is the least integer k such that G admits a k-°ow|assuming that such a k exists. We call this least k the °ow number of G and denote it by \u2019(G); °ownumber if G has no k-°ow for any k, we put \u2019(G) := 1. \u2019(G) The task of determining °ow numbers quickly leads to some of the deepest open problems in graph theory. We shall consider these later in the chapter. First, however, let us see how k-°ows are related to the more general concept of H-°ows. There is an intimate connection between k-°ows and Zk-°ows. Let ¾k denote the natural homomorphism i 7! i from Z to Zk. By compo- ¾k sition with ¾k, every k-°ow deflnes a Zk-°ow. As the following theorem shows, the converse holds too: from every Zk-°ow on G we can construct a k-°ow on G. In view of Corollary 6.3.2, this means that the general question about the existence of H-°ows for arbitrary groups H reduces to the corresponding question for k-°ows. Theorem 6.3.3. (Tutte 1950) A multigraph admits a k-°ow if and only if it admits a Zk-°ow. [ 6.4.1 ] [ 6.4.2 ] [ 6.4.3 ] [ 6.4.5 ] Proof . Let g be a Zk-°ow on a multigraph G = (V;E); we construct a k-°ow f on G. We may assume without loss of generality that G has g no loops. Let F be the set of all functions f : ! E!Z that satisfy (F1), F jf(!e)j < k for all !e 2 !E, and ¾k \u2013 f = g; note that, like g, any f 2 F is nowhere zero. Let us show flrst that F 6= ;. Since we can express every value g(!e) 2 Zk as i with jij < k and then put f(!e) := i, there is clearly a map f : ! E!Z such that jf(!e)j < k for all !e 2 !E and ¾k \u2013f = g. For each edge e 2 E, let us choose one of its two directions and denote this by !e. We may then deflne f 0: ! E!Z by setting f 0(!e) := f(!e) and f 0(\u2c6e) := ¡f(!e) for every e 2 E. Then f 0 is a function satisfying (F1) and with values in the desired range; it remains to show that ¾k \u2013 f 0 and g agree not only on the chosen directions !e but also