ListaTG09_Exercicios

Prévia do material em texto

Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
Teoria dos Grafos 
Lista 1 de Exercícios 
 
Profa. Eliane Oliveira Santiago 
 
1. Escolha seis questões dos conteúdos online, módulos 1 e 2 e I e II Complementar, responda 
e justifique suas respostas. Esta atividade vale até 1.0 ponto. 
 
1) Podemos afirmar que a soma dos graus dos vértices de um grafo G não direcionado, é 
sempre um número: 
a) maior que 4 
b) par 
c) ímpar 
d) primo 
e) igual ao seu número de arestas. 
A resposta correta é: B. por conta do número par. Ela possui duas arestas. 
 
2) Um grafo completo simples indicado por K7: 
A) possui 7 arestas. 
B) possui 21 vértices (ou nós). 
C) possui 21 arestas. 
D) é isomorfo ao grafo K5. 
E) é isomorfo ao grafo K9. 
A resposta correta é: C. o grafo K7 possui 21 arestas. 
 
3) Considere as afirmativas: 
Afirmativa 1: A única condição para que um grafo seja chamado de simples é não ter laços 
ou loop. 
Afirmativa 2: A única condição para que um grafo seja chamado de simples é não aestas 
paralelas. 
Afirmativa 3: Um grafo completo simples é aquele que cada vértice liga-se a todos os outros 
apenas em uma arestas. 
É correto afirmar: 
A) Apenas afirmativa 1 é verdadeira. 
B) Apenas afirmativa 2 é verdadeira. 
C) Apenas afirmativa 3 é verdadeira. 
D) Todas as afirmativas são verdeiras. 
E) Todas as afirmativas são falsas. 
A resposta correta é: C. a afirmativa 3 é verdadeira. Um grafo completo simples é aquele que 
cada vértice liga-se a todos os outros apenas em uma arestas. 
 
4) Analise as condições para um grafo. 
Condição 1: Não existe laços nem arestas paralelas. 
Condição 2: Cada vertice tem aresta com todos outros. 
Condição 3: Sendo n o néumero vertices o número de aresta é n.(n-1)/2. 
Para que um grafo seja considerado completo. 
a) Apenas a condição 1 é verificada. 
b) Apenas a condição 2 é verificada. 
c) Apenas a condição 2 é verificada. 
d) Não é necessário a verificação de nenhum das condições. 
e) As 3 condições são verificadas. 
A resposta correta é: E. as 3 condições são verificadas e corretas. 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
5) Análise as condições para um grafo. 
Condição 1: Não existe laços nem arestas paralelas. 
Condição 2: Cada vértice tem aresta com todos outros. 
Condição 3: Sendo n o número vértices o número de aresta é n. (n-1)/2. 
Para que um grafo seja considerado simples. 
a) É necessário que a condição 1 seja satisfeita. 
b) É necessário que a condição 2 seja satisfeita. 
c) É necessário que a condição 3 seja satisfeita. 
d) Não é necessário que nenhuma das condições. 
e) É necessário que a todas as condições sejam satisfeitas. 
A resposta correta é: A. condição 1 seja satisfeita. 
 
6) Uma grafo compleo de 7 vértices chamado de K7 possui: 
A) 7 arestes. 
B) 14 arestas. 
C) 15 arestas. 
D) 20 arestas. 
E) 21 arestas. 
A resposta correta é: E. 21 arestas. 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
Teoria dos Grafos 
Lista 2 de Exercícios 
 
Profa. Eliane Oliveira Santiago 
 
1) Escreva um programa para ler como entrada uma matriz de adjacências de um grafo e 
responder as seguintes perguntas? 
 
a) Quais são as arestas do grafo? 
b) É um dígrafo ou um grafo não-direcionado? 
c) Qual é o grau de cada vértice? 
d) O grafo é conexo ou desconexo? 
e) O grafo é cíclico ou acíclico? 
f) Qual é a lista de adjacências do mesmo grafo? 
 
package Exercicio1; 
 
import java.util.ArrayList; 
 
