Teoria dos Grafos e Seus Algoritmos - T01
Primeira prova P1 - 21/09/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;
• Se o exercı́cio solicitar um algoritmo especı́fico, apenas soluções usando aquele algoritmo
serão consideradas;
• Quando simular a execução de um algoritmo, sempre que for indiferente a ordem de escolha
de alguns elementos do grafo, siga as seguintes orientações:
– Se o elemento a escolher for um vértice, escolha-os em ordem crescente de rótulo (seja
numérico ou alfabético);
– Se o elemento a escolher for uma aresta, escolha-as na ordem da ponta de menor
rótulo. Em caso de empate, entre as arestas incidentes no mesmo vértice de menor
rótulo, escolha-as em ordem crescente do rótulo do outro extremo da aresta. Ex: as
arestas {1, 6}, {2, 4}, {2, 5}, {3, 4} seriam processadas nesta ordem, se isto for indife-
rente para o algoritmo.
1. (2,0) Dado o grafo G abaixo, considere o subconjunto de vértices X = {3, 4, 6, 10, 13} e responda
o valor de cada um dos itens abaixo.
Figura 1: O grafo G da Questão 1.
(a) δ(G); Um vértice de menor grau é o 9, logo δ(G) = g(9) = 1.
(b) c(G); As três componentes conexas são {1, 2, 3, 4, 5}, {6, 7, 8} e {9, 10, 11, 12, 13}. Logo
c(G) = 3.
(c) ∇(X); As arestas do corte definido por X. ∇(X) = {{3, 1}, {3, 5}, {4, 2}, {4, 5}, {6, 7}, {6, 8},
{9, 13}, {11, 13}, {12, 13}}.
(d) G[X]. O grafo induzido por X. Temos que V (G[X]) = X = {3, 4, 6, 10, 13} e A(G[X]) =
{{3, 4}, {10, 13}}.
Figura 2: O grafo H da Questão 2.
2. (3,0) Dado o grafo H, com pesos inteiros positivos em cada aresta, faça o que se pede. Observe
os comentários sobre como escolher vértices e arestas quando existe opção.
(a) (2,0) Encontre uma Árvore Geradora Mı́nima usando o algoritmo de Kruskal. Liste as
arestas adicionadas à árvore pelo algoritmo na ordem em que isto acontece e indique o
peso da árvore obtida.
Arestas adicionadas em ordem: ({b, g}, {a, f }, {d, i}, {f, i}, {g, h}, {h, i}, {e, f }, {g, j},
{c, h}). O custo da árvore é 1 + 5 · 2 + 2 · 3 + 4 = 21.
(b) (1,0) Suponha que o grafo H ′ foi obtido de H adicionando a aresta {d, e} com peso 4.
Apresente uma Árvore Geradora de H ′ que contenha a aresta {d, e} e possua peso mı́nimo
entre todas as árvores geradoras de H ′ que contenham a aresta {e, d}. Descreva como
você obteria esta árvore.
A partir da árvore anterior, adicione a aresta {d, e} que forma um ciclo (d, e, f, i, d).
Remove-se a aresta de maior custo do ciclo, exceto a aresta {d, e}. No caso, remove-se a
aresta {e, f }.
Outra possibilidade seria executar o algoritmo de Kruskal, mas antes pré-selecionando
a aresta {d, e} e já marcando d e e no mesmo componente conexo. Assim, a árvore
encontrada garantidamente é mı́nima e contém a aresta desejada.
3. (2,5) Seja G um grafo desconexo (obviamente com n(G) ≥ 2). Mostre que G é conexo.
Se G é desconexo, então G possui dois vértices distintos x e y tais que não existe caminho com
tais extremos. Agora, seja X o componente conexo de G que contém x e seja Y , o componente
conexo de G que contém y. Provaremos que todo par de vértices distintos a, b são ligados por
um caminho em G.
Se a ∈ X e b ∈ X: Logo não há arestas conectando a a y nem b a y. Logo, em G existe o
caminho P ′ = (a, y, b).
Se a ∈ X e b ∈
/ X: Logo não há a aresta conectando a a b. Logo, em G existe o caminho
P = (a, b).
′
Se a ∈
/ X eb∈/ X: Logo não há arestas conectando a a x nem b a x. Logo, em G existe o
caminho P = (a, x, b).
′
4. (2,5) Seja G um grafo conexo tal que V (G) = A ∪ B, com A ∩ B = ∅ e tal que não existe aresta
de G com dois extremos no mesmo conjunto (A ou B). Ou seja, os vértices de G estão divididos
em dois conjuntos disjuntos e todas as arestas do grafo ligam um vértice de um conjunto com
um vértice do outro conjunto. Sejam x ∈ A e y ∈ V (G) dois vértices distintos de G (y pode
estar em B ou A). Prove que qualquer caminho em G de x a y tem um número par de vértices
se y ∈ B e um número ı́mpar de vértices se y ∈ A.
Prova por indução no número de vértices do caminho.
Base: P = (x, y). |P | = 2 que é par e y está em B.
Passo: seja P = (x = v1 , v2 , . . . , vk+1 = y) um caminho em G com k + 1 ≥ 3 vértices e seja
P ′ = (x = v1 , v2 , . . . , vk ) um caminho com k ≥ 2 vértices obtido removendo o último vértice
de P ′. Por hipótese de indução, se vk ∈ A então |P ′| é ı́mpar e se vk ∈ B, então |P ′| é par.
Sabendo que vk é adjacente a vk+1 = vy , temos que, se vy ∈ A, então vk ∈ B e |P | = |P ′| + 1 é
ı́mpar; se vy ∈ B, então vk ∈ A e |P | = |P ′ | + 1 é par.
