Bevezetés a számításelméletbe II.

1. gyakorlat, 2005. február 18.

                              Koblinger Egmont <egmont@cs.bme.hu>

Euler- és Hamilton-bejárások

Euler-bejárások

1. Milyen n esetén tartalmaz a teljes n pontú gráf Euler-kört illetve -utat?

2. Van-e olyan egyszerű gráf, melynek van zárt Euler-vonala, továbbá páros számú pontja és páratlan számú éle van?

3. Igazoljuk, hogy ha egy gráf minden pontjának a foka 4, akkor élei színezhetők piros és kék színekkel úgy, hogy minden él teljes hosszában egyszínű legyen, és minden ponthoz két piros és két kék él illeszkedjék!

4. Bizonyítsuk be, hogy ha egy összefüggő gráfban a páratlan fokszámú pontok száma 2k, akkor a gráf élei bejárhatóak k darab sétával.

5. Egy gráf csúcsai a négy hosszúságú 0–1 sorozatok. Két pont akkor van összekötve, ha a nekik megfelelő sorozatok pontosan egy helyen térnek el. Található Euler-kör ebben a gráfban?

6. A gráf csúcsai legyenek ugyanazok, mint az előző példában, de most akkor kössük össze őket, ha pontosan két helyen térnek el a sorozatok. A kérdés ugyanaz.

Hamilton-bejárások

7. Van-e Hamilton-kör az alábbi gráfokban?

8. Milyen m és n értékekre tartalmaz Hamilton-kört illetve -utat az m × n méretű négyzetháló-gráf (amelynek összesen (m + 1) × (n + 1) pontja van)?

9. Legyen G olyan, a V = {p_{1}, p_{2}, ..., p_{2005}} ponthalmazon értelmezett egyszerű gráf, amelyben {p_{i}, p_{j}} ∈ E pontosan akkor teljesül, ha |i − j| ⩽ 2. Van-e G-ben Hamilton-kör vagy Hamilton-út?

10. Be lehet-e járni huszárral egy 4 × 4-es sakktáblát?

11. Mutassuk meg, hogy tetszőleges n ≥ 5 értékre igaz az alábbi két állítás:

(a) Létezik olyan n csúcsú G gráf, hogy G is és \overline{G} is tartalmaz Hamilton-kört.

(b) Létezik olyan n csúcsú gráf, hogy sem G, sem \overline{G} nem tartalmaz Hamilton-kört.

12. Bizonyítsuk be, hogy ha egy 2n + 1 pontú egyszerű gráf minden csúcsának fokszáma legalább n, akkor a gráfban van Hamilton-út.

13. Bizonyítsuk be, hogy a Petersen gráfban nincsen Hamilton-kör.

14. Egy szállodába egy 100 fős társaság érkezik, akik közül kezdetben bármely két ember jóban van egymással. Esténként egyetlen nagy kerek asztal körül ül le mindenki. Sajnos egy vacsora alkalmával az egymás mellé került emberek örökre összevesznek egymással. A társaság minden vacsora előtt úgy ül le, hogy mindenki a szomszédjaival jóban legyen. Ha ez lehetetlen, akkor az összes résztvevő még aznap este haza megy. Bizonyítsuk be, hogy legalább 25 éjszakát a szállodában tölt a társaság!