public class Exercicio1 { 
 public static <T> String joinLista(ArrayList<T>[] listaAdjacencia) { 
 String strJoin = ""; 
 for (int i = 0; i < listaAdjacencia.length; i++) { 
 strJoin += (i > 0 ? "\n" : "") + "[" + i + "]: {"; 
 for (int j = 0; j < listaAdjacencia[i].size(); j++) { 
 strJoin += (j > 0 ? ", " : "") + 
listaAdjacencia[i].get(j); 
 } 
 strJoin += "}"; 
 } 
 return strJoin; 
 } 
 
 public static String joinMatriz(int[][] matriz) { 
 String strJoin = ""; 
 for (int i = 0; i < matriz.length; i++) { 
 strJoin += (i > 0 ? ",\n" : "") + "\t{"; 
 for (int j = 0; j < matriz[i].length; j++) { 
 strJoin += (j > 0 ? ", " : "") + matriz[i][j]; 
 } 
 strJoin += "}"; 
 } 
 return "{\n" + strJoin + "\n}"; 
 } 
 
 public static void main(String[] args) { 
 System.out.println("---------------------- Exercicio 1 ----------
------------"); 
 
 int[][] matrizAdjacencia = { 
 {0, 1, 1, 1}, 
 {0, 0, 1, 1}, 
 {0, 0, 0, 1}, 
 {0, 0, 0, 0}, 
 }; 
 GrafoMatriz grafo1 = new GrafoMatriz(matrizAdjacencia); 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 System.out.println("\nGrafo de entrada: " + 
joinMatriz(matrizAdjacencia)); 
 System.out.println("\nGrafo \"corrigido\": " + 
joinMatriz(grafo1.getGrafo())); // é corrigido porque preenche os lugares 
que não foram espelhados as conexões 
 
 System.out.println("\na) Quais são as arestas do grafo? \nR: " + 
joinMatriz(grafo1.getArestas()).replaceAll("[\t\n]+", " ")); 
 // OBS: mudei o verbo "É" para "Era" porque a análise foi feita 
em cima da matriz de entrada, que fica diferente da matriz "corrigida", como 
foi dito anteriormente 
 // OBS: Após a correção, o grafo por passa a se tornar não-
direcionado (caso não fosse); por esta razão a quantidade de arestas no 
exercicio a) não foi repetido no "vice-versa" 
 System.out.println("\nb) Era um dígrafo ou um grafo não-
direcionado? \nR: " + (grafo1.isEntradaDigrafo() ? "Dígrafo" : "Grafo não-
direcionado")); 
 System.out.println("\nc) Qual é o grau de cada vértice? \nR: " + 
grafo1.joinGrau()); 
 System.out.println("\nd) O grafo é conexo ou desconexo? \nR: " + 
(grafo1.isConexo() ? "Conexo" : "Desconexo")); 
 System.out.println("\ne) O grafo é cíclico ou acíclico? \nR: "); 
 System.out.println("\nf) Qual é a lista de adjacências do mesmo 
grafo? \nR: " + joinLista(grafo1.getListaAdjacencia())); 
 } 
} 
 
 
2) Escreva um programa que receba como entrada um número inteiro n correspondente ao número 
de vértices e apresente como saída a matriz e a lista de adjacências para o grafo completo Kn. 
package Exercicio2; 
 
import Exercicio1.Exercicio1; 
 
public class Exercicio2 { 
 public static void main(String[] args) { 
 System.out.println("---------------------- Exercicio 2 ----------
------------"); 
 
 final int N = 4; 
 int[][] matrizKn = new int[N][N]; 
 for (int i = 0; i < matrizKn.length; i++) { 
 for (int j = 0; j < matrizKn[i].length - (matrizKn.length - 
1 - i); j++) { 
 if (i == j) { 
 matrizKn[i][j] = 0; 
 continue; 
 } 
 matrizKn[i][j] = 1; 
 matrizKn[j][i] = 1; 
 } 
 } 
 
 System.out.println("\nGrafo completo K"+N + ": " 
+Exercicio1.joinMatriz(matrizKn)); 
 } 
} 
package Exercicio1; 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
import java.util.ArrayList; 
 
public class GrafoMatriz { 
 private int[][] grafo; 
 private ArrayList<Integer>[] listaAdjacencia; 
 private int[] grau; 
 private int[][] arestas; 
 private int qtdArestas; 
 
 private boolean entradaDigrafo; 
 private boolean conexo; 
 
