Z poslední přednášky (4-té): Ještě není hotová... :-(( Dodělávám - trochu problémy u důkazu Spernerova problému... :-(( tkz. Ernekerův problém :-))

Definice: Graf G je dvojice (V,E).
V je konečná množina vrcholů.
E je množina hran.
počet hran |E| Ł (V nad 2) - tj. můžou být spojeny každý vrchol s každým, ale to je maximum, stejně tak nějaké být spojeny nemusí.
e Î E. e={x,y} - tedy hrana je množina dvou bodů které spojuje. Pokud si to srovnáme s uspořádáním, vidím rozdíl jeden a to, že hrana nemá směr. Je to jen množina, nikoliv uspořádaná dvojice.
Stupeň vrcholu x v grafu G: d_G(x)=|{e; e Î E & x Î e}| - tedy počet hran které x s něčím spojují.

Kolik hran může mít graf s n vrcholy jestliže neobsahuje trojúhelník ? (Tj. nevyskytují se v něm tři různé vrcholy z nichž každé dva jsou spojené hranou)
t(n) - trojúhelníkové číslo.
t(n) < (n nad 2) - t(n) je určitě menší než maximální možný počet hran.

Věta: t(n) = dolní celá část z [(n²)/4)] Důkaz: Indukcí dle n
pro n = 1,2,3 poměrně zřejmé, stačí nakreslit si to.
n ® n+2
Dokážeme t(n) Ł dolní celá část z [(n²)/4)]:
Máme Graf (V,E) který má n+2 vrcholů a nemá trojúhelník.
E ą 0   {x,y} Î E. Uvažme Graf (V-{x,y},{e; e Î E & e Ç {x,y} = 0) a pojmenujme jej třeba (V',E')- tj. česky - graf bez bodů x a y a bez hrany spojující x a y. Pak |E| = |E'| + počet hran mezi + 1. Vysvětlení - počet hran v E je počet hran v E' plus počet hran mezi x,y a zbývajícímí prvky v V' plus jedna hrana mezi x a y kterou jsme odstranili.
Podle indukce je |E'| Ł dolní celá část z [(n²)/4)], pak je počet hran v E roven počtu hran v E' + n + 1. Někoho by mohlo zarážet proč plus n, je to proto, že pokud je x spojený s něčím ve zbytku množiny, pak už s tímtéž nemůže být spojeno y, neboť by to vytvořilo trojúhelník. Není to tedy 2n jak by člověk bez rozmyslu usuzoval, ale n a to ještě maximálně.
Tj. vzorcem: |E| Ł dolní celá část z [(n²)/4)] + n + 1 Ţ |E| Ł dolní celá část z [((n + 2)²)/4)]
Tj. máme celou větu dokázanou, ačkoliv ta tvrdí rovnost, je to proto, že t(n) jsem definovali jako kolik jich graf může mít a ten jich maximálně bude mít právě při rovnosti.

Mám v šešitě poznámku ještě o úplném bipartitním grafu, což je podle toho jak jsem to pochopil, něco takového, že množinu rozdělím na dvě části, řekněme levou a pravou a to tak, že hrany grafu jsou pouze mezi těmito částmi nikoliv v nich, tj. žádné dva prvky levé (resp. pravé) části mezi sebou nemají hranu. V takovémto grafu není tedy žádný trohúhelník. V učebnici je však tento výraz výborně vysvětlen na stránce 98.

Dodatek k větě: Nechť (V,E) je graf bez trojúhelníků, |V| = n; |E| = t(n). Potom (V,E) je isomorfní úplný bipartitní graf.
Doporučuji připomenout si definici isomorfismu...

Jen poznámka... t(n) je přibližně polovina všech možných hran (nebral-li bych ohled na nějaké trojúhelníky).
Kolik nejvýše hran má graf bez čtverců ? Bylo by to nejvýše n^(3/2)

