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

8. FEJEZET: Utak, távolság, átmérő.

Bezárás: [ X ]

Úthossz, leghosszabb utak

Feladat: 8.1.
Igaz-e, hogy egy k-reguláris gráfban mindig van legalább k élű út?
 
[  Megoldás  ]
Feladat: 8.2.
Hány 2 hosszú út lehet egy
a) ötpontú fában?
b) hatpontú fában?
 
[  Megoldás  ]
Feladat: 8.3.
a) Maximálisan hány 2 hosszú út lehet egy n pontú egyszerű gráfban?
b) És egy n pontú fában?
c) *Milyen n-re lehet egy n pontú fában a maximálisnál eggyel kevesebb 2 hosszú út?
 
[  Megoldás  ]
Feladat: 8.4.
Hány 2 hosszú út van a K5,6 teljes páros gráfban?
 
[  Segítség, útmutatás  ]
Feladat: 8.5.
[4], 19. old. Hány 2 hosszú út van a Kn,m teljes páros gráfban?
 
[  Segítség, útmutatás  ]
Feladat: 8.6.
Egy társaságban tíz fiú és húsz lány van. Le szeretnénk ültetni minél több fiút és lányt egy asztal köré úgy, hogy fiúk és lányok felváltva üljenek, és mindenki ismerje a két szomszédját. Hány ember ültethető így egy asztal köré a legjobb esetben?
 
[  Segítség, útmutatás  ]
Feladat: 8.7.
Bizonyítsuk be, hogy ha egy páros gráfban a kisebbik osztályban k pont van, akkor a leghosszabb kör nem lehet 2k-nál hosszabb. Mit állíthatunk a leghosszabb útról?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 8.8.
Bizonyítandó, hogy egy összefüggő gráf bármely két leghosszabb útjának van közös pontja.
 
[  Segítség, útmutatás  ] , [  Megoldás  ]
Feladat: 8.9.
Bizonyítsuk be, hogy egy gráf és a komplementere közül legalább az egyik összefüggő.
 
[  Segítség, útmutatás  ] , [  Megoldás  ]

Ehhez a témához lásd még a 12.5.-12.15. feladatokat. Ezek a feladatok foglalkoznak azzal a kérdéssel, hogy milyen fokszám feltétel mellett milyen körök garantálhatók egy gráfban.

Távolság, átmérő

Általában egy felületen két pont távolságának a közöttük futó legrövidebb utat szoktuk tekinteni. Mivel gráfok esetében is van út, és értelmes az út hossza is, ezért itt is definiálható két pont távolsága: a közöttük futó legrövidebb út. Persze előfordulhat, hogy két pont között nem vezet út. Ebben az esetben sem jövünk zavarba, azt mondjuk, hogy a távolságuk végtelen. De a definíciónk még így sem egyértelmű. Hiszen az utak hosszát mérhetjük az élek számával is, a pontok számával is. Ha a pontok számával mérnénk, akkor egyrészt két különböző pont távolsága legalább kettő volna, másrészt például ha a gráf két csatlakozó élből áll és ezek xy és yz, akkor x és y távolsága kettő, y és z távolsága is kettő, míg x és z távolsága három. Pedig nem ,,rövidült" az út, amíg x-ből elmentünk y-ba, majd onnan z-be. Ezért célszerű az utak hosszát most az élek számával mérnünk. Így a következő definíciót kapjuk:
Definíció. Adott egy G gráf, két pontja x és y. Az x és y pont G-beli távolságán definíció szerint a közöttük a gráfban futó legrövidebb út hosszát értjük, a hosszat élekben számolva. Ha két pont között nincs út a gráfban, akkor e két pont távolságát végtelennek tekintjük.

Feladat: 8.10.
A távolság-fogalomtól meg szoktuk követelni, hogy teljesítse a háromszögegyenlőtlenséget. Azt tehát, hogy ha x, y, z tetszőleges három pont, akkor a x és a z pont távolsága legfeljebb akkora legyen, mint az x és y pontok távolságának és az y és z pontok távolságának az összege.
Ha x és z nincs egy komponensben, akkor távolságukat végtelennek vettük, de akkor x és z közül valamelyik y-nal sincs egy komponensben, tehát ezek távolsága is végtelen. Így ,,mindkét oldalon" végtelen áll. Ha x és z egy komponensben van, akkor távolságuk véges, és ha y valamelyikükkel nincs egy komponensben, akkor attól vett távolsága végtelen. Ekkor ,,azt kapjuk", hogy ,,végtelen nagyobb a végesnél", amit igaznak szoktunk tekinteni. Ebben az értelemben tehát a háromszög egyenlőtlenség igaz, ha nem mind a három pont van egy komponensben.
De mi a helyzet, ha mind a három pont azonos komponensben van?
 
[  Megoldás  ]
Feladat: 8.11.
a) Bizonyítsuk be, hogy ha egy gráfban P a legrövidebb út P két végpontja között, akkor legrövidebb út P bármely két pontja között is.

