MO405 - Atas das Aulas

Ata de Aula: 28/10/2002

Redator: Vagner Katsumi Okura

7.1 Grafos Linha e Coloração de Arestas

Grafo linha: (João Guilherme) O grafo linha de G (L(G)) é o grafo onde os seus vértices são as arestas de G, com arestas ab pertence a E(L(G)) se a e b possuem um vértice em comum em G.

Coloração de Arestas: (João Paulo) É um conceito análogo ao de coloração de vértices.

• k-aresta-coloração : Dado um grafo G, é um rotulamento f: E(G) → S, onde |S| = k. Os rótulos são cores, e as arestas de uma cor formam um classe de cor.
• Própria: uma k-aresta-coloração é própria se arestas incidentes têm rótulos diferentes, ou seja, se cada classe de cor é um emparelhamento.
• k-aresta-colorável: um grafo G é k-aresta-colorável se ele possui uma k-aresta-coloração própria.
• Índice cromático: o índice cromático ou número cromático de arestas de um grafo se loop G (χ’(G))é o menor k tal que G é k-aresta-colorável.

Aplicação: (João Meidanis) programar rodadas de jogos de um campeonato com um número par de times, onde todos os times devem jogar um contra o outro em cada rodada, e um time não pode ter dois jogos na mesma rodada.

Exemplo: Considere os times 1, 2, 3 e 4

Rodada 1 (r1): 1-2, 3-4

Rodada 2 (r2): 1-3, 2-4

Rodada 3 (r3): 1-4, 2-3

Transformando o problema em um grafo, achar as rodadas de um campeonato com 2n times, equivale a colorir as arestas de K_2n com n-1 cores. No grafo abaixo, podemos colorir K₄ com 3 cores.

Multiplicidade: (Luis Augusto) Dados dois vertices x e y , a multiplicidade (μ(x,y))mede o número de arestas entre x e y. A multiplicidade de um grafo G (μ(G)) mede o máximo das multiplicidades de G.

Teorema de Vizing-Gupta: (Vitor) Se G é um grafo simples, então χ’(G) <= Δ(G) + 1.

Generalização para multigrafos: (Vinícius) χ’(G) <= Δ(G) + μ(G).

Classe 1: (Alberto) Um grafo G é classe 1 se χ’(G) = Δ(G).

Classe 2: (Alberto) Um grafo G é classe 2 se χ’(G) = Δ(G) + 1.

Exemplos de grafos classe 1: K_2n, C_2n, K_n,n.

Exemplos de grafos classe 2: K_2n+1, C_2n+1

Complexidade para coloração de arestas: (Alberto) NP-difícil.

Overfull: (João Meidanis) um sub-grafo H é overfull quando n(H) é impar e

[(n(H)-1)/2] * Δ(G) < e(H)

Caracterizações de Grafos linha (7.1.16): (Candida) Para um grafo simples G, existe uma solução L(H) = G se e somente se G decompõem-se em sub-grafos completos, com cada vértice de G aparecendo no máximo em dois desses sub-grafos completos.

• Comentários (Meidanis)
• Condição necessária para ser classe 1: não ter sub-grafos overfull.
• Essa caracterização parece difícil, pois é preciso olhar todos os sub-grafos.

Caracterizações de Grafos linha (7.1.17): (Cibele) Para um grafo simples G, existe uma solução L(H) = G se e somente se G não possui um garra (claw) e triângulos duplos de G não tenham triângulos ímpares.

• Um triângulo T é ímpar se |N(v) ∩ V(T)| é ímpar para algum v pertencente a V(G).
• Um triângulo T é par se |N(v) ∩ V(T)| é par para todo v pertencente a V(G).

• Comentários (Meidanis)
• Verificar se grafo tem um sub-grafo fixo é polinomial. Para um sub-grafo de quatro vértices, um algoritmo simplista teria 4 laços, sendo O(n⁴).

Caracterizações de Grafos linha (7.1.18): (Cláudio) Um grafo simples G é grafo linha de algum grafo simples se e somente se G não possui nenhum dos grafos abaixo como sub-grafos induzidos.

• Comentários (Meidanis)
• Polinomial.
• O grafo é único se G não tem componente conexa que não seja triângulo e garra.