Diskusia – 1. diel - Úvod do teórie grafov

Krásný článek, jednoduchý a populárně psaný, pochopitelný i pro nematfyzáky

Jen bych rád podotknul k definici na začátku:

Definice pro normální lidi: Mějme nějaký graf, který je tvořen pomocí puntíků a čar. Puntíky jsou body, čáry jsou hrany. Hrana musí být zakončena vrcholem, jinak to není hrana.

V článku už pak nadále správně používáš pojem vrcholy, takže slovo body mi tu přijde matoucí (a zároveň je zcela objektivně nesprávné, graf nemá nic jako "body")

Takže bych to upravil takto:

Definice pro normální lidi: Mějme nějaký graf, který je tvořen pomocí puntíků (bodů) a čar (úseček). Puntíky jsou vrcholy, čáry jsou hrany. "Čára" musí být zakončena vrcholem, jinak to není hrana.

Jinak je to opravdu zdařilý článek, máš ode mě ★★★★★

Víte, že vrchol na pozici i má potomky na pozici 2i a 2i + 1

nemělo by to být 2i + 1 a 2i + 2?

Máš rozhodně pravdu, 2i a 2i +1 je pro pole indexované od 1.

Ta tradičnější definice skutečně vychází z pole indexovaného od 1, což je standardní např. pro Pascal (ano, dynamická pole jsou od 0, ale ten klasický přístup to tak má), který vzniknul pro výuku programovaní.

Klasická pole indexovaná od 0 mají tu výhodu, že indexy synů mají jen jiné uzávorkování
levý 2i + 1
pravý 2(i + 1)

Samozřejmě je možné odečítat či přičítat jedničku na základě počátku indexů

První obrázek: na grafu vlevo komunikuje v1 s v4, v3. Na grafu vpravo bych čekal totéž, ale není tomu tak. Přesto jsou izomorfní?

Tento graf je blbě pojmenovaný, ale i přesto izomorfní jsou. Špatně jsem to v článku napsal: nejenom přeskládáním, ale i přejmenováním vrcholů jsou grafy izomorfní. Jde o to, že grafy jsou izomorfní, pokud to, co platí pro vrcholy (u,v) tak platí i pro jejich obrazy (f(u),f(v)). Neboli pokud v grafu G vrchol u má souseda v, tak v grafu G' má vrcho f(u) souseda f(v). Neboli jak si vrcholy pojmenuji, je vlastně jedno. Nás zajímají vlastnosti. Pokud z vrcholu u vedou 4 hrany, pak z vrcholu f(u) vedou 4 hrany atd...

Obecně izomorfismus u grafu hledám takto. Zkusím druhý graf přejmenovat tak, aby seděl na ten první graf. Druhý graf by měl mít správně označené vrcholy vůči prvnímu takto: V_1, V_4, V_2, V_4, V_3.

Čili pouze struktura větvení musí zůstat stejná? A co případné délky hran, ty taky musí odpovídat? A směry, v případě orientovaného grafu?

Celá myšlenka izomorfismu stojí na tom, že se to jeví jinak, ale je to stejné. Jelikož nás u grafu zajímají pouze "objekty" = vrcholy a "vztahy" = hrany. Vzdálenosti nejsou důležité. Ani křížení hran nás v podstatě nezajímá. Jsou typy grafů (rovinné grafy), kde to důležité je, ale v obecných grafech ne. Směry odpovídat musí, protože jde o vztah dvou vrcholů, který musí zůstat zachován. Délky hran jsou nám jedno. Chceme-li, můžeme hrany ohodnotit (brzy se objeví ve zdrojácích) Hrana potom sama nese informaci, jestli je dlouhá 1200 ci 5 jednotek, nezávisle na délce hrany v nakreslení.

Ono to není vyloženě blbě. Vrcholy v pravém izomorfu jsou pojmenované s čárkou. Pak lze snadno nahlédnout, že

pokud v1 ~ v1'
pak
v2 ~ v4'
v3 ~ v2'
v4 ~ v5'
v5 ~ v3'