Hledáš dárek, který neskončí v koši? Nyní 90 % extra kreditů ZDARMA s promo kódem PREKVAPENI90. Zjisti více:
NOVINKA: Staň se datovým analytikem od 0 Kč a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:

Diskuze – Lekce 1 - Úvod do teorie grafů

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Nejnovější komentáře jsou na konci poslední stránky.
Avatar
krepsy3
Tvůrce
Avatar
krepsy3:6.3.2019 13:03

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

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ě ★★★★★

Editováno
Odpovědět
Programátor je stroj k převodu kávy na kód.
Avatar
Atrament
Člen
Avatar
Atrament:6.3.2019 13:05

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?

Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovídá na Atrament
Ondřej Michálek:6.3.2019 13:14

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

Odpovědět
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
krepsy3
Tvůrce
Avatar
Odpovídá na Ondřej Michálek
krepsy3:6.3.2019 13:27

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ů :)

Odpovědět
Programátor je stroj k převodu kávy na kód.
Avatar
jika knaifl
Člen
Avatar
jika knaifl:6.3.2019 17:27

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

Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovídá na jika knaifl
Ondřej Michálek:6.3.2019 17:48

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...

Editováno
Odpovědět
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovídá na Ondřej Michálek
Ondřej Michálek:6.3.2019 17:58

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.

Odpovědět
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
jika knaifl
Člen
Avatar
Odpovídá na Ondřej Michálek
jika knaifl:6.3.2019 18:06

Č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?

Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovídá na jika knaifl
Ondřej Michálek:6.3.2019 18:42

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

Odpovědět
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
krepsy3
Tvůrce
Avatar
krepsy3:16.4.2019 12:49

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'

Odpovědět
Programátor je stroj k převodu kávy na kód.
Nejnovější komentáře jsou na konci poslední stránky.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 12.