Teoria dos grafos

Prévia do material em texto

1. ] Dentro de uma escola deseja-se elaborar o horário das provas finais de forma que alunos que façam mais de uma disciplina não tenham as provas destas disciplinas acontecendo no mesmo horário.
Foi elaborada a tabela abaixo onde as linhas e colunas de 1 a 7 são os nomes das disciplinas, e o símbolo "*" na linha i, coluna j, indica que a disciplina i tem um aluno em comum com a disciplina j.
Utilizando a teoria dos grafos, descubra quantos horários diferentes serão necessários para que todas as provas sejam realizadas.
OBS: A tabela é simétrica, por isso foi preenchida somene com os valores acima da diagonal principal.
	
	
	6 horários diferentes 
	
	
	5 horários diferentes
	
	
	3 horários diferentes
	
	
	4 horários diferentes
	
	
	7  horários diferentes
1 pontos   
PERGUNTA 2
1. Um grafo bipartido é um grafo G = (V,E) cujo conjunto de vértices V pode ser separado em dois conjuntos X e Y, tal que toda aresta de E liga somente vértices de X com vértices de Y.Observe os dois grafos mostrados abaixo e assinale a alternativa que indica corretamente a classificação dos grafos.
	
	
	O grafo a é bipartido, mas b não é
	
	
	Nenhum dos grafos é bipartido
	
	
	O grafo b é bipartido, mas a não é
	
	
	Ambos são bipartidos, mas não são isomorfos
	
	
	Os dois grafos são bipartidos e isoformos
1 pontos   
PERGUNTA 3
1. Uma lista de adjacência é uma estrutura de dados usada para representar grafos. Em uma representação de lista de adjacência mantemos, para cada vértice do grafo, uma lista de todos os outros vértices com os quais ele tem uma aresta. Considere o grafo abaixo assim como sua representação por lista de adjacência.
A Árvore em Largura e a Árvore em Profundidade, respectivamente, tendo como raiz o vértice 1, são:
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
1 pontos   
PERGUNTA 4
1. 
Uma matriz de adjacência qualquer (M) terá a quantidade de vértices (n) de número de linha e colunas, ou seja, uma para cada vértice.
Em uma matriz M para o gráfico não ponderado, podemos completar suas linhas(i) e colunas(j) com apenas 0 e 1, pois só existe a opção de conter ou não ligações entre os vértices.
Então em uma matriz (M)de adjacência não ponderada, temos que:
M[i, j] = 1, se houver uma aresta saindo do vértice i e indo até o j
M[i, j] = 0, caso contrário.
O grafo G dado acima pode ser representado pela seguinte matriz de adjacência:
	
	
	0 1 1 0 0 
1 0 1 0 1
1 1 0 1 0
1 1 1 0 1
1 1 0 0 0
	
	
	0 1 1 1 1
1 0 1 1 1
1 1 0 1 1 
1 1 1 0 1
1 1 1 1 0
	
	
	0 1 1 1 1
1 0 1 1 1
 1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
	
	
	0 1 0 1 0
1 0 0 0 1
0 1 0 0 0 
1 0 0 0 1
0 1 0 1 0
	
	
	0 1 0 1 0
1 0 1 0 1
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
1 pontos   
PERGUNTA 5
1. Considere a estrutura abaixo que representa um problema de rotas em pequena escala.
Considere que foi solicitado para você encontrar alguma estratégia lógica para, partindo do ponto 1, chegar ao ponto 6 usando a menor rota disponível.
Lembrando que de um mesmo ponto pode haver mais de uma rota, com distâncias diferentes, a lógica correta utilizada por você, em função dos pontos a serem percorridos, foi:
	
	
	{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6
	
	
	{1} {2,3} {2,4} {5,6}{6}, caminho mais curto 1-2-5-6
	
	
	{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-4-6
	
	
	{1} {2} {4} {6}, caminho mais curto 1-2-4-6
	
	
	{1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6
1 pontos   
PERGUNTA 6
1. Um Grafo é uma estrutura de dados formada por um conjunto de não vazio de vértices (ou nós) e por um conjunto de arestas (ou arcos), ligando estes vértices. Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Com relação aos grafos ilustrados nas figuras I e II e no que se refere à teoria dos grafos, assinale a alternativa correta.
	
	
	As matrizes de adjacências dos dois grafos são distintas.
	
	
	Ambos os grafos são regulares.
	
	
	Os dois grafos são circuitos.
	
	
	Os grafos são isomórficos entre si.
	
	
	Os dois grafos são completos.
1 pontos   
PERGUNTA 7
1. Dado um grafo não-orientado G=(V,A).Ele será n-colorido se existir a função cor : V = {1, 2, 3,..., n} onde cor(u) != cor(v), para cada vértice(u,v) em A.
Em outras palavras: cada número representa uma cor v, e seus vértices adjacentes possuem cor diferente.
O número cromático representa a quantidade mínima de cores necessárias para colorir um grafo.
Considere um grafo K6. Qual o número cromático para esse grafo?
	
	
	3
	
	
	7
	
	
	4
	
	
	5
	
	
	6
1 pontos   
PERGUNTA 8
1. O código abaixo pode ser utilizado para atravessar um grafo.
Entrada: um gráfico G e um vértice v de G
Saída: todos os vértices alcançáveis de v marcados
função DFS(G,v):
     marque v
     para todas as arestas adjacentes a v, faça
          se vértice w não estiver marcado, então
               Chame recursivamente DFS(G,w)
          fim se
     fim para
fim função
Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo:
	
	
	busca em profundidade ou Depth-First Search.
	
	
	busca melhor-primeiro ou Best-First Search
	
	
	busca exaustiva ou Brute-Force Search.
	
	
	percurso ótimo ou Best Route
	
	
	busca em largura ou Breadth-First Search.
1 pontos   
PERGUNTA 9
1. 
Um caminho C num grafo é mínimo se não existe outro caminho que tenha a mesma origem e o mesmo término que C mas comprimento menor que o de C. A tabela acima apresenta o resultado da aplicação do algoritmo de Dijkstra para a obtenção do caminho mínimo para o deslocamento entre diversas cidades.
A partir dos dados da tabela, conclui-se que:
	
	
	um viajante terá que se deslocar 5 km, para percorrer o menor caminho entre a cidade B e a cidade E.
	
	
	um viajante deverá se deslocar na sequência A – B – E – F, para percorrer o menor caminho entre as cidades A e F.
	
	
	a menor distância entre as cidades A e F é de 15 km.
	
	
	um viajante deverá passar obrigatoriamente na cidade C, para percorrer o menor caminho entre as cidades A e F.
	
	
	o menor caminho entre as cidades A e D é de 2 km.