Jarní soustředění KSP 2012

Recepty z programátorské kuchařky
Grafy

Celý leták, který posíláme také papírově: (PDF) a (PS) pro čtení, (PDF) a (PS) pro tisk.

V dnešním vydání známého bestselleru budeme péci grafy souvislé i nesouvislé, orientované i neorientované, ba i rovinné. Řekneme si o základním procházení grafem, komponentách souvislosti, topologickém uspořádání a dalších grafových algoritmech. Abychom ale mohli začít, musíme si nejprve říci, s čím budeme pracovat.

Ingredience

Neorientovaný graf je určen množinou vrcholů V a množinou hran, což jsou neuspořádané dvojice vrcholů. Hrana e = x, y spojuje vrcholy x a y. Většinou požadujeme, aby hrany nespojovaly vrchol se sebou samým (takovým hranám říkáme smyčky) a aby mezi dvěma vrcholy nevedla více než jedna hrana (pokud toto neplatí, mluvíme o multigrafech). Neorientovaný graf většinou zobrazujeme jako body pospojované čarami.

Neorientovaný graf a jeho kostra; multigraf

Podgrafem grafu G rozumíme graf G', který vznikl z grafu G vynecháním některých (a nebo žádných) hran a vrcholů.

Často nás zajímá, zda se dá z vrcholu x dojít po hranách do vrcholu y. Ovšem slovo „dojít“ by mohlo být trochu zavádějící, proto si zavedeme pár pojmů:

  • sled budeme říkat takové posloupnosti vrcholů a hran tvaru v1,e1,v2,e2,… ,en-1,vn, že ei={vi,vi+1} pro každé i. Sled je tedy nějaká procházka po grafu. Délku sledu měříme počtem hran v této posloupnosti.
  • tah je sled, ve kterém se neopakují hrany, tedy ei ≠ ej pro i ≠ j.
  • cesta je sled, ve kterém se neopakují vrcholy, čili vi ≠ vj pro i ≠ j. Všimněte si, že se nemohou opakovat ani hrany.

Lehce nahlédneme, že pokud existuje sled z vrcholu x do y (v1=x, vn=y), pak také existuje cesta z vrcholu x do vrcholu y. Každý sled, který není cestou, obsahuje nějaký vrchol u dvakrát, nechť u = vi = vj, i < j. Z takového sledu ale můžeme vypustit posloupnost ei,vi+1,… ,ej-1,vj a dostaneme také sled spojující v1 a vn, který je určitě kratší než původní sled. Tak můžeme po konečném počtu úprav dospět až ke sledu, který neobsahuje žádný vrchol dvakrát, tedy k cestě.

Kružnicí nazýváme cestu délky alespoň 3, ve které oproti definici platí v1 = vn. Někdy se na cesty, tahy a kružnice v grafu také díváme jako na podgrafy, které získáme tak, že z grafu vypustíme všechny ostatní vrcholy a hrany.

Ještě si ukážeme, že pokud existuje cesta z vrcholu a do vrcholu b a z vrcholu b do vrcholu c, pak také existuje cesta z vrcholu a do vrcholu c. To vyplývá z faktu, že existuje sled z vrcholu a do vrcholu c, který můžeme dostat například tak, že spojíme za sebe cesty z a do b a z b do c. A jak jsme si ukázali, když existuje sled z a do c, existuje i cesta z a do c.

V mnoha grafech (například v těch na předchozím obrázku) je každý vrchol dosažitelný cestou z každého. Takovým grafům budeme říkat souvislé. Pokud je graf nesouvislý, můžeme ho rozložit na části, které již souvislé jsou a mezi kterými nevedou žádné další hrany. Takové podgrafy nazýváme komponentami souvislosti.

Teď se podívejme na pár pojmů z přírody: Strom je souvislý graf, který neobsahuje kružnici. List je vrchol, ze kterého vede pouze jedna hrana. Ukážeme, že každý strom s alespoň dvěma vrcholy má nejméně dva listy. Proč to? Stačí si najít nejdelší cestu (pokud je takových cest více, zvolíme libovolnou z nich). Oba koncové vrcholy této cesty musí být nutně listy: kdyby z některého z nich vedla hrana, musela by vést do vrcholu, který na cestě ještě neleží (jinak by ve stromu byla kružnice), ale o takovou hranu bychom cestu mohli prodloužit, takže by původní cesta nebyla nejdelší.

