Grafos Infinitos

Um grafo G=(V,E) é infinito quando V ou E é infinito. O caso de trabalho é V contavelmente infinito: os vértices se enumeram v₀, v₁, v₂, …, em bijeção com ℕ.

Caminho entre um par nomeado, raio e término de busca deste tópico — e BFS, DFS e componentes nos tópicos vizinhos — partem dessa enumeração.

As páginas se agrupam em quatro blocos. O primeiro fixa o universo: V enumerável; E infinito implica V infinito.

O segundo separa caminho de raio. Caminho entre u e v é sequência finita; d(u,v) é um natural ou o par está em componentes distintas. Raio é sequência infinita num sentido, sem segundo extremo.

O terceiro calcula nos dois modelos: d(i,j)=|i−j| em P_∞, e a subida ao prefixo comum na árvore binária sobre {0,1}*, sem folhas.

O quarto pergunta se a busca para: BFS encontra o vértice nomeado a distância finita e não esvazia a fila ao varrer V; DFS ao longo de um raio pode não voltar.

Caminho entre u e v nomeados, sempre finito, e o raio sem último termo estão em Introdução aos Grafos Infinitos. Passeio, trilha, caminho e ciclo no grafo finito estão em Passeio, Caminho e Ciclo.

d(i,j)=|i−j| em P_∞ e d(u,v) pela soma dos comprimentos após o prefixo comum em {0,1}* estão em Introdução aos Grafos Infinitos.

Procurar o vértice nomeado e parar na camada k, ou varrer V sem a fila esvaziar, está em Introdução aos Grafos Infinitos. Fila, camadas e término com |V| finito estão em Algoritmo BFS.

DFS que desce sempre à esquerda e nunca visita o ramo direito está em Introdução aos Grafos Infinitos. Pilha e classificação árvore/retorno/avanço/cruzamento estão em Algoritmo DFS.