AV1 Lista 2

1.
AV1 - LISTA 2 DE TEORIA DOS GRAFOS
1 AV1 - Lista 2 de Teoria dos Grafos
Instruções
A lista pode ser feita digitada ou manuscrita, mas deve ser entregue em formato físico, com prazo limite em
17/09.
Toda e qualquer dúvida sobre interpretação pode ser retirada em aulas ou com o envio de torpedos.
Boa avaliação!
Questões
Exercício 1
Uma rede de computadores possui cinco dispositivos: D1, D2, D3, D4 e D5, que estão conectados
segundo a lista:
• D1: conectado a D2, D3 e D5
• D3: conectado a D1 e D4
Sobre esta rede, faça o que se pede:
(a) Apresente uma matriz de adjacência para o grafo formado por esta rede.
(b) Dizemos que duas máquinas estão a dois passos, se ambas são vizinhas de uma mesma máquina. Por
exemplo, D2 e D3 estão a dois passos, pois D1 é adjacente a ambas. Apresente o grafo cujos vértices são as
máquinas, se são ligadas por aresta se estão a dois passos.
(c) Qual a matriz de adjacência do grafo apresentado em (b)?
(d) Qual a relação entre as matrizes apresentadas nos itens (a) e (c)?
Exercício 2
Considere o grafo a seguir:
(a) Neste grafo existe um emparelhamento completo? Justifique.

(b) Neste grafo existe um circuito euleriano? Justifique.
(c) Neste grafo existe um caminho hamiltoniano? Justifique.
1
Exercício 3
O grafo a seguir modela uma rede viária nas proximidades de uma usina nuclear situada em 𝑠.
No caso de emergência, os moradores das proximidades de 𝑠 devem se deslocar ao vértice 𝑡, onde haverá
abrigo.
(a) Seja 𝑛 uma quantidade de vértices mínima cuja remoção faz com que não exista caminho saindo de 𝑠
e chegando em 𝑡.
(b) Apresente 𝑛 caminhos de 𝑠 para 𝑡 distintos e que não compartilham de nenhum vértice.
Exercício 4
Dado um grafo 𝐺 = (𝑉 , 𝐸(𝐺)), denotamos o complementar, 𝐺 = (𝑉 , 𝐸(𝐺)), o grafo no mesmo conjunto

de vértices de 𝐺, mas satisfazendo:
𝑢𝑣 ∈ 𝐸(𝐺) ⇔ 𝑢𝑣 ∉ 𝐸(𝐺).
Determine o número cromático do grafo complementar de um ciclo de 6 vértices.
2
1. AV1 - LISTA 2 DE TEORIA DOS GRAFOS
Exercício 5
Nos algoritmos de rota mais curta, temos um grafo 𝐺 com arestas ponderadas. Em geral estes pesos
são positivos, mas para algumas aplicações é possível que as arestas tenham pesos negativos. Entretanto,
para que possamos de fato encontrar uma rota mais curta, o grafo não pode ter ciclos cuja soma dos pesos é
negativa, chamado de ciclo negativo.
Para modelar um grafo com peso nas arestas, adaptamos a matriz de adjacência 𝑀 = (𝑚[𝑖][𝑗]) onde:
{
0, se não existe aresta 𝑖, 𝑗
𝑚[𝑖][𝑗] =
𝜔𝑖,𝑗 , se existe a aresta e esta tem peso 𝜔𝑖,𝑗
Considere o grafo de vértices 1, 2, … , 7 cuja matriz de adjacência é:
⎡ 0 −3 4 0 0 0 0⎤
⎢−3 0 1 4 −2 0 0⎥
⎢4 1 0 −6 0 −4 5⎥
⎢ ⎥
𝑀 =⎢0 4 −6 0 3 2 0⎥
⎢ 0 −2 0 3 0 −3 2⎥
⎢0 0 −4 2 −3 0 5⎥
⎢ ⎥
⎣0 0 5 0 2 5 0⎦
Verifique se este grafo possui ciclo negativo. Em caso afirmativo, indique os vértices do ciclo. Em caso
negativo, indique os vértices do ciclo de menor soma de pesos das arestas.

AV1 Lista 2

Enviado por

Direitos autorais:

Formatos disponíveis

AV1 Lista 2

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

AV1 Lista 2

Enviado por

Direitos autorais:

Formatos disponíveis

1.

AV1 - LISTA 2 DE TEORIA DOS GRAFOS

1 AV1 - Lista 2 de Teoria dos Grafos

Considere o grafo a seguir:

(a) Neste grafo existe um emparelhamento completo? Justifique.

Dado um grafo 𝐺 = (𝑉 , 𝐸(𝐺)), denotamos o complementar, 𝐺 = (𝑉 , 𝐸(𝐺)), o grafo no mesmo conjunto

Considere o grafo de vértices 1, 2, … , 7 cuja matriz de adjacência é:

Você também pode gostar