Grafům bez kružnic budeme obecně říkat lesy, jelikož každá komponenta souvislosti takového grafu je strom.

Les, jak ho vidí matematici

Někdy se hodí jeden z vrcholů stromu prohlásit za kořen, čímž jsme si v každém vrcholu určili směr nahoru (ke kořeni – je to zvláštní, ale grafoví teoretici obvykle kreslí stromy kořenem vzhůru) a dolů (od kořene). Souseda vrcholu směrem nahoru pak nazýváme jeho otcem, sousedy směrem dolů jeho syny.

Kostra souvislého grafu je strom, který spojuje všechny vrcholy. Pro nesouvislé grafy nazveme kostrou les tvořený kostrami jednotlivých komponent. Na prvním obrázku je kostra levého grafu znázorněna silnými hranami.

Orientované grafy

Často potřebujeme, aby hrany byly pouze jednosměrné. Takovému grafu říkáme orientovaný graf. Hrany jsou nyní uspořádané dvojice vrcholů (x, y) a říkáme, že hrana vede z vrcholu x do vrcholu y. Hrany (x,y) a (y, x) jsou tedy dvě různé hrany (i když se mohou vyskytovat v grafu obě najednou). Orientovaný graf většinou zobrazujeme jako body spojené šipkami. Většina pojmů, které jsme definovali pro neorientované grafy, platí i pro grafy orientované, jen si musíme dát pozor na směr hran. Kružnici v orientovaném grafu často nazýváme cyklem.

Silně a slabě souvislý orientovaný graf

Se souvislostí orientovaných grafů je to trochu složitější. Rozlišujeme slabou a silnou souvislost. Slabě souvislý je graf tehdy, když zapomeneme-li na orientaci hran, dostaneme souvislý orientovaný graf. Silně souvislým ho nazveme tehdy, vede-li mezi každými dvěma vrcholy x, y (x≠ y) orientovaná cesta v obou směrech. Pokud je graf silně souvislý, je i slabě souvislý, ale jak ukazuje náš obrázek, opačně to platit nemusí.

Komponenta silné souvislosti orientovaného grafu G je takový podgraf G', který je silně souvislý a není podgrafem žádného většího silně souvislého podgrafu grafu G. Komponenty silné souvislosti tedy mohou být mezi sebou propojeny, ale žádné dvě nemohou ležet na společném cyklu.

Reprezentace grafů

Nyní už víme o grafech hodně, ale ještě jsme si neřekli, jak graf reprezentovat v paměti počítače. Nejčastější jsou tyto dva způsoby:

  • matice sousednosti – to je pole A velikosti N ×N (kde N je počet vrcholů). Na pozici A[i, j] uložíme hodnotu 0 nebo 1 podle toho, zda z vrcholu i do vrcholu j vede hrana (1) nebo nevede (0). S maticí sousednosti se zachází velmi snadno, ale má tu nevýhodu, že je vždy kvadraticky velká bez ohledu na to, kolik je hran. Výhodou naopak je, že místo jedniček můžeme ukládat nějaké další informace o hranách, třeba jejich délky. Vpravo od tohoto odstavce najdete matici sousednosti grafu z prvního obrázku.
    011000001
    100110001
    100100000
    011010000
    010101000
    000010110
    000001011
    100001100
    110000100
  • seznam sousedů se obvykle zapisuje dvěma poli: polem hran E, do kterého uložíme všechny hrany tak, aby hrany vedoucí z jednoho vrcholu tvořily souvislý úsek, a polem vrcholů V, které pro každý vrchol udává začátek odpovídajícího úseku v poli E. Pokud do V[N+1] uložíme M+1, kde M je počet hran, platí, že hrany vycházející z vrcholu i jsou uloženy v E[V[i]], …, E[V[i+1]-1]. Tato reprezentace má tu výhodu, že má velikost pouze O(N + M) a sousedy každého vrcholu máme pěkně pohromadě a nemusíme je hledat. Pro graf z 1. obrázku:
