Notas sobre Grafos

Algumas anotações da cadeira Tópicos Avançados em Algoritmos em Grafos ministrada pela profa. Cláudia Linhares.

Grafo: Um grafo (ou um grafo não-direcionado) G é um par ordenado G = (V,E) sujeito as condições:

• V é um conjunto os quais elementos são chamados nós ou vértices (em inglês, vertices).
• E é um conjunto de pares (não ordenados) de vértices distintos, chamados arestas (em inglês, edges).

Grafo simples: Um grafo G = (V,E), finito, sem laços ou arestas múltiplas.

Clique: Seja G um grafo simples. Q é uma clique de G se Q ⊆ V(G) e para todo u,v ∈ Q então uv ∈ E(G).

Problema clique máxima: Dado G =(V,E), determinar o tamnho da maior clique de G (ou da clique máxima de G). Denotamos por ω(G) o tamanho da maior clique de G.

Conjunto independente (estável): S ⊆ V(G) é um conjunto independente se ∀u,v ∈ S, uv ∉ E(G).

Problema do conjunto independente máximo: Dado G = (V,E), determinar o tamanho do maior conjunto indepdente de G. Denotamos por α(G) o tamanho do maior conjunto independente de G.

Grafo Bipartite: Seja um grafo G=(V,E) é chamado bipartite se existe uma partição V=V₁⋃V₂ (de vértices) tal que ∀uv ∈ E temos u ∈ V₁ e v ∈ V₂. Podemos escrever G como G=(V₁+V₂ ,E).

Grafo Bipartite balanceado: G=(V₁+V₂ ,E) tal que |V₁|+|V₂|.

K-Coloração própria de G: Seja k = V(G). Seja uma função C:V(G)→{1,…,k}. C é um k-coloração própria de G se ∀uv ∈ E(G), C(u) ≠ C(v).

• Todo bipartite admite uma 2-coloração própria.
• Todo conjunto independente admite uma 1-coloração própria.

Exercício 1:

1. G é bipartite se somente se não tem ciclo ímpar.
2. G é bipartite se somente se adimite 2-Coloração própria.

Solução do exercício 1.1:

• ⟹ Prova de que se G é bipartite então G não tem ciclo ímpar: O grafo é da forma G=(V₁+V₂ ,E). O grafo G pode ter ou não um ciclo. Se ele não tem ciclo, então ele não tem um ciclo ímpar. Caso ele tenha um ciclo ele pode ser descrito como uma lista de arestas como (ab, bc, cd, …., xa). Vamos colocar os vértices A primeira aresta ab é tal que a ∈ V₁ e b ∈ V₂, a segunda aresta bc é tal que b ∈ V₂ e c ∈ V₁, e assim alternando até o fim do ciclo, mas necessariamente a ultima aresta xa é tal que a ∈ V₁ (já que colocamos a em V₁ inicialmente) e portanto x ∈ V₂. Para que isso aconteça não resta alternativas a não ser o ciclo ser par, pois caso contrário não teríamos como começar e terminar com a ∈ V₁.
• ⟸ Prova de que se G não tem ciclo ímpar então G é bipartite: Se G nãi tem ciclo ímpar ele pode ter somente ciclos pares ou então não ter ciclo nenhum. Se ele não tem ciclo nenhum, então ele é uma árvore e pode ser particionado colocando uma nível da árvore em V₁ e o outro em V₂ alternadamente. Caso ele tenha um ciclo ele é par pois não é ímpar. Como já foi mostrado antes, um ciclo par pode ser particionado em duas partições.

Como provamos que se G é bipartite então G não tem ciclo ímpar e que se G não tem ciclo ímpar então G é bipartite então provamos que se G é bipartite se somente se não tem ciclo ímpar. ∎

Solução do exercício 1.2:

• ⟹ Se G é bipartite então admite 2-coloração própria: G é G=(V₁+V₂, E). Então criamos uma função C:V(G)→{1,2} tal que C(x)=1 se x ∈ V₁ e C(x)=2 se x ∈ V₂. Pela definição de grafo bipartite ∀uv ∈ E(G) temos u ∈ V₁ e v ∈ V₂ e portanto pela definição de C temos que ∀uv ∈ E(G), C(u) ≠ C(v). Logo C é uma 2-coloração própria.
• ⟸ Se G admite 2-coloração própria então G é bipartite: Se G adimite uma 2-coloração própria então sabemos que existe uma certa função C tal que se ∀uv ∈ E(G), C(u) ≠ C(v). Criamos uma partição de V colocando os vértices de uma cor em em V₁ e os vértices da outra cor em V₂. Dessa forma ∀uv ∈ E(G) temos u ∈ V₁ e v ∈ V₂, que é a definição de bipartite.

como provamos que Se G é bipartite então admite 2-coloração própria e também que Se G admite 2-coloração própria então G é bipartite, portanto provamos que G é bipartite se somente se adimite 2-Coloração própria. ∎

Problema da coloração de vértices: Dado G=(V,E), determinar o menor inteiro k tal que G admite uma k-coloração própria. Denominamos por χ(G) o menor inteiro K tal que G admite uma k-coloração própria. χ(G) é o número cromático de G. Denotamos por C_i o conjunto dos vértices de G coloridos com a cor i. C_i é uma classe de cor.

• Obs1: n ≤ χ(G)⋅α(G)
• Obs2: n/α(G) ≤ χ(G)

Cobertura por cliques: dizemos que Q₁, Q₂, …, Q_k é uma cobertura de cliques de G se:

• Cada Qi é uma clique
• Q_i ∩ Q_j = ∅
• V = Q₁∪Q₂∪…∪Q_k

• obs: cobrir por cliques é fácil! O interessante é encontrar o menor número de cliques que cobre todos os vértices.

Problema: Cobertura de cliques mínima. Dado G = (V,E), determinar o menor inteiro K tal que G admite uma partição de V(G)=Q₁∪Q₂∪…∪Q_k onde cada Q_ié uma clique de G.

Denotamos por Æ”(G) o menor inteiro K tal que G admite uma corbertura com K cliques.

Observe que α(G)≤Ɣ(G), pois cada clique contribui no máximo com 1 vértice para o conjunto independente.

Lembre-se: seja G = (V,E) um grafo simples. G’, o complemento de G, é assim definido: V(G’) = V(G). E(G’)={uv|uv ∉ E(G)} ou seja uv ∈ E(G’) sse uv ∉ E(G).

Ex:

Se G=C₅ então G’=C₅.

Referências:

• Cormen. Thomas (2000); Leiserson, Charles.; Rivest, Ronald. Introduction to Algorithmics, McGraw-Hill.
• http://en.wikipedia.org/wiki/Graph (mathematics)