28-29. óra: Gráfelméleti feladatok

1. feladat: Egy 5 csúcsú egyszerû gráfnak 8 éle van. Mekkorák lehetnek a csúcsok fokszámai?

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

2. feladat: Egy körmérkõzéses sakkversenyen legalább 6 versenyzõ vesz részt. Bizonyítsa be, hogy bármely forduló után vagy vagy van három olyan versenyzõ, akik az egymás elleni mérkõzéseiket már mind lejátszották, vagy van három olyan versenyzõ, kik közül még semelyik kettõ nem játszott egymással.

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

3. feladat: Izomorfak-e az alábbi gráfpárok?



Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

4. feladat:
 
A) Van-e olyan 4, illetve 5 csúcsú egyszerû gráf, amely izomorf a komplementerével?
 
B) Bizonyítsa be, hogy ha egy egyszerû gráf csúcsainak száma páros, de 4-gyel nem osztható, akkor nem lehet olyan részgráfja, amely izonorf a komplementerével.

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

5. feladat: Egy öttagú társaság minden tagja legalább 3 másik tagjával kölcsönös ismeretségben van.
 
A) Bizonyítsa be, hogy a társaság leülhet egy kerek asztal köré úgy, hogy mindenkinek mindkét szomszédja ismerõse legyen.
 
B) Igaz-e a feladat állítása öttagú társaság esetén hattagúra. (Feltéve itt is a min. 3 ismerõt mindenkire nézve.)

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

6. feladat: Igazolja, hogy bármely egyszerû gráfban található két azonos fokszámú pont.

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

7. feladat: Egy megye 22 településébõl ötben van kórház. Legalább hány utat kell megépítenünk, amely két-két telepüést köt össze, hogy bármely településbõl el lehessen jutni legalább egy kórházba?

Megoldás: (megjelenik) ↓ (eltûnik) ↑

Késõbb...

8. feladat: A 0-tól 8-ig számozott dominókészlet minden lapja elhelyezhetõ-e a kirakás szabályai szerint egyetlen 'körben'? ('Nyaklánccá' lehet-e 'fûzni' a dominókészlet minden tagját a szomszédos lapokra elõírt szabályok szerint?)

Megoldás: (megjelenik) ↓ (eltûnik) ↑