IT rekvalifikácia. Seniorní programátori zarábajú až 6 000 €/mesiac a rekvalifikácia je prvým krokom. Zisti, ako na to!

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

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre
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ě ★★★★★

Editované 6.3.2019 13:03
Odpovedať
6.3.2019 13:03
Programátor je stroj k převodu kávy na kód.
Avatar
Atrament
Člen IT Redactor Gang
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?

 
Odpovedať
6.3.2019 13:05
Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovedá na Atrament
Ondřej Michálek:6.3.2019 13:14

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

Odpovedať
6.3.2019 13:14
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
krepsy3
Tvůrce
Avatar
Odpovedá 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ů :)

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

 
Odpovedať
6.3.2019 17:27
Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovedá 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...

Editované 6.3.2019 17:50
Odpovedať
6.3.2019 17:48
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovedá 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.

Odpovedať
6.3.2019 17:58
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
jika knaifl
Člen
Avatar
Odpovedá 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?

 
Odpovedať
6.3.2019 18:06
Avatar
Ondřej Michálek
Tvůrce
Avatar
Odpovedá 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í.

Odpovedať
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'

Odpovedať
16.4.2019 12:49
Programátor je stroj k převodu kávy na kód.
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!