 public GrafoMatriz(int[][] grafo) { 
 
 // O Algoritmo abaixo serve para ajuster o grafo caso haja 
inconformidade na definição da matriz (que deve ser quadrada) 
 // Ex: Vertices {A, B, C}; porém a matriz não é 3x3, então com 
base nos vertices indicados, 
 // será preenchido corretamente a matriz 3x3 conectando todos os 
vertices que foram definidos. 
 // 
 // O algoritmo abaixo também complementa as conexões de origem 
com a final (caso vc se esqueça de colocar) 
 // Ex: se você conectar A com B e esquecer de especificar na 
matriz o B com A, ele especifica automaticamente 
 // ou seja, a matriz { {0, 1}, {0, 0} } ficará { {0, 1}, {1, 0} } 
 qtdArestas = 0; 
 conexo = true; 
 entradaDigrafo = true; 
 int maxLength = grafo.length; 
 for (int i = 0; i < grafo.length; i++) { 
 if (grafo[i].length > maxLength){ 
 maxLength = grafo[i].length; 
 } 
 } 
 int[][] fixedGraph = new int[maxLength][maxLength]; 
 int[] grau = new int[maxLength]; 
 for (int i = 0; i < fixedGraph.length; i++) { 
 for (int j = 0; j < fixedGraph.length; j++) { 
 fixedGraph[i][j] = 0; 
 } 
 } 
 
 ArrayList<int[]> arestas = new ArrayList<int[]>(); 
 listaAdjacencia = new ArrayList[maxLength]; 
 
 for (int i = 0; i < grafo.length; i++) { 
 grau[i] = 0; 
 listaAdjacencia[i] = new ArrayList<Integer>(); 
 for (int j = 0; j < grafo[i].length; j++) { 
 if (i == j) continue; 
 
 if (fixedGraph[i][j] == 1) { 
 grau[i]++; 
 listaAdjacencia[i].add(j); 
 continue; 
 } 
 if (i == maxLength - 1) continue; 
 if (grafo[i][j] >= 1) { 
 if (grafo[j][i] >= 1) entradaDigrafo = false; 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 fixedGraph[i][j] = 1; 
 fixedGraph[j][i] = 1; 
 grau[i]++; 
 arestas.add(new int[] {i, j}); 
 listaAdjacencia[i].add(j); 
 qtdArestas++; 
 } 
 } 
 if (grau[i] == 0) conexo = false; 
 } 
 
 Object[] arestasArray = arestas.toArray(); 
 this.arestas = new int[arestasArray.length][]; 
 for (int i = 0; i < arestasArray.length; i++) { 
 this.arestas[i] = (int[]) arestasArray[i]; 
 } 
 this.grafo = fixedGraph; 
 this.grau = grau; 
 } 
 
 public int[][] getGrafo() { 
 return grafo; 
 } 
 
 public ArrayList<Integer>[] getListaAdjacencia() { 
 return listaAdjacencia; 
 } 
 
 public int[] getGrau() { 
 return grau; 
 } 
 
 public int[][] getArestas() { 
 return arestas; 
 } 
 
 public int getQtdArestas() { 
 return qtdArestas; 
 } 
 
 public boolean isEntradaDigrafo() { 
 return entradaDigrafo; 
 } 
 
 public boolean isConexo() { 
 return conexo; 
 } 
 
 public String joinGrau() { 
 String strJoin = ""; 
 for (int i = 0; i < grau.length; i++) { 
 if (i > 0) strJoin += "\n"; 
 strJoin += "[" + i + "]: " + grau[i]; 
 } 
 return strJoin; 
 } 
} 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
3) Escreva um programa que receba como entrada uma matriz de adjacências de um grafo simples, 
ponderado e conexo e escreva como saída as arestas (na forma de pares ordenados e seus pesos). 
package Exercicio3; 
 
import java.util.ArrayList; 
 
import Exercicio1.Exercicio1; 
 
public class Exercicio3 { 
 
