6. Fluxos
- Este capítulo estuda um conceito de fluxo mais restritivo que aquele encontrado no estudo de Fluxo em Redes. O capítulo termina com as fundamentais conjecturas de Tutte sobre k-fluxos.
6.1 Circulações
- Neste capítulo, H denota um grupo comutativo. Por exemplo, H pode ser Z (= conjunto dos inteiros). Outro exemplo: H pode ser Z4 (= inteiros mod 4).
- Para qualquer grafo G = (V, E), quaisquer partes X e Y de V, e qualquer função f de V × V em H, a expressão f (X, Y) denotará a soma de todos os f (x, y) tais que a aresta xy está em E(X,Y).
-
Uma H-circulação (= circulation)
em um grafo G = (V, E) é uma função f
de V × V em H tal que
- f (x, y) = 0 se xy não é aresta,
- f (x, y) = −f (y, x) para toda aresta xy, e
- f (v, V) = 0 para todo vértice v.
Se H = Z, dizemos também que f é uma circulação inteira.
- Circulações são fechadas sob adição: Se f e g são H-circulações então f + g também é uma H-circulação.
- Proposição 6.1.1: Se f é uma circulação então f (X, V−X) = 0 para toda parte X de V.
- Corolário 6.1.2: Se f é uma circulação e xy é uma ponte então f (x, y) = f (y, x) = 0.
- Exercícios:
-
Uma orientação de um grafo G = (V, E) é um subconjunto F
de V × V tal que
(1) para todo par ordenado (x, y) em F
o par não ordenado xy está em E e
(2) para todo xy em E
um e apenas um dos pares (x, y)
e (y, x) está em F.
Mostre que a definição de circulação equivale à seguinte: Uma Z-circulação em um grafo G = (V, E) é uma orientação F juntamente com uma função c que associa um inteiro não-negativo a cada elemento de F de modo que c(V, v) = c(v, V) para todo vértice v. (A expressão c(X, Y) denota a soma de todos os c(x, y) com (x, y) em F ∩ (X × Y). Portanto, a igualdade c(V, v) = c(v, V) pode ser verbalizada assim: a soma dos c que
entram
em v é igual à soma dos c quesaem
de v.)
-
Uma orientação de um grafo G = (V, E) é um subconjunto F
de V × V tal que
(1) para todo par ordenado (x, y) em F
o par não ordenado xy está em E e
(2) para todo xy em E
um e apenas um dos pares (x, y)
e (y, x) está em F.
6.3 k-fluxos e Zk-fluxos
- Um H-fluxo em um grafo é uma H-circulação nunca-nula (= nowhere zero), ou seja, uma H-circulação f tal que f (x, y) ≠ 0 para toda aresta xy. Fluxos não são fechadas sob adição.
-
Um k-fluxo
é um Z-fluxo com valores em {1, … , k−1}.
Em outras palavras, um k-fluxo é uma Z-circulação
tal que
0 <
| f (x, y)|
< k
para toda aresta xy.
Pode-se dizer, informalmente, que um k-fluxo e um Zk-fluxo têm o mesmo conjunto de valores mas o valor da expressão f (v, V) é calculado de maneira diferente nos dois casos: em aritmética usual no primeiro caso e
mod k
no segundo. - Teorema 6.3.3 (Tutte): Um grafo tem um k-fluxo se e só se tem um Zk-fluxo. A afirmação também vale para multigrafos.
- Proposição 6.3.2: Para quaisquer grupos comutativos finitos H e H' de mesma ordem, um multigrafo tem um H-fluxo se e só se tem um H'-fluxo.
- Exercícios:
- Faça uma ilustração do Teorema 6.3.3: exiba um Z4-fluxo interessante em um grafo e transforme-o em um 4-fluxo.
- [6.4] Seja f uma H-circulação em G e g um homomorfismo de H em um grupo H'. Mostre que g composto com f é uma H'-circulação em G. É verdade que g composto com f é um H'-fluxo se f é um H-fluxo?
6.4 k-fluxos para valores pequenos de k
- Proposição 6.4.1 (equivale ao teorema de Euler): G tem um 2-fluxo se e só se G é par (= todos os vértices têm grau par).
- Corolário: Todo Kn com n ímpar tem um 2-fluxo (mas não tem um 1-fluxo).
- Proposição 6.4.2: Um grafo cúbico (= todo vértice tem grau 3) tem um 3-fluxo se e só se é bipartido.
- Proposição 6.4.3: Todo Kn com n par e maior que 4 tem um 3-fluxo (mas não tem um 2-fluxo).
- Proposição 6.4.4: Todo grafo 4-aresta-conexo tem um 4-fluxo.
-
Proposição 6.4.5.i:
G tem um 4-fluxo se e só se G é união
de dois subgrafos pares.
Proposição 6.4.5.ii: Um grafo cúbico tem um 3-fluxo se e só se chi'(G) = 3.
- Em geral, é mais fácil obter um k-fluxo quando k é grande. Denotamos por phi(G) o menor k para o qual o grafo (ou multigrafo) G admite um k-fluxo.
- Exercícios:
- [6.8] Seja H um grupo comutativo finito, G um grafo, e T uma árvore geradora de G. Mostre que toda função das orientações de E(G) − E(T) em H que satisfaça a condição b da definiçao de circulação pode ser estendida de maneira única a uma H-circulação em G.
- [6.9] Mostre que todo multigrafo sem pontes tem um k-fluxo para algum k. Não use o Teorema 6.6.1.
- [6.10] Suponha que G tem uma coleção de m árvores geradoras tal que toda aresta de G pertence a menos que m das árvores. Mostre que G tem um 2m-fluxo. Não use o Teorema 6.6.1.
- [6.11] Seja G um grafo conexo sem pontes e k o número ‖G‖−|G|+2. Mostre que G tem um k-fluxo. (Sugestão: Use uma árvore de busca em profundidade Não use o Teorema 6.6.1.
- [6.12] Mostre que todo grafo hamiltoniano tem um 4-fluxo.
- [6.6] Mostre que phi(G/e) ≤ phi(G) para toda aresta e de G, sendo G/e o resultado da contração de e. É possível deduzir daí que, para todo k, a classe dos multigrafos que admitem um k-fluxo é fechada sob máinors?
- [6.13] Uma cobertura dupla por ciclos (= cycle double cover = CDC) é uma coleção de ciclos que cobre cada aresta do grafo exatamente duas vezes. Conjectura CDC: todo multigrafo sem pontes tem uma CDC. Prove a restrição da conjectura a grafos dotados de 4-fluxo. (Veja observação no capítulo Planaridade.)
- Uma d-cobertura por ciclos é uma coleção de ciclos que cobre cada aresta pelo menos uma vez e no máximo d vezes. Qual a relação entre k-fluxos e d-coberturas por ciclos? Se G tem um k-fluxo, qual o menor d tal que G tem uma d-cobertura? Se G uma d-cobertura, qual o menor k tal que G tem um k-fluxo?
6.5 Dualidade entre fluxo e coloracão
- Todo k-fluxo em um multigrafo plano define uma k-coloração dos vértices de seu dual. E vice-versa.
- Teorema 6.5.3 (Tutte): Para todo par dual (G,G*) de grafos planos, chi(G) = phi(G*).
- Exercícios:
- Defina coloração das faces de um grafo plano da maneira óbvia: duas faces com aresta em comum devem ter cores distintas. Mostre que um grafo tem um k-fluxo se e só se admite uma coloração das faces com k cores.
- Faça uma ilustração interessante do Teorema 6.5.3.
6.6 Conjecturas de Tutte
- Conjectura phi ≤ 5 (Tutte): Todo multigrafo sem pontes admite um 5-fluxo.
- Conjectura phi ≤ 4 (Tutte): Todo multigrafo sem pontes que não inclua o grafo de Petersen como máinor admite um 4-fluxo.
- Conjectura phi ≤ 3 (Tutte): Todo multigrafo sem cortes com 1 ou 3 arestas admite um 3-fluxo.
- Teorema 6.6.1 (phi ≤ 6) (Seymour): Todo grafo sem pontes admite um 6-fluxo.
- Exercícios:
- Mostre que o grafo de Petersen tem um 5-fluxo mas não admite 4-fluxo.
- Faça uma ilustração interessante do Teorema 6.6.1.