Caminhos e Ciclos

Um caminho em G=(V,E) é uma sequência de vértices adjacentes sem repetir vértice. O ciclo fecha essa sequência no início. O passeio admite repetição; a trilha exige arestas distintas. O comprimento é o número de arestas.

Trilha euleriana e caminho hamiltoniano deste tópico — e conexidade, árvores geradoras e buscas nos tópicos seguintes — partem desse percurso.

As páginas se agrupam em três blocos. O primeiro classifica uma sequência dada: passeio, trilha, caminho ou ciclo, aberto ou fechado, e reconhece a corda de um ciclo.

O segundo decide se as arestas cabem numa só trilha, pelos graus e pela componente que tem aresta. No digrafo o suporte precisa ser fracamente conexo.

O terceiro decide se os vértices cabem numa só ordem: caminho hamiltoniano com n−1 arestas, ou circuito com a aresta de fechamento. Dirac e Ore garantem o circuito quando valem; partes desiguais num bipartido o descartam.

Nomear o que uma sequência pode repetir, se ela fecha, ou se uma aresta é corda, está em Passeio, Caminho e Ciclo. Decidir se alguma trilha esgota E está em Caminhos e Circuitos Eulerianos.

Contar graus ímpares — zero ou dois — e a componente com aresta está em Caminhos e Circuitos Eulerianos. Montar uma permutação de V com aresta entre consecutivos está em Caminhos e Circuitos Hamiltonianos.

Grau 0 não cria componente com aresta: o isolado fica fora do teste euleriano, em Caminhos e Circuitos Eulerianos. Grau 1 impede o circuito hamiltoniano, porque cada vértice do ciclo usa duas arestas; isso está em Caminhos e Circuitos Hamiltonianos.