Reprezentace grafu seznamem vrcholů

Recepty

Naše povídání o grafových algoritmech začneme dvěma základními způsoby procházení grafem. K tomu budeme potřebovat dvě podobné jednoduché datové struktury: Fronta je konečná posloupnost prvků, která má označený začátek a konec. Když do ní přidáváme nový prvek, přidáme ho na konec posloupnosti. Když z ní prvek odebíráme, odebereme ten na začátku. Proto se tato struktura anglicky nazývá first in, first out, zkráceně FIFO. Zásobník je také konečná posloupnost prvků se začátkem a koncem, ale prvky přidáváme a odebíráme z konce zásobníku. Anglický název je (překvapivě) last in, first out, čili LIFO.

Hroch ve studni

Algoritmus prohledávání grafu do hloubky:

  1. Na začátku máme v zásobníku pouze vstupní vrchol w. Dále si u každého vrcholu v pamatujeme značku zv, která říká, zda jsme vrchol již navštívili. Vstupní vrchol je označený, ostatní vrcholy nikoliv.
  2. Odebereme vrchol ze zásobníku, nazvěme ho u.
  3. Každý neoznačený vrchol, do kterého vede hrana z u, přidáme na zásobník a označíme.
  4. Body 2 a 3 opakujeme, dokud není zásobník prázdný.

Na konci algoritmu budou označeny všechny vrcholy dosažitelné z vrcholu w, tedy v případě neorientovaného grafu celá komponenta souvislosti obsahující w. To můžeme snadno dokázat sporem: Předpokládáme, že existuje vrchol x, který není označen, ale do kterého vede cesta z w. Pokud je takových vrcholů více, vezmeme si ten nejbližší k w. Označme si y předchůdce vrcholu x na nejkratší cestě z w; y je určitě označený (jinak by x nebyl nejbližší neoznačený). Vrchol y se tedy musel někdy objevit na zásobníku, tím pádem jsme ho také museli ze zásobníku odebrat a v kroku 3 označit všechny jeho sousedy, tedy i vrchol x, což je ovšem spor.

To, že algoritmus někdy skončí, nahlédneme snadno: v kroku 3 na zásobník přidáváme pouze vrcholy, které dosud nejsou označeny, a hned je značíme. Proto se každý vrchol může na zásobníku objevit nejvýše jednou, a jelikož v bodě 2 pokaždé odebereme jeden vrchol ze zásobníku, musí vrcholy někdy (konkrétně po nejvýše N opakováních cyklu) dojít. V bodu 3 probereme každou hranu grafu nejvýše dvakrát (v každém směru jednou). Časová složitost celého algoritmu je tedy lineární v počtu vrcholů N a počtu hran M – O(N+M). Paměťová složitost je stejná, protože si musíme hrany a vrcholy pamatovat.

Nejjednodušší implementace prohledávání do hloubky je rekurzivní funkcí. Jako zásobník v tom případě požíváme přímo zásobník programu, kde si program ukládá návratové adresy funkcí. Může to vypadat třeba následovně:

var Hrany: array[1..MaxN + 1] of Integer; 
  Sousedi: array[1..MaxM] of Integer; 
  Oznacen: array[1..MaxN] of Boolean;
 
procedure Projdi(V: Integer); 
var I: Integer; 
begin
  Oznacen[V]:= True; 
  for I:= Hrany[V] to Hrany[V + 1] do
    if not Oznacen[Sousedi[I]] then 
      Rekurze(Sousedi[I]); 
end;

Rozdělit neorientovaný graf na komponenty souvislosti je pak už jednoduché. Projdeme postupně všechny vrcholy grafu a pokud nejsou v žádné z dosud označených komponent grafu, přidáme novou komponentu tak, že graf z tohoto vrcholu prohledáme do hloubky. Vrcholy značíme přímo číslem komponenty, do které patří. Protože prohledáváme do hloubky několik oddělených částí grafu, každou se složitostí O(Ni + Mi), kde Ni a Mi je počet vrcholů a hran komponenty, vyjde dohromady složitost O(N + M). Nic nového si ukládat nemusíme, a proto je paměťová složitost také O(N + M).

