Zk 18.6

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

OK, tak ja uz jen trosku doplnim... ;)

<u>zneni 4:</u>
a) G je rovinny, pokud neobsahuje zadny z grafu K₄, K_3,5 a K_4,4 jako podgraf. (NE)
b) Je-li G rovinny, pak neobsahuje zadny z grafu K₆, K_3,5 a K_4,4 jako podgraf. (ANO)
c) Je-li G rovinny, pak neobsahuje deleni K₆ (ANO)
d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K₄, K_2,4 a K_3,3 (ANO)

<u>presne zneni 5 b) :</u>
∀ 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 ->

tak ještě upravim hodnocení:
3: 15 - 22,5
2: 23 - 27,5

Myshaak wrote:<u>zneni 4:</u>
a) G je rovinny, pokud neobsahuje zadny z grafu K₄, K_3,5 a K_4,4 jako podgraf. (NE)
b) Je-li G rovinny, pak neobsahuje zadny z grafu K₆, K_3,5 a K_4,4 jako podgraf. (ANO)
c) Je-li G rovinny, pak neobsahuje deleni K₆ (ANO)
d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K₄, K_2,4 a K_3,3 (ANO)

Jak se dalo přijít na tohle? Kuratowski říká, že graf je rovinný, pokud neobsahuje K5 a K3,3 jako podgraf.

Jochanan wrote:

Myshaak wrote:<u>zneni 4:</u>
a) G je rovinny, pokud neobsahuje zadny z grafu K₄, K_3,5 a K_4,4 jako podgraf. (NE)
b) Je-li G rovinny, pak neobsahuje zadny z grafu K₆, K_3,5 a K_4,4 jako podgraf. (ANO)
c) Je-li G rovinny, pak neobsahuje deleni K₆ (ANO)
d) Graf je rovinny, pokud neobsahuje deleni zadneho z grafu K₄, K_2,4 a K_3,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 K_3,3 (K₅ neobsahuje, lebo by uz mal K₄)
b) K₆ ma podgraf K₅ ...a K_3,5 aj K_4,4 maju podgraf K_3,3....a kdedze je rovinny, nemoze ich mat
c) neobsahuje delenie K₆ lebo rovinny graf nemoze obsahovat delenie K₅ (a ak ma dlenie K₆, musi mat aj delenie K₅..bez jedneho vrcholu a k nemu prislusnych "deliacich" vrcholov)
d) neobsahuje delenie K₄, z toho vyplyva ze ani delenie K₅ nemoze mat , a neobsahuje dlenie K_3,3, teda bude rovinny

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

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 <=