 public static void main(String[] args) { 
 System.out.println("---------------------- Exercicio 3 ----------
------------"); 
 
 int[][] grafo = { 
 {0, 1, 0, 1}, 
 {0, 0, 1, 1}, 
 {0, 1, 0, 1}, 
 {0, 1, 1, 0} 
 }; 
 
 ArrayList<int[]> listaArestas = new ArrayList<int[]>(); 
 for (int i = 0; i < grafo.length; i++) { 
 for (int j = 0; j < grafo[i].length; j++) { 
 if (i == j) continue; 
 if (grafo[i][j] >= 1) { 
 listaArestas.add(new int[] {i, j}); 
 } 
 } 
 } 
 
 String arestasJoin = "{ "; 
 for (int i = 0; i < listaArestas.size(); i++) { 
 if (i > 0) arestasJoin += ", "; 
 arestasJoin += "{" + listaArestas.get(i)[0] + ", " + 
listaArestas.get(i)[1] + "}"; 
 } 
 arestasJoin += " }"; 
 System.out.println("\nGrafo: " + Exercicio1.joinMatriz(grafo)); 
 System.out.println("\nArestas do grafo: " + arestasJoin); 
 } 
 
} 
 
 
 
4) Escreva um programa que receba como entrada uma matriz de adjacências para o grafo não-
direcionado em sua forma triangular inferior, conforme ilustrado abaixo e retorne a matriz 
completa, obtendo a parte superior considerando a simetria. 
 
0 
 
1 0 
 
0 1 0 
 
0 1 1 0 
 
1 1 0 1 0 
 
0 0 1 1 1 0 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
Dica: faça a entrada como um arquivo de texto (entrada.txt) no formato abaixo, onde a primeira 
linha indica a dimensão da matriz quadrada e as linhas abaixo são os elementos de cada posição 
da matriz. 
 
6 
0 1 0 0 1 0 
1 0 1 1 1 0 
0 1 0 1 0 1 
0 1 1 0 1 1 
1 1 0 1 0 1 
0 0 1 1 1 0 
 
 
 
package Exercicio4; 
 
import java.util.ArrayList; 
 
import Exercicio1.Exercicio1; 
 
public class Exercicio4 { 
 
 public static void main(String[] args) { 
 System.out.println("---------------------- Exercicio 4 ----------
------------"); 
 
 int[][] matrizTriangularInferior = { 
 {0}, 
 {1, 0}, 
 {0, 1, 0}, 
 {0, 1, 1, 0}, 
 {1, 1, 0, 1, 0}, 
 {0, 0, 1, 1, 1, 0} 
 }; 
 int maxLength = matrizTriangularInferior.length; 
 
 int[][] grafoCompleto = new int[maxLength][maxLength]; 
 for (int i = 0; i < matrizTriangularInferior.length; i++) { 
 for (int j = 0; j < matrizTriangularInferior[i].length; 
j++) { 
 if (i == j) continue; 
 
 if (grafoCompleto[i][j] == 1) continue; 
 if (matrizTriangularInferior[i][j] >= 1) { 
 
 grafoCompleto[i][j] = 1; 
 grafoCompleto[j][i] = 1; 
 } 
 } 
 } 
 System.out.println("\nMatriz triangular: " + 
Exercicio1.joinMatriz(matrizTriangularInferior)); 
 System.out.println("\nGrafo completo: " + 
Exercicio1.joinMatriz(grafoCompleto)); 
 } 
 
} 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
Teoria dos Grafos 
Lista 3 de Exercícios 
 
Profa. Eliane Oliveira Santiago 
 
1) Dado o grafo a seguir, como você o representaria com uma matriz de adjacências? 
 
 
 a b c d e f g h i j 
 0 1 2 3 4 5 6 7 8 9 
a 0 0 1 1 1 0 0 0 0 0 0 
b 1 1 0 1 0 1 0 1 0 0 0 
c 2 1 1 0 0 1 1 0 0 0 0 
d 3 1 0 0 0 0 1 0 0 0 0 
e 4 0 1 1 0 0 1 1 0 0 0 
f 5 0 0 1 1 1 0 0 0 0 0 
g 6 0 1 0 0 1 0 0 1 0 1 
h 7 0 0 0 0 0 1 1 0 1 0 
i 8 0 0 0 0 0 0 0 1 0 1 
j 9 0 0 0 0 0 0 1 0 1 0 
 
 
2) Dado o grafo acima, como você o representaria com uma lista de adjacências? 
 
 
 
A B C D 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
 
 
 
 
 
 
 
 
 
