Nový algoritmus řeší problém izomorfních grafů

10. listopadu na semináři Kombinatoriky a teoretické informatiky na Univerzitě v Chicagu představil počítačový vědec László Babai svůj nový algoritmus, který řeší problém izomorfních grafů. Co to vlastně jsou izomorfní grafy? Následující obrázek ukazuje dva různé grafy, které jsou naprosto totožné, byť každý vypadá úplně jinak:

Každý vrchol grafu je označen barvou, která odpovídá pro lepší orientaci stejným vrcholům v obou grafech.

Problém, který László Babai řešil je ten, jak nejrychleji určit, zdali jsou dva samostatné soubory propojených bodů, které jsou známé jako grafy, spojeny stejným způsobem i v případě, že oba grafy vypadají zcela odlišně. Na obrázku výše se jedná o vzhledově odlišné hrafy, nicméně jsou oba stejné, tedy izomorfní. Podle Ryana Williamse ze Stanfordovy university se jedná o objev, který je v teoretické informatice nejdůležitější za období více než deseti let.

Dle současných algoritmů se izomorfismus grafů dá zjistit s exponenciální časovou složitostí. To znamená Babai tvrdí, že vytvořil algoritmus, který vyhodnocuje i ty nejkomplikovanější grafy v kvazipolynomiální časové složitosti. Kvazipolynomiální složitost algoritmu se pohybuje mezi exponenciální a polynomiální. Polynomiální je pak následující:

Babi nyní předložil svůj algoritmus vědecké veřejnosti, aby jej buď potvrdila anebo vyvrátila. Samotné testování bude asi nějakou dobu trvat.

Tento algoritmus se dá uplatnit i mimo teoretickou informatiku, například k porovnávání komplexních molekul, zdali mají stejnou vazebnou strukturu.

Zkusil jsem si porovnat oba grafy z obrázku pomocí stromové struktury. U těchto grafů to bude velmi jednoduché, neboť jsou zrcadlové a ať je otáčíme jakkoli, vypadají stále stejně. Výsledek porovnání grafů je zde:

Stavy, které se začínají opakovat jsou označeny modře. Je patrné, že přestože strom nezačal sloučením vrcholů A a 1, ale A a 5, diagram potvrdil izomorfismus. Na první pohled by se dal algoritmus pro zjištění izomorfismu grafů popsat asi takto:

1. Vytvoř tolik stromových diagramů, kolik je v grafu vrcholů.
2. Každý diagram bude začínat kořenem, který bude obsahovat první vrchol z prvního grafu a postupně každý vrchol z druhého grafu.
3. Vypočítej nový řádek pro každý stromový diagram.
4. Pokud v některém stromovém diagramu nedošlo ke správnému spojení vrcholů z obou vstupních grafů, pak tyto dva grafy nemohou být isomorfní a tento stromový diagram odstraň.
5. Pokud nedošlo ke spojení všech vrcholů obou grafů a pokud existuje alespoň jeden stromový diagram pokračuj krokem 3.
6. V tuto chvíli jsme zjistili, zdali jsou grafy izomorfní – pokud máme alespoň jeden stromový diagram.

Z návrhu algoritmu se zdá, že by se nemuselo jednat o exponenciální složitost, ale spíše kvazipolynomiální…

Facebook

Twitter