Lista3 -Teoria os Grafos

Prévia do material em texto

UFG - Instituto de Informática Teoria dos Grafos
PPGCC Profa. Erika Coelho1
3
a
Lista de Exercícios – 2022.1
Conectividade
1. Escreva um algoritmo para determinar se um vértice é ponto de articulação ou vértice de corte.
2. Seja T uma árvore e v um vértice de T tal que d(v) ≥ 2. É verdade que v é uma articulação? Justifique.
3. É verdade que todo grafo sem articulações não tem pontes? É verdade que todo grafo sem pontes não
tem articulações? Justifique.
4. Determine κ(G) e κ′(G) no grafo abaixo.
5. Determine κ(G) e κ′(G) nos grafos abaixo.
6. Uma empresa possui nove computadores conectados em rede. Isto possibilita que os funcionários
compartilhem recursos e consigam colaborar melhor para o desempenho de suas tarefas dentro da
empresa. No entanto, as máquinas não estão diretamente conectadas todas entre si. Por economia
de recursos, a topologia de rede adotada apresenta apenas um subconjunto das conexões possíveis. A
figura abaixo mostra as conexões entre as nove máquinas da empresa.
Note que as conexões são sempre bidirecionais. Apesar de alguns computadores não estarem direta-
mente conectados entre si, eles ainda conseguem se comunicar porque existe um algoritmo de rotea-
mento capaz de conectar dois computadores através de várias conexões diretas. No entanto, freqüen-
temente as máquinas precisam passar por uma revisão de rotina. Quando alguma máquina está em
manutenção, ela precisa ser temporariamente desconectada da rede e levada para a oficina. Assim, o
algoritmo de roteamento não tem mais como estabelecer conexões utilizando este computador, o que
1
e-mail: erikamorais@inf.ufg.br
pode acabar desconectando duas ou mais partes da rede e prejudicando o trabalho na empresa. A em-
presa deseja saber o número mínimo de máquinas que se retiradas podem desconectar a rede. Justifique
sua resposta mostrando como e qual ferramental teórico você usou para resolver o problema.
7. Considere o grafo abaixo e faça o que se pede:
s
t
(a) Encontre 3 caminhos aresta-disjuntos entre s e t.
(b) Quantos caminhos internamente disjuntos há entre s e t.
(c) Encontre um corte de arestas contendo 3 arestas que separe s e t.
8. Prove que se v é um vértice de corte de um grafo G então existem dois vértices u e w, diferentes de v,
tal que v está em todo caminho u− w de G.
9. Seja G um grafo com n vértices, onde n ≥ 2. Prove que G tem pelo menos dois vértices que não são
de corte.