Artikulační body a mosty

O(V + E)

V neorientovaném grafu je artikulační bod (řezný vrchol) vrchol, jehož odebrání graf rozpojí, a most je hrana se stejnou vlastností. Označují jediné body selhání v síti. Tarjanův algoritmus je najde všechny jedním DFS. Při návštěvě každého vrcholu mu přiřadí čas objevení disc[u] a spočítá low[u]: nejdříve objevený vrchol dosažitelný z podstromu u pomocí stromových hran a nejvýš jedné zpětné hrany. Klíčový test pro stromovou hranu z u dolů do v: pokud low[v] ≥ disc[u], pak podstrom v nemá zpětnou hranu šplhající nad u, takže odebrání u by ho odřízlo — u je řezný vrchol. Je-li nerovnost ostrá (low[v] > disc[u]), je hrana u–v most. Kořen DFS je zvláštní: je řezným vrcholem, jen má-li dva či více potomků. Běží v O(V + E). Řezné vrcholy jsou červené, mosty zvýrazněné.

Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. DFS grafu, čísluj vrcholy v pořadí návštěvy (disc).
  2. Sleduj low[u]: nejdříve objevený vrchol dosažitelný z podstromu u.
  3. Potomek, jehož podstrom nešplhá nad u (low[v] ≥ disc[u]), dělá z u řezný vrchol.
  4. Pokud nedosáhne ani na u (low[v] > disc[u]), je spojující hrana most.

Pseudokód

1articulation(graph):                # Tarjan, O(V + E)2  DFS, numbering vertices disc[u] in visit order3  low[u] = lowest disc reachable from u’s subtree4          (via tree edges + one back edge)5  for a tree edge u→v:6    if low[v] ≥ disc[u] and u is not the root: u is a cut vertex7    if low[v] > disc[u]: edge u–v is a bridge8  root is a cut vertex iff it has ≥ 2 DFS children