var Komponenta: array[1..MaxN] of Integer; 
  Hrany: array[1..MaxN + 1] of Integer; 
  Sousedi: array[1..MaxM] of Integer;
  NovaKomponenta: Integer;
 
procedure Projdi(V: Integer); 
var I: Integer; 
begin
  Komponenta[V]:= NovaKomponenta; 
  for I:= Hrany[V] to Hrany[V + 1] do 
    if (Komponenta[Sousedi[I]] = -1) then
      Rekurze(Sousedi[I]); 
end; 
var I: Integer; 
begin 
   ...  
   for I:= 1 to N do Komponenta[I]:= -1;
   NovaKomponenta:= 1; 
   for I:= 1 to N do
      if Komponenta[I] = -1 then 
         begin 
            Projdi(I);
            Inc(NovaKomponenta); 
         end; 
   ...
end.

Průbeh prohledávání grafu do hloubky můžeme znázornit stromem. Z počátečního vrchol w učiníme kořen. Pak budeme graf procházet do hloubky a vrcholy zakreslujeme jako syny vrcholů, ze kterých jsme přišli. Hranám mezi těmito vrcholy budeme říkat stromové hrany. Protože jsme do žádného vrcholu nešli dvakrát, vznikne nám strom. Hrany, které vedou do již navštívených vrcholů na cestě, kterou jsme přišli z kořene, jsou tzv. zpětné hrany. Dopředné hrany vedou naopak z vrcholu blíže kořeni do už označeného vrcholu dále od kořene. A konečně příčné hrany vedou mezi dvěma různými podstromy grafu.

Všimněte si, že při prohledávání neorientovaného grafu objevíme každou hranu dvakrát: buďto poprvé jako stromovou a podruhé jako zpětnou, a nebo jednou jako zpětnou a podruhé jako dopřednou. Příčné hrany se objevit nemohou – pokud by příčná hrana vedla „doprava“, vedla by do dosud neoznačeného vrcholu, takže by se prohledávání vydalo touto hranou a nevznikl by oddělený podstrom; „doleva“ rovněž vést nemůže: představme si stav prohledávání v okamžiku, kdy jsme opouštěli levý vrchol této hrany. Tehdy by naše hrana musela být příčnou vedoucí doprava, ale o té už víme, že neexistuje.

Strom prohledávání do hloubky

Prohledávání do hloubky lze tedy využít na hledání kostry neorientovaného grafu, což je strom, který jsme prošli, a rovnou při tom také zjistíme, zda graf neobsahuje cyklus, což je v případě, kdy nalezneme zpětnou hranu různou od té stromové, kterou jsme do vrcholu přišli.

Pro orientované grafy je opět situace složitější: stromové a dopředné hrany jsou orientované vždy ve stromě shora dolů, zpětné zdola nahorů a příčné hrany mohou existovat, ovšem vždy vedou „zprava doleva“, tedy pouze do podstromů, které jsme již prošli (nahlédneme opět stejně).

Prohledávání do šířky

Prohledávání do šířky je založené na trochu jiné myšlence a narozdíl od prohledávání do šírky používá jinou datovou strukturu, a to frontu.

  1. Na začátku máme ve frontě pouze jeden prvek, a to zadaný vrchol w. Dále si u každého vrcholu x pamatujeme číslo H[x]. Všechny vrcholy budou mít na začátku H[x] = -1, jen H[w] = 0.
  2. Odebereme vrchol z fronty, označme ho u.
  3. Každý vrchol v, do kterého vede hrana z u a jeho H[v] = -1, přidáme do fronty a dáme nastavíme jeho H[v] na H[u] + 1.
  4. Body 2 a 3 opakujeme, dokud není fronta prázdná.
