21.5. [zap]

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. <i>k</i>, pro ktere lze graf vnorit do roviny s nejvyse <i>k</i> 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 <i>k</i> 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.

6. Plati, ze pro kazdy <i>n,p1,p2,k</i> ex. N tz. v kazdem uplen hypergrafu s hyperhranami velikosti <i>p1</i> a <i>p2</i> obervenymi pomoci <i>k</i> barev existuje jednobarevny (uplny) podhypergraf velikosti n.

7. 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 <b>lat. obdelniky</b>, 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-)

8. Je prauda, ze kazdy Hamilton. graf ma perfektni parovani? Je to prauda aspon pro grafy se sudym #vrcholu?

9. Urcete [K_n,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!

Cau nechcete se nekdo podelit o reseni?

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, 2x^4 + 2x^5 + 2x^6 ... a 5x^4 + 6x^5 + 7x^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).

luckless wrote:Cau nechcete se nekdo podelit o reseni?

Muzu uz jen doplnit k tomu, co je vyse:

1. Podle me ne, vezmu graf K₂, ten je maximalni a pritom jeho jedina stena neni trojuhelnik

2. 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...

3. 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.

Beru zpet, je to spatne!!! Mam to primo od zdroje, tak zapomente, co jsem sem psala za blbosti...:)