3. FEJEZET: Összefüggések a fokszám és az élszám között
Á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
Feladat: 3.1. (M)
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?
Feladat: 3.2. (M)
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.
Feladat: 3.3. (M)
Hogyan általánosítható a
3.2. feladat? Fogalmazzuk meg állításunkat a gráfelmélet nyelvén is!
Feladat: 3.4. (M)
Igaz-e nem egyszerű véges gráfokra is az az Euler-tétel, mely szerint a fokszámok összege mindig páros?
Feladat: 3.5. (M)
Mit mondhatunk egy hurokél nélküli gráfban a páratlan fokú pontok számáról?
É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. (M)
Hogyan általánosítható a
2.24. feladat állítása?
Feladat: 3.10. (M)
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?
Feladat: 3.11. (M)
[
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ő)
Az irányított gráfok esete
Feladat: 3.12. (M)
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!
Feladat: 3.13. (M)
Hogyan szól a fokszámösszegre vonatkozó összefüggés irányított gráfoknál?