Prévia do material em texto

UFBA
Instituto de Computação
MATA53 – Teoria dos Grafos – 2025.1
Professor: Roberto Freitas Parente
Avaliação 01 – Gabarito
Questão 1. Defina de forma precisa os seguintes conceitos:
a) Grafo bipartido.
Resposta. Grafo bipartido G = (V,E) é tal que existe uma partição dos vértices de G em X e Y tal que X∪Y = V
e X ∩ Y = ∅ e ∀xy ∈ E(G) temos que x ∈ X e y ∈ Y , i.e., G[X] e G[Y ] são conjuntos independentes.
b) Componentes conexas de um grafo G.
Resposta. Componentes conexas são conjunto de vértices X ⊂ V (G) maximal conexos.
c) Floresta e Árvore com n vértices.
Resposta. Uma floresta é um grafo aćıclico e uma árvore é uma floresta conexa.
d) Subgrafo gerador e subgrafo induzido
Resposta. Um subgrafo gerador H de um grafo G = (V,E) é um subgrafo H ⊆ G tal que o seu conjunto de
vértices de H é igual ao conjunto de vértices do grafo original G, ou seja, V (H) = V (G). Subgrafo induzido H
de G é um grafo V (H) ⊂ V (G) e E(H) = {xy ∈ E(G) : x, y ∈ V (H)}.
Questão 2. Utilizando as definições conhecidas, responda abaixo.
1. Para quais valores de n podemos afirmar que Kn é um grafo euleriano?
Resposta. Pelo resultado visto em sala sabemos que um grafo euleriano é um grafo que tem todos os vértices com
grau par e no máximo uma componente conexa não trivial. Observe Kn é conexo e todo vértice de tem grau n− 1.
Desta forma Kn é euleriano quando n é um número ı́mpar.
2. Para quais valores de r podemos afirmar que Kr,r é um grafo hamiltoniano?
Resposta. Pelo resultado visto em sala, dizemos que G é um grafo hamiltoniado quando δ(G) ≥ n/2 e n ≥ 3.
Desta forma, Kr,r é o grafo bipartido completo onde cada parte tem r vértices, ou seja, todos os vértices tem grau
r. Como n = 2r, precisamos apenas que r ≥ 2.
3. Prove ou desprove: Toda árvore é um grafo bipartido
Resposta. Para demonstrar que toda árvore é um grafo bipartido basta observar o resultado de König visto em
sala que afirma que todo grafo é bipartido se, e somente se, não contém ciclo ı́mpar. Por definição uma árvore não
contém ciclo, então toda árvore será um grafo bipartido.
Questão 3. Seja T uma árvore com n ≥ 2 vértices prove a seguinte afirmação: Para k ∈ N, se ∆(T ) ≥ k, então existem
pelo menos k folhas
Resposta. Observe que, como visto em sala, uma árvore com pelo menos 2 vértices será terá duas folhas. Para tal basta
pegarmos um caminho maximal em e seus extremos terão grau 1, caso contrário teŕıamos um ciclo.
Para k = 1 e ∆(T ) = 1 temos que T é apenas uma aresta e o resultado está provado. Para k ≥ 2, pegue v um vértice
de T tal que d(v) = ∆(T ) ≥ k. Observe que v não será folha e como T não contém ciclo T ′ \ v será desconexo onde
cada vizinho de v estará em uma componente conexa distinta. Sejam C1, C2, . . . , C∆(T ) as componentes conexas. Cada
componente conexa Ci pode ter trivial ou não. Se |Ci| = 1 (componente conexa trivial) temos que o único vértice em Ci
terá grau 1 em T e será uma folha em T . Se |Ci| ≥ 2 temos duas folhas, como visto acima, e v é vizinho apenas de um
vértice de Ci e pelo menos uma das folhas de Ci será folha em T . Por fim, como cada componente conexa contribuirá com
pelo menos ∆(T ) folhas e o resultado segue.
Questão 4. Considere um sistema de tráfego aéreo com k companhias aéreas. Suponha que:
1. Um serviço direto entre duas cidades significa um serviço direto de ida e volta; e
2. Cada par de cidades tenha um serviço direto de pelo menos uma companhia aérea.
1
Suponha também que nenhuma companhia aérea possa programar um ciclo através de um número ı́mpar de cidades. Como
você modelaria o problema? Em termos de k, como podemos calcular o número máximo de cidades no sistema?
Resposta. Modelagem do problema:
1. Cada cidade será representada como um vértice.
2. Cada servico de tráfego da companhia aérea i será representada por um grafo Gi
3. As arestas de Gi representa o serviço entre duas cidades (vértices). Como um serviço direto entre duas cidades
significa um serviço de ida e volta, as arestas não são direcionadas.
4. Como nenhuma companhia aérea pode programar um ciclo através de um número ı́mpar de cidades, temos que, para
cada companhia i, o grafo Gi não possui ciclos ı́mpares. Isso implica, pelo resultado de König visto em sala, que os
grafos Gi são bipartidos.
5. A condição de que cada par de cidades possui um serviço direto de pelo menos uma companhia aérea garante que⋃k
i=0 Gi = Kn, onde n é o conjunto de cidades.
Por fim, para calcular o número máximo de cidades basta estudar qual o maior grafo completo podemos gerar com úniões
de grafos bipartidos.
Obs: Na prova não é necessário explicar qual a quantidade de cidades, mas no livro do Douglas West tem o resposta
em Theorem 1.2.23.
Questão 5. Resolva os seguintes itens sobre grafos hamiltonianos
1. Defina grafo hamiltoniano e fecho hamiltoniano de um grafo.
Resposta. Um grafo é chamado hamiltoniano se contiver um ciclo hamiltoniano. Um ciclo hamiltoniano de G é
um ciclo C ⊂ G em que V (C) = V (G). O fecho hamiltoniano de um grafo G com n vértices é o grafo obtido a partir
de G pela adição iterativa de arestas entre pares de vértices não adjacentes u e v tais que d(u) + d(v) ≥ n. Esse
processo continua até que não existam mais tais pares.
2. Prove ou desprove o seguinte: Se G tem um subgrafo gerador euleriano, então L(G) é hamiltoniano.
Resposta. Obs: A intenção inicial era que fosse verdade, mas para funcionar teŕıamos que ter “subgrafo gerador
conexo euleriano” em vez de “subgrafo gerador euleriano”. Desta forma, o seguinte grafo é contraexemplo para o
resultado:
3. Prove ou desprove o seguinte: Todo torneio tem um caminho hamiltoniano direcionado.
Resposta. Vamos provar a afirmação por indução sobre o número de vértices n do torneio T . Base da indução:
Para n = 1: um torneio com um único vértice possui trivialmente um caminho hamiltoniano (o próprio vértice).
Para n = 2: um torneio com dois vértices v1 e v2 tem exatamente uma aresta entre eles (por exemplo, v1 → v2).
Essa aresta forma um caminho hamiltoniano.
Hipótese de indução: Suponha que todo torneio com n − 1 ≥ 2 vértices possui um caminho hamiltoniano
direcionado.
Passo indutivo: Considere um torneio T com n vértices. Escolha um vértice arbitrário v ∈ T e considere o subgrafo
T ′ = T −v, que é um torneio com n−1 = k vértices. Pela hipótese de indução, T ′ possui um caminho hamiltoniano:
P = v1 → v2 → · · · → vk. Vamos tentar inserir o vértice v em alguma posição do caminho P para obter um caminho
hamiltoniano em T .
• Se v → v1, então podemos colocar v no ińıcio do caminho: v → v1 → v2 → · · · → vk que é um caminho
hamiltoniano em T . Analogamente se temos vk → v, então teremos o caminho v1 → v2 → · · · → vk → v.
• Observe que existe um vértice vi tal que vi → v → vi+1, onde 1 ≤ i ≤ k, pois caso contrário estaŕıamos em um
dos dois casos anteriores. Desta forma, podemos montar o caminho v1 → v2 → · · · → vi → v → vi+1 → · · · → vk
que também é hamiltoniano.
4. Prove o seguinte teorema: Um grafo simples é hamiltoniano se, e somente se, seu fecho hamiltoniano é hamiltoniano.
2
Resposta. Seja G = G0, G1, G2, . . . , Gℓ = [G] a sequência de adição de arestas onde [G] é o grafo resultado do fecho
hamiltoniano de G.
IDA (=⇒): Como G é hamiltoniano, então pode definição existe um ciclo hamiltoniano C em G. O fecho hamilto-
niano é obtido apenas por adição de arestas e não removeremos ciclos existentes. Como [G] contém todas as arestas
de G, o ciclo C também está em [G]. Portanto [G] é hamiltoniano.
Volta (⇐=): Suponha que o fecho hamiltoniano [G] de G é hamiltoniano. Pela definição de fecho hamiltoniano
temos que com Gi = Gi−1 + xiyi tal que xi e yi são não adjacentes e dGi
(xi) + dGi
(yi) ≥ n. Pelo Teorema de
Ore visto em sala temos que se Gi é hamiltoniano, então Gi−1 também será. Portanto todos os grafos da sequência
G = G0, G1, G2, . . . ,Gℓ = [G] serão hamiltonianos e Conclúımos que G é hamiltoniano.
3