Gama algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. ledna 2020; kontroly vyžadují 2 úpravy .

Algoritmus gama  je algoritmus pro položení grafu naplocho a kontrolu jeho rovinnosti podél cesty .

Definice

Algoritmus

Položte na rovinu libovolný cyklus H grafu G bez opakování vrcholů.

  1. Sestrojte všechny segmenty S 1 ,..,S k grafu G z H .
  2. Pokud existuje segment S i s jednou přípustnou plochou  , vyberte jej.
  3. Pokud mají všechny segmenty několik dalších ploch, vyberte kteroukoli.
  4. Vyberte libovolný gama řetězec segmentu a vložte jej do přípustné plochy.
  5. Přejděte ke kroku (2) přidáním gama řetězce do H grafu .

Vlastnosti grafů pro správnou funkci algoritmu

  1. Graf musí být připojen .
  2. Graf musí mít alespoň jeden cyklus .
  3. Graf by neměl mít můstky , tedy hrany, po jejichž odstranění se graf rozdělí na dvě spojené složky .

Pokud dojde k porušení vlastnosti (1), pak je třeba graf skládat samostatně podle připojených komponent. Pokud je porušena vlastnost (2), pak je graf strom a je triviální nakreslit jeho zploštění.

Případ porušení majetku (3) bude zvažován podrobněji. Pokud jsou v grafu můstky, pak je třeba je oříznout, každou připojenou součást zploštit samostatně a poté spojit můstky. Zde může nastat problém: během procesu pokládání mohou být koncové vrcholy mostu uvnitř rovinného grafu. Nakreslíme jednu připojenou součást a postupně k ní přidáme další. Každá nová připojená komponenta bude vykreslena na ploše obsahující koncový vrchol odpovídajícího mostu. Vzhledem k tomu, že graf konektivity můstky připojených komponent je strom, budeme schopni získat ploché balení.

Věta

Graf Г je rovinný právě tehdy, když jej gama algoritmus umístí do roviny.

Důkaz

V opačném směru je důkaz zřejmý.

Pojďme to rovnou dokázat. Je-li graf Γ rovinný, pak podgraf H rozložený v rovině může být dokončen do položení grafu Γ . Zejména pro poslední krok to znamená, že graf Γ je zcela rozložen v rovině.

Nechť je graf Γ rovinný. Potom je libovolný cyklus grafu Γ reprezentován jako mnohoúhelník, když je naskládán. Tento mnohoúhelník je zahrnut do pokládání grafu Γ na rovinu.

Nechť je tvrzení pravdivé až do n-té iterace algoritmu.

Možnosti:

  1. S zapadá do jediné plochy grafu H , graf H je doplněn do ohybu grafu G a v tomto přehybu leží segment S v jediné ploše. V důsledku toho vložení jakékoli gama-dráhy C segmentu S do této plochy vede ke sjednocení grafu H s C , které lze rozšířit na dlaždici Г.
  2. Každý segment má několik platných ploch.

Nechť S  je úsečka s přípustnými plochami F 1 a F 2 . Podgraf H je doplněn do položení grafu Г indukční hypotézou. V tomto případě segment S zapadá do jedné z přípustných ploch. Bez ztráty obecnosti nechť je tato tvář F 1 . Dokažme, že existuje prodloužení H až po položení grafu Г , ve kterém úsečka S leží v ploše F 2 . Protože F 1 a F 2  jsou další plochy, obě obsahují všechny kontaktní vrcholy segmentu S . Proto všechny kontaktní vrcholy segmentu S leží v množině společných vrcholů F 1 a F 2 . Nechť S 1 ,..,S k  jsou všechny segmenty obsažené v F 1 . Nechť S ' 1 ,..,S ' m  jsou všechny segmenty v F 2 obsahující jeden z vrcholů. Nechť segment S'i má vrchol kontaktu a další vrchol kontaktu nepatřící do F 1 . Pak přípustné plochy S ' i je plocha F 2 , a to je předpoklad bodu (2). Z rozporu vyplývá, že všechny vrcholy kontaktu S ' i (podobně jako S i ) leží v množině vrcholů segmentů S ' 1 ,..,S ' m .

Proto při pokládání grafu G je možné posunout segmenty S 1 ,..,S k až F 2 a S ' 1 ,..,S ' m na F 1 , což povede k položení grafu Г , ve kterém segment S leží v ploše F 2 .

Algoritmus tedy přizpůsobí jakýkoli rovinný graf rovině. Což bylo požadováno.

Viz také

Literatura