Conectividade

Um grafo não dirigido G=(V,E) é conectado quando existe caminho entre todo par de vértices: a distância d(u,v) é finita. Sem caminho, G se parte em componentes, subgrafos maximais conectados.

Corte, ponte e componentes fortemente conexas deste tópico — e árvores geradoras e buscas nos tópicos seguintes — partem dessa relação de alcance.

As páginas se agrupam em três blocos. O primeiro decide se o grafo não dirigido é conectado: marca as componentes por BFS ou DFS e lê d(u,v)=∞ na ausência de caminho.

O segundo parte de G já conectado e remove um vértice ou uma aresta. O número de componentes sobe se o elo era corte ou ponte; disc e low na DFS encontram esses elos.

O terceiro orienta as arestas: forte pede ida e volta em todo par, fraca lê só o subjacente, unilateral pede um sentido. Os blocos maximais fortes são as CFC; contraí-las dá um DAG.

Caminho entre todo par, sem direção, está em Grafos Conectados. Ida e volta com setas, ou só o subjacente conectado, está em Conectividade em Grafos Dirigidos.

A componente conexa — o conjunto alcançável a partir de u — está em Grafos Conectados. A CFC — os v que alcançam u e são alcançados por u — está em Conectividade em Grafos Dirigidos.

Remover v com as arestas incidentes, ou remover a aresta e, está em Vértices de Corte e Pontes. Contar as buscas que marcam V está em Grafos Conectados.

disc[u] e low[u] na DFS não dirigida estão em Vértices de Corte e Pontes. Duas DFS, a segunda no grafo transposto, estão em Conectividade em Grafos Dirigidos.