3) Dado o grafo a seguir, como você o representaria com uma matriz de adjacências? 
 
 
 
 a b c d e f g 
 0 1 2 3 4 5 6 
a 0 0 1 1 0 0 0 0 
b 1 0 0 0 1 0 0 0 
c 2 0 0 0 0 1 1 0 
d 3 0 0 0 0 0 0 0 
e 4 0 0 0 1 0 0 0 
f 5 0 0 0 0 0 0 1 
g 6 0 0 0 0 0 0 0 
 
4) Como você o representaria o grafo acima com uma lista de adjacências? 
 
A 
B 
C 
D 
E 
F 
G 
 
 
B C 
D 
E F 
 
 
D 
G 
 
B 
 
 
 
 
 
 
 
A C E G 
C A B E F 
D A F 
E B C F G 
F C D E 
G B E H J 
H F G I 
 
 
I H J 
J G I 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
5) Escreva as matrizes de adjacências que representam o grafos abaixo: 
 
(a) 
 
 1 2 3 4 5 
1 1 1 0 0 2 
2 1 1 1 1 1 
3 0 1 0 1 0 
4 0 1 1 0 0 
5 2 1 0 0 0 
 
b) 
 
 1 2 3 4 5 
1 0 1 0 0 0 
2 0 0 1 1 0 
3 0 0 0 1 0 
4 0 0 1 0 0 
5 0 0 0 0 0 
 
 
6) Desenhe o grafo representado pelas matrizes de adjacências apresentadas. 
 
a) 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
b) 
 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
 
 
 
7) Desenhe o grafo não-direcionado representado pela lista de adjacências a seguir 
 
 
 
 
 
 
 
 
 
 
 
 
 
8) Dado o grafo a seguir, como você o representaria com uma lista de arestas? 
 
 
u v 
a b 
a c 
c e 
d e 
d f 
e f 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
 
 
9) Com relação ao grafo a seguir, responda: 
 
a. Desenhe sua representação na forma de lista de adjacências. 
 
b. Quantas posições de memória são necessárias para o armazenamento 
da lista de adjacências? (Admita que um ponteiro ocupa uma posição de 
memória.) 
 
c. Quantas posições de memória são necessárias para o armazenamento 
da matriz de adjacências deste grafo? 
Serão necessárias 11 posições na 
memória; a quantidade 1 
 2 
2 33 4 5 6 
4 
5 
6 
 
 
 
10. Considerando que E é o número de arestas, e V é o número de vértices, categorize o espaço 
abaixo: 
 
 
 Θ(E) Θ(V+E) Θ(V2) 
Matriz de Adjacências x 
Listas de adjacências x 
Listas de Arestas x 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
11. Use o grafo direcionado a seguir para responder as seguintes perguntas: 
 
 
Não Este grafo é trivial? 
Não É um grafo simples? 
Não É um grafo múltiplo? 
Não É um grafo completo? 
Não É um grafo conexo? 
Não É um grafo desconexo? 
 
Possui ciclo(s)? 
_sim_______________________________________ 
Qual(is)? 3, 4, 5, 6, 3; 1,2,1; 3,5,6 
________________________________________ 
 
Informe o grau de cada vértice 
 
Vértices 
Grau de 
entrada 
Grau de 
saída 
1 1 2 
2 2 3 
3 2 2 
4 2 1 
5 2 1 
6 2 1 
 
Possui vértice de articulação (ou corte)? 
____Não__________ 
Qual(is)?___________________________________________________ 
 
 
Possui aresta de articulação (ou ponte)? 
__sim____________ 
Qual(is)?__2,2_____________________________________________
____ 
 
 
 
 
12) Qual dos grafos abaixo não é isomorfo aos outros? Por quê? 
 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
R: b), d) e e) não são isomorfos; primeiro que o d) e e) possuem quantidade de vértices 
diferente ao a) e c); quanto ao b), o mesmo possui uma curva no centro que não é possível 
chegar nos isomorfos a) e c) 
 
 
 
 
 
 
 
 
 
 
 
13) Diga se os dois grafos apresentados são ou não isomorfos. Se forem, apresente a função que 
estabelece o isomorfismo entre eles; caso contrário, explique o porquê. 
 
