Listas teoria dos grafos

Prévia do material em texto

UNINASSAU 
Professor: 
Bernardo Caldas 
Disciplina: 
TEORIA DOS GRAFOS 
LISTA DE 
EXERCÍCIOS 
Aluno 
 
Assinatura Matrícula Nota 
 
Código: 1 
Usando a terminologia de grafos, responda e/ou desenvolva as questões relativas ao grafo fornecido: 
O grafo é simples? - O grafo é completo? - O grafo é conexo? – Encontre dois caminhos do nó 3 para 6 no grafo. – 
Encontre um ciclo no grafo. – Qual arco deve ser removido para o grafo tornar-se acíclico? – Qual arco deve ser 
removido para o grafo tornar-se não conexo? – Qual o tamanho do grafo? – Qual a ordem do grafo? – Qual a função 
g que associa a cada arco as suas extremidades? – Quais os nós adjacentes ao nó 5? – Quais os arcos adjacentes 
ao nó 3? – Qual o grau do nó 3? – O nó 7 é acessível ao nó 1? – Esboce um subgrafo do grafo fornecido. – Qual a 
distância de cada nó aos demais? – O grafo é regular? – O grafo é planar? – Qual a matriz de incidência do grafo? 
Qual a lista de adjacência do grafo? Faça a coloração do grafo usando o número cromático de cores. 
 
 
 
(X)a – resposta válida com a apresentação dos desenhos e respostas 
Obs.: é só ver o material fornecido 
 
Código: 2 
Esboce um desenho para cada um dos grafos indicados a seguir: 
a. Um grafo simples com três nós, cada um com grau 2. 
b. Um grafo com quatro nós e ciclos de comprimento 1, 2, 3 e 4. 
c. Um grafo não completo com quatro nós, cada um de grau 4. 
 
(X)a – resposta válida com a apresentação dos desenhos 
Obs.: problema 3 pagina 451 
 
Código: 3 
Desenhe um K3,4 e indique um ciclo 
 
(X)a – resposta válida com a apresentação do desenho e indicação 
Obs.: problema 6 pagina 451 
 
Código: 4 
Desenhe um grafo com cada uma das características apresentadas abaixo, ou explique por que não existe tal grafo: 
a) Quatro nós de graus 1, 2, 3 e 4, respectivamente 
b) Simples com quatro nós de graus 1, 2, 3 e 4, respectivamente 
c) Quatro nós de graus 2, 3, 3 e 4, respectivamente 
d) Quatro nós de graus 2, 3, 3, e 3, respectivamente 
e) Grafo com 6 nós, 3 regular 
 
(X)a – resposta válida com a apresentação do desenho e/ou explicações 
Obs.: problema 7 pagina 451 
 
 
Código: 5 
Considerando que sejam retirados o(s) dígito(s) zero(s) de sua matrícula (se existir(em)) e que o número 
remanescente corresponda ao total de nós do grafo, (seja a matricula 011023409 => 112349 n° de nós). Calcule o 
número de arcos que esse grafo possuirá. 
 
(X)a – resposta válida com a apresentação dos cálculos 
Obs.: aplicar => n(n-1)/2 
 
Código: 6 
Grafos isomorfos são grafos idênticos embora suas aparências sejam diferentes. Do exposto, quais dos grafos 
apresentados não é isomormo aos outros, e por quê? E no caso de haver isomorfismo entre os grafos, apresente as 
funções de transformações. 
 
 
 
 
(X)a – resposta válida com a apresentação das justificativas e funções 
Obs.: problema 13 pagina 453 
 
Código: 7 
Faça o desenho de um grafo K2,3 e mostre que ele é planar. 
 
(X)a – resposta válida com a apresentação do desenho e justificativa e funções 
Obs.: problema 27 pagina 455 
 
Código: 8 
Desenhe o grafo representado pela matriz de adjacência. 
 
 
 
(X)a – resposta válida com a apresentação do desenho do grafo 
Obs.: problema 48 da pagina 457 
 
Código: 9 
Desenhe a lista de adjacência para o grafo direcionado com pesos da figura abaixo. 
 
 
 
 
(X)a – resposta válida com a apresentação da lista de adjacência 
Obs.: problema 60 da pagina 457 
 
Código: 10 
Desenhe o dual do mapa a seguir. 
 
 
 
 
(X)a – resposta válida com a apresentação do desenho dual do grafo 
Obs.: problema 79 da pagina 459 
 
Código: 11 
Desenhe os grafos complementares das imagens. 
 
 
 
 
(X)a – resposta válida com a apresentação dos grafos complementares 
Obs.: 
 
Código: 11 
Responda as questões referentes as figuras ‘a’ e figura ‘b’ 
 
a) O grafo ‘a’ é regular? Por quê? 
b) Existe alguma fonte ou sumidouro no grafo ‘b’? 
 
 
 
 
(X)a – resposta válida com as justificativas 
Obs.: