1
EXERCÍCIOS SOBRE GRAFOS
1a QUESTÃO
Dizer se as afirmativas abaixo são verdadeiras ou falsas, justificando.
1. O grafo K4 não é 2-conexo.
2. O grafo K5 não é embutido na esfera.
3. Se G é uma grafo e ω(G) = 2, então o diâmetro de G é infinito.
2a QUESTÃO
Seja um grafo G1 = (V(G1), E(G1), ψG1) com n vértices e m arestas e seja um outro grafo G2 = (V(G2), E(G2),
ψG2), também com n vértices e m arestas. Sabendo-se que V(G1) = V(G2), E(G1) = E(G2), ψG1 e ψG2 são dadas,
respectivamente pelas matrizes de incidência IG1 e IG2, faça um algoritmo para verificar se G1 e G2 são iguais.
3a QUESTÃO
Para o grafo mostrado a seguir, faça o que se pede com justificativa.
B
C
A
D
E
F
G
(a)
(b)
(c)
(d)
(e)
(f)
Calcule o seu centro;
Calcule o seu diâmetro;
Calcule a sua conectividade;
Calcule a sua conectividade de aresta;
Diga se ele é ou não hamiltoniano;
Diga se ele é ou não euleriano.
4a QUESTÃO
Para os digrafos a seguir diga se eles são unilateralmente conexos e/ou fortemente conexos, justificando.
c
a
c
b
a
b
2
5a QUESTÃO
Seja G1 um grafo e e uma aresta de G1. Sabe-se que ω(G1) = 1 e d(x,y) = 2, onde x e y são dois vértices de G1.
Após ser retirada a aresta e de G1, teremos um novo grafo G2, no qual d(x,y) = ∞. Diga se as afirmações abaixo
são verdadeiras ou falsas, justificando.
(a)
(b)
(c)
(d)
(e)
(f)
G1 não é necessariamente um grafo conexo.
A aresta e define um limite.
A quantidade de componentes conexas de G2 é indeterminada.
A conectividade de aresta de G1 é um e a de G2 é zero.
Os centros de G1 e G2 não são definidos.
O grafo G1 não é hamiltoniano.
6a QUESTÃO
Seja G1 um grafo com mais de uma aresta e seja e uma aresta de G1. Sabe-se que ω(G1) = 1. Após ser retirada a
aresta e de G1, teremos um novo grafo G2, no qual ω(G2) = 2. Diga se as afirmações abaixo são verdadeiras ou
falsas, justificando.
a.
b.
c.
d.
e.
Falta informações para afirmar que G1 é um grafo conexo.
A aresta e forma um ciclo em G1.
Pelo menos uma das extremidades da aresta e trata-se de um vértice de corte em G1.
Posso calcular a conectividade de aresta de G1 e de G2.
O diâmetro de G2 é infinito.
7a QUESTÃO
Para o grafo a seguir: 1) Diga se ele é ou não é hamiltoniano; 2) Ache uma orientação para ele de tal forma que o
mesmo se torne um digrafo unilateralmente conexo. Justifique as respostas.
8a QUESTÃO
Seja uma árvore T dada pela matriz de incidência IT. Tal árvore possui n vértices. Faça um algoritmo para calcular
a quantidade de vértices de corte dessa árvore.
9a QUESTÃO
Seja um digrafo D com n vértices e m arestas representado pela matriz de incidência ID. Faça um algoritmo para
calcular a quantidade de vértices sumidouros que D possui. Convém destacar que na matriz de incidência de um
digrafo, as arestas que incidem no vértice possui valor -1 e aquelas que emergem do vértice possuem valor 1.
10a QUESTÃO
Dizer se as afirmativas abaixo são verdadeiras ou falsas, justificando as falsas.
1. Todo grafo conexo não trivial possui pelo menos dois vértices com distância entre eles infinita.
2. O grafo K3,3 é embutido na esfera.
3. Qualquer vértice de uma árvore que não é folha é um vértice de corte.