a) 
 
 
 
 
Grafos (a) e (b) são isomorfos 
Resolvido em classe pelo método da construção. 
Estes grafos são isomorfos porque existe uma 
função bijetora no conjunto de vértice do grafo 
(a) para o conjunto de vértices do grafo (b), 
dada abaixo: 
 
 
f(x) = y 
f(1) = a 
f(2) = b 
f(3) = c 
f(4) = d 
f(5) = e 
f(6) = f 
 
Grafo (a) 
V = {1, 2, 3, 4, 5} 
E = {(1,3), (1,4), (2,4), (2,5), (3,5)) 
 
Grafo (b) 
V = {a, b, c, d, e} 
E = {(a,c), (a,d), (b,d), (b,e), (c,e)) 
 
 
b) 
 
e b 
a 
d c 
(
b
)
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
Os grafos (a) e (b) são isomorfos porque atendem aos critérios: possuir a mesma 
quantidade de vértices; a mesma quantidade de arestas; e seus respectivos vértices 
possuem o mesmo grau e a mesma conexão. 
 
 
 
 
 
 
 
 
 
 
 
 
 
c) 
 
 
 
São isomorfos, pois mesmo que não tenham a 
conexão relativa com os vértices, ainda sim 
atendem aos requisitos que foram listados 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
14) Desenhe o grafo que representa a matriz de adjacências para o grafo não-direcionado 
dada em sua forma triangular inferior por 
 
 
 
 
2 1 0 0 
 1 0 1 1 
 0 1 1 2 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 0 1 2 0 
 
 
 
 
 
 
 
 
 
15) Responda as perguntas a seguir com Verdadeiro ou Falso. 
 
v Um grafo conexo com quatro vértices ímpares pode ser conexo. 
f 
Existe um caminho euleriano em qualquer grafo com um número par de vértices 
ímpares. 
f 
Um circuito hamiltoniano usa cada aresta e vértice do grafo exatamente uma vez, 
exceto pelo vértice inicial e final. 
v A árvore geradora mínima de um grafo não é única. 
v 
O grafo de possui um conjunto unitário de vértices e um conjunto de arestas vazio é 
um grafo trivial. 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
Teoria dos Grafos 
Lista 4 de Exercícios 
 
Profa. Eliane Oliveira Santiago 
 
1. Verifique se os grafos abaixo são eulerianos. 
 
Grafo G Grafo H 
 
R: O grafo G é euleriano (circuito), pois todos os vértices possuem grau par; ao contrário do 
grafo H que possui ao menos um (mais de um, na verdade) grau impar 
2. Aplique o algoritmo de Fleury para encontrar um circuito euleriano no grafo abaixo a partir do 
vértice 5. Dê a sequencia de vértices visitados, marque no grafo as arestas excluídas e as pontes que 
sobram. 
 
R: A sequência pode ser dada por 1,5,2,6,3,7,6,5,4,1; removendo então na sequência, as 
arestas b,c,d,e,f,i,h,g,a 
 
3) Usando o teorema do caminho euleriano, determine se os grafos abaixo tem a um caminho 
euleriano. 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
R: Os grafos 1, 2, 7 são circuitos eulerianos (e portanto, são caminhos também) pois todos os 
vértices possuem grau par e o grafo 5 é apenas um circuito (pois possui 2 vértices com grau 
impar). 
 
4) Demonstre que qualquer grafo com um ciclo hamiltoniano é conexo. 
R: Todo grafo hamiltoniano é conexo, pois sua teoria consiste em acessar TODOS os vértices do 
grafo retornando ao vértice de origem, visitando cada vértice APENAS UMA VEZ; se um grafo 
fosse desconexo não haveria possibilidade de acessar TODOS os vértices, pois ao menos um 
estaria inacessível sem nenhuma aresta ligando ao restante do grafo 
 
 
5) Dado que Km,n denota um grafo bipartido completo cujas partições têm m e n vértices, 
respectivamente. 
a) para quais valores de m e n existe um caminho euleriano em Km,n? 
R: existe um caminho euleriano em um K3,2; K2,1, pois nesses casos haverão 
exatamente 2 vértices com grau impar; fora esse, para qualquer valor de m e n, tal que 
sejam > 0 e ambos sejam pares haverá um circuito, e portanto um caminho 
 
