# 21.5. [zap]
<{ForumPost(poster="Myshaak", timestamp=2007-05-21 21:53:36)}>
Zadani zapoctovky u Pergela, treba to nekomu k necemu bude ;)
1) Je prauda, ze na toru ma kazdy maximalni ("toridalne-rovinny") graf kazdou stenu tvorenou trojuhelnikem?
2) Prusecikovym cislem grafu G oznacime cr(G) a nazveme min. k, pro ktere lze graf vnorit do roviny s nejvyse k krizenimi hran (takze pro rovinne grafy je to nula). Ukazte, ze pro kazdy graf G plati: cr(G) >= |E(G)| - 4|V(G)| ... Napoveda: Zkuste tvrzeni napred mirne zesilit.
3) Urcit formuli pro dimenzi prostoru cyklu nesouvislych grafu (konretne s k komponentami)
4) Urcete dim. rovinnych triangulaci na 7 a 9 vrcholech. Popiste nejakou bazi.
5) Znetvorujici fce pro (0,0,0,1,7,8,9,10,11,...)
6)Zformulujte obecnou Ramseyovu vetu - konecnou pro hypergrafy.
7) Plati, ze pro kazdy n,p1,p2,k ex. N tz. v kazdem uplen hypergrafu s hyperhranami velikosti p1 a p2 obervenymi pomoci k barev existuje jednobarevny (uplny) podhypergraf velikosti n.
8) Alenka a Bertik si hraji s latinskymi ctverci. Sehnali si ctvereckovy papir. Bertik vybral 8 sloupcu a vyzval Alenku, at vyplni prvni radek s tim, ze se budou postupne stridat (cili budou postupne vytvaret lat. obdelniky, dokud to pujde, maji k dispozici 8 cifer) a prohraje ten, kdo nemuze vytvorit dalsi radek. Kdo vyhraje?
Kdyz jeden z nich stale prohraval, rozhodl se Bertik zmenit pravidla. Vybral tedy 9 sloupcu misto 8 a stanovil, ze budou doplnovat po radcich, ale stridat se budou po kazdem cisle, a zacal (vyplnenim jednoho cisla na pozici 1,1) Urcete, kdo komu brzy dojde na nedaleke piskoviste rozdupat vsechny babovicky. 8-)
9) Je prauda, ze kazdy Hamilton. graf ma perfektni parovani? Je to prauda aspon pro grafy se sudym #vrcholu?
10) Urcete \[Kn,n] (Chvataluv uzaver) a rozhodnete, zda je tento graf Ham.
Z pisemky bylo lze ziskat 38 bodu. K dosazeni zapoctu je treba 26 bodu, z toho 7 bodu je moze ziskati za ostre nadpolovicni dochazku. :)
EDIT: Tak uz mam vysledek, je to mirne nad horni hranici toho, s cim jsem po napsani tak pocital (=> hodnoceni neni tvrde), cili jsem to o prsa vietnamske sprinterky dal! :) Hodne stesti tem, ktere to jeste ceka!
<{/ForumPost}>
<{ForumPost(poster="luckless", timestamp=2007-05-24 15:57:05)}>
Cau nechcete se nekdo podelit o reseni?
<{/ForumPost}>
<{ForumPost(poster="Manicka", timestamp=2007-05-24 18:35:09)}>
Mam par reseni, ale nezarucuju spravnou uvahu!
2 :pokud je G maximalni rovinny, tak cr(G) = 0, jelikoz maximalni rovinny graf je rovinna triangulace, lze lehce spocitat, ze |E| = 3|V| - 6 a 0 >= -|V| - 6. Pokud do takovehleho grafu pridam hranu tak se cr(G) zvysi minimalne o 1, ale zvysi se i |E| prave o 1, tudiz zustane nerovnost zachovana. Ale pridavanim hran do rovinne tringulace muzu dostat libovolny graf. Plati to pro grafy |V| >= 3 pro grafy mensi se to snadno overi rozborem a pro grafy obycejne rovinne je to jasne, pokud je to overene pro maximalni rovinne.
3 :vime, ze dimenze prostoru cyklu souvisleho G je velika |E| - |V| + 1 (coz je pocet hran grafu G, ktere nejsou v kostre G), pokud je graf nesouvisly o k komponentach, tak pokud tyto komponenty spojime k-1 hranou, tak dostaneme souvisly graf, kde velikost dimenze je |E| + k-1 - |V| + 1 (|E| myslim pred pridanim k-1 spojujicich hran). Ale vime, ze techto k-1 hran musi byt na kostre nove vznikleho grafu, tim padem neovlivni pocet hran ktere nejsou na kostrach prislusnych komponent, tedy ani velikost dimenze prostoru cyklu techto komponent.
4 :dosazenim do vzorecku je to 8 a 13 (pocet hran triangulace na 7 (9) vrcholech je 15 (21), da se odvodit vzorec pro pocet hran triangulace na n vrcholech indukci podle poctu pridanych vrcholu (a pripojenych hranami) do trojuhelniku).
5 :je to humac x^3 + (2x^4) / (1-x) + (5x^4 - 4x^5) / (1-x)^2
a spocita se to :radu rozlozim na 3 scitance x^3, 2*x^4 + 2*x^5 + 2*x^6 ... a 5*x^4 + 6*x^5 + 7*x^6 ... Ten druhy je normalni geometricka rada a ten treti je derivace rady x^5 + x^6 + x^7 ... takze tu sectu a vysledek sderivuju a prictu (to je ten treti clen konecneho souctu).
6 : Pro kazde n,k,p prirozene existuje N prirozene, ze v uplnem p-hypergrafu (hypergraf s hyperhranami velikosti p) obarvenem k barvami (barvim cele hyperhrany) existuje uplny podhypergraf na n vrcholech cely obarveny 1 barvou.
10 : \[Kn,n] = K2n tudiz uplnak a ten ma HK (ukaze se to tak, ze v kazde komponente muzu propojit kazdy vrchol s kazdym, protoze maji stupen n, coz je polovina poctu vrcholu, a jelikoz komponenty jsou spolu propojene stylem kazdy vrchol se vsemi z druhe komponenty, tak jsme propojili kazdy vrchol s kazdym v celem grafu).
<{/ForumPost}>
<{ForumPost(poster="Myshaak", timestamp=2007-05-24 19:57:11)}>
> luckless wrote:Cau nechcete se nekdo podelit o reseni?
Muzu uz jen doplnit k tomu, co je vyse:
1) Podle me ne, vezmu graf K2, ten je maximalni a pritom jeho jedina stena neni trojuhelnik
8) Podle vety z prednasky, lze kazdy lat. obdelnik doplnit az na ctverec, tedy na zacatku musi vzdy vyhrat Bertik (doplni posledni, 8. radek). I po zmene pry vyhraje Bertik, ale neumim to dokazat...
9) Neplati, vezmu treba lichou kruznici, tam zadne perf. parovani byt nemuze! ;) Pro grafy se sudym # vrcholu: existuje ham. kruznice, ta ma sudou delku => muzu ji "rozsekat" na dvojice spojene hranou -> mam parovani.
<{/ForumPost}>
<{ForumPost(poster="Manicka", timestamp=2007-05-24 21:01:29)}>
Beru zpet, je to spatne!!! Mam to primo od zdroje, tak zapomente, co jsem sem psala za blbosti...:)
<{/ForumPost}>