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.
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.)
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)
↑