Definíció. Legyen G egy tetszőleges (véges vagy végtelen) gráf. A P (véges vagy végtelen) utat akkor és csak akkor nevezünk geodetikus útvonalnak, ha semely két pontja között nincs rövidebb út a gráfban.
A feladat tehát így is fogalmazható: Bizonyítsuk be, hogy ha egy gráfban P a legrövidebb út P két végpontja között, akkor P geodetikus útvonal.
 
[  Segítség, útmutatás  ]
Feladat: 8.12.
Kutató munka:
Nevezzünk alkalmilag ,,jó pontpárnak" egy gráf két pontját, ha nincsenek éllel összekötve, de van közös szomszédjuk. Melyik n pontú egyszerű gráfban van a legtöbb ,,jó pontpár"?
 
Feladat: 8.13.
Kutató munka:
Bergengócia bizonyos városait oda-vissza repülőjárat köt össze. Minden városból legfeljebb három repülőjárat indul és bármely városból bármely másik városba el lehet jutni legfeljebb egy átszállással. Legfeljebb hány városa van Bergengóciának?
 
[  Megoldás  ]
Feladat: 8.14.
Kutató munka:
Fogalmazzuk meg, milyen tulajdonság közös a 8.12. és a 8.13. feladat maximális gráfját adó gráfban!
 

Egy alakzat átmérőjén a geometriában az alakzat két legtávolabbi pontja közötti távolságot szoktuk érteni. (A fogalom persze nem mindig ilyen egyszerű - csak zárt ponthalmazok esetén az -, de véges ponthalmazok esetén megfelelő.)

Minthogy definiáltuk a gráf pontjai közötti távolságot, ezért az átmérőt is definiálni tudjuk. Itt már zavart okozhatna a végtelen távolság, ezért az átmérőt csak véges gráfokra definiáljuk:

Definíció. Egy összefüggő véges gráf átmérőjét a pontjai között fellépő maximális távolságként definiáljuk. Így például a teljes gráf átmérője 1, a csillagé 2.

Feladat: 8.15.
Fogalmazzuk meg az átmérő fogalma segítségével gráfelméleti nyelven a 8.13. feladat állítását!
Megjegyzés. A feladat folytatása a 10.6. feladat.
 
[  Megoldás  ]
Feladat: 8.16.
Mekkora egy négy, illetve egy ötpontú kör átmérője?
 
[  Segítség, útmutatás  ]
Feladat: 8.17.
Mekkora egy k pontú kör átmérője?
 
[  Segítség, útmutatás  ]
Feladat: 8.18.
Határozzuk meg az öt szabályos test gráfjának átmérőjét!
 
[  Segítség, útmutatás  ]
Feladat: 8.19.
Mekkora a 8.19. ábrán látható három gráf átmérője?

1. ábra

 
[  Segítség, útmutatás  ]
Feladat: 8.20.
A páros gráfok közül melyek átmérője 2?
 
[  Segítség, útmutatás  ]
Feladat: 8.21.
Mit tudunk mondani egy nem összefüggő gráf komplementerének átmérőjéről?
 
[  Segítség, útmutatás  ] , [  Megoldás  ]

2-átmérőjű gráfok élszáma

Feladat: 8.22.
Egy 2-átmérőjű gráfban van egy elsőfokú pont. Mit mondhatunk a szomszédjáról?
 
[  Segítség, útmutatás  ]
Feladat: 8.23.
Legalább hány éle van egy n pontú 2-átmérőjű gráfnak?
 
[  Segítség, útmutatás  ]
Feladat: 8.24.
Tekintsük a következő 11 pontú gráfot.
A gráf pontjai x1 , x2 , x3 , x4 , x5 , y1 , y2 , y3 , y4 , y5 ,z.
Az xi pontok a megadott sorrendben egy C5 -öt alkotnak. Az yi pont xi-1 -gyel és xi+1 -gyel van összekötve (az indexelés mod 5 periodikus), továbbá z-vel. (Az xi pontok tehát negyedfokúak, az yi pontok harmadfokúak, z pedig ötödfokú.) Lásd az 1. ábrát is!

1. ábra
Mekkora ennek a gráfnak az átmérője?
 
[  Segítség, útmutatás  ]
Feladat: 8.25.
* a) Bizonyítsuk be, hogy ha egy n pontú 2-átmérőjű gráfban nincs telített pont, akkor élszáma legalább (3n-5)/2,
b) Legyen n≥5. Mutassunk példát olyan n pontú, telített pont nélküli, 2-átmérőjű gráfra, amelynek 2n-5 éle van.
Megjegyzés. Bebizonyítható, hogy 2n-5-nél kevesebb éle nem lehet egy ilyen gráfnak. L. a 8.26. feladatot.
 
[  Megoldás  ]
Feladat: 8.26.
** Bizonyítsuk be, hogy ha egy n pontú 2-átmérőjű gráfban nincs telített pont, akkor élszáma legalább 2n-5.
 
[  Megoldás  ]
Feladat: 8.27.
** Van-e olyan n, amelyre van olyan pontú, 2-átmérőjű gráf, amelyben minden pont foka legalább három és élszáma 2n-5?
 
[  Megoldás  ]