Lista de Atividades I

Prévia do material em texto

Faculdade Pitágoras - São Luís 
Curso: Ciência da Computação - 6º Período - Noturno 
Disciplina: Teoria dos Grafos 
Professor: Darlan Quintanilha 
Aluno: 
 
Lista de Atividade 1 
1. Faça a representação gráfica dos seguintes grafos G(V, A): 
 
a) V = {A, B, C, D}, A = { }. 
b) V = {1,2,3,4,5,6,7,8}, A = {(1,2),(2,2),(2,3),(3,4),(3,4),(3,5),(6,7),(6,8),(7,8)}. 
 
2. Um escultor deseja criar uma escultura que represente a paz mundial. Para isto, ele esculpirá 7 
pilares (um para cada continente) e os colocará em um círculo. Depois, ele esticará um fio de 
ouro entre os pilares, de forma que, cada pilar estará conectado a 3 outros pilares. Embora a 
ideia seja boa, a escultura é impossível. Porquê? 
 
3. Quantos vértices um grafo simples precisa ter para poder ter 200 arestas? 
 
4. Considere o grafo abaixo e responda as seguintes perguntas: 
 
a) O grafo é simples? 
b) O grafo é completo? 
c) O grafo é conexo? 
d) É possível encontrar dois caminhos do nó 3 para o nó 6? 
e) É possível encontrar um ciclo? 
f) É possível encontrar um arco cuja remoção transforma o grafo em um grafo acíclico? 
g) É possível encontrar um arco cuja remoção transforma o grafo em um grafo não-conexo? 
 
5. Escreva a sequência de graus para os grafos a, b e c. 
 
6. Esboce um grafo com as seguintes características: 
a) simples com 3 nós, cada um com grau 2; 
b) 4 nós e ciclos de comprimento 1, 2, 3 e 4; 
c) não completo com 4 nós, cada um com grau 4. 
 
7. Seja G o seguinte grafo: 
 
Quais dos seguintes grafos são subgrafos de G? 
 
 
8. Observe o seguinte grafo direcionado abaixo e responda as seguintes perguntas: 
 
 
 
a) Quais são os nós acessíveis a partir do nó 3? 
b) Qual o caminho mais curto do nó 3 para o nó 6? 
 
9. Forneça exemplos: 
a) Grafo bipartido e regular; 
b) Grafo em que k(G) < grau(G). 
 
10. Falso ou verdadeiro? (Justifique). 
a) Se G é um grafo desconexo, então seu complemento G é conexo. 
b) Se G é um grafo com exatamente dois vértices de grau ímpar, então existe um caminho 
ligando estes vértices em G. 
 
11. Indique quais grafos abaixo são bipartidos. 
 
 
12. Classifique cada uma das seguintes informações como verdadeiras ou falsas: 
a) Se G e H são grafos isomorfos, então eles possuem o mesmo número de vértices e o mesmo 
número de arestas. 
b) Se G e H possuem o mesmo número de vértices e arestas, então eles são isomorfos. 
c) Se G e H são grafos isomorfos, então eles possuem a mesma sequência de graus. 
d) Se G e H possuem a mesma sequência de graus, então eles são isomorfos? 
 
13. Diz que um grafo é auto-complementar se ele for isomorfo ao seu complemento. 
a) Dê exemplo de um grafo simples, com 4 vértices, que seja auto-complementar. 
b) Dê exemplo de um grafo simples, com 5 vértices, que seja auto-complementar. 
c) Verifique que não há grafos auto-complementares com 2 nem 3 vértices 
d) Quantas arestas deve ter um grafo auto complementar que possui n vértices? 
 
14. Dado o grafo orientado G abaixo, calcule as funções N+ e N- (vizinhos sucessores e antecessores) 
e para cada vértice de G, e, posteriormente, calcule as componentes fortes do grafo. 
 
15. Para o grafo da figura abaixo, apresente a sequência de vértices após a aplicação da DFS a partir 
do vértice 7, assim como a árvore de profundidade. Considere a representação por listas de 
adjacências em ordem numérica.