29.6.

[Návštěvník]

Dneska opet 4 priklady.
varianta B:

1.Urcete vytvorujici funkci pro posloupnost (0,0,-3,-6,-9,-12,...)
2.Dokazte nebo vyvratte:
(a) kazdy hranove 2-souvisly graf je hamiltonovsky
(b) kazdy hamiltonovsky graf je vrcholove 2-souvisly
(c) kazdy graf majici alespon dve ruzne hamiltonovske kruznice je vrcholove 3-souvisly
3.Rozhodnete, zda existuje n takove, ze sehraje-li n sachistu kazdy s kazdym jednu sachovou partii (dohromady tedy (n nad 2) partii), potom se mezi nimi najde sest hracu h0,h1,h2,h3,h4,h5 takovych, ze hi nevyhral s hj pro kazde i < j (zduvodnete).
4.Dokazte: Plati-li deg(u)+deg(v) >= |V(G)|+1 pro libovolne dva u,v z V(G), u!=v, potom G ma hamiltonovskou kruznici.

Naznak reseni:
1. trivka : vemu vytvor.fci pro 1,2,3,4,... ; vynasobim -3 a posunu o dve mista doprava
2. (a) je jednoduchy protipriklad (takovy ten "motylek")
(b) plati
(c) nevim
3. Ramseyovka pro 2 barvy.
4. Chtel i dukaz Oreho vety. Jenom jeji pouziti nestaci.

Pokud budou jeste nejake terminy v zari tak hodne stesti ten co nedali.

[PyromaN]

Jen doplnim, ze 2c neplatilo, slo to bud uvahou vrcholove 3 souvisly == hranove alespon 3 souvisly a ukazat obrazek, kde neplati 3hranova a ma aspon 2 hamiltonovice. To splnuje treba K3 - "trojuhelnik",kteremu do "teziste" strcite dalsi vrchol a spojite jej se 3 dalsimi a pote jednu hranu na obvodu trojuhelnika rozdelite [tzn. prikreslite "doprostred" hrany dalsi vrchol].
Jina moznost byla primo protipriklad.


4] se melo delat pres Čvátalův uzávěr [Čvátalův == Chvátalův - kdo jste byli na prednasce vite proc :] ]
Vsechny vrcholy grafu splnuji podminku v algoritmu vyroby uzaveru.
Chvatalovym uzaverem bude kompletni graf.
Pak pry bylo nutno dokazat Chvatalovu vetu [stacilo, ma-li Chvataluv uzaver HK, pak i graf ma HK]