01ZTGA:Kapitola0

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 16. 1. 201200:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201514:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201213:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201213:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201213:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201213:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201213:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201910:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201213:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201213:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201214:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201214:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201214:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201214:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201214:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201214:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201214:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201215:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201215:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201215:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201215:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201215:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201215:22 cast3_kapitola2.tex

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\chapter*{Úvod}
 
\addcontentsline{toc}{chapter}{Úvod}
 
V průběhu přípravy na zkoušku ze Základů teorie grafů jsem si uvědomil,
že mé zápisky z přednášky jsou natolik kvalitní, že by bylo možné
je použít jako základ pro docela slušná skripta z tohoto předmětu.
Ještě před samotnou zkouškou jsem tedy zkusil napsat pár stránek a
s výsledkem jsem byl natolik spokojen, že jsem s chutí pokračoval
dál, pouze s motivací vytvořit něco smysluplného a užitečného. Přesto
mám poněkud rozporuplné pocity z následků, které uveřejnění tohoto
materiálu může mít.
 
Je jasné, že dobré zápisky nelze sestavit na základě nedobrých přednášek.
Skvělé a zajímavé přednášky paní docentky Edity Pelantové je však
skoro škoda publikovat tak, aby byly každému snadno a volně dostupné.
Student získá určitou jistotu, o kterou se v případě potřeby bude
moci opřít, ale po krátkém čase usoudí, že sám si o mnoho lepší poznámky
z přednášky neodnese. Je-li student trochu línější, na přednášce se
už neukáže. Je pravda, že ve čtvrtém ročníku již velká většina studentů
brzy rozpozná kvalitu přednášek a dokáže si jí vážit. Ale vy, kteří
jste v pokušení, vězte, že byste přišli opravdu o hodně. I kdybyste
na žádné jiné přednášky nechodili, na grafy choďte, protože skutečně
stojí za to. A dělejte si zápisky, protože tak se toho nejvíc naučíte
:-)
 
ZTG se od akademického roku 2005/2006 dělí na dva předměty s odlišnou
náplní. ZTG-B se skládá z 1 přednášky a 1 cvičení týdně. Na přednášce
jsou představeny základní kapitoly z teorie grafů, které pokrývá první
část těchto zápisků. Na cvičení jsou pak předmětem studia mimo jiné
algoritmy řešící některé známé grafové úlohy. ZTG-A se skládá ze 2
přednášek týdně, přičemž jedna je vždy vedena v době, kdy posluchači
varianty B tohoto předmětu mají zrovna cvičení. Předmětem této přednášky
jsou některé pokročilejší partie teorie grafů, jako jsou věty z extremální
teorie grafů a ramseyovská čísla, dále pak generující funkce a jejich
využití demonstrované na velmi pěkných příkladech z oboru kombinatoriky
nebo teorie čísel. Tato část přednášky je pokryta ve druhé a třetí
kapitole.
 
Celý text velmi těsně kopíruje látku vyloženou na přednáškách, některé
pasáže jsou však mírně modifikovány, aby jejich pochopení nebo návaznost
byly (z mého pohledu) přirozenější. Vzhledem k tomu, že existuje kvalitní
a přitom na internetu volně dostupná anglická literatura (dva příklady
jsou uvedeny v seznam použité literatury), opatřil jsem mnoho definic
jednotlivých pojmů též jejich anglickým zněním. Důkazy jsou někdy
komentovány až příliš, mou snahou však bylo nenechat žádného čtenáře
na holičkách. Na druhou stranu však platí, že nejlépe si pamatujeme
to, na co přijdeme sami.
 
Přeji vám všem, aby vám tyto poznámky byly užitečnou pomůckou při
studiu a abyste úspěšně složili zkoušky nejen z teorie grafů.
 
\bigskip{}
\begin{flushright}Pavel Strachota\end{flushright}