8. FEJEZET: Utak, távolság, átmérő.{mchap:k_ii_grafutak}
Úthossz, leghosszabb utak
Feladat: 8.1. {k_ii_100108sl_uth01}
Igaz-e, hogy egy
k-reguláris gráfban mindig van legalább
k élű út?
Feladat: 8.2. {k_ii_091213sl_gralap01}
Hány 2 hosszú út lehet egy
a) ötpontú fában?
b) hatpontú fában?
Feladat: 8.3. {k_ii_091213sl_gralap02}
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?
Feladat: 8.4. {k_ii_100108sl_gralap01a}
Hány 2 hosszú út van a
K5,6
teljes páros gráfban?
Feladat: 8.5. {k_ii_100108sl_gralap01}
[
4], 19. old.
Hány 2 hosszú út van a
Kn,m
teljes páros gráfban?
Feladat: 8.6. {k_ii_090825sl_grut01b}
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?
Feladat: 8.7. {k_ii_090825sl_grut01}
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?
Feladat: 8.8. {k_ii_090810sl_grafutak01}
Bizonyítandó, hogy egy összefüggő gráf bármely két leghosszabb útjának van közös pontja.
Feladat: 8.9. {k_ii_090823sl_grut01}
Bizonyítsuk be, hogy egy gráf és a komplementere közül legalább az egyik összefüggő.
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. {k_ii_100101sl_grut23}
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?
Feladat: 8.11. {k_ii_090822sl_grut01}
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.
Feladat: 8.12. {k_ii_100916sl_grut04}
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. {k_ii_sl_petersen01}
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?
Feladat: 8.14. {k_ii_100916sl_grut05}
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. {k_ii_100916sl_grut02}
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.
Feladat: 8.16. {k_ii_100101sl_grut21}
Mekkora egy négy, illetve egy ötpontú kör átmérője?
Feladat: 8.17. {k_ii_100101sl_grut22}
Mekkora egy
k pontú kör átmérője?
Feladat: 8.18. {k_ii_100105sl_grut11}
Határozzuk meg az öt szabályos test gráfjának átmérőjét!
Feladat: 8.19. {k_ii_100105sl_grut12}
Mekkora a
8.19. ábrán látható három gráf átmérője?
1. ábra{fig:k_ii_100105sl_grut12}
Feladat: 8.20. {k_ii_100109sl_atmero03}
A páros gráfok közül melyek átmérője 2?
Feladat: 8.21. {k_ii_090823sl_grut02}
Mit tudunk mondani egy nem összefüggő gráf komplementerének átmérőjéről?
2-átmérőjű gráfok élszáma
Feladat: 8.22. {k_ii_100109sl_atmero01}
Egy 2-átmérőjű gráfban van egy elsőfokú pont. Mit mondhatunk a szomszédjáról?
Feladat: 8.23. {k_ii_100109sl_atmero02}
Legalább hány éle van egy
n pontú 2-átmérőjű gráfnak?
Feladat: 8.24. {k_ii_100105sl_grut12a}
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{fig:k_ii_100105sl_grut12a}
Mekkora ennek a gráfnak az átmérője?
Feladat: 8.25. {k_ii_100109sl_atmero05}
* 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.
Feladat: 8.26. {k_ii_100110sl_atmero01}
** 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.
Feladat: 8.27. {k_ii_100110sl_atmero02}
** 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?