Lista 1 Algoritmo em grafos

Prévia do material em texto

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS 
 
 
 
 
 
LEONARDO RAVAIANI DA SILVA 
 
 
 
 
 
 
 
 
 
LISTA 1 ALGORITMOS EM GRAFOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
BELO HORIZONTE 
2021/2 
1- 
 
2- a) Unicursal, pois existem 2 vértices de grau ímpar. 
 
b) Não, pois grafo Euleriano não pode conter vértices de grau ímpar, e 
todos os vértices desse grafo são de grau ímpar. 
 
c) n = 20 -> par e n>=4 
 (n-2)/2 = 18/2 = 9 
 9 ciclos hamiltonianos disjuntos de arestas. 
 
3- a) Um grafo completo sempre vai ser regular quando n >= 1, pois todos 
os vértices terão o mesmo grau. 
 
b) Quando n >= 3, todos os vértices terão grau 2. 
 
4- 4n/2 = 2n arestas 
2n = 10, i.e., n = 5 vértices 
 
5- Dado o grafo G com n vértices, seu grafo complementar G’ irá se unir a G 
e fará com que os vértices sejam ligados a todos os outros vértices, 
fazendo que vire um grafo completo. 
 
6- Como cada coluna representa uma aresta, a soma da coluna vale 2, 
quando a aresta liga dois vértices, ou 1, quando a aresta é um laço. 
 
7- a) Sim. Circuito: a-g-f-e-g-h-b-c-d-h-a 
 
b) Ele se tornará Unicursal, pois terá 2 vértices de grau ímpar. 
Caminho: b-c-d-h-g-e-f-g-a-h-b