Exercício 13712

Um grafo é uma figura constituída de um número finito de arestas ou arcos, cujas extremidades são chamadas vértices. Em um grafo, a “ordem de um vértice” é o número de extremi- dades de arestas ou arcos que se apoiam naquele vértice. A figura 1 é um grafo cujos vértices A e C possuem ordem 3 (o vértice A é o apoio de um arco cujas extremidades coinci- dem) e os demais vértices possuem ordem 2. E F D Cc A B figura 1 Além disso, dizemos que um grafo admite um “passeio de Euler” se existir um caminho do qual façam parte todas as arestas ou arcos desse grafo, sendo possível desenhá-lo sem tirar o lápis do papel e passando-o uma única vez em cada aresta ou arco. Na figura | é possível fazer um “passeio de Euler” partindo-se apenas dos vértices “A” ou “C”. Por exem- plo, um possível “passeio” pode ser representado pela sequên- cia de vértices dada por: AABCDEFC. Consideres os grafos: I. II. HI. E E E K D E DoF D A Cc A Co A Cc B B B IV. V. E E F D F D At CA c B B Os que admitem um “passeio de Euler” são apenas: (A) Te HI. (B) Ie IV. (C) LIleV. (D) I, Ile IV. (E) LIVev.