Euler-bejárás

1.

Bejárható-e Königsberg város 7 hídja úgy, hogy mindegyiken pontosan egyszer megyünk át? Ha igen, hogyan, ha nem, hogy lehetne ezen változtatni?

2.

Mutassuk meg, hogy egy összefüggő gráf élei bejárhatóak úgy, hogy mindegyiken kétszer megyünk végig, éspedig mindkét irányban egyszer-egyszer.

3.

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.

4.

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?

5.

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

6.

Milyen x és y értékekre tartalmaz ilyet az x*y méretű kockás papír (amelynek összesen (x+1)*(y+1) pontja van)?

Hamilton-bejárás

1.

Ha egy páros gráfban van Hamilton-kör, akkor a gráf két pontosztálya azonos elemszámú.

2.

Ha egy G gráfban van Hamilton-kör, akkor bármely v csúcsára és bármely e élére a G-v és a G-e gráf is összefüggő.

3.

Ha egy G gráf tetszőleges S ponthalmazára a G-S gráf összefüggő komponenseinek száma több, mint S pontjainak a száma, akkor G-ben nem lehet Hamilton-kör. Lehet-e ilyenkor Hamilton-út G-ben?

4.

Ha egy összefüggő G gráf K köréből egy élt törölve G egy leghosszabb útját kapjuk, akkor K Hamilton-köre G-nek.

5.

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

6.

Mutassuk meg, hogy Pósa tételéből következik Ore tétele.

7.

Képzeljünk el egy képzőművészeti kiállítást. A látogatók szeretik a saját lelkiviláguk szerint élvezni a tárlat anyagát, azaz annyira elmerülnek az esztétikai élmények kavalkádjában, hogy útjelző táblák figyelemmel követésére már nem képesek. Annyi azért persze még tőlük is elvárható, hogy mindig olyan folyosón haladnak tovább, amerre addig még nem jártak és ha egy adott pillanatban látnak ilyen folyosót, akkor azok egyikén tovább is haladnak.

Feladat: határozzuk meg, milyen lehet egy ilyen kiállítócsarnok, ha azt szeretnénk, hogy az összes látogató a saját korlátoltsága ellenére végignézhesse a kiállítást (gráfnyelven: melyek azok a gráfok, melynek egy adott pontjából (bejárat) induló elakadó séta szükségképppen Euler-kör).

8.

Legalább hány éle van egy olyan hat pontú gráfnak, melynek van Hamilton-köre?

Vissza