| |
Be lehet vezetni minden csúcs generációs indexét, ami a csúcsból a gyökérbe vezető egyetlen út hossza. A gyökér generációs indexe 0, egy csúcs apjának generációs indexe a csúcs indexénél 1-gyel kisebb.
Tegyük fel, hogy a leghosszabb út hossza legfeljebb 2k-1, és legyen ez az út P=x1x2
xm, m<2k. Ekkor van két olyan szomszédos pont, xi és xi+1, hogy x1-ből megy él xi+1-be és xm-ből megy él xi-be.
Két csúcs távolsága (jelölése dG(u, v)) a G gráfban az egyik legrövidebb köztük menő út hossza. A G gráfra utaló alsó index elhagyható, ha nem vezet félreértésre. Ha u és v egybeesnak, akkor távolságuk 0.
azaz a P 1 Ⲡ⪠Q ⪠P 2 Ⲡút hosszabb P 2 -nél, ami ellentmondás.
 See also: Halmaz, Összefüggő, Végpont, Sorozat, Fokszám
  
|
RSS
