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:

isomorphism

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á oxnBabai 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í:

onx

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:

Babai

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í…

1 comment

  1. Hey, this is Eric and I ran across michaluvweb.cz a few minutes ago.

    Looks great… but now what?

    By that I mean, when someone like me finds your website – either through Search or just bouncing around – what happens next? Do you get a lot of leads from your site, or at least enough to make you happy?

    Honestly, most business websites fall a bit short when it comes to generating paying customers. Studies show that 70% of a site’s visitors disappear and are gone forever after just a moment.

    Here’s an idea…

    How about making it really EASY for every visitor who shows up to get a personal phone call you as soon as they hit your site…

    You can –

    Talk With Web Visitor is a software widget that’s works on your site, ready to capture any visitor’s Name, Email address and Phone Number. It signals you the moment they let you know they’re interested – so that you can talk to that lead while they’re literally looking over your site.

    CLICK HERE http://www.talkwithwebvisitors.com to try out a Live Demo with Talk With Web Visitor now to see exactly how it works.

    You’ll be amazed – the difference between contacting someone within 5 minutes versus a half-hour or more later could increase your results 100-fold.

    It gets even better… once you’ve captured their phone number, with our new SMS Text With Lead feature, you can automatically start a text (SMS) conversation.

    That way, even if you don’t close a deal right away, you can follow up with text messages for new offers, content links, even just “how you doing?” notes to build a relationship.

    Pretty sweet – AND effective.

    CLICK HERE http://www.talkwithwebvisitors.com to discover what Talk With Web Visitor can do for your business.

    You could be converting up to 100X more leads today!

    Eric
    PS: Talk With Web Visitor offers a FREE 14 days trial – and it even includes International Long Distance Calling.
    You have customers waiting to talk with you right now… don’t keep them waiting.
    CLICK HERE http://www.talkwithwebvisitors.com to try Talk With Web Visitor now.

    If you’d like to unsubscribe click here http://talkwithwebvisitors.com/unsubscribe.aspx?d=michaluvweb.cz

Napsat komentář

Your email address will not be published.