Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Teoria dos Grafos Professor: Marco Antonio M. Carvalho Lista de Exercícios 10 1. Mostre que se um grafo G não é 2-­‐conexo, então G não é hamiltoniano. 2. Um grafo grade 5x5 é hamiltoniano? E um grafo grade nxn para qualquer valor de n? 3. Demonstre que o primeiro grafo abaixo é hamiltoniano, ao passo que o segundo grafo não é hamiltoniano. 4. Para cada um dos grafos abaixo, xdetermine se o mesmo: a. É hamiltoniano; b. É euleriano; c. É semi-­‐hamiltoniano; d. É semi-­‐euleriano; e. Está de acordo com o teorema de Dirac; f. Está de acordo com o teorema de Ore; g. Está de acordo com o teorema de Bondy-­‐Chvátal; h. Está de acordo com o teorema de Euler. 5. Execute os algoritmos de Hierholzer e Fleury para os grafos do exercício anterior que estão de acordo com o teorema de Euler.