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.
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.
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);
		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;
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;
					
					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;
	}
}
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
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));
	}
}
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 
	 
	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 
	
	
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 
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) 
 
	
	b)
 
	
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
	
	
	
	
	
	
	
	
	
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?
	1
	
	2
	
	
	2
	
	3
	
	
	3
	
	4
	5
	6
	4
	
	
	
	
	5
	
	
	
	
	6
	
	
	
	
Serão necessárias 11 posições na memória; a quantidade
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
	
	
	
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ê?
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)
e
b
a
d
c
(b)
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) 
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 
	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.
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.
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 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 
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
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).
 
 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.
 
14. Considere a relação de exames requeridos, na mesma época, pelos alunos 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
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.