# [zk] 5.6.2006 <{ForumPost(poster="gASK", timestamp=2006-06-05 11:39:45)}> \[zk] 5.6.2006 *Attachments:* - *[kombagra.JPG](/Forum%20archiv/Attachments/kombagra.jpg)* <{/ForumPost}> <{ForumPost(poster="hydrant", timestamp=2006-06-05 13:59:01)}> pls, premozte sa niekto a dajte sem aj riesenia, zvlast ten 2 a 4 priklad su nie zrovna zrejme. Riesenia vam vysvetloval pred vysledkami tak ich sem napiste.... a tiez by sa zisla druha varianta pisomky vdaka hydrant <{/ForumPost}> <{ForumPost(poster="Dawe", timestamp=2006-06-05 14:36:46)}> Ten 4 příklad se řešil pomocí důkazu Tuteho věty. K muselo být liché (to je kvůli počtu vrcholů s lichým stupněm). 2 jsem neměl vůbec. Šel jsem za ním, že mám jeden příklad špatně ohodnocenej (chyběl mi bod do dvojky). Tak jsem se o tom tak nějak bavily, pak se zeptal na Hamiltonovskou kružnici, co o ní vím a tak. Pak mi celkem spokojeně napsal 2 - teda snad, ještě jsem se nekoukal... :-) Jinak říkal, že mu opravující říkaly, že byla písemka těžší než minule, takže bylo hodnocení asi takové: 1 - 32-25 2 - 24 - 17 3 - 16 - ? zkoušení ? 4 - ? Ten zbytek ať kdyžtak někdo doplní (myslím, že 8 bodů ještě bylo na ústní). Skupina byla jen jedna ( alespoň z toho co ukazoval jak se to má řešit). <{/ForumPost}> <{ForumPost(poster="qk", timestamp=2006-06-05 17:26:28)}> trojak 12-16 ustni 7-11 sem byl az dotad na ustnim a nakonec sem vymlatil trojku, coz s mym "formalnim" zapisem se skoro uspech, ale i z ustniho se da bojovat o dvojku a mozna i vyse <{/ForumPost}> <{ForumPost(poster="Maputo", timestamp=2006-06-05 19:25:44)}> Tak jsem ted prisel domu z ustni, skoncil jsem asi v 18:40... nektery tam jeste mozna jsou... Dostal jsem: co vim o Hamiltonovskejch kruznicich, Pocet koster pres determinant, Hallovu vetu... Mel jsem 8 bodu z pisemny, napsal jsem mu to vsechno s def, lemmatama a dukazama tak nakonec za 2. Co tam jeste padalo byl obchod. cestujici, edmondsuv zahradni alg, projektivni roviny s dukazem |P| = |P'|, dusledky hallovi vety ( to je to lemma pro bipart. graf a doplneni lat. obdelniku na ctverec). Jednu dusi se tam zeptal na pocet lat. ctvercu radu n... no vic si uz nak nevybavuju. <{/ForumPost}> <{ForumPost(poster="snail", timestamp=2006-06-05 20:18:34)}> No koukam na ten 2. priklad. Mnozina B je vlastne prostor rezu grafu Kn. Takze dim bude n-1. Jen zatim netusim co presne by bylo bazi. <{/ForumPost}> <{ForumPost(poster="laliebijard", timestamp=2006-06-05 23:34:43)}> > snail wrote:No koukam na ten 2. priklad. Mnozina B je vlastne prostor rezu grafu Kn. > Takze dim bude n-1. > Jen zatim netusim co presne by bylo bazi. Bazou su nieco ako vsetky "hviezdy", to jest jedna partita ma velkost 1. Ak som to teda nepoplietol... <{/ForumPost}> <{ForumPost(poster="David", timestamp=2006-06-06 10:36:17)}> Posilam "navody" k prikladum. No, spis jsou to navrhy. Je to hodne nepresny, neco je asi uplne spatne, tak me kdyztak opravte. Ja mel 3 a jsem rad, ze mam kombinatoriku za sebou... 8) 1. > 1, -4, 9, -16, 25, -36 druha derivace, myslim posunout, pricist radu 1, 2, 3, ... a substituce -x za x 2. (z tohohle jsem mel 0 bodu, takze reseni moc nevim...) a) Musi se dokazat, ze je uzavrene na nasobeni: trivialni (0, 1) scitani: Scitani je XOR. Je treba dokazat, ze kdyz A a B jsou uplne bip. grafy a C = A + B tak C je take. Je dobre nakreslit si obrazek. - Napred cele mnoziny vrcholu. Ta se rozdeli na dve casti. - Dve partity. Pri scitani se to cele rozdeli na 4 casti. Z toho, ze scitani je xor vyplyne, ze hrany vysledneho poscitaneho grafu pujdou jen pres sousedni ctvrtiny. Ne nijak jinak. Z toho se uvidi, ze vysledny graf C je uplny bipartijni b) n-1 Bazi tvori grafy "hvezdice". - Jedna parita ma velikost 1, stupen vrcholu na ni je n-1. Je jich n, ale dve jsou linearne zavisle c) To nevim. Ale zajimave je, ze v GF(2) neplati, ze kdyz je E ortogonalni doplnek B, tak musi mit neprazdny prunik. Ale delalo by se to nejak pomoci tech hvezdic... d) Hvezdice 3. a) Kdyz odendam Ham. kruznici, zbyde podgraf stupne 1. - Perf. parovani Nebo pomoci toho, ze kdyz je lichy stupen, musi byt sudy pocet vrcholu, takze Ham. kruznice je suda. - Ze sude vytvorit perf. parovani b) asi jako a) (mam perf. par => mam 1-faktor) c) Petersen, nebo treba dva K4... (to je uz hodne spatne, kdyz me nenapadlo ani tohle...) d) asi jako c) 4. Kdyby bylo k sude, je lichy pocet vrcholu (myslim). Tedy nemuze byt perf. par. K liche. Pomoci Tuttovy vety. Vime, ze pocet vrcholu je sudy. Kdyz vyberu nejaky vrcholovy rez (vrcholy po jejichz odebrani je graf nesouvisly) vime, ze z kazde liche komponenty musi jit aspon k cest do A. Dohromady k*l. Z a vede |A|*k cest. Ty musi vest do lichych komponent a i do sudych. Tedy: k*l <= k*|A| tedy k <= |A| Snad jsem tim nikoho moc nezmatl. Jeste to radsi promyslete. Ja s kombinatorikou koncim. Definitivne. Jupi!!!! :D <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-06-06 10:58:03)}> Ke? Asi jsem ještě někde v labu zapomněl uložený heslo či co - někdo to sem dal pod mým jménem. No ať se stydí! :twisted: <{/ForumPost}> <{ForumPost(poster="stana", timestamp=2006-06-06 17:27:25)}> 2.c To uz neni tezke: plati, ze bipartitni grafy neobsahuji liche kruznice. Takze prunik libovolneho bipartitniho grafu s kruznici ma sudy pocet hran. Jinymi slovy, skalarni soucin vektoru prislusneho bip. grafu a kruznice je sude cislo, tedy 0. Z toho uz plyne ortogonalita. <{/ForumPost}> <{ForumPost(poster="Hugo", timestamp=2006-06-06 20:45:26)}> gask: ja jsem to teda nebyl, ale jeden znamy povidal, ze to sem dal "pod nejakou kockou, ktera byla tady prihlasena, kdyz se nalogoval":)) <{/ForumPost}> <{ForumPost(poster="gASK", timestamp=2006-06-06 21:11:43)}> > Hugo wrote:gask: ja jsem to teda nebyl, ale jeden znamy povidal, ze to sem dal "pod nejakou kockou, ktera byla tady prihlasena, kdyz se nalogoval":)) Už se mi tu byl osobně omluvit. Prej jsem byl loglej pod explorerem, což je divný. Ale asi jsem ho někdy použil, zaškrtl políčko a zapomněl na něj...nu což. :twisted: <{/ForumPost}> <{ForumPost(poster="Hugo", timestamp=2006-06-06 23:10:03)}> ty brdo, takove matfyzacke slusnosti...to ja bych se jen skodolibe pochechtaval..:) <{/ForumPost}>