# 29.6.

<{ForumPost(poster="Anonymous", timestamp=2007-06-29 19:00:36)}>
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.
<{/ForumPost}>

<{ForumPost(poster="PyromaN", timestamp=2007-07-02 10:04:32)}>
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]
<{/ForumPost}>