TGD1

Neoficiální stránky předmětu TGD1 - Teorie grafů a diskrétní optimalizace 1 očima jednoho matematického analfabeta.

Poslední úpravy 13.2.2006 - a budou další.

Účelem těchto stránek je doplnit informace, které se dají získat na oficiálních stránkách o materiály, které tam nenaleznete. Budiž to činěno ku prospěchu všem, kteří mají potřebu či zájem.
Tento předmět jsem navštěvoval v zimním semestru školního roku 2005/2006 a mým učitelem byl Prof. RNDr. Zdeněk Ryjáček, DrSc.

Několik užitečných odkazů:
Oficiální stránky předmětu - na kterých je ke stažení dokument s pracovními texty přednášek.
K doporučené literatuře patří skripta Diskrétní matematika, která obsahem více odpovídají stejnojmennému předmětu, ze kterého však TGD1 vychází. Skripta napsali autoři Roman Čada, Tomáš Kaiser, Zdeněk Ryjáček a vydala Západočeská univerzita v Plzni. K dostání v univerzitní prodejně skript. Cena 210 Kč

Fotografie z přednášek.

Je až obdivuhodné, s jakou rychlostí dokáže pan Ryjáček pokrýt tabuli grafickými útvary a přitom navíc ještě plynule provádět výklad. Nejen z vlastní zkušenosti vím, že je občas nesnadné soustředěně vnímat výklad a ještě přitom provádět nákresy. Je sice pravda, že jsou k dispozici vypracované zápisy z přednášek, ale co si člověk sám prožije a vyzkouší je jen obtížně nahraditelné.
Na pomoc tak přichází "moderní technika" a za pomoci digitálního fotoaparátu doháním co má ruka zameškala. Zde jsou tedy fotografie z jednotlivých přednášek. Omluvte prosím sníženou kvalitu jsem jen fotograf amatér.
Přednáška 1. Přednáška 2. Přednáška 3. Přednáška 4. Přednáška 5. Přednáška 6. Přednáška 7. Přednáška 8. Přednáška 9. Přednáška 10. Přednáška 11.
Oskenované příklady ze cvičení. Zatím jako 2 MB ZIP soubor. Určitě je ještě vylepším.

Paměťové mapy Teorie Grafů

Moje snaha setřídit poznatky z příprav na zkoušku. Samozřejmě grafem :-)
Prozatím příprava není úplně kompletní.

Verze s obrázkem a klikací mapou.

Verze v jednoduchém html.
Verze s javascriptem.

Odkazy na stránky s podobnou tématikou.

http://cs.wikipedia.org/wiki/Graf Odkaz na stránky Wikipedie nejnovější to způsob předávání lidského poznání. Kdokoliv může přispět. Stačí stisknout na [EDITOVAT].

http://www.cam.zcu.cz/~rkuzel/aplety/ Vynikající ukázky pomocí java apletů, které jsou zatím ve stádiu vývoje, ale dostatečně použitelném. Za tuto práci vděčíme Alisher Abdurahmanovi a Ruslanu Gumerovi, které vede Roman Kužel.

