Teoria dos Grafos

Prévia do material em texto

Teoremas de Euler, Percursos e Caminhos Eulerianos e Hamiltonianos
 
· Pergunta 1
3 em 3 pontos
	
	
	
	Considere que  G é  um grafo qualquer e que V e E são os conjuntos de vértices e de arestas de G, respectivamente. Considere também que grau (v) é  o grau de um vértice v pertencente ao conjunto V. Nesse contexto, analise as seguintes asserções.
            Em  G, a quantidade de vértices com grau ímpar é  ímpar.
                                           PORQUE
            Para G, vale a identidade dada pela expressão Somatória grau(v) = 2 |E|, v ϵ V.
Acerca dessas asserções, assinale a opção correta:
	
	
	
	
		Resposta Selecionada:
	E. 
A primeira asserção é uma proposição falsa e a segunda é uma  proposição verdadeira .
	Respostas:
	A. 
As duas asserções são proposições verdadeiras e a segunda é justificativa correta da primeira .
	
	B. 
Tanto a primeira quanto a segunda asserções são proposições falsas .
	
	C. 
As duas asserções são proposições verdadeiras e a segunda não é justificativa correta da primeira .
	
	D. 
A primeira asserção é uma proposição verdadeira e a segunda é uma  proposição falsa .
	
	E. 
A primeira asserção é uma proposição falsa e a segunda é uma  proposição verdadeira .
	Comentário da resposta:
	Em  G, a quantidade de vértices com grau ímpar é sempre par, pois para G, vale a identidade dada pela expressão Somatória grau(v) = 2 |E|, v ϵ V.
	
	
	
· Pergunta 2
0 em 3 pontos
	
	
	
	Tendo por base as afirmativas abaixo a respeito de percursos e caminhos em grafos.
1. Um percurso é simples se não repetir vértices.
2. Um percurso é elementar se não repetir ligações.
3. Percurso, aberto ou fechado,  é hamiltoniano quando utiliza cada vértice do grafo uma única vez.
4. O caminho é euleriano quando utiliza cada ligação do grafo uma única vez e considera a orientação  das ligações.
5. Um percurso, aberto ou fechado, é euleriano quando utiliza cada ligação do grafo uma única vez.
 
Assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	D. 
As afirmativas I, II e III são Verdadeiras
	Respostas:
	A. 
As afirmativas I, II e IV são falsas .
	
	B. 
As afirmativas III e V são Verdadeiras .
	
	C. 
As afirmativas II e III são falsas .
	
	D. 
As afirmativas I, II e III são Verdadeiras
	
	E. 
As afirmativas II,  III e V são Verdadeiras .
	Comentário da resposta:
	O correto em cada afirmativa é:
II. Um percurso é simples se não repetir ligações.
II. Um percurso é elementar se não repetir vértices.
II. Percurso, aberto ou fechado,  é hamiltoniano quando utiliza cada vértice do grafo uma única vez.
II. O caminho é euleriano quando utiliza cada ligação do grafo uma única vez e considera a orientação  das ligações.
II. Um percurso, aberto ou fechado, é euleriano quando utiliza cada ligação do grafo uma única vez.
	
	
	
1. Pergunta 3
0 em 4 pontos
	
	
	
	
Seja G = (V,E) um grafo simples conexo não-euleriano. Queremos construir um grafo H que seja euleriano e que contenha G como subgrafo. Considere os seguintes possíveis processos de construção:
III. Acrescenta-se um novo vértice, ligando-o a cada vértice de G por uma aresta.
III. Acrescenta-se um novo vértice, ligando-o a cada vértice de grau ímpar de G por uma aresta.
III. Cria-se uma nova cópia G’ do grafo G e acrescenta-se uma aresta ligando cada par de vértices correspondentes.
III. Escolhe-se um vértice arbitrário de G e acrescentam-se arestas ligando este vértice a todo vértice de grau ímpar de G.
III. Duplicam-se todas as arestas de G.
III. Acrescentam-se arestas a G até se formar o grafo completo com |V| vértices.
Quais dos processos acima sempre constroem corretamente o grafo H?
	
	
	
	
		Resposta Selecionada:
	C. 
