Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Staré Projekty z Teorie grafů

Projekty z akademického roku LS 2007/2008

  1. Hra "šprouti"   Na papíře je nakresleno n puntíků. Hráči se střídají, kdo nemůže udělat další tah, prohrál. V každém tahu spojí hráč křivkou dva puntíky tak, aby neprotnul žádnou jinou křivku a na křivku nakreslí nový puntík. Puntík se smí použít jako konec nového křivky jen pokud z něj vedou nejvýše dvě další křivky. Ukažte, že pro n počátečních puntíků má hra nejvýše 3n-1 tahů a nejméně 2n tahů.}
  2. Hra "podvodní šprouti"   Na papíře je nakresleno n křížků. Hráči se střídají, kdo nemůže udělat další tah, prohrál. V každém tahu spojí hráč křivkou dva křížky tak, aby neprotnul žádnou jinou křivku a na křivku nakreslí nový puntík. Nové křivky se připojují pouze k ramenům křížků. Puntík se smí použít jako konec nového křivky jen pokud z něj vedou nejvýše dvě další křivky. Nový křížek vytvoříme vždy přeškrtnutím křivky. Ukažte, že hra má vždy právě 5n-2 tahů.
  3. Hranová barvení   Najděte algoritmus hranového Δ(G)+1 barvení libovolného grafu. Dokažte správnost algoritmu. Problém rozeberte.
  4. Mapy   Dokažte Eulerův vzorec pro nesouvislé grafy alespoň čtyřmi různými způsoby.
  5. Jedním tahem   Najděte a dokažte algoritmus kreslení multigrafů se smyčkami jedním otevřeným eulerovským tahem.
  6. Heslo   Sejf se otvírá digitální klávesnicí, přičemž sejf se otevře při zadání správné posloupnosti bez ohledu na předchozí stisknuté klávesy. Je-li například 1234 heslo otvírající sejf, tak se k otevření můžeme zadat 1234, nebo 81234 nebo klidně 63825431234. K prolomení kódu můžeme postupně zadat všechna čísla od 0000 do 9999. Avšak to bychom museli naťukat celkem 40 000 cifer, což by trvalo zbytečně dlouho. a) Jaký je nejmenší počet cifer, který zajistí prolomení kódu?
    b) Jak sestrojit příslušnou posloupnost čísel?
    c) Uměli byste úlohu vyřešit i pro n-ciferná čísla s číslicemi 1, 2, ..., q?
  7. Rovinné grafy   Najděte nekonečně mnoho 5-pravidelných rovinných souvislých grafů.
  8. Turnaje   Ukažte, že každý turnaj obsahuje hamiltonovskou cestu a že pro každé přirozené číslo n existuje jediný tranzitivní turnaj (až na izomorfismus).

Poznámky:
Témata, která byla zadaná, jsou šedá. Očekává se, že projekty jsou vypracovány na úrovni, která odpovídá studentům čtvrtého ročníku vysoké školy. Případná různá obtížnost témat byla kompenzována mírou, jak přísně byly projekty hodnoceny.

Zpět na předmět Teorie grafů.

 


email
kancelář EA536, tel. 597 325 972
Upraveno: 29.12.2011