http://www.cc.ioc.ee/jus/gtglossary/gtglossary_ing.htm Glosař Teorie grafů - Obsáhlé, pěkné ale v angličtině, takže některé termíny je třeba hledat pod jiným názvem.
http://home.eunet.cz/berka/o/grafy.htm Celkem lidské psaní o teorii grafů od Doc. RNDr. Milan BERKA, CSc.
Teorie Grafů i jako PDF soubor.Z letního semestru roku 1999 na ČVUT fakultě dopravní. Přednášející RNDr. Jiří Taufer, CSc. Zpracoval Radim Perkner. http://www.fd.cvut.cz/Personal/xjirap/Teorgr.doc
http://www.volny.cz/martin.smetana/skola/prace/ti/ Jarníkův-Primův algoritmus sloužící k vyhledání minimální kostry grafu.
Teorie grafů - cvičení 2004 108 příkladů a ukázek z teorie grafů. Petr Švec, z Fakulty strojního inženýrství, Vysokého učení technického Brně.
http://gis.vsb.cz/pad/obsah.htm Stránky na VŠB technické univerzity v Ostravě věnované Prostorové analýze. Zajímavá je kapitola 5.2 Vhodné také jako praktická ukázka využití teorie grafů.
PPA2 p8 převedený na SWF Flash A pro jistotu ještě na PDF. Prezentace do předmětu ppa2 od paní Klečkové se zaměřením na využití teorie grafů (http://www.kiv.zcu.cz/~kleckova/ppa2-old/docs/p8.ppt).

Slovníček pojmů

Vlastnosti Relací

Reflexivní - pokud pro každé x které je prvkem množiny X platí že x R X
Symetrická - pokud pro každé x a y které jsou prvky množiny X platí x R y => y R x
Slabě antisimetrická - pokud pro každé x a y které jsou prvky množiny X platí že x R y a y R x => x=y
Tranzitivní - pokud pro každé x, y a z které jsou prvky množiny X platí že x R y a y R z => x R z

Typy matic

Matice incidence - matice vyjadřující vazby mezi uzly a hranami. 1 pokud hrana vstupuje do uzlu, 0 pokud nevstupuje. Pro orientované grafy lze používat +1 a -1. Podrobněji zde.
Pozor, zřejmě chyba Matice sousednosti - známá také jako "Matice spojitosti" vyjadřuje vztah jak daleko jsou uzly od sebe. Čím více hran je nutné projít z jednoho uzlu do druhého, tím vyšší číslo se v matici objeví. Pokud cesta mezi uzly neexistuje, zapíše se 0. Podrobněji zde.
Matice dosažitelnosti - je v podstatě zredukovaná matice sousednosti, která vyjadřuje pouze zda existuje (dosadí 1) cesta z uzlu do jiného uzlu nebo neexistuje (dosadí 0)Podrobněji zde.

Přímo o grafech

Převzato z http://gis.vsb.cz/pad/Kap_5/kap__5_2_1.htm
Graf - Matematická struktura modelující skutečnost, že v nějaké množině prvků existují vazby. Pro prvky se používá označení uzly, pro vazby označení hrany. Veverky (1989)
Incidence - označení skutečnosti, že hrana vstupuje nebo vystupuje z uzlu.

Označení	Vysvětlení, příklad
Orientovaný graf	obsahuje pouze orientované hrany
Neorientovaný graf	obsahuje pouzeneorientované hrany
Smíšený graf	obsahuje orientované i neorientované hrany
Prostý graf	neobsahuje násobné hrany
Jednoduchý graf	prostý graf bez smyček
Konečný graf	jeho množina uzlů a hran je konečná. Většina praktických úloh řeší právě konečné grafy.
Plošný(planární) graf	je zobrazitelný v rovině bez protínání hran. Hrany nemají žádné společné body kromě uzlů. Neplošný graf nám dovoluje realizovat např. mimoúrovňová křížení v dopravní síti.
Úplný graf	Mezi každými 2 uzly existuje právě 1 hrana. Úplný neorientovaný graf o n uzlech tak obsahuje n*(n-1)/2 neorientovaných hran.
Izomorfní grafy	Grafy, které se liší pouze označením uzlů a hran a způsobem zakreslení (diagramem). Kardinalita vztahu mezi uzly je 1:1 a stejně tak pro hrany.
Faktor grafu	část grafu, která má tutéž množinu uzlů
Souvislý graf	mezi libovolnými 2 uzly existuje sled
Silně souvislý graf	mezi libovolnými 2 uzly existuje orientovaná cesta tam i zpět
Strom	Souvislý graf bez kružnic
Kostra grafu	Faktor grafu, který je jeho stromem
Acyklické grafy	Orientovaný graf bez cyklu. Příkladem může být kanalizační síť.
Ohodnocený graf	Hrany nebo uzly jsou ohodnoceny. Ohodnocením se zaznamenávají kvalitativní a kvantitativní charakteristiky hran a uzlů. Používají se zpravidla kladná, reálná čísla. Prvním krokem ohodnocení prvků grafu je jejich indexace.