# Zk 18.6
<{ForumPost(poster="ranger_86", timestamp=2007-06-18 16:12:01)}>
Tak dneska to bylo docela zajimave, tady je to malo co si pamatuju ze zadani skupiny A:
1) 2 grafy, ukolem urcit, zda obsahuji Hamiltonovsky cyklus
a) skoro uplny K5,5, kde chybely hrany mezi protejsimi vrcholy
b) K5, kde 4 hrany (dve bocni a dve vnitrni) byly rozdeleny vrcholem
2) Tri systemy mnozin a pro kazdou urcit, zda ma System ruznych reprezentantu
3) Docela veliky graf=sit a v ni nalezt maximalni tok (krome nalezeni bylo treba ukazat, ze je max. - napr. proc jsou vsechny cesty nasycene vcetne definice nasycenosti ...)
4) 4 tvrzeni na Kuratowskeho vetu, presne zneni si nepamatuju, ale slo dost o slovickareni, aby si clovek uvedomil spravny smer implikace
Vsechno ve stylu G je rovinny(Je-li G rovinny), obsahuje-li(pokud neobsahuje/obsahuje) (nasledovala kombinace z nasledujicich grafu) K4, K4-4, K2-4, K6, K3-5 jako podgraf
5) Dokazat nejaka dve tvrzeni na Mengerovu a FordFulkersonovu vetu
a) Je-li G k-vrcholove spojity a pridame-li do nej vrchol v, ktery spojime k hranami s vrcholy G, bude vznikly graf G' opet k-vrcholove souvisly
b) Zneni si uz presne nepamatuju, ale slo o dukaz k-vrcholove spojitosti na n>=k+1 vrcholech, kde jsme vedeli, ze pro kazde rozdeleni podmnoziny vrcholu G na skupiny A,B po k vrcholech, vede mezi A,B k uplne disjunktnich cest
Jinak bodovani bylo docela mirne (ja mam sice za 3 o fous, ale moje blbost)
3-4: 11-14.5 (ustni povinna)
3: 15-21
2: 22-28
1: 29-34
Tim znamkovanim nad 3 si nejsem uplne jisty, ale tak nejak. Kazdopadne se vyplati si po zkontrolovani pisemku projit s danymi cvicicimi, protoze se tam mnohdy daji nahonit nejake body navic (napr dovysvetlenim nepresneho zapisu, ...)
Jinak u Toku v siti je dulezite dukladne rozepsat jednotlive dilci toky tak, aby bylo poznat, co clovek delal. Ja to mel cele v jednom grafu a prec dobre, uhadal jsem jedinny bod, bo to pry bylo neprehledne zapsane.
Takze vsem, ktere to jeste ceka, hodne zdaru
<{/ForumPost}>
<{ForumPost(poster="Myshaak", timestamp=2007-06-18 17:46:19)}>
OK, tak ja uz jen trosku doplnim... ;)
zneni 4:
a) G je rovinny, pokud neobsahuje zadny z grafu K4, K3,5 a K4,4 jako podgraf. (NE)
b) Je-li G rovinny, pak neobsahuje zadny z grafu K6, K3,5 a K4,4 jako podgraf. (ANO)
c) Je-li G rovinny, pak neobsahuje deleni K6 (ANO)
d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K4, K2,4 a K3,3 (ANO)
presne zneni 5 b) :
∀ k ≥1 plati: Graf G o n ≥ k+1 vrcholech je vrcholove k-souvisly prave tehdy, kdyz pro kazde dve k-prvkove podmnoziny X,Y vrcholu existuje k uplne disj. cest z X do Y.
...ohodnoceni otazek klasicke, 6-6-6-8-8
...a znamkovani opravdu celkem mirne, hranice mezi 1 a 2 byla dokonce jeste lepsi, nez psal kolega:
2: 22 - 27,5
1: 28 ->
<{/ForumPost}>
<{ForumPost(poster="doser", timestamp=2007-06-18 22:57:04)}>
tak ještě upravim hodnocení:
3: 15 - 22,5
2: 23 - 27,5
<{/ForumPost}>
<{ForumPost(poster="Jochanan", timestamp=2007-06-19 11:26:11)}>
> Myshaak wrote:zneni 4:
> a) G je rovinny, pokud neobsahuje zadny z grafu K4, K3,5 a K4,4 jako podgraf. (NE)
> b) Je-li G rovinny, pak neobsahuje zadny z grafu K6, K3,5 a K4,4 jako podgraf. (ANO)
> c) Je-li G rovinny, pak neobsahuje deleni K6 (ANO)
> d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K4, K2,4 a K3,3 (ANO)
Jak se dalo přijít na tohle? Kuratowski říká, že graf je rovinný, pokud neobsahuje K5 a K3,3 jako podgraf.
<{/ForumPost}>
<{ForumPost(poster="devra", timestamp=2007-06-19 12:10:54)}>
> Jochanan wrote:
> > Myshaak wrote:zneni 4:
> > a) G je rovinny, pokud neobsahuje zadny z grafu K4, K3,5 a K4,4 jako podgraf. (NE)
> > b) Je-li G rovinny, pak neobsahuje zadny z grafu K6, K3,5 a K4,4 jako podgraf. (ANO)
> > c) Je-li G rovinny, pak neobsahuje deleni K6 (ANO)
> > d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K4, K2,4 a K3,3 (ANO)
>
> Jak se dalo přijít na tohle? Kuratowski říká, že graf je rovinný, pokud neobsahuje K5 a K3,3 jako podgraf.
vsetko prave porovnavas s Kuratowskeho vetou a sazis sa zistit ako sa tie podmienky maju k sebe...
a) neobsahuje to co je uvedene, ale moze obsahovat K3,3 (K5 neobsahuje, lebo by uz mal K4)
b) K6 ma podgraf K5 ...a K3,5 aj K4,4 maju podgraf K3,3....a kdedze je rovinny, nemoze ich mat
c) neobsahuje delenie K6 lebo rovinny graf nemoze obsahovat delenie K5 (a ak ma dlenie K6, musi mat aj delenie K5..bez jedneho vrcholu a k nemu prislusnych "deliacich" vrcholov)
d) neobsahuje delenie K4, z toho vyplyva ze ani delenie K5 nemoze mat , a neobsahuje dlenie K3,3, teda bude rovinny
<{/ForumPost}>
<{ForumPost(poster="Jochanan", timestamp=2007-06-19 13:18:25)}>
at se snažim jak se snažim, pořád to tam nevidim...
ad a) pokud neobsahuje K4, tak neobsahuje ani K5, ne?
zato v b) pokud neobsahuje K6, tak muze klidne obsahovat K5, takže nechápu, proc je odpoved ze je rovinny..
a takhle by se dalo pokračovat.
//EDIT : Možná jsem už na to přišel. Je to tou formulací vět? Jednou to je, že G je roviný pokud a druhá je ... je-li rovinný , pak... v tom je taky dost velký rozdíl... Je to v tomhle slovíčkaření, nebo to bylo špatný prozření ?
<{/ForumPost}>
<{ForumPost(poster="Myshaak", timestamp=2007-06-20 10:35:39)}>
> Jochanan wrote:
> //EDIT : Možná jsem už na to přišel. Je to tou formulací vět? Jednou to je, že G je roviný pokud a druhá je ... je-li rovinný , pak... v tom je taky dost velký rozdíl... Je to v tomhle slovíčkaření, nebo to bylo špatný prozření ?
Jo!! Presne o tom to je! :D Zatimco "je-li... pak..." znamena implikaci => , tak "..., pokud..." znamena <=
<{/ForumPost}>