Podobně jako u prohledávání do hloubky jsme se dostali právě do těch vrcholů, do kterých vede cesta z w (a označili jsme je nezápornými čísly). Rovněž je každému vrcholu přiřazeno nezáporné číslo maximálně jednou. Vrcholy se stejným číslem tvoří ve frontě jeden souvislý celek, protože nejprve odebereme z fronty všechny vrcholy s číslem n, než začneme odebírat vrcholy s číslem n + 1. Navíc platí, že H[v] udává délku nejkratší cesty z vrcholu w do x. Že neexistuje kratší cesta, dokážeme sporem: Pokud existuje nějaký vrchol v, pro který H[v] neodpovídá délce nejkratší cesty z w do v, čili vzdálenosti D[v], vybereme si z takových v to, jehož D[v] je nejmenší. Pak nalezneme nejkratší cestu z w do v a předposlední vrchol z této cesty. Vrchol z je bližší než v, takže pro něj už musí být D[z]=H[z]. Ovšem když jsme z fronty vrchol z odebírali, museli jsme objevit i jeho souseda v, který ještě nemohl být označený, tudíž jsme mu museli přidělit H[v]=H[z]+1=D[v], což je spor.

Prohledávání do šířky má časovou složitost taktéž lineární s počtem hran a vrcholů. Na každou hranu se také ptáme dvakrát. Fronta má lineární velikost k počtu vrcholů, takže jsme si oproti prohledávání do hloubky nepohoršili a i paměťová složitost je O(N + M). Algoritmus implementujeme nejsnáze cyklem, který bude pracovat s vrcholy v poli, které nám bude představovat frontu.

var Fronta, Delka: array[1..MaxN] of Integer;
  Oznacen: array[1..MaxN] of Boolean;
  Hrany: array[1..MaxN + 1] of Integer;
  Sousedi: array[1..MaxM] of Integer;
  I, Prvni, Posledni, PocatecniVrchol: Integer;
begin
  ...
  Prvni:= 1;
  Posledni:= 1;
  Fronta[Prvni]:= PocatecniVrchol;
  Delka[Prvni]:= 0;
 
  repeat 
  for I:= Hrany[Fronta[Prvni]] to 
                 Hrany[Fronta[Prvni]+1]-1 do
    if not Oznacen[Sousedi[I]] then begin
      Oznacen[Sousedi[I]]:= True;
      Delka[Sousedi[I]]:=Delka[Fronta[Prvni]]+1;
      Inc(Posledni);
      Fronta[Posledni]:= Sousedi[I];
    end;
  Inc(Prvni);
  until Prvni > Posledni;  {Fronta je prazdna}
  ...
end.

Prohledávání do šířky lze také použít na hledání komponent souvislosti a hledání kostry grafu.

Topologické uspořádání

Teď si vysvětlíme, co je to topologické uspořádání. Máme orientovaný graf G s N vrcholy a chceme očíslovat vrcholy čísly 1 až N tak, aby všechny hrany vedly z vrcholu s větším číslem do vrcholu s menším číslem, tedy pro každou hranu e = (vi, vj) platí i > j. Představme si ho jako srovnání vrcholů grafu na přímku tak, aby „šipky“ vedly pouze zprava doleva.

Nejprve si ukážeme, že pro žádný orientovaný graf, který obsahuje cyklus, nelze takovéto topologické pořadí vytvořit. Označme vrcholy tohoto cyklu v1, …, vn, takže hrana vede z vrcholu vi do vrcholu vi-1, resp z v1 do vn. Pak vrchol v2 musí dostat vyšší číslo než vrchol v1, v3 než v2,… , vn než vn-1. Ale vrchol v1 musí mít zároveň vyšší číslo než vn, což je spor.

Pokud graf cyklus neobsahuje, lze ho vždycky topologicky uspořádat. Zde je algoritmus:

  1. Na začátku máme orientovaný graf G a proměnnou p = 1.
  2. Najdeme takový vrchol v, ze kterého nevede žádná hrana. Pokud žádný takový není, výpočet končí, protože jsme našli cyklus.
  3. Odebereme z grafu vrchol v a všechny hrany, které do něj vedou.
  4. Přiřadíme vrcholu v číslo p.
  5. Proměnnou p zvýšíme o 1.
  6. Opakujeme kroky 2 až 5, dokud graf obsahuje alespoň jeden vrchol.