Somente (II) e (IV)
	Respostas:
	A. 
Somente (III), (V) e (VI)
	
	B. 
Somente (I), (III), (IV) e (V)
	
	C. 
Somente (II) e (IV)
	
	D. 
Somente (II), (IV), (V) e (VI)
	
	E. 
Somente (II), (IV) e (V)
	Comentário da resposta:
	Uma possibilidade é acrescentar um novo vértice e ligá-lo a cada vértice de grau ímpar de G, isso faz com que estes todos os vértices do grafo fiquem com grau par e H seja euleriano.
Uma segunda possibilidade é escolher um vértice arbitrário de G e acrescentar arestas ligando este vértice a todo vértice de grau ímpar de G, dessa forma todos os vértices do grafo ficarão com grau par e H será euleriano.
Enfim, uma terceira possibilidade é duplicar todas as arestas de G, ao realizar a duplicação os vértices que possuem grau par continuarão com grau par e os vértices com grau ímpar ficarão com seu grau par, assim, todos os vértices do grafo ficarão com grau par e H será euleriano.
	
	
	
	
	
	
	
	
Conceitos gerais, h-conexo e Percurso em Profundidade
 
· Pergunta 1
0 em 3 pontos
	
	
	
	Seja G = (V,E) um grafo simples e finito, onde |V | = n e |E| = m
Nesse caso, analise as seguintes afirmativas.
I. Se G é hamiltoniano, então G é ao menos 2-conexo.
II. Se G é completo, então G é hamiltoniano.
III. Se G é 4-regular e conexo, então G é euleriano.
IV. Se G é bipartite com partições A e B, então G é hamiltoniano se, e somente se, |A| = |B|.
V. Se G é euleriano, então G é 2-conexo.
A análise permite concluir que são FALSOS
	
	
	
	
		Resposta Selecionada:
	B. 
apenas os itens II e IV
	Respostas:
	A. 
apenas os itens III e IV
	
	B. 
apenas os itens II e IV
	
	C. 
apenas os itens IV e V
	
	D. 
apenas os itens I e III
	
	E. 
apenas os itens I  e V
	Comentário da resposta:
	Justificativa:
