aula4

Grafos Eulerianos:

Um grafo possui um percurso euleriano se existe um

caminho no grafo (aberto ou fechado) que inclui todas as

arestas

Circuito Euleriano: Um circuito euleriano em um grafo G é um

circuito simples que contem cada aresta

Algoritmo de Hierholzer: Algoritmo para a construção de um ciclo euleriano sugerido a partir da prova do teorema de Euler

Aqui você vai removendo as arestas que passou para conseguir testar se tem um ciclo euleriano no grafo

Grafos Hamiltonianos

Um grafo possui um percurso hamiltoniano se possui um caminho (aberto ou fechado (ciclo)) que inclui todos os vértices do grafo apenas uma vez

Um grafo É HAMILTONIANO se possui um caminho fechado (ciclo) que inclui todos os vértices do grafo apenas uma vez

Um ciclo hamitoniano em um grafo conexo G é definido como um caminho simples e fechado, isto é, passa-se por cada vértice de G exatamente uma vez, exceto, naturalmente, no vértice inicial que é considerado também vértice terminal.

Define-se caminho hamiltoniano como sendo um caminho simples e aberto que passa por cada vértice de G exatamente uma vez.

Grafos Não Hamiltonianos

Se um vértice v tem grau 2, todas as arestas incidentes em v devem fazer parte de

qualquer ciclo hamiltoniano

Durante a construção, nenhum ciclo pode ser formado até todos os vértices terem sido

visitados

Se durante a construção, duas arestas incidentes em um vértice v são necessárias,

todas as outras arestas incidentes podem ser apagadas