Os números de capítulos, seções, teoremas e exercícios se referem ao livro de Diestel, 2a edição.

11. Máinors, árvores e anticadeias infinitas

O foco deste capítulo é o Graph Minor Theorem de Robertson e Seymour. O teorema afirma que todo conjunto infinito de grafos, algum grafo é máinor de outro. Uma consequência importante: todo conjunto de grafos fechado sob isomorfismo e sob máinors tem um conjunto finito de máinors proibidos.

12.1 Anticadeias infinitas

Uma quase-ordem (= quasi-order) sobre um conjunto X é uma relação reflexiva e transitiva entre os elementos do conjunto. A quase-ordem será denotada por ≤ . [A notação é infeliz, porque dá a falsa impressão de que estamos supondo também que a relação é antisimétrica.]
Exemplo: A relação é-máinor-de entre grafos é uma ordem parcial e portanto uma quase-ordem.
Dada uma quase-ordem ≤ sobre um conjunto X, dizemos que elementos x e y de X são incomparáveis se não temos x ≤ y nem y ≤ x. Uma anticadeia (= antichain) é um subconjunto de X cujos elementos são dois a dois incomparáveis (ou seja, um conjunto independente no grafo com vértices X e arestas dadas pela relação ≤).
Dada uma quase-ordem ≤ sobre um conjunto X, a relação > é definida assim: x > y se y ≤ x mas não é verdade que x ≤ y. Uma sequência x₀, x₁, x₂, … é crescente se x₀ ≤ x₁ ≤ x₂ ≤ … e estritamente decrescente se x₀ > x₁ > x₂ > …
Proposição 12.1.1 (Corolário do Teorema 9.1.2 (Ramsey)): Em qualquer quase-ordem sobre X, toda sequência infinita de elementos de X contém (1) uma anticadeia infinita ou (2) uma subsequência infinita crescente ou (3) uma subsequência infinita estritamente decrescente.
(Por razões técnicas, convém desviar a atenção dos conjuntos infinitos, como os que são mencionados no enunciado do teorema de Robertson e Seymour, e concentrá-la sobre as sequências infinitas.)
Uma sequência infinita x₀, x₁, x₂, … é boa se há um par i < j de índices tal que x_i ≤ x_j. A propósito, se toda sequência infinita em X é boa, dizemos que X está bem quase-ordenado (= well-quasi-ordered = WQO).
Consequência da Proposição 12.1.1: Suponha que nossa quase-ordem não tem sequências infinitas estritamente decrescentes (como acontece com a relação é-máinor-de). Então não existe anticadeia infinita se e só se toda sequência infinita é boa.

Exercícios:
1. Suponha que ≤ é uma quase-ordem em X. Mostre que a relação > é transitiva.
2. [12.6] Existem anticadeias infinitas na relação é-subgrafo-de entre grafos? Existem anticadeias infinitas na relação é-isomorfo-a-subgrafo-de entre grafos? Para essa mesma relação, existem anticadeias infinitas de árvores?
3. Seja G um grafo completo infinito. Pinte as arestas de G com 3 cores (ou qualquer número finito de cores) de modo que cada aresta tenha uma e uma só cor. Prove que G tem um subgrafo induzido monocomático infinito. (Sugestão: Caso particular da prova do Teorema 9.1.2.)
4. [12.3] Prove a Proposição 12.1.1 diretamente, sem usar o Teorema 9.1.2. Prove diretamente (sem usar o Teorema 9.1.2) a seguinte afirmação: se toda sequência infinita em X é boa então toda sequência infinita em X tem uma subsequência crescente infinita.

12.2 O teorema Graph Minor para árvores

Teorema 12.2.1 (Kruskal): O conjunto de todas as árvores não tem anticadeia infinita sob a relação é-máinor-topológico-de. (Mais especificamente, toda sequência infinita de árvores é boa sob a relação é-máinor-topológico-de).
Em particular, a relação é-máinor-de entre árvores não tem anticadeias infinitas.
(Em termos bem mais vagos e informais: não existe uma variedade infinita de árvores.)
[O teorema de Kruskal figura como exercício no Fundamental Algorithms, 2a. edição, de D. E. Knuth. Veja seção 2.3.4.3. O exercício está resolvido no fim do livro.]

12.3 Decomposições arbóreas

