Nepostradatelný kanál

Jak na to:

• Detekce cyklů grafu
• Jeden průchod do hloubky
• Návratová hodnota rekurzivní implementace == OPEN uzly do kterých průchod ťuknul
• Všechny uzly při návratu z rekurze jsou v cyklu (a hrany samozřejmě také) až do uzlu, který odpovídá některému v seznamu ťuknutých (implementace: při návratu ze seznamu odeberu uzel, kterým se aktuálně vracím, pokud je seznam neprázdý, tak je pořád v nějakém cyklu)…ťuknutí na CLOSED netřeba řešit (větev byla zpracována z druhé strany (je to přístup z opačné strany do cyklu, který byl vyřešen návratem z OPEN uzlu))
• Tímto postupem se označí všechny hrany v cyklech, zbylé jsou nepostradatelné

Algoritmus hledani mostu:

Hranu, jejíž odebrání by způsobilo zvýšení počtu komponent souvislosti grafu, nazýváme most.

Na hledání mostů nám poslouží opět upravené prohledávání do hloubky a DFS strom. Všimněme si, že mostem může být jedině stromová hrana – každá jiná hrana totiž leží na nějaké kružnici. Odebráním mostu se graf rozpadne na část obsahující kořen DFS stromu a podstrom „visící“ pod touto hranou. Jediné, co tomu může zabránit, je existence nějaké další hrany mezi podstromem a hlavní částí, což musí být zpětná hrana, navíc taková, která není jenom stromovou hranou viděnou z druhé strany. Takovým hranám budeme říkat ryzí zpětné hrany.

Proto si pro každý vrchol spočítáme hladinu, ve které se nachází (kořen je na hladině 0, jeho synové na hladině 1, jejich synové 2, …). Dále si pro každý vrchol v spočítáme, do jaké nejvyšší hladiny (s nejmenším číslem) vedou ryzí zpětné hrany z podstromu s kořenem v. To můžeme udělat přímo při procházení do hloubky, protože než se vrátíme z v, projdeme celý podstrom pod v. Pokud všechny zpětné hrany vedou do hladiny stejné nebo větší než té, na které je v, pak odebráním hrany vedoucí do v z jeho otce vzniknou dvě komponenty souvislosti, čili tato hrana je mostem. V opačném případě jsme nalezli kružnici, na níž tato hrana leží, takže to most být nemůže. Výjimku tvoří kořen, který žádného otce nemá a nemusíme se o něj proto starat.

Algoritmus je tedy pouhou modifikací procházení do hloubky a má i stejnou časovou a paměťovou složitost O(N + M). Zde jsou důležité části programu:

var Hladina, Spojeno: array[1..MaxN] of Integer;

  DvojSouvisle: Boolean;
  I: Integer;

procedure Projdi(V, NovaHladina: Integer); var I, W: Integer; begin

Hladina[V] := NovaHladina;
Spojeno[V] := Hladina[V];
for I := Zacatky[V] to Zacatky[V+1]-1 do
begin
  W := Sousedi[I];
  if Hladina[W] = -1 then
  begin  stromová hrana 
    Projdi(W, NovaHladina + 1);
    if Spojeno[W] < Spojeno[V] then 
      Spojeno[V] := Spojeno[W];
    if Spojeno[W] > Hladina[V] then 
      DvojSouvisle := False; { máme most }
  end else { zpětná nebo dopředná hrana }
  if (Hladina[W] < NovaHladina-1) and
     (Hladina[W] < Spojeno[V]) then
    Spojeno[V] := Hladina[W];
end;

end; begin

...
for I := 1 to N do
  Hladina[I] := -1;
DvojSouvisle := True;
Projdi(1, 0);
...

end.

bohuzel nevim jak udelat, aby to ten kod tady takle nezprznilo …