gabarito_prova02_Parente-2023.2

Prévia do material em texto

R
as
cu
nh
o
UFBA
INSTITUTO DE COMPUTAÇÃO
MATA53 – Teoria dos Grafos – 2023.2
Professor: Roberto Freitas Parente
Gabarito – Prova 02
Questão 1 (3.0 pts). Defina formalmente os seguintes conceitos:
1. Grafo hamiltoniano e Caminho hamitoniano
Resposta. G é um Grafo hamiltoniano se contém um ciclo hamiltoniano. Um caminho hamiltoniano é
um caminho que passa por todos os vértices do grafo
2. Emparelhamento
Resposta. Um emparelhamento de G é um conjunto de arestas de G dois a dois disjuntos
3. Cobertura por vértices
Resposta. Q ⊂ V (G) é um cobertura de G se para todoa aresta xy ∈ E(G) temos que x ∈ Q ou
y ∈ Q.
4. Fecho hamiltoniano
Resposta. Definimos C(G) o fecho hamiltoniano de um grafo G com n vértices pelo grafo resultante do
seguinte procedimento: para toda xy ̸∈ E(G) tal que d(x) + d(y) ≥ n faça G = G+ xy.
5. Árvore Geradora
Resposta. Uma árvore geradora de um grafo G é um subgrafo gerador de G tal que é uma árvores
(conexo e aćıclic).
6. k-fator
Resposta. Um k-fator de G é um sugrafo gerador k-regular.
Questão 2 (2,0 pts). Prove o Teorema (Bondy–Chvátal’1976): Um grafo simples é hamiltoniano se, e somente
se, seu fecho hamiltoniano é hamiltoniano.
Resposta. IDA(⇒): Denotaremos [G] como o fecho hamiltoniano de um grafo G. Primeiro observe que
[G] possui o mesmo conjunto de vértices de G e seu conjunto de arestas é formado pelas arestas de G com,
possivelmente, arestas adicionadas, ou seja, temos G ⊆ [G] com V (G) = V ([G]). Então se existe um ciclo
hamiltoniano C em G, então C também será um ciclo hamiltoniano em [G].
VOLTA(⇐): Seja o fecho [G] constrúıdo tal que G = G1, G2, . . . , Gk = [G], onde todo Gi é o passo
da construção que adiciona uma aresta entre um par de vértice x, y ∈ V tal que d(x) + d(y) ≥ |V (Gi−1)|.
Precisamos mostrar apenas que se Gi é hamiltoniano, então Gi−1 é hamiltoniano. Para tal, basta observarmos
o Teorema de Ore apresentado em sala (Grafos hamiltonianos – II). Observe que Gi−1 satisfaz as hipóteses do
Teorema de Ore, então temos que se Gi é Hamiltoniano, então Gi−1 é hamiltoniano, pois existe u, v ∈ V tal
que d(v) + d(u) ≥ n. Desta forma, podemos aplicar em Gi e Gi−1 para i = 2, . . . , k e o resultado segue.
Questão 3 (2,0 pts). Duas pessoas jogam o seguinte jogo sob um grafo G: Jogador 1 começa pela escolha de
qualquer vértice. Cada escolha subsequente deve ser adjacente à escolha anterior do outro jogador. Desta forma,
juntos eles seguem um caminho. Um jogador ganha quando sua movimentação é a última rodada posśıvel. Prove
o seguinte:
1. O segundo jogador tem uma estratégia vencedora se G tem um emparelhamento perfeito; e
2. caso contrário o primeiro jogador tem um estratégia vencedora.
1
R
as
cu
nh
o
Resposta. Observe que se G tem um emparelhamento perfeito M significa que cada escolha do Jogador 1 de
x ∈ V permite que o Jogador 2 escolha o vértice y em que xy ∈ M . Desta forma, a estratégia do Jogador
2 será sempre escolher o vértice adjacente em que a aresta formada com a escolha do Jogador 1 estará no
emparelhamento M .
Seja M um emparelhamento máximo de G em que M não é perfeito. Como M não é perfeito, existe um
vértice em que não está no emparelhamento M e o Jogador 1 deverá escolhé-lo forçando jogador 2 a escolher um
vértice coberto por M (caso contrário M não seria máximo). A partir desse ponto o Jogador 1 poderá seguir
com a estratégia de sempre escolher o x ∈ V na vizinhança da escolha y ∈ V do Jogador 2 de forma a xy ∈ M .
Observe que o Jogador 1 sempre terá essa possibilidade pela maximalidade de M .
Questão 4 (3,0 pts). Prove ou dê um contraexemplo:
1. (1,0 pts) Todo grafo tem quantidade par de vértices com grau ı́mpar.
Resposta. Sabemos que ∑
v∈V (G)
dG(x) = 2|E(G)|.
Desta forma, temos que a soma dos graus de um grafo é par. Se tivéssemos uma quantidade ı́mpar de
vértices com graus ı́mpares então teŕıamos que
∑
d(x) seria ı́mpar.
2. (1,0 pts) Todo grafo conexo tem uma árvore geradora
Resposta. Como G é conexo, basta pegarmos um subgrafo maximal aćıclio de G.
3. (1,0 pts) Toda árvore é um grafo bipartido
Resposta. Sabemos por resultado visto em sala (König) que todo grafo sem ciclo ı́mpar é bipartido.
Como árvores são aciclicos, então árvores são bipartidos
Questão 5 (2,0 pts). Seja T uma árvore com n vértices e α(T ) = k. Determine o valor de α′(T ) em função
de n e k.
Obs: α e α′ são o tamanho do conjunto independente máximo e emparelhamento máximo respectivamente.
Resposta. Sabemos que toda árvore é um grafo bipartido. Desta forma, seja a bipartição (S, S̄) de T tal que
S é o conjunto máximo independente de T com k elemento. S̄ é uma cobertura mı́nima de T , pois ∀xy ∈ E(T )
teremos x ou y em S̄, caso contrário xy ∈ G[S], uma contradição com o fato de S ser um conjunto independente.
Como S̄ tem n−k elementos e pelo Teorema (König–Egerváry) visto em sala, temos que, em um grafo bipartido,
a cobertura mı́nima é igual ao emparelho máximo. Desta forma, temos que α′(T ) = β(T ) = |S̄| = n− k.
2