Matkönyv feladatgyűjtemény: Kombinatorika 9--10

3. FEJEZET: Összefüggések a fokszám és az élszám között

Bezárás: [ X ]

Átismételjük - immár ,,gráfelméleti nyelven" - a fokszám és élszám közötti nevezetes Euler-összefüggést és pár következményét. Egy kevésbé ismert, de fontos élesítését is tárgyaljuk és megvizsgáljuk, hogyan szól irányított gráfokra. Ebben a fejezetben aránylag kevés feladat szerepel, viszont a következő 4. fejezet első feladatai e fejezet témáját folytatják.

Az Euler-összefüggés

Ide tartozó korábbi feladatok: 2.2., 2.3, 2.4, 2.5, 2.6, 2.7.

Feladat: 3.1.
Egy nyolctagú társaság minden tagjától megkérdeztük, hogy hány ismerőse van a társaságban. Sorra a következő válaszokat kaptuk: 3, 5, 4, 2, 5, 2, 4, 4. Lehetséges-e, hogy a társaságban kölcsönösek az ismeretségek?
 
[  Megoldás  ]
Feladat: 3.2.
Egy tíztagú társaságban mindenki összeszámolta ismerőseit. Kiderült, hogy hármuknak van öt-öt ismerőse, kettőnek csak kettő-kettő, a többi ötnek négy-négy ismerőse van. Tudjuk, hogy az ismeretségek kölcsönösek. Igazoljuk, hogy valaki rosszul számolt.
 
[  Megoldás  ]
Feladat: 3.3.
Hogyan általánosítható a 3.2. feladat? Fogalmazzuk meg állításunkat a gráfelmélet nyelvén is!
 
[  Megoldás  ]
Feladat: 3.4.
Igaz-e nem egyszerű véges gráfokra is az az Euler-tétel, mely szerint a fokszámok összege mindig páros?
 
[  Megoldás  ]
Feladat: 3.5.
Mit mondhatunk egy hurokél nélküli gráfban a páratlan fokú pontok számáról?
 
[  Megoldás  ]

Élesítések

Feladat: 3.6.
Kutató munka:
Egy társaságban, ahol az ismeretségek kölcsönösek, bármely két embernek együtt legalább tíz ismerőse van. Mit mondhatunk a társaságban levő ismeretségek számáról?
És mit mondhatunk, ha bármely két embernek együtt legfeljebb tíz ismerőse van?
 
Feladat: 3.7.
Kutató munka: Hogyan általánosítható a 3.6. feladatban megfogalmazott állítás?
 
Feladat: 3.8.
Kutató munka:
Egy egyszerű gráfban bármely három pont fokszámának az összege legalább 3k. Mit mondhatunk a gráf élszámáról?
És mit mondhatunk, ha bármely három pont fokszámának az összege legfeljebb 3k?
* Hogyan általánosítható a feladat?
 
Feladat: 3.9.
Hogyan általánosítható a 2.24. feladat állítása?
 
[  Megoldás  ]
Feladat: 3.10.
Egy üdülő bármely három lakója között van kettő, aki nem ismeri egymást, de bármely hét lakója között van kettő, aki ismeri egymást. Az üdülés befejeztével mindenki megajándékozza minden ismerősét egy-egy ajándékkal. Bizonyítsuk be, hogy n lakó esetén legfeljebb 6n ajándéktárgyat adtak át! (OKTV 1986, I. kategória, döntő)
Hogyan fogalmazható át a feladat gráfelméleti nyelvre?
 
[  Megoldás  ]
Feladat: 3.11.
[186], 148. oldal.
Egy n megfigyelőállomással rendelkező sarkkutató expedíció állomásai között legfeljebb k olyan van, amelyek között semelyik kettő nincs egymással közvetlen telefon-összeköttetésben. Nincs köztük továbbá három olyan, amelyek mindegyike mindegyikkel közvetlen összeköttetésben van.
Bizonyítsuk be, hogy ekkor a közvetlen telefon-összeköttetések száma nem lehet több, mint nk/2. (Ki miben tudós? 1966/döntő)
 
[  Megoldás  ]

Az irányított gráfok esete

Feladat: 3.12.
a) Egy tízpontú irányított gráfban a kifokok rendre 1,1,2,3,3,3,4,4,4,4. Hány éle van a gráfnak?
b) Egy kilencpontú irányított gráfban a befokok rendre 1,1,2,3,3,3,4,4,4. Hány éle van a gráfnak? Rajzoljunk ilyen gráfot!
 
[  Megoldás  ]
Feladat: 3.13.
Hogyan szól a fokszámösszegre vonatkozó összefüggés irányított gráfoknál?
 
[  Megoldás  ]