Bizonyítsuk be, hogy egy összefüggő gráf átmérője is polinomiális idoben meghatározható.
A biyznyításhoz az egyszerűség kedvéért bevezetjük egy gyökeres fa magasságának fogalmát: ez a gyökértől legtávolibb pont távolsága a gyökértől. Vagy másképp: a fa (gyökértől különböző) szintjeinek száma.
Minden x ponthoz megkeressük az x gyökerű szélességi favázat. Ennek magassága az x-tol legtávolabbi pont távolsága. Jelöljük ezt t(x)-szel. Ha minden x-re meghatározzuk t(x)-et, akkor a gráf átmérője a legnagyobb t(x) lesz. Márpedig t(x) meghatározásához elég p(n) idő, és n pont van, ezért az összes t(x) meghatározásához is elég np(n) idő, ami szintén polinom. A maximum meghatározása minden x-nél csak plussz egy lépés: összehasonlítjuk azt, amit az aktuális t(x)-re kaptunk, az eddigi legnagyobb értékkel és a kettő közül a nagyobbat tároljuk.
TARTALOMJEGYZÉK |