Lista de Exercícios - Teoria dos Grafos (com respostas)

Prévia do material em texto

Lista de Exercícios 06
Teoria dos Grafos e Análise Combinatória
(com respostas)
Rodrigo Machado
rma@inf.ufrgs.br
2015/1
1. Considere o seguinte grafo simples G. Determine:
G = a b
c d e
f g h
(a) Grau mínimo e máximo de G.
δ(G) = 2 ∆(G) = 5
(b) Bipartido?
Não, pois possui um triângulo (de vértices a, d e e).
(c) Tripartido?
Sim, pois temos a seguinte tripartição: {a, b, h}, {d, g}, {c, e, f}
(d) Existência ou não de circuitos/trilhas eulerianas (com justificativa).
Como há exatamente dois nodos com um número ímpar de elementos (c e d), há uma
trilha aberta euleriana. Portanto, o grafo é semi-euleriano.
Trilha euleriana: c, a, g, c, d, a, f, b, e, d, f, g, h, d
(e) Existência ou não de caminhos/ciclos hamiltonianos (com justificativa).
Possui ciclo hamiltoniano, portanto o grafo é hamiltoniano.
Ciclo hamiltoniano: g, h, d, e, b, f, a, c, g
(f) Planar ou não planar?
Não planar, pois possui uma extensão de K3,3 com bipartição {a, d, g} e {c, e, f}.
1
2. Considere o seguinte grafo simples com pesos H.
H = a 3
1
5
b
2
3
c 6
4
d
4
e2
4
7
f 3 g
1
h2
3
(a) Existe solução para o problema do caixeiro viajante?
Sim, pois é hamiltoniano.
Ciclo hamiltoniano: c, g, f, a, b, e, h, d, c
(b) Determine a árvore geradora mínima do grafo (usando Prim ou Kruskal)
AGM(H) = a
1
b
2
c
4
d e2
f 3 g
1
h2
(c) Utilize o algoritmo de Dijkstra e calcule as distâncias partindo de c para qualquer
outro nodo do grafo.
a 6
b 7
c 0
d 5
e 7
f 7
g 4
h 6
(d) Determine se o grafo em questão é planar ou não.
Sim, apresentado pela imersão abaixo:
H = a
d e b
f c g h
2
3. Prove que todo grafo prisma – resultado do produto Cn×P2 (para algum n ≥ 3) – possui
caminho hamiltoniano.
Cada grafo prisma é composto por dois ciclos a1, a2, . . . , an, a1 e b1, b2, . . . , bn, b1, ligados
ponto a ponto (ai conectado a bi para todo 1 ≤ i ≤ n).
Dessa forma, temos sempre o ciclo hamiltoniano descrito abaixo:
a1, a2, . . . , an, bn, bn−1, . . . , b1, a1
4. Considere o dígrafo D determinado pela seguinte matriz de incidência.
A B C D E F
1 2 0 0 0 0 0
2 1 −1 0 0 0 0
3 −1 0 1 0 0 0
4 0 1 0 −1 0 0
5 0 1 −1 0 0 0
6 0 0 1 −1 0 0
7 0 1 0 0 −1 0
8 0 0 0 1 −1 0
9 0 0 0 1 0 −1
10 0 0 0 −1 1 0
(a) Apresente uma representação gráfica para D.
A
��
// B
��
//
 
E
��
C
__
// D
OO
// F
(b) Apresente um componente fortemente conexo maximal de D.
Qualquer um dos próximos: {A,B,C}, {E,D}, {F}.
(c) Apresente algum clique maximal de D (conectividade forte).
O subgrafo induzido por {E,D} ou os vértices {B}, {C}, {A}, {F}.
(d) Calcule uma tabela de distâncias de B para qualquer nodo do grafo (respeite direção
das setas).
A 2
B 0
C 1
D 1
E 1
F 2
3
(e) D é hamiltoniano? Se for, apresente o ciclo hamiltoniano. Se não for, qual o menor
número de arestas direcionadas que devem ser adicionadas para que ele se torne
hamiltoniano (e quais seriam elas) ?
O grafo é semi-hamiltoniano, pois possui o caminho aberto C, A, B, E, D, F. Se
adicionarmos somente uma aresta F → C ele se torna hamiltoniano.
5. Seja G o grafo simples subjacente ao dígrafo D (desconsidere possíveis loops e arestas
paralelas), apresentado na questão anterior. Determine as seguintes questões sobre G:
G = A B E
C D F
(a) G é bipartido?
Não, pois possui triângulo.
(b) G é cíclico?
Sim. Ciclo: A, B, C, A.
(c) G é conexo?
Sim.
(d) G é hamiltoniano? Se não for, G é semi-hamiltoniano?
Semi-hamiltoniano. Caminho: C, A, B, E, D, F.
(e) G é euleriano? Se não for, G é semi-euleriano?
Semi-euleriano: Trilha: C, A, B, C, D, B, E, D, F.
(f) Quais os graus mínimo e máximo de G? Ele é regular?
δ(G) = 1, ∆(G) = 4, não-regular.
(g) Considerando G, quantas árvores geradoras o subgrafo induzido por {A,B,E,D, F}
possui?
Três (formas de abrir o ciclo B,E,D,B).
(h) G é planar? Se não for planar, apresente uma justificativa. Se for planar, qual o
número mínimo de arestas que devemos adicionar para que ele se torne não-planar?
Planar (conforme imersão acima).
(i) Qual o número cromático de G?
χ(G) = 3.
(j) Qual o número cromático de G ∪ ({B,E, F}, {{B,F}, {E,F}})?
χ(G ∪ ({B,E, F}, {{B,F}, {E,F}})) = 4.
4
6. Determine, dentre os três grafos a seguir, os dois grafos que são isomorfos. Apresente o
isomorfismo que confirma essa afirmação.
São isomorfos o primeiro e o segundo grafos.
Isomorfismo:
d→v
c→w
a→y
b→t
h→x
g→u
e→s
f→z
7. Um grafo floresta possui 100 nodos e 92 arestas. Quantos componentes conexos existem?
Como florestas são acíclicas, cada inserção de aresta acaba conectando dois componentes
conexos, reduzindo em 1 o número de componentes. Portanto, há 100-92 = 8 componentes
conexos no grafo em questão.
5