Távolság (gráfelmélet)

A gráfelméletben a gráf két csúcsa közötti távolság a legrövidebb út éleinek száma (más néven gráf geodéziai ). A gráfban lévő távolságot geodéziai távolságnak is nevezik [1] . Két csúcs között több legrövidebb út is lehet [2] . Ha két csúcs között nincs út, vagyis ha különböző összefüggő komponensekhez tartoznak , akkor a távolságot végtelennek szokás tekinteni.

Irányított gráfok esetén a és két csúcs közötti távolság a -tól -ig tartó legrövidebb út hossza , amely ívekből áll [3] . Az irányítatlan gráfokkal ellentétben előfordulhat, hogy nem esik egybe a -val , sőt az is előfordulhat, hogy az egyik távolság létezik, a másik pedig nem. $d(u,v)$ $u$ $v$ $u$ $v$ $d(u,v)$ $d(v,u)$

Alapdefiníciók

A gráf távolsága alapján meghatározott pontok halmazán definiált metrikus teret gráfmetrikának nevezzük . A csúcshalmaz (egy irányítatlan gráf) és a távolságfüggvény akkor és csak akkor alkot metrikus teret, ha a gráf össze van kötve .

Egy csúcs excentricitása a legnagyobb geodéziai távolság a gráf bármely más csúcsa között. Azaz a távolság a grafikon tetejétől legtávolabbi részig. $\epsilon (v)$ $v$ $v$ $v$

\epsilon (v)=\max _{u\in V}d(v,u)

A gráf sugara az összes gráfcsúcs minimális excentricitása $r$

r=\min _{v\in V}\epsilon (v)

A gráf átmérője a gráf összes csúcsa közötti maximális excentricitás. Így a gráfcsúcsok összes párja közötti legnagyobb távolság $d$ $d$

d=\max _{v\in V}\epsilon (v)

A gráf átmérőjének meghatározásához először keresse meg az összes csúcspár közötti legrövidebb utat . A legrövidebb út legnagyobb hossza a gráf átmérője.

A gráf sugarú központi csúcsa egy olyan csúcs, amelynek excentricitása egyenlő . Vagyis az a csúcs, ahol a sugár elérésre kerül $r$ $r$

\epsilon (v)=r

Az átmérőgráf perifériás csúcsa az a csúcs, amelynek excentricitása egyenlő $d$ $d$

\epsilon (v)=d

Pszeudo-periférikus csúcsnak nevezzük azt a csúcsot, amelyre bármely csúcs rendelkezik - ha a lehető legtávolabb , akkor a lehető legtávolabb . Formálisan egy csúcs pszeudoperiférikus, ha bármely c , . $v$ $u$ $v$ $u$ $u$ $v$ $u$ $v$ $d(u,v)=\epsilon(u)$ $\epsilon (u)=\epsilon (v)$

A gráf csúcsainak részhalmazokra való felosztását az adott kezdeti csúcstól való távolságuk szerint a gráf szintstruktúrájának [ nevezzük.

Algoritmus pszeudo-periférikus csúcsok keresésére

A ritka mátrixok algoritmusai gyakran nagy excentricitású kezdőcsúcsot igényelnek. Jobb lenne perifériás csúcsot használni, de egy nagy gráfban nehéz megtalálni. A legtöbb esetben pszeudo-periférikus csúcsok használhatók. A pszeudo-periférikus csúcs könnyen megtalálható a következő algoritmussal:

Válasszunk egy felsőt . $u$
A -tól legtávolabbi csúcsok között legyen a minimális fok . $u$ $v$
Ha , akkor lépjen a 2. lépésre, ellenkező esetben ez egy pszeudo-periférikus csúcs. $\epsilon (v)>\epsilon (u)$ $u=v$ $v$

Lásd még

Jegyzetek

↑ Jérémie Bouttier, P. Di Francesco, E. Guitter. Geodéziai távolság síkgráfokban. - 2003. - T. 663 , sz. 3 . - S. 535-567 . - doi : 10.1016/S0550-3213(03)00355-9 .
↑ Weisstein, Eric W. Graph Geodesic . MathWorld – A Wolfram webes erőforrása . Wolfram kutatás. - "A gráf geodéziai hosszát ezen d(u,v) pontok között az u és v közötti gráftávolságnak nevezzük." Letöltve: 2008. április 23. Az eredetiből archiválva : 2008. április 23.. (határozatlan)
↑ F. Harary. gráfelmélet . - MA: Addison-Wesley, 1969. - 199. o .