A afirmação I é VERDADEIRA, pois, se um grafo é hamiltoniano, significa que existe um percurso fechado que utiliza cada vértice do grafo uma única vez, ou seja, possui um circuito, então existe dois percursos disjuntos entre cada par de vértice x, y e o grafo é no mínimo 2-conexo.
A afirmação II é VERDADEIRA, pois se G é completo, é possível realizar um percurso fechado que utilliza cada vértice do grafo uma única vez, portanto G é hamiltoniano.
A afirmação III é VERDADEIRA, pois se G é 4-regular e conexo, significa que o grau de cada vértice x pertencente a G d(x) = 4, ou seja, é PAR, portanto, pelo teorema dos caminhos Eulerianos o grafo G é Euleriano.
A afirmação IV é FALSA, pois se G é bipartite e |A| = |B|, não necessariamente o grafo é hamiltoniano. Por exemplo,  O Grafo G abaixo é bipartite com 3 vértices em cada partição e não é hamiltoniano.
G = (V, E), onde V = { a, b, c, d, e, f }
E = { {a, d}, {a, f}, {b, d}, {b, f}, {c, d}, {c, e}} , Partição 1 = { a, b, c} e Partição 2 = { d, e, f}.
A afirmação V é FALSA, pois se G é euleriano não necessariamente é 2-conexo, por exemplo, o grafo abaixo é simples, finito, euleriano e 4-conexo.
G = (V, E), onde V = { 1, 2, 3, 4, 5 }
E = { {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}.
	
	
	
· Pergunta 2
3 em 3 pontos
	
	
	
	Considere o algoritmo de busca em profundidade em grafos. Dado o grafo a seguir e o vértice A como ponto de partida, a ordem em que os vértices são visitados é dada por:
	
	
	
	
		Resposta Selecionada:
	D. 
A B D C E F
	Respostas:
	A. 
A B C E D F
	
	B. 
A B C D E F
	
	C. 
A C D B F E
	
	D. 
A B D C E F
	
	E. 
A B D F E C
	Comentário da resposta:
	Resposta: C
Justificativa:
A partir da execução do algoritmo percurso em profundidade estudado em sala:
1. Visita-se um nó n previamente selecionado;
2. Marca o nó n;
3. Empilha n em uma pilha P;
4. Enquanto a pilha P não estiver vazia;
   4.1 O nó n é desempilhado da pilha P; (n ← pop(P) (atribuição))
   4.2 Para cada nó m não marcado e adjacente a n faça
            4.2.1 O nó m é visitado;
            4.2.2 O nó n é colocado na pilha P;
            4.2.3 O nó m é marcado;
            4.2.4 Troca o valor de n para m (n ← m (atribuição)).
 
Utiliza-se uma pilha para armazenar os vértices já visitados e um vetor para marcá-los, obtendo-se a ordem de visitação dos nós: A B D C E F.
	
	
	
· Pergunta 3
4 em 4 pontos
	
	
	
	A busca primeiro em  profundidade é um algoritmo de exploração sistemática em grafos, em que as arestas são exploradas a partir do vértice v mais recentemente  descoberto que ainda tem arestasinexploradas saindo dele. Quando todas as arestas de v são exploradas, a busca regressa para explorar as arestas que deixam o vértice a partir do qual v foi descoberto. Esse processo continua até que todos os vértices acessíveis a partir do vértice inicial sejam explorados.
CORMEN, T. H LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to algorithms, 3. ed.
Cambridge, Massachutts: The MIT Press, 2009 (adaptado).
 
No percurso em profundidade, no caso de um vértice explorado ter mais de um vértice adjacente, pode-se utilizar a ordem alfabética crescente como critério para priorizar a exploração ou ainda a sequência estabelecida na matriz de adjacência.
 
Considere o grafo a seguir:
E as afirmações abaixo:
I.   A matriz de adjacência do Grafo é dada pela matriz:
II.   A categoria de conexidade do grafo é C1.
III.  O seu grafo reduzido Gr apresenta 3 vértices.
IV.   A sequência de vértices descobertos no grafo durante a execução de uma busca em profundidade com controle de estados repetidos, utilizando o vértice r como o inicial é dado por r, u, y, q, s, p, w, t, x, z.
V.   O grafo é hamiltoniano.
A análise permite concluir que são Verdadeiros:
	
	
	
	
		Resposta Selecionada:
	E. 
apenas os itens I, II e IV
	Respostas:
	A. 
apenas os itens I, III, IV e V
	
	B. 
apenas os itens I, II, IV e V
	
	C. 
apenas os itens I e IV
	
	D. 
apenas os itens II e IV
	
	E. 
apenas os itens I, II e IV
	Comentário da resposta:
	Justificativa:
I. VERDADEIRA. A matriz de adjacência para o grafo é dada pela matriz apresentada no texto do enunciado.
II. VERDADEIRA. O grafo é categoria C1, pois é simplesmente conexo e não semi-fortemente conexo. Veja que não há um caminho em nenhum sentido entre,  por exemplo, s e x.
III. FALSA. O grafo reduzido apresenta 5 vértices.
IV. VERDADEIRA. O percurso em profundidade, começando por r é dado por: r, u, y, q, s, p, w, t, x, z.
V. FALSO. O grafo tem um caminho hamiltoniano aberto, mas não é um grafo hamiltoniano, pois não apresenta um caminho hamiltoniano fechado.
	
	
	
Profundidade, Largura e Ordenação Topológica
 
· Pergunta 1
0 em 3 pontos
	
	
	
	Considere o algoritmo de busca em largura em grafos. Dado o grafo a seguir e o vértice A como ponto de partida, a ordem em que os vértices são visitados é dada por:
	
	
	
	
		Resposta Selecionada:
	E. 
A B D C E F
	Respostas:
	A. 
A B C D E F
	
	B. 
A C D B F E
	
	C. 
A B C E D F
	
	D. 
A B D F E C
	
	E. 
A B D C E F
	Comentário da resposta:
	Justificativa:
A partir da execução do algoritmo percurso em largura estudado em sala:
1. Visita-se um nó n previamente selecionado;
2. Marca o nó n;
3. Inserir n em uma fila F;
4. Enquanto a fila F não estiver vazia;
   4.1 Retira um elemento da fila F e atribui ao nó n;
   4.2 Para cada nó m não marcado e adjacente a n faça
            4.2.1 O nó m é visitado;
            4.2.2 O nó m é colocado na fila F;
            4.2.3 O nó m é marcado;
 
Utiliza-se uma fila para armazenar o vértice já visitado e um vetor para marcá-los, obtendo-se a ordem de visitação dos nós: A B C D E F.          
	
	
	
· Pergunta 2
0 em 4 pontos
	
	
	
	A linha de produção de uma fábrica de automóveis tem diversos setores. Cada setor se encarrega de construir certas partes do automóvel.  A tabela abaixo ilustra os 8 setores da fábrica e qual é o setor seguinte no qual as peças do automóvel devem prosseguir.
Considere as afirmações a seguir:
I. Na modelagem do problema, é mais indicado o uso de um grafo direcionado.
II. Um algoritmo que resolve o problema é o Percurso em profundidade.
III. Um percurso ordenação topológica resolve o problema encontrando a sequência de setores na seguinte ordem: 1, 7, 4, 2, 3, 5, 6, 8.
ssinale a alternativa correta.Com base no descrito e nas afirmações, a
	
	
	
	
		Resposta Selecionada:
	A. 
Apenas I e II
	Respostas:
	A. 
Apenas I e II
	
	B. 
Apenas I e III
	
	C. 
Apenas II
	
	D. 
Apenas I
	
	E. 
I, II e III
	Comentário da resposta:
	A solução deste problema pode ser obtida montando-se o problema como um grafo direcionado. Observa-se que o grafo direcionado obtido é acíclico e que há uma relação de dependência entre os setores (vértices). Assim, utilizando-se o algoritmo Ordenação Topológica, é possível obter uma sequência considerando os setores anteriores e os próximos:
Visita:  1, 7, 4, 2, 3, 5, 6, 8
	
	
	
· Pergunta 3
0 em 3 pontos
	
	
	
	Sobre os algoritmos de percursos em grafos, relacione os algoritmos da coluna esquerda com sua descrição à direita.
Assinale a alternativa que contém a associação correta.
	
	
	
	
		Resposta Selecionada:
	B. 
I-A, II-C, III-B
	Respostas:
	A. 
I-C, II-A, III-B
	
	B. 
I-A, II-C, III-B
	
	C. 
I-C, II-B, III-A
	
	D. 
I-B, II-C, III-A
	
	E. 
I-B, II-A, III-C
	Comentário da resposta:
	Justificativa:
Percurso em Profundidade: Toma como entrada um grafo, selecionando um nó n, visita-se um nó adjacente a ele e, para esse nó, visita-se um dos nós adjacentes até o momento em que for encontrado um nó sem adjacentes ocorrendo um “retorno” com o objetivo de visitar os nós restantes adjacentes a n, e o processo repete-se novamente.
 
Percurso em Largura: Toma um grafo como entrada e visita-se um nó n aleatório, a seguir, visita-se todos os nós localizados a uma distância d desse nó n, posteriormente, visita-se os nós localizados a uma distância d+1 de n e assim, sucessivamente, até que todos os nós sejam visitados.
 
Ordenação Topológica: Toma como entrada um grafo orientado acíclico, utiliza basicamente busca em profundidade considerando os graus de entrada (d-(v)=0) e fazendo uso de uma fila.
	
	
	
· 
	
Caminhos Mínimos e Dijkstra
 
	 Pergunta 1
0 em 3 pontos
	
	
	
	Uma região composta de 4 cidades possui algumas rodovias que as interligam conforme tabela que indica as distâncias em km das rodovias abaixo .
A partir das informações da tabela, tendo em vista o percurso e as distâncias mínimas para sair da cidade 3 e chegar a quaisquer das outras cidades, considere a execução e os resultados obtidos com o algoritmo de Dijkstra. Além disso, considere as afirmações a seguir .
Com base no descrito e nas afirmações, assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	E. 
Apenas I e II
	Respostas:
	A. 
Apenas II
	
	B. 
Apenas I
	
	C. 
I, II e III
	
	D. 
Apenas I e III
	
	E. 
Apenas I e II
	Comentário da resposta:
	Justificativa:
 
I. Ao final da execução do algoritmo de Dijkstra, vetor de distâncias será di1 = { 0, 30, 30, 15 }.
II. Ao final da execução do algoritmo de Dijkstra, a menor distância para sair da cidade 3 para chegar na cidade 2 é 30.
III. O vetor de rotas resultante, ao final da execução do algoritmo de Dijkstra, é rot = { 0, 4, 1, 1 }.
	
	
	
 Pergunta 2
0 em 2 pontos
	
	
	
	Considerando as afirmações a seguir .
IV. Uma aplicação de Caminhos Mínimos em Grafos é determinar o caminho mais curto entre um determinado par de roteadores para uma rede de computadores.
V. Uma aplicação de Caminhos Mínimos em Grafos é determinar quais estruturas de redes (cabeamentos) devem ser construídas para que o custo da construção seja mínimo envolvendo uma empresa multinacional que possui nove prédios em uma área próxima, e a diretoria deseja conectá-las por meio de cabeamento de redes de tal forma que cada prédio possa se comunicar com outro por meio de uma ou mais estruturas de redes.
VI. Uma aplicação de Caminhos Mínimos em Grafos é determinar a distância mais curta entre duas localidades tendo por base um mapa de um país/cidade/continente onde cada nó de um grafo pode representar um país/cidade ou cruzamento entre ruas.
Com base nas afirmações, assinale a alternativa que apresenta somente as afirmações relativas a aplicação de Caminhos Mínimos em grafos.
	
	
	
	
		Resposta Selecionada:
	B. 
I, II e III
	Respostas:
	A. 
Apenas I e II
	
	B. 
I, II e III
	
	C. 
Apenas III
	
	D. 
Apenas I
	
	E. 
Apenas I e III
	Comentário da resposta:
	Justificativa:
VII. VERDADEIRA, pois Uma aplicação seria determinar o caminho mais curto entre um determinado par deroteadores para uma rede de computadores.
VIII. FALSA, visto que uma aplicação de ÁRVORE GERADORA DE CUSTO MÍNIMO seria determinar quais estruturas de redes (cabeamentos) devem ser construídas para que o custo da construção seja mínimo envolvendo uma empresa multinacional que possui nove prédios em uma área próxima, e a diretoria deseja conectá-las por meio de cabeamento de redes de tal forma que cada prédio possa se comunicar com outro por meio de uma ou mais estruturas de redes.
VERDADEIRA, pois uma aplicação seria determinar a distância mais curta entre duas localidades tendo por base um mapa de um país/cidade/continente onde cada nó de um grafo pode representar um país/cidade ou cruzamento entre ruas.
	
	
	
 Pergunta 3
3 em 3 pontos
	
	
	
	Uma região composta de 4 cidades possui algumas rodovias que as interligam conforme tabela que indica as distâncias em km das rodovias abaixo .
A partir das informações da tabela, tendo em vista o percurso e as distâncias mínimas para sair da cidade 3 e chegar a quaisquer das outras cidades, considere a execução e os resultados obtidos com o algoritmo de Dijkstra. Além disso, considere as afirmações a seguir.
Com base no descrito e nas afirmações, assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	C. 
Apenas I e II
	Respostas:
	A. 
Apenas I e III
	
	B. 
Apenas I
	
	C. 
Apenas I e II
	
	D. 
I, II e III
	
	E. 
Apenas II
	Comentário da resposta:
	Justificativa:
 
IX. VERDADEIRA, pois na inicialização do algoritmo de Dijkstra o vetor de distâncias será d1i = { 0, infinito, infinito, infinito }.
X. VERDADEIRA, pois a sequência de vértices inserida no conjunto F (Fechado - contendo os vértices para os quais já se conhece um caminho mínimo) na ordem correta de inserção será F = { 1, 4, 2, 3 }.
XI. FALSA, pois ao final da execução do algoritmo de Dijkstra, a sequência de cidades para sair da cidade 3 para chegar na cidade 2, considerando a menor distância, é 3, 4, 2.
	
	
	
 Pergunta 4
0 em 2 pontos
	
	
	
	Considerando os conceitos sobre Caminhos Mínimos em Grafos e as afirmações a seguir .
XII. Há dois tipos básicos de problemas de caminhos mínimos: os que envolvem a determinação de caminhos a partir de um vértice, tendo como algoritmos Dijkstra e Floyd; e os que exigem a determinação dos caminhos unindo todos os pares de vértices, como o algoritmo de Bellman Ford.
XIII. Somente existirão caminhos mínimos entre todos os pares de vértices se o grafo direcionado for categoria C3 ou não direcionado for não conexo.
XIV. O algoritmo de Dijkstra trabalha apenas com grafos ponderados (valorados) com valores positivos.
 
Com base no descrito e nas afirmações, assinale a alternativa correta.
	
	
	
	
		Resposta Selecionada:
	B. 
Apenas II e III
	Respostas:
	A. 
Apenas I
	
	B. 
Apenas II e III
	
	C. 
Apenas I e II
	
	D. 
Apenas III
	
	E. 
I, II e III
	Comentário da resposta:
	Justificativa:
XV. FALSA, pois há dois tipos básicos de problemas de caminhos mínimos: os que envolvem a determinação de caminhos a partir de um vértice, tendo como algoritmos Dijkstra e Bellman Ford; e os que exigem a determinação dos caminhos unindo todos os pares de vértices, como o algoritmo de Floyd.
XVI. FALSA, visto que somente existirão caminhos mínimos entre todos os pares de vértices se o grafo direcionado for categoria C3 ou não direcionado for conexo.
XVII. VERDADEIRA, pois o algoritmo de Dijkstra trabalha apenas com grafos ponderados (valorados) com valores positivos.
	
	
	
· Pergunta 1
0 em 4 pontos
	
	
	
	Seja G = (V,E) um grafo simples, conexo e planar e as afirmações abaixo :
I. G é 4-cromático.
II. Em G a fórmula de Euler "r = m - n + 2" se aplica , onde  r = o número de regiões totalmente fechadas mais uma região infinita exterior,  n = número de vértices e m = o número de arestas.
III. G sempre será pintado com no máximo 3 cores.
As afirmações verdadeiras são:
	
	
	
	
		Resposta Selecionada:
	B. 
Somente (II) e (III)
	Respostas:
	A. 
Somente (I) e (II)
	
	B. 
Somente (II) e (III)
	
	C. 
Somente (I) e (III)
	
	D. 
Todas as afirmações são verdadeiras
	
	E. 
Somente (II)
	Comentário da resposta:
	Justificativa:
A afirmação I é verdadeira, pois segundo o Teorema das 4 cores: Todo grafo planar é 4-cromático.
A afirmação II é verdadeira, pois um grafo simples, conexo e planar a fórmula de Euler se aplica.
A afirmação III é falsa, pois segundo o Teorema das 4 cores, um grafo planar pode ser pintado com até 4 cores.
	
	
	
· Pergunta 2
3 em 3 pontos
	
	
	
	Sejam os grafos não direcionados abaixo:
Os únicos grafos planares são:
	
	
	
	
		Resposta Selecionada:
	B. 
II, III e IV
	Respostas:
	A. 
I e II
	
	B. 
II, III e IV
	
	C. 
I, III e IV
	
	D. 
III e IV
	
	E. 
I, II e III
	Comentário da resposta:
	Os grafos II, III e IV podem ser desenhados em uma folha de papel (no plano) sem a interseção das arestas, portanto são planares
	
	
	
Pergunta 3
3 em 3 pontos
	
	
	
	Qual é o número cromático do grafo K2,9?
	
	
	
	
		Resposta Selecionada:
	D. 2
	Respostas:
	A. 9
	
	B. 4
	
	C. 6
	
	D. 2
	
	E.  8
	Comentário da resposta:
	Justificativa:
Aplicando-se o algoritmo de Coloração Sequencial ou Coloração por Classe obtém-se 2 cores, que é o menor número de cores possíveis para pintar o grafo K2,9, ou seja, X(G) = 2 (número cromático).