b) para quais valores de m e n existe um ciclo hamiltoniano em Km,n? 
R: haverá sempre um circuito hamiltoniando, quando o valor de m e n forem iguais, 
independentemente de serem valor par ou valor impar 
 
6) Demonstre que sempre existe um ciclo hamiltoniano em um grafo cujo grau de todos os vértices 
seja 2. 
R: Quando o grau de todos os vértices de um grafo é igual a 2, sempre existirá um ciclo hamiltoniano, 
pois é o necessário para que ele possa entrar naquele vértice por meio de um vértice x, e continue 
para o próximo vértice y, mantendo assim um circuito sem repetição, pois não há a possibilidade 
de um vértice com grau 2 retornar para um outro vértice (sem ser o anterior do qual veio) já 
acessado, sem que aumente ou diminua o grau do mesmo 
 
7) No algoritmo de Prim (Política #1) para a obtenção de árvore geradora mínima de um grafo, a 
árvore cresce a partir de um vértice inicial, através da inclusão de arestas pequenas adjacentes. 
 
O algoritmo de Kruskal (Política #2) inclui arestas na ordem de suas distâncias crescentes, sempre 
que elas puderem pertencer ao grafo. Os empates são decididos arbitrariamente e a restrição é a 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
inclusão não formar um ciclo. O algoritmo termina quando todos os vértices tiverem sido 
incorporados a uma estrutura conexa. 
 
Encontre a árvore geradora mínima para os grafos abaixo usando o algoritmo de Prim 
(Política #1) e Kruskal (Política #2). 
 
Grafo G Grafo H 
 
 
Grafo I 
 
 
Grafo G Grafo H 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
 
8. Desenhe o K3,4. 
 
9. Demonstre que o grafo K2,3 é um grafo planar. 
 
10. Demonstre que o grafo a seguir é um grafo planar. 
 
 
 
11. Desenhe o grafo dual a partir do mapa rodoviário de uma parte do estado do Arizona 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
 
12. Se um grafo simples, conexo e planar tem seis vértices, todos de grau 3, em quantas regiões ele 
divide o plano? Determine se o grafo é planar (mostrando uma representação planar) ou não-planar 
(encontrando um subgrafo homeomorfo a K5 ou K3,3). 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 Divide o plano em 4 regiões 
 
 
13. Desenhe o grafo dual do mapa da figura abaixo: 
 
 
 
14. Encontre o número cromático de cada grafo. 
 
 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
 
 
 
14. Considere a relação de exames requeridos, na mesma época, pelosalunos de uma Universidade. 
 
 
a) Montar o grafo para a situação descrita acima, 
considerando: 
 Os vértices representam as disciplinas oferecidas. 
 Uma aresta entre duas disciplinas indicam que pelo 
menos um aluno estará cursando as duas disciplinas. 
b) sua representação gerou um grafo simples, conexo e 
planar? 
c) Definir o número cromático para o grafo gerado no item 
a. 
a) 
 
b) Sim 
Nome Kevin De Lima Cruz N231FC2 CC5B13 DATA 30/05/2020 
c) 
15) A italiana Giusepina esperava seus quatro filhos Eugênio, José, Leonardo e Ananda para um 
lanche da tarde e preparou os seguintes sanduíches: Baurú, Misto-quente, Misto-Frio e X-Salada. 
Eugênio gosta de Misto frio e de X-salada. José de Baurú e X-salada. Leonardo de Misto Quente e 
Misto Frio. Ananda de Baurú e Misto Quente. Desenhe o grafo que modela essa situação e use esse 
grafo para descobrir se é possível que cada filho de Giusepina receba o lanche que gosta. 
 Cada filho pode 
receber um lanche do que gosta, se for percorrer o grafo de forma circular em um sentido 
único, por exemplo: No sentido horário começando por Eugênio; 
Eugênio come o X-Salada; José come o Baurú; Ananda come o Misto quente; e Leonardo come 
o Misto Frio; desta forma, todos receberam um lanche dos quais gostam. 
No sentido anti-horário também começando por Eugênio teriamos: 
Eugênio come Misto frio; Leonardo come Misto quente; Ananda come bauru; e José come X-
salada; também se obteve uma solução, só que desta vez comeram uma variavel diferente de 
lanche das que haviam comido anteriormente.