Nejprve si ukážeme, že neprázdný graf, který neobsahuje cyklus, vždy obsahuje vrchol, ze kterého nevede žádná hrana. Pro spor předpokládejme, že žádný takový vrchol neexistuje. Pak si vyberme libovolný vrchol v1. Z něj vede hrana do dalších vrcholů, vybereme jeden z nich a označme ho v2. Z v2 vybereme další hranu a takto pokračujeme. Protože je vrcholů konečný počet, dospějeme k jednomu z těchto případů:
  • Z některého vrcholu vi nevede žádná hrana.
  • Některé dva vrcholy vi, vj jsou stejné, a graf tedy obsahuje cyklus.
Což je spor s našimi předpoklady. Graf G má konečně mnoho vrcholů a protože v bodě 3 pokaždé odebereme další vrchol grafu, musí algoritmus skončit. Z vrcholu v, který přidáváme do posloupnosti, nevedou žádné hrany, a proto může mít nižší číslo než zbývající vrcholy grafu. To platí pro každý takový vrchol v, a proto je uspořádání korektní.

Algoritmus můžeme snadno upravit tak, aby netratil příliš času hledáním vrcholů, z nichž nic nevede – stačí si takové vrcholy pamatovat ve frontě, a kdykoliv nějaký takový vrchol odstraňujeme, zkontrolujeme si, zda jsme nějakému jinému vrcholu nezrušili poslední hranu, která z něj vedla, a pokud ano, přidáme takový vrchol na konec fronty. Celé topologické třídění pak zvládneme v čase O(N+M).

Také můžeme graf prohledat do hloubky a všimnout si, že pořadí, ve kterém jsme se z vrcholů vraceli, je právě topologické pořadí. Pokud právě opouštíme nějaký vrchol a číslujeme ho dalším číslem v pořadí, rozmysleme si, jaké druhy hran z něj mohou vést: stromová nebo dopředná hrana vede do vrcholu, kterému jsme již přiřadili vyšší číslo, zpětná existovat nemůže (v grafu by byl cyklus) a příčné hrany vedou pouze zprava doleva, takže také do již očíslovaných vrcholů. Časová složitost je opět O(N+M).

var Hrany: array[1..MaxN + 1] of Integer;
  Sousedi: array[1..MaxM] of Integer;
  Ocislovani: array[1..MaxN] of Integer;
  Posledni: Integer;
  I: Integer;
procedure Projdi(V: Integer);
var I: Integer;
begin
  for I:= Hrany[V] to Hrany[V+1]-1 do
    if Ocislovani[Sousedi[I]] = 0 then 
      Projdi(Sousedi[I]);
 
  Inc(Posledni);
  Ocislovani[Vrchol]:= Posledni;
end;
 
begin
  ...
  for I:= 1 to N do
  Ocislovani[I]:= 0;
 
  Posledni:= 0;
  for I:= 1 to N do
  if Ocislovani[I] = 0 then Projdi(I);
  ...
end.

Hranová a vrcholová souvislost

Nyní se podíváme na trochu komplikovanější formu souvislosti. Říkáme, že neorientovaný graf je hranově 2-souvislý, když platí, že:

  • má 3 a více vrcholů,
  • je souvislý,
  • zůstane souvislý po odebrání libovolné hrany.
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. Pokud by v grafu nebyly žádné zpětné hrany, byla by mostem každá hrana – rozdělila by graf na část obsahující kořen a podstrom „visící“ pod touto hranou. Aby nevznikly dvě komponenty souvislosti, musí mezi těmito částmi vést další hrana (a může to být jedině zpětná hrana).

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é nejnižší hladiny vedou 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 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 Hrany: array[1..MaxN + 1] of Integer;
  Sousedi: array[1..MaxM] of Integer;
  Hladina, Spojeno: array[1..MaxN] of Integer;
  DvaSouvisle: Boolean;
  I: Integer;
 
