gabarito-pr1-grafos

Prévia do material em texto

IC/UFF - Teoria dos Grafos
Primeira Prova - 04/10/12
1. (1,0) Falso ou verdadeiro? (Justifique) Se G é um grafo desconexo,
então seu complemento G é conexo.
Verdadeiro. Se dois vértices x e y estão em componentes conexas dis-
tintas de G, então existe uma aresta entre eles em G. Se x e y estão
numa mesma componente conexa de G, então existe um caminho xuy
em G, onde u é um vértice em outra componente qualquer de G. Em
qualquer caso, existe caminho entre x e y em G, de onde conclúımos
que G é conexo.
2. (1,0) Falso ou verdadeiro? (Justifique) Não existe grafo 3-regular com
7 vértices.
Verdadeiro. Em todo grafo o número de vértices de grau ı́mpar tem
que ser par.
3. (1,0) Falso ou verdadeiro? (Justifique) Se G é um grafo conexo, e f é
uma aresta que pertence a toda árvore geradora de G, então f é uma
ponte.
Verdadeiro. Se f não fosse um ponte, estaria contida em um ciclo C,
e então G − f seria conexo e admitiria uma árvore geradora T sem a
aresta f (absurdo – T seria árvore geradora de G também).
4. (1,0) Falso ou verdadeiro? (Justifique) SeG é um grafo com exatamente
dois vértices de grau ı́mpar, então existe um caminho ligando estes
vértices em G.
Verdadeiro. G admite um passeio Euleriano aberto entre estes vértices
(digamos, x e y). Eliminando os trechos deste passeio que retornam a
um vértice já percorrido, obtemos um caminho entre x e y.
5. (2,0) Para quais valores de k o grafoK3,3 possui um corte com k arestas?
(Justifique.)
Para k = 3, 4, 5, 6 e 9. Assuma que os vértices do grafo K3,3 se dividam
em dois conjuntos estáveis U e V . Seja [S, S] um corte neste grafo, e
escreva k =| [S, S] |. Se S contém apenas um vértice, então k = 3. Se
S contém apenas dois vértices de U , então k = 6. Se S = U , então
k = 9. Se S contém um vértice de U e outro de W , então k = 4. Se S
contém dois vértices de U e um de W , então k = 5. Os demais casos
seguem por simetria.
6. (2,0) Calcule κ(G) e κ′(G) para o grafo G abaixo.
Temos κ(G) = 2 (considere a retirada dos dois vértices a e b que estão
fora dos 3 hexágonos centrais) e κ′(G) = 2 (considere a retirada das
duas arestas que ligam o hexágono de cima aos vértices a e b).
7. (2,0) O grafo da questão anterior possui ciclo hamiltoniano? Possui
caminho hamiltoniano? Justifique suas respostas.
O grafo não é hamiltoniano, pois, para o subconjunto S = {a, b}, te-
mos 2 = |S| < 3 = ω(G − S). Mas é fácil ver que possui caminho
hamiltoniano, basta listar.
8. (2,0) Desenhe um grafo 3-regular que não possua emparelhamento per-
feito.