A GRÁFBELI TÁVOLSÁGFOGALOMRÓL
Igaz-e, hogy a gráfokban definiált távolságfogalom „valódi távolságfogalom” abban az értelemben, hogy teljesíti a háromszög-egyenlőtlenséget? Vagyis ha a gráfnak vesszük három pontját, a-t, b-t és c-t, akkor az a és b pontok távolsága és a b és c pontok távolsága együtt nem kisebb az a és c pontok távolságánál: d(a, b) + d(b,c) ≥ (a,c) ?
Fontos kérdés, hogy egy gráf mennyire „tömör”, vagy másképp fogalmazva: megkérdezhetjük, hogy két pont maximálisan milyen távol van egymástól a gráfban. Véges ponthalmazoknál két pont maximális távolságát nevezzük a ponthalmaz átmérőjének. Pontosan ugyanígy bevezethetjük egy gráf átmérőjének a fogalmát is:
Ha a gráf nem összefüggő, akkor mondhatjuk, hogy az átmérő végtelen, vagy megszoríthatjuk a definíciót összefüggő gráfokra.
Az átmérőre vonatkozó egyszerű feladatok a következők:
a) Mely gráfoknak 1 az átmérője? MEGOLDÁS
b) Mennyi a csillag átmérője? MEGOLDÁS
c) Mennyi az 5 hosszú kör átmérője? És a 7 hosszúé? Mennyi általában az n pontú köré? MEGOLDÁS
d) Mennyi egy 10 élből álló út átmérője? És általában az n élű úté? MEGOLDÁS
e) Mennyi a tetraédek és a kocka élgráfjának átmérője? MEGOLDÁS
f) Mennyi az oktaéder élgráfjának átmérője? MEGOLDÁS
g) Mennyi az ikozaéder élgráfjának átmérője? MEGOLDÁS
h) Egy fának a gyökéren kívül 5 emelete van. Legfeljebb mekkora lehet az átmérője? MEGOLDÁS
Már sokkal bonyolultabb az a kérdés, hogy milyenek a 2-átmérőjű gráfok. Erre a kérdésre a 29. és a 49. feladatban térünk vissza, majd a IV. fejezet 18–20. feladataiban foglalkozunk részletesen egy nevezetes 2-átmérőjű gráffal.
Az átmérővel kapcsolatban egyelőre csak annyit jegyzünk meg, amit az előző algoritmusainkból ki tudunk róluk olvasni:
Bizonyítsuk be, hogy összefüggő gráf átmérője is polinomiális időben meghatározható.
| TARTALOMJEGYZÉK |