PUC-Rio Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão Período: 2004.1
2 de junho de 2004
ESTRUTURAS DISCRETAS (INF 1308)
1o Trabalho
Considere o problema abaixo:
-
Dado um grafo conexo não orientado G=(V,E), implemente um algoritmo
para encontrar um vértice cuja retirada do grafo deixe o grafo conexo. Em outras
palavras, seja v este vértice e d (v) o conjunto das arestas com uma
extremidade em v, então G'=( V - { v }, E - d (v) ) é conexo.
O algoritmo que você deve implementar segue:
Passo 1
Utilizando um algoritmo para percorrer os elementos de um grafo (Busca em Largura ou
Busca em Profundidade), obtenha uma árvore geradora qualquer. Armazene esta árvore
em um vetor com |V| posições, onde cada posição corresponde a um vértice e o conteúdo
indica o vértice ao qual este vértice está ligado na árvore. (Como a árvore só tem
|V|-1 arestas, um dos vértices não precisa ter seu campo preenchido. Por exemplo,
podemos ter vetor[1]=-1, com os demais definindo árvore).
Passo 2
Determine o grau de cada vértice nesta árvore encontrada.
Passo 3
Para cada vértice com grau 1 nesta árvore,
execute um algoritmo que retira este vértice do grafo e testa para todos os pares
dos vértices restantes se existe caminho entre eles.
Passo 4
Para cada vértice com grau 2 nesta árvore (se houver),
execute um algoritmo que retira este vértice do grafo e testa para todos os pares
dos vértices restantes se existe caminho entre eles.
-
Você deve executar este algoritmo para muitos grafos aleatórios com número de
vértices menor ou igual a 10. Apresente uma tabela com o número de vértices de grau
1 e de grau 2. Indique também para quantos dos vértices de grau 2 retirados, o grafo
ficou continuou conexo.
- Finalmente, escolha 2 grafos onde a retirada de um vértice de grau 2 deixou o grafo
desconexo. Desenhe o grafo, a árvore obtida e o grafo sem o vértice que o desconecta.
- Sua tabela deve conter pelo menos 10 grafos diferentes.
This document was translated from LATEX by HEVEA.