Ciclos, ordem topológica e conetividade

Ciclo e ordem

Dirigido usa branco, cinzento e preto. Aresta para cinzento fecha ciclo; para preto não prova nada. Não dirigido ignora só a aresta de entrada; paralelas pedem IDs.

Ordem topológica põe u antes de v em cada u->v. Só existe em DAG.

Método	Faz	Falha quando
DFS	Ordena por saída decrescente	Encontra ciclo
Kahn	Retira um vértice com grau de entrada zero; por cada aresta de saída, decrementa o grau de entrada do destino e põe na fila os que chegam a zero	Retira menos de V

Ambos custam $O(V+E)$. Ordem única só quando Kahn tem uma escolha em cada passo.

Fortes com Tarjan

Uma componente fortemente ligada tem caminho nos dois sentidos entre qualquer par e é máxima com essa propriedade. Contrair cada componente dá um DAG.

1. Quando descobres u, define disc[u]=low[u] com o contador atual e empilha u.
2. Para cada aresta u->v na DFS: se v é filho na árvore, faz low[u]=min(low[u],low[v]) depois da chamada; se v já está na pilha de componentes, faz low[u]=min(low[u],disc[v]).
3. Quando low[u]==disc[u], retira da pilha até u: é uma componente fechada.

Pilha de componentes não é a pilha de chamadas.

1. Fecha 1
   chamadas: 0componentes: 0, 1
   low[1]=0; continua na pilha.
2. 2 vê 1
   chamadas: 0, 2componentes: 0, 1, 2
   Propaga disc[1], porque 1 ainda está na pilha de componentes.
3. Fecha 0
   SCC: 0, 1, 2
   low[0]=disc[0] encerra.

Pontes e articulações

Grafo não dirigido. Ponte aumenta componentes ao sair; articulação ao sair com as suas arestas.

Procura	Condição sobre a aresta da árvore u->v
Ponte u-v	low[v]>disc[u]
Não raiz articula	Algum filho v com low[v]>=disc[u]
Raiz articula	Dois ou mais filhos na DFS

Aqui u é o extremo mais próximo da raiz e v o filho na árvore DFS. low propaga-se pelos filhos e por uma aresta de retorno para um antepassado ainda na pilha. A igualdade evita a ponte mas ainda pode articular. Arestas paralelas eliminam a ponte.

Detalhes e exemplos.