Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha2 [2009/10/07 23:09]
dundee created
+++ courses:a4m33pal:uloha2 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ==== 2. ÚLOHA ====
 Nepostradatelný kanál
+[[http://cmp.felk.cvut.cz/cmp/courses/a4m33pal/task.php?task=mosty|Zadání]]
+Limit: 2s
+[[http://www.algoritmy.net/article/1525/Nepostradatelny-most|Řešení na Algoritmy.net]]
 Jak na to:
@@ Řádek 8: / Řádek 14: @@
   * 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:
+<code pascal>
+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.
+</code>
+~~DISCUSSION~~

courses/a4m33pal/uloha2.1254949748.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru