Staré Projekty z Teorie grafů
- 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ů.}
- 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ů.
- Hranová barvení
Najděte algoritmus hranového Δ(G)+1 barvení libovolného grafu.
Dokažte správnost algoritmu.
Problém rozeberte.
- Mapy
Dokažte Eulerův vzorec pro nesouvislé grafy alespoň čtyřmi různými způsoby.
- Jedním tahem
Najděte a dokažte algoritmus kreslení multigrafů se smyčkami jedním otevřeným eulerovským tahem.
- 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?
- Rovinné grafy
Najděte nekonečně mnoho 5-pravidelných rovinných souvislých grafů.
- 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ů.
|
Petr<tečka>Kovar<zavináč>vsb<tečka>cz kancelář EA536, tel. 597 325 972 |
Upraveno: 29.12.2011 |
|