32. óra: Gráfelméleti feladatok II.
1. feladat: Egy hattagú
társaságban mindenkinek pontosan három barátja van. (E barátságok
kölcsönösek.) Egy alkalommal hat mozijegyet kaptak, három moziba,
mindegyikbe kettõt. Mindenki csak valamelyik barátjával hajlandó miziba
menni. Meg tudják-e szervezni a mozilátogatást?
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
2. feladat: Bizonyítsa
be, hogy ha egy gráf nem tartalmaz hurokélt, és minden pontjának a
fokszáma legalább 3, akkor van benne páros hosszúságú kör!
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
3. feladat: Egy
nemzetközi konferencián 20 küldött vett részt. Minden küldött legalább
10 társával címet váltott (megadták egymásnak a címüket). Késõbb
bármelyikük tudja-e értesíteni egy eseményrõl az összes többit, ha:
A) minden küldött hajlandó közvetítésre;
B) egy küldött nem hajlandó közvetítésre?
A) minden küldött hajlandó közvetítésre;
B) egy küldött nem hajlandó közvetítésre?
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
4. feladat: Egy
szigetország \(n\) szigete közül \(\left(n\in\mathbb N,
n\ge2\right)\) bármely kettõt vagy közvetlen repülõjárat, vagy közvetlen
hajójárat köt össze. (Vagy-vagy.) Igazolja, hogy vagy a hajójáratokat,
vagy a repülõjáratokat meg lehet szüntetni úgy, hogy bármely két sziget
között fennmaradjon az összeköttetés.
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
5*. feladat: Igazolja,
hogy bármely fagráfnak van olyan csúcsa, amelyen az összes leghosszabb út
áthalad! (Lefogó pont.)
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
6. feladat: Van-e a
szabályos oktaéder élgráfjában Hamilton-kör?
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
7. feladat: Bizonyítsa
be, hogy ha egy \(n\) csúcsú \(\left(n\in\mathbb N, n\ge3\right)\)
egyszerû gráf bármely két nem szomszédos csúcsának
fokszámösszege legalább \(n\), akkor a gráfnak van Hamilton-köre.
Megoldás: (megjelenik)
↓ (eltûnik)
↑
Késõbb...