procedure Projdi(V, NovaHladina: Integer);
var I: Integer;
begin
  Hladina[V]:= NovaHladina;
  Spojeno[V]:= Hladina[V];
 
  for I:= Hrany[V] to Hrany[V + 1] do
    if Hladina[Sousedi[I]] = -1 then
    begin
      Projdi(Sousedi[I], NovaHladina + 1);
      if Spojeno[Sousedi[I]] < Spojeno[V] then 
        Spojeno[V]:= Spojeno[Sousedi[I]];
      if Spojeno[Sousedi[I]] > Hladina[V] then 
        DvaSouvisle:= False;
    end else
    if Hladina[Sousedi[I]] < Spojeno[V] then 
      Spojeno[V]:= Hladina[Sousedi[I]];
end;
 
begin
  ...
  for I:= 1 to N do
    Hladina[I]:= -1;
 
  DvaSouvisle:= True;
  Projdi(1, 0);
  ...
end.

Další formou souvislosti je vrcholová souvislost. Graf je vrcholově 2-souvislý, právě když:

  • má 3 a více vrcholů,
  • je souvislý,
  • zůstane souvislý po odebrání libovolného vrcholu.
Artikulace je takový vrchol, který když odebereme, zvýší se nám počet komponent souvislosti.

Algoritmus pro zjištění vrcholové 2-souvislosti grafu je velmi podobný algoritmu na zjišťování hranové 2-souvislosti. Jen si musíme uvědomit, že odebíráme celý vrchol. Ze stromu procházení do hloubky může odebráním vrcholu vzniknout až několik podstromů, které všechny musí být spojeny zpětnou hranou s hlavním stromem. Proto musí zpětné hrany z podstromu určeného vrcholem v vést až nad vrchol v. Speciálně pro kořen nám vychází, že může mít pouze jednoho syna, jinak bychom ho mohli odebrat a vytvořit tak dvě nebo více komponent souvislosti. Algoritmus se od hledání hranové 2-souvislosti liší jedinou změnou ostré nerovnosti na neostrou, sami zkuste najít, které nerovnosti.

O rovinných grafech

Rovinný graf je graf, který můžeme nakreslit do roviny tak, že vrcholům přiřadíme vhodné body a hrany nakreslíme jako křivky spojující příslušné body, a to tak, že se žádné dvě křivky neprotínají mimo své krajní body. Ne každý graf takto nakreslit můžeme – sami si rozmyslete, že například graf K5, což je 5 vrcholů spojených každý s každým, žádné rovinné nakreslení nemá. Na druhou stranu například každý strom určitě rovinný je.

Vezměme si tedy nějaký graf a jeho rovinné nakreslení, například tento:

Rovinný graf

Hrany nakreslení dělí rovinu na několik oblastí, těm budeme říkat stěny. Náš graf má 6 stěn: jednu čtvercovou, čtyři „trojúhelníkové“ (tedy ohraničené třemi hranami, byť to nejsou vždy úsečky) a jednu 6-úhelníkovou (to je celý zbytek roviny okolo grafu, tzv. vnější stěna). Například libovolné rovinné nakreslení stromu by mělo pouze jednu stěnu, a to tu vnější. Všimněte si, že pokud v grafu nejsou mosty ani akrtikulace, je každá stěna ohraničena nějakou kružnicí. [Pozor, to, jak vypadají stěny, závisí na konkrétním nakreslení do roviny!]

O rovinných grafech platí několik důležitých vět, které se často hodí při vytváření grafových algoritmů:

Věta: (o počtu hran stromu) Pro každý strom platí, že e=v-1, kde v je počet vrcholů a e počet hran.

Důkaz: Indukcí podle počtu vrcholů. Pro strom s jedním vrcholem formulka určitě platí. Strom s v>1 vrcholy má jistě list, tak jej odtrhneme [poněkud vandalské, nicméně účinné], čímž získáme strom s menším počtem vrcholů, pro který podle indukčního předpokladu formulka platí, a opětovným přidáním listu platit nepřestane, protože k oběma stranám přičteme jedničku.

Věta: (Eulerova formule) Pro každý souvislý graf nakreslený do roviny platí, že v+f=e+2, kde v je počet vrcholů, e počet hran a f počet stěn.

