8. FEJEZET: Utak, távolság, átmérő.
Úthossz, leghosszabb utak
Feladat: 8.1.
Igaz-e, hogy egy
k-reguláris gráfban mindig van legalább
k élű út?
Feladat: 8.2.
Hány 2 hosszú út lehet egy
a) ötpontú fában?
b) hatpontú fában?
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?
Feladat: 8.4.
Hány 2 hosszú út van a
K5,6
teljes páros gráfban?
Feladat: 8.5.
[
4], 19. old.
Hány 2 hosszú út van a
Kn,m
teljes páros gráfban?
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?
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?
Feladat: 8.8.
Bizonyítandó, hogy egy összefüggő gráf bármely két leghosszabb útjának van közös pontja.
Feladat: 8.9.
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.
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.
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.
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?
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.
Feladat: 8.16.
Mekkora egy négy, illetve egy ötpontú kör átmérője?
Feladat: 8.17.
Mekkora egy
k pontú kör átmérője?
Feladat: 8.18.
Határozzuk meg az öt szabályos test gráfjának átmérőjét!
Feladat: 8.19.
Mekkora a
8.19. ábrán látható három gráf átmérője?
1. ábra
Feladat: 8.20.
A páros gráfok közül melyek átmérője 2?
Feladat: 8.21.
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.
Egy 2-átmérőjű gráfban van egy elsőfokú pont. Mit mondhatunk a szomszédjáról?
Feladat: 8.23.
Legalább hány éle van egy
n pontú 2-átmérőjű gráfnak?
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?
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.
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.
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?