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
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 6.3.2019 13:03
Odpovědět
6.3.2019 13:03
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?

 
Odpovědět
6.3.2019 13:05
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
6.3.2019 13:14
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
6.3.2019 13:27
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í?

 
Odpovědět
6.3.2019 17:27
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 6.3.2019 17:50
Odpovědět
6.3.2019 17:48
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
6.3.2019 17:58
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?

 
Odpovědět
6.3.2019 18:06
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
6.3.2019 18:42
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
16.4.2019 12:49
Programátor je stroj k převodu kávy na kód.
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.