Věta: Součet stupňů vrcholu všech vrcholů grafu je roven dvojnásobku počtu hran.
Důkaz: Velice prosté - stačí si uvědomit, že každá hrana spojuje dva body a stupeň vrcholu je vlastně jen to, kolikrát se daný bod v množině hran vyskytne. Tj. pokud se koukám kolikrát se tam vyskytnou všechny body, musí to být přesně dvakrát počet hran, jinak by hrana nespíše nemohla spojovat dva body, ale nějaké jiné množství... Upozorňuji však, že na přednášce se důkaz lišil, byl více matematický a snáze z něj vyplýval důsledek, který bude vzápětí. Tohle je ale jednoduchá úvaha, ze které je věta zřejmá (kéž by bylo všechno takhle jednoduché :-)).

Důsledek: (lemma o potřásání rukou)
Počet vrcholů s lichým stupněm je sudý (pozor, nula je sudé číslo !!)
Proč ?? Protože součet stupňů všech vrcholů je sudý, pokud by to tak nebylo, nemohlo by sudé číslo nikdy vyjít.

Cesta v grafu G z vrcholu x do y je posloupnost x=v₀,e₁,v₁ ,e₂ ,...,e_t ,v_t=y kde e_i = {v_i-1 ,v_i}; v_i ą v_j pro každé i,j různé.
Tah v grafu G je posloupnost ... atd. atd.. kde e_i ą e_j
Sled je posloupnost v grafu G.
A rozdíly ? Tedy cesta je něco, kde říkáme, že v žádném bodě nejsme dvakrát. Tah je něco, kde nám o nějaké navštěvování bodů vůbec nejde, ale definujeme si, že nesmíme po jedné hraně jít víckrát. A sled je něco, u čeho nám o nějaké body či hrany vůbec nejde, prostě je to nějaké procházení grafem z x do y, aniž bychom kontrolovali zda jsme po dané hraně šli či nějaký bod už navštívili. Jinak index t u posloupnosti nám udává délku cesty, tahu či sledu. Jinak, zamyslíte-li se nad podmínkou u cesty, je asi jasné, že je to podmínka dostačující k tomu, abychom zároveň nenavštívili dvakrát stejnou cestu. Cesta je tedy nejvymezenější, tah méně, neboť bod v něm navštívit víckrát můžeme a sled není vymezený vůbec, to je jenom některý z možných průchodů.

Kružnice v grafu G je posloupnost bodů a hran u nichž jsou všechny body až na první a poslední různé a první a poslední naopak stejné. Jde nám tedy o to, abychom žádný bod nenavštívili dvakrát. No co je kružnice snad všichni víte, ne ? Je to naprosto logický. Délka kružnice je pak rovna indexu posloupnosti, tedy opět t obdobně jako předchvílí u cesty, tahu a sledu.

Definice: G je souvislý, jestliže pro každé dva jeho vrcholy (body) existuje v G cesta a je spojující (tj. každé dva body jsou spojeny cestou).
Teď když nad tím tak přemýšlím, řekl bych že existence cesty je hodně, stejně tak by nejspíš stačil tah, či sled, neboť když tak nad tím přemýšlím, jestliže existuje tah, pak jistě existuje cesta... a stejně tak se sledem. Jde prostě o to, abych se z každého bodu grafu dostal do všech ostatních, pokud ano, pak je souvislý. Pokud ne, pak je graf vlastně někde rozdělený na více nějakých komponent (vlastně menších grafů, které s tím zbytkem nejsou spojené) které sami o sobě už můžou být souvislé, graf jako celek však nikoliv. Taky pozor, můžu se mýlit, zkuste nad tím raději přemýšlet sami.