Důkaz: Opět indukcí, tentokráte podle počtu hran. Každý souvislý graf má alespoň v-1 hran a pokud jich má právě tolik, je to strom. (Kdyby ne, stačí se podívat na kostru grafu, což musí být strom a ty, jak už víme, mají právě tolik hran a náš graf měl hran více.) Jenže každé rovinné nakreslení stromu má právě jednu stěnu, takže Eulerova formule platí.

Pokud máme nakreslení grafu, který je souvislý a není to strom, znamená to, že obsahuje alespoň jednu kružnici. A každá hrana na kružnici jistě odděluje nějaké dvě stěny. Zvolme si tedy nějakou takovou hranu h a z grafu ji odeberme. Tím získáme graf s menším počtem hran (opět nakreslený do roviny), použijeme indukční předpoklad, Eulerova formule pro něj tedy již platí, a vrátíme hranu zpět. Levá strana rovnosti se tím zvětší o 1 (přidali jsme stěnu), pravá také (přidali jsme hranu), tedy rovnost stále platí.

Věta: (o hustotě rovinných grafů) O každém rovinném grafu platí, že e ≤ 3v-6.

Důkaz: Zvolme si libovolné nakreslení grafu do roviny. Nejprve předpokládejme, že je to triangulace, čili že každá stěna je trojúhelník. V takovém grafu patří každá hrana k právě dvěma trojúhelníkovým stěnám, takže e=f·3/2, čili f=e·2/3. Dosazením do Eulerovy formule získáme v+(2/3)e=e+2, tedy e=3v-6.

Není-li náš graf triangulace, může to mít několik důvodů. Buďto není souvislý (pak ale stačí větu dokázat pro jednotlivé komponenty a nerovnosti sečíst), nebo je moc malý (má nejvýše dva vrcholy, proto to musí být jedna samotná hrana a pro tu naše věta určitě platí) a nebo obsahuje nějakou stěnu ohraničenou více než třemi hranami. Dovnitř takové stěny ovšem můžeme dokreslit další hrany a tím ji rozdělit na trojúhelníčky. Tím tedy dokážeme graf doplnit hranami na triangulaci, pro tu, jak už víme, platí dokonce rovnost, a když přidané hrany opět odebereme, snížíme pouze počet hran a uděláme tak z rovnosti nerovnost.

Věta: (o vrcholu nízkého stupně) V každém rovinném grafu existuje vrchol stupně maximálně 5. (Stupeň vrcholu je počet hran, které s vrcholem sousedí.)

Důkaz: Sporem. Kdyby všechny vrcholy měly stupeň alespoň 6, byl by součet stupňů alespoň 6v. Jenže součet stupňů je přesně dvojnásobek počtu hran (každá hrana má dva konce), takže e≥ 3v, což je spor s předchozí větou.

Poznámky na okraj:

  • K čemu je to všechno dobré, zjistíte třeba v řešení úlohy 17-1-2.
  • Kdybychom definici rovinného nakreslení změnili a dovolili hrany kreslit pouze jako úsečky místo libovolných křivek, překvapivě se nic nezmění: každý rovinný graf má rovinné nakreslení, v němž jsou všechny hrany úsečky. Ale není to zrovna jednoduché dokázat.
  • Stejně jako do roviny bychom mohli grafy kreslit třeba na povrch koule. Tím se také nic nezmění, zkuste sami vymyslet, jak z rovinného nakreslení udělat „kulové“ a naopak. Ale třeba anuloid (povrch pneumatiky) se už chová jinak, například zmíněný nerovinný graf K5 se na anuloid dá nakreslit bez křížení hran.
  • Rovinné grafy, jejichž všechny vrcholy mají stupeň právě 5, opravdu existují, je to například graf odpovídající pravidelnému dvacetistěnu [má 12 vrcholů stupně 5 a 20 trojúhelníkových stěn]. V jistém smyslu je tedy naše poslední věta nejlepší možná.
  • Více informací o teorii (nejen rovinných) grafů najdete například v knížce pánů Matouška a Nešetřila Kapitoly z diskrétní matematiky.
Dnešní menu Vám servírovali
Martin Mareš & Petr Škoda