Teoria dos Grafos e Seus Algoritmos - T01
Segunda prova (P2) - 21/11/2023 FACOM - UFMS
Nome: Q1 Q2 Q3 Q4 Nota
RGA:
Observações:
• Responda claramente cada exercı́cio;
• Utilize a mesma notação usada em aula e no livro-texto;
1. Desenhe um grafo G conexo de grau mı́nimo 2 com uma clique maximal Q com 3 vértices e
uma clique máxima K com 4 vértices. Enumere os vértices do grafo e identifique as cliques K
e Q.
No grafo da Figura 1, K = {1, 2, 3, 4} e Q = {3, 4, 5}.
Figura 1: Um grafo G resposta da Questão 1.
2. Seja G um grafo com pelo menos uma aresta (observe que isto garante que χ(G) ≥ 2) e que
contenha v ∈ V (G) tal que g(v) ≤ χ(G) − 2. Prove que χ(G) = χ(G − v).
Lembre-se que χ(G) é o tamanho de uma coloração de vértices mı́nima.
Como qualquer coloração dos vértices de G é uma coloração dos vértices de G − v, sabe-se que
χ(G − v) ≤ χ(G). Resta mostrar que χ(G − v) ≥ χ(G).
Suponha, por contradição, que χ(G − v) < χ(G), ou seja, χ(G − v) ≤ χ(G) − 1. Seja o :
V (G − v) → N uma coloração de G − v com no máximo χ(G) − 1 cores. Vamos criar uma
coloração o′ para G da seguinte forma: o′ (u) = o(u) para todo vértice u de G − v. Como v tem
no máximo χ(G) − 2 vizinhos, haverá uma cor x entre as cores de 0 a χ(G) − 2 que não foi
usada por nenhum dos vizinhos de v. Fazemos então o′ (v) = x. A coloração o′ é válida para G
e tem pelo menos uma cor a menos que χ(G), um absurdo.
Figura 2: O grafo G da questão 3.
3. Considere o grafo G acima.
(a) Apresente um emparelhamento maximal M de G que não contenha a aresta {5, 6}, mas
que sature ambos os vértices 5 e 6.
(b) Apresente dois caminhos M-aumentantes distintos.
Lembre-se: um emparelhamento satura os vértices que são extremos de suas arestas.
Emparelhamento M = {{1, 3}, {4, 5}, {6, 8}}. Caminhos P1 = (2, 1, 3, 4, 5, 6, 8, 7) e P2 =
(2, 4, 5, 6, 8, 7).
4. Seja G um grafo r-regular com número ı́mpar de vértices e r ≥ 2. Mostre que χ′ (G) ≥ r + 1.
Observe que todo vértice possui o mesmo grau r. Lembre-se que χ′ (G) é o tamanho de uma
coloração de arestas mı́nima. Dica: mostre que G é sobrecarregado.
Em um grafo r-regular, m(G) = n(G)r
2
. Como n(G) é ı́mpar, temos que r é par. Um grafo é so-
brecarregado se m(G) > ∆(G)⌊ 2 ⌋. Uma vez que n(G) é ı́mpar, ⌊ n(G)
n(G)
2
⌋ = n(G)−1
2
. Lembrando
que ∆(G) = r para grafos regulares:
n(G) n(G) − 1 ∆(G)(n(G) − 1) r(n(G) − 1)
∆(G)⌊ ⌋ = ∆(G) = = =
2 2 2 2
rn(G) − r rn(G) r r
= − = m(G) −
2 2 2 2
Logo m(G) > ∆(G)⌊ n(G)
2
⌋ e G é sobrecarregado. Assim X ′ (G) ≥ ∆(G) + 1 = r + 1.