Uma decomposição arbórea (= tree decomposition) de um grafo G é um par (T, V) onde T é uma árvore e V é uma função que associa a cada vértice t de T um conjunto V_t de vértices de G de tal modo que
1. todo vértice de G está em algum V_t ;
2. toda aresta de G tem ambas as pontas em algum V_t ;
3. se y está entre x e z em T então V_x ∩ V_z ⊆ V_y.
Como sempre, y está entre x e z significa que y está no caminho de x a z em T. Algumas pessoas gostam de dizer que cada V_t é uma sacola ou bag.
Lema 12.3.1: Seja xy uma aresta de T. Se X e Y são os componentes de T − xy, então o conjunto V_x ∩ V_y separa (em G) a união de todos os V_t com t em X da união de todos os V_t com t em Y. (Em particular, todo caminho em G que começa em V_x e termina em V_y passa por V_x ∩ V_y.)
A decomposição arbórea de um grafo é herdade por seus máinors, como mostram os seguintes lemas:
Lema 12.3.2: Seja H um subgrafo de G e W_t o conjunto V_t ∩ V(H) para cada t. Então (T, W) é uma decomposição arbórea de H.
Lema 12.3.3: Seja H uma contração de G. (Portanto, o conjunto de vértices de H é uma partição de V(G). Seja W_t o conjunto das partes de V(H) que intersectam V_t. Então (T, W) é uma decomposição arbórea de H.
Lema 12.3.4 (corolário de 12.3.1): Seja (T, V) uma decomposição arbórea de G. Se W é parte de V(G) mas não é parte de nenhum V_t então existe aresta xy de T e vértices w₁ e w₂ em W − (V_x ∩ V_y) que são separados por V_x ∩ V_y .
Lema 12.3.5 (corolário de 12.3.4): Todo subgrafo completo de G é parte de algum V_t.

Exercícios:
1. [12.11] Seja G um grafo, T um conjunto, e V uma função que leva T em partes de V(G) de modo a satisfazer os axiomas (i) e (ii) da definição de decomposição arbórea. Mostre que existe uma árvore com conjunto T de vértices que satisfaz o axioma (iii) se e só se existe uma enumeração t₁, … , t_n de T tal que, para k = 2, … , n, a interseção de V_{t_k} com a união V_t₁∪ … ∪ V_{t_k–1} é parte de V_{t_j} para algum j < k. (Esta condição é mais conveniente, às vezes, que o axioma (iii). Ela pode ser útil, por exemplo, na construção de uma decomposição arbórea que tenha um número pré-fixado de partes.)
2. Suponha que (T, V) é uma decomposição arbórea de G. Sejam x, y e z vértices de T tais que y está entre x e z. Mostre que V_y separa V_x de V_z.
3. [12.12] Prove a seguinte recíproca do Lema 12.3.1: se (T, V) satisfaz o axioma (i) e o enunciado do lema, então (T, V) é uma decomposição arbórea de G.
4. [12.14] Seja (T, V) uma decomposição arbórea de G. Para cada vértice v de G, seja T_v o conjunto dos vértices t de T tais que V_t contém v. Mostre que T_v é conexo em T.

12.3′ Largura arbórea

Seja (T, V) uma decomposição arbórea de um grafo G. A largura (= width) da decomposição é o maior número da forma |V_t| − 1, com t em T.
A largura arbórea (= tree-width) de um grafo G é a largura da decomposição arbórea mais estreita de G. A largura arbórea de G é denotada por tw(G). (A determinação da largura arbórea de um grafo é um problema NP-difícil.)
Proposição 12.3.6: Se H é máinor de G então tw(H) ≤ tw(G).
Teorema 12.3.7 (Robertson & Seymour): Para todo k, o conjunto dos grafos que têm largura arbórea menor que k não possui anticadeia infinita sob a relação é-máinor-de.
Como tornar evidente o fato de que tw(G) ≥ k?
Sejam X e Y dois conjuntos de vértices; dizemos que X e Y se tocam (= touch) se X intersecta Y ou há uma aresta ligando X a Y. Um bramble é um conjunto de partes conexas de V(G) que se tocam duas a duas.
Uma cobertura de um bramble B é um conjunto de vértices que intersecta cada elemento de B. A ordem de B é a cardinalidade da menor cobertura de B.
Exemplo: Digamos que G é uma grade k×k, isto é, os vértices de G são todos os pares da forma (i, j) com i e j em {1, … , k} e as arestas são os pares {(i, j), (p, q)} com |i−p| + |j−q| = 1. Uma cruz (i, j) é o conjunto de todos os vértices da forma (i, l) mais todos os vértices da forma (l, j). O conjunto de todas as cruzes é um bramble de ordem k.
Teorema 12.3.9 (tree-width duality, Seymour & Thomas): Para todo k e todo G, tw(G) ≥ k se e só se G tem um bramble de ordem maior que k.
Corolário: Se G é uma grade k×k então tw(G) ≥ k−1.

Exercícios:
1. Para todo grafo G existe k tal que tw(G) < k. Logo, o Teorema 12.3.7 mostra que o conjunto de todos os grafos não tem anticadeia infinita sob é-máinor-de. O raciocínio está certo?
2. [12.10] Mostre que tw(G) ≤ 1 se e só se G é uma floresta.
3. Mostre que tw(G) ≤ 2 se e só se G é série-paralelo.
4. [12.13] Seja H uma subdivisão de G. É possível que tw(H) < tw(G)? É possível que tw(H) > tw(G)?
5. [12.15, fácil] O bramble number de G é a ordem do bramble de maior ordem em G. O bramble number de G será denotado por br(G). Deduza do Teorema 12.3.9 que tw(G) = br(G)−1.
6. [12.16] Suponha que G é uma grade k×k. Mostre que tw(G) = k.

12.3″ Decomposições magras e decomposições simpliciais

Uma decomposição arbórea (T, V) de G é magra (= lean) se, para todo inteiro s e quaisquer vértices x e z de T, ou G tem s caminhos disjuntos de V_x a V_z ou existe y entre x e z em T tal que |V_y| < s.
(Pelo Lema 12.3.1, V_y separa V_x de V_z.)
Teorema 12.3.10 (Thomas): Todo grafo G tem uma decomposição arbórea magra de largura tw(G).
Uma decomposição arbórea (T, V) de G é simplicial se todos os conjuntos da foma V_x ∩ V_y induzem subgrafos completos de G.
Uma decomposição simplicial é particularmente simples se G[V_t] é um grafo completo para todo t. Grafos com essa propriedade são conhecidos como triangulados ou cordias (= chordal).

Exercícios:
1. [12.20] Seja H um conjunto de grafos. Construa G recursivamente a partir de elementos de H sobrepondo subgrafos completos. Mostre que G tem uma decomposição simplicial (T, V) tal que cada G[V_t] está em H.

12.4 Largura arbórea e máinors proibidos

Uma propriedade gráfica (= graph property) é um conjunto de grafos fechado sob isomorfismo. Uma propriedade gráfica P é hereditária se for fechada sob máinors, ou seja, se P contém todos os máinors dos grafos que estão em P.
Para qualquer conjunto H de grafos, Forb(H) (= forbidden H minor) é a propriedade dos grafos que não têm máinors em H. Essa propriedade é gráfica.
Exemplos: De acordo com o teorema de Kuratowski-Wagner, Forb(K⁵, K_3,3) é o conjunto dos grafos planares. De acordo com a conjectura de Hadwiger, chi(G) < k para todo G em Forb(K^k).
Proposição 12.4.1: A propriedade Forb(H) é hereditária. Reciprocamente, toda propriedade gráfica hereditária é da forma Forb(H).
Considere a seguinte propriedade da largura arbórea limitada: dado k, tome o conjunto dos grafos G tais que tw(G) < k. Quando k = 2, essa propriedade é Forb(K³). Quando k = 3, essa propriedade é Forb(K⁴).
Dado um grafo H, suponha que a largura arbórea dos grafos em Forb(H) é limitada. (Ou seja, existe k tal que tw(G) ≤ k para todo G em Forb(H).) Segue de 12.3.9 que H é planar. Veja a recíproca:
Teorema 12.4.3 (Robertson & Seymour): Para todo grafo planar H, os grafos em Forb(H) têm largura arbórea limitada.
Esse teorema segue do seguinte Teorema 12.4.4 (Robertson & Seymour): Para todo r, existe k tal que todo grafo G com tw(G) ≥ k tem um máinor que é uma grade r×r.

12.5 O teorema Graph Minor

Teorema 12.5.2 (Graph Minor Theorem, Robertson & Seymour): Não existe anticadeia infinita de grafos sob a relação é-máinor-de. (Ou seja, em toda sequência infinita G₀, G₁, G₂, … de grafos, existem i < j tais que G_i é máinor de G_j.)
Corolário 12.5.3: Toda propriedade gráfica hereditária é da forma Forb(H) com H finito.
Corolário 12.5.4: Para toda superfície S, existe um conjunto finito H₁, … , H_n de grafos tal que Forb(H₁, … , H_n) é o conjunto dos grafos não imersíveis em S.
(É oportuno lembrar que todo grafo pode ser imerso em alguma superfície.)