Graph Theory
322 pág.

Graph Theory


DisciplinaTeoria dos Grafos330 materiais1.545 seguidores
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