Avaliação - TEORIA DOS GRAFOS (Prova Online)

Prévia do material em texto

<p>Avaliação - TEORIA DOS GRAFOS</p><p>Prova Online</p><p>Abaixo estão as questões e as alternativas que você selecionou:</p><p>QUESTÃO 1</p><p>Um grafo semi-euleriano é:</p><p>a ) um grafo que possui um caminho euleriano, mas não um ciclo euleriano.</p><p>b ) um grafo euleriano, mas sem um ciclo euleriano.</p><p>c ) um grafo que não possui um caminho euleriano.</p><p>d ) um grafo com ciclo hamiltoniano.</p><p>e ) um grafo sem caminho euleriano, mas em que a adição de uma aresta cria um caminho euleriano.</p><p>Justificativa da resposta</p><p>Segundo a definição, um grafo semi-euleriano possui um caminho que passa por todas as arestas do grafo</p><p>(caminho euleriano), mas que começa e termina em vértices diferentes. Portanto, não é um ciclo.</p><p>A afirmativa que diz que o grafo semi-euleriano é um grafo euleriano, mas sem um ciclo euleriano é</p><p>inconsistente, pois todo grafo euleriano tem um ciclo euleriano.</p><p>O fato de o grafo ter um ciclo hamiltoniano não garante ser euleriano ou semi-euleriano. E, por fim, se um grafo</p><p>não possui caminho euleriano, então, ele não é nem semi-euleriano, nem euleriano, pois, pela definição, um</p><p>grafo semi-euleriano possui um caminho (não um ciclo) que passar por todas as arestas (euleriano).</p><p>QUESTÃO 2</p><p>Dado o grafo a seguir:</p><p>Segundo as características dos algoritmos e o subgrafo encontrado, qual algoritmo poderia gerar esse subgrafo?</p><p>a ) Busca em largura.</p><p>b ) Algoritmo de Kruskal.</p><p>c ) Busca em profundidade.</p><p>d ) Algoritmo de Prim.</p><p>e ) Algoritmo de Dijkstra.</p><p>Justificativa da resposta</p><p>Pelas características do subgrafo encontrado, pode-se dizer que ele é uma árvore geradora. Como o grafo é não</p><p>ponderado, deve ter sido aplicada a busca em largura ou em profundidade. Logo, a busca que tem a característica</p><p>de visitar vértices "filhos" o mais profundo possível é a busca em profundidade.</p><p>QUESTÃO 3</p><p>Dado um grafo G e seu bloco G’, tal que G ≠ G’. Assim, pode-se afirmar que:</p><p>a ) algum vértice de G é uma articulação.</p><p>b ) G’ possui articulações.</p><p>c ) G é hamiltoniano.</p><p>d ) alguma aresta de G é uma ponte.</p><p>e ) G é biconexo em vértices.</p><p>Justificativa da resposta</p><p>QUESTÃO 4</p><p>Pode-se representar o mapa do Brasil como um grafo em que os estados (e o DF) são os vértices e as arestas</p><p>indicam se os estados são vizinhos. Considerando a figura a seguir, indique quantos vértices e quantas arestas o</p><p>mapa possui.</p><p>a ) 27 vértices e 27 arestas.</p><p>b ) 27 vértices e 54 arestas.</p><p>c ) 27 vértices e 51 arestas.</p><p>d ) 27 vértices e 32 arestas.</p><p>e ) 27 vértices e 44 arestas.</p><p>Justificativa da resposta</p><p>Este é o grafo do mapa do Brasil:</p><p>Portanto, são 27 vértices e 51 arestas.</p><p>QUESTÃO 5</p><p>Considerando a seguinte matriz de adjacências, selecione o grafo que ela representa.</p><p>Justificativa da resposta</p><p>QUESTÃO 6</p><p>Para que um grafo completo K2, n > 2 seja eureliano, ele precisa, necessariamente:</p><p>a ) ter um número par de vértices.</p><p>b ) ser bipartido.</p><p>c ) ter um número ímpar de vértices.</p><p>d ) ser hamiltoniano.</p><p>e ) grafos completos não são eulerianos.</p><p>Justificativa da resposta</p><p>QUESTÃO 7</p><p>Considere um grafo simples G = (V, A) euleriano. Sobre G é possível afirmar que:</p><p>a ) o grau de todos os seus vértices é ímpar.</p><p>b ) possui laços.</p><p>c ) é um grafo completo.</p><p>d ) a soma dos graus dos vértices não adjacentes é maior ou igual a |V|.</p><p>e ) o grau de todos os seus vértices é par.</p><p>Justificativa da resposta</p><p>Segundo o teorema de Euler, um grafo é euleriano se, e somente se, o grau de todos os seus vértices é par.</p><p>A soma dos graus dos vértices não adjacentes ser maior ou igual a |V| é parte das condições suficientes para um</p><p>grafo ser hamiltoniano. Como o enunciado traz que o grafo é simples, não é possível que tenha laços. E, por fim,</p><p>não há qualquer menção sobre o grafo ser completo. Apesar de grafos completos serem eulerianos, não é</p><p>possível concluir isso a partir do enunciado.</p><p>QUESTÃO 8</p><p>Segundo o teorema de Appel e Haken (1976), todo grafo planar:</p><p>a ) é 3-colorível.</p><p>b ) é 4-colorível.</p><p>c ) possui um subgrafo homeomorfo a K5 ou K3,3.</p><p>d ) possui uma clique como subgrafo.</p><p>e ) possui uma cobertura de vértices mínima.</p><p>Justificativa da resposta</p><p>Segundo o Teorema das Quatro Cores, de Appel e Haken, todo grafo planar é 4-colorível.</p>