Definujme pro graf G=(V,E) relaci R na V předpisem (x,y) Î R Ű existuje cesta z x do y v G.
Pak můžeme pozorovat:
1) R je ekvivalence pro každý graf G. 2) R má jednu třídu Ű G je souvislý.
Důkaz: prvním je, že (x,x) je v R. No tak to je jasné... :-) Jinak tento bod se nazývá reflexivitou, to jen pro připomenutí.
dalším bodem je antisymetrie, tj. je-li (x,y) v R, pak zcela jistě i (y,x) je v R. No tak to je snad také jasné. Tady je krásně vidět rozdíl mezi hranou a uspořádanou dvojicí. Hrana je jak jsem již psal, tkz. bez šipky, je to spojení dvou vrcholů bez udání směru jejich spojení. Uspořádanou dvojici si můžeme zase snadno představit jako šipku. Je to vyjádření nějaké relace, tedy šipka naznačuje, kterým směrem relace platí. Ale to jen na okraj.
A dalším bodem důkazu máme transitivitu, tj. máme-li první s druhým bodem spojené cestou a zároveň máme druhý s třetím spojené cestou, pak máme zcela jistě i první s třetím.

Pozorování které nám vzešlo z úvahy nad transitivitou.
Sled nejkratší délky mezi dvěma vrcholy je cesta.
No a už jsme u toho. Něco takového jsem uvažoval u souvislého grafu, tedy kousek výše. Když si představíte sled, tedy nějaký průchod grafem, pak když je to sled, může se Vám proti cestě stát jen že křížíte, nebo že jdete po jedné cestě víckrát. Tak to ale snadno vyřešíme - jdete-li po jedné cestě suděkrát, vůbec na ní nechoďte (tj. jdete tam a zpátky, tj. suděkrát...), jdete-li po ní lichokrát, je to stejné jako by jste po ní šli jenom jednou... A pokud křížíte (pozor, je myšleno křížení v bodě, tj. návštěva jednoho bodu víckrát), tak se na to křížení vykašlete a když v tom bodě budete prvně jděte rovnou tam, kam by jste šli až po projítí nějaké té kroužnice která by Vás vrátila do tohoto bodu.
No a když se nad tím zamyslíte a je Vám to jasné (a jako že to asi je, je to přece jenom dosti "zřejmé"), pak Vám musí být i zřejmé, že nejkratší tah mezi dvěma vrcholy je opět cesta... Tah je přece také sled. A cesta je tah a stejně tak i sled.

Defnice: Třídy ekvivalence R se nazývají komponenty grafu.
graf je souvislý Ű má jedinou komponentu
G=(V,E) je souvislý Ű pro každý rozklad V = A Č B existuje hrana e Î E & e Ç A ą 0 & e Ç B ą 0
No to je asi jasné. Netuším kdo si pamatujete komponenty a co je to jedna komponenta, ale každopádně druhé podánní je dosti jasné. Pouze snad při čtení e průnik A nezapomeňte, že e je definována jako množina oněch dvou bodů, které spojuje. Tedy říká to vlastně, že pokud to rozdělím na jakýkoliv rozklad, vždycky najdu mezi jednotlivými množinami rozkladu nějakou hranu, kterou bych musel "roztrhnout".

Definice: G=(V,E) nazvu stromem jestliže G je souvislý a neobsahuje kružnici.
No co k tomuhle ? Co je kružnice už všichni víme, co je souvislý graf také. Nejlepší interpretací je právě představa stromu, je to naprosto přesné. Z každého bodu se dostanu do všech ostatních a zároveň z jednoho vrcholu existuje do všech ostatních pouze jedna jediná cesta (to je asi také jasné - druhá cesta by byla kružnicí, neboť 1. mluvím o cestě, to je ten nejkratší sled (či tah, podle toho co jste našli :-)) a 2. pokud jdu po cestě a můžu odbočit abych šel do stejného místa jinou cestou, tak musí zákonitě existovat kružnice jejíž jednou části bude první z cest a další z částí druhá z cest až do místa kde se opět sejdou (což zákonitě musí, neboť bych se jinak nemohl dostat do stejného místa aniž bych se vracel (což je zase podmínka cesty))).