Afstand (grafteori)

I grafteori er afstanden mellem to hjørner af en graf antallet af kanter i den korteste vej (også kaldet grafens geodætiske ). En afstand i en graf kaldes også en geodætisk afstand [1] . Der kan være flere korteste veje mellem to spidser [2] . Hvis der ikke er nogen vej mellem to hjørner, det vil sige, hvis de tilhører forskellige forbundne komponenter , er det sædvanligt at betragte afstanden som uendelig.

I tilfælde af rettede grafer er afstanden mellem to hjørner og defineret som længden af den korteste vej fra til , bestående af buer [3] . I modsætning til tilfældet med urettede grafer, falder det muligvis ikke sammen med , og det kan endda ske, at den ene afstand eksisterer og den anden ikke. $d(u,v)$ $u$ $v$ $u$ $v$ $d(u,v)$ $d(v,u)$

Grundlæggende definitioner

Et metrisk rum defineret på et sæt punkter i form af afstand i en graf kaldes en grafmetrik . Toppunktet (af en urettet graf) og afstandsfunktionen danner et metrisk rum, hvis og kun hvis grafen er forbundet .

Excentriciteten af et toppunkt er den største geodætiske afstand mellem og ethvert andet toppunkt i grafen. Det vil sige afstanden til længst fra toppen af grafen. $\epsilon (v)$ $v$ $v$ $v$

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

Grafens radius er minimumsexcentriciteten blandt alle grafens toppunkter $r$

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

Grafens diameter er den maksimale excentricitet blandt alle grafens toppunkter. Således er den største afstand mellem alle par af grafens hjørnepunkter $d$ $d$

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

For at finde diameteren af en graf skal du først finde de korteste veje mellem alle par af hjørner . Den største længde af den korteste vej er diameteren af grafen.

Det centrale toppunkt på grafen med en radius er et toppunkt, hvis excentricitet er lig med . Det vil sige det toppunkt, hvor radius nås $r$ $r$

\epsilon (v)=r

Diametergrafens perifere toppunkt er det toppunkt, hvis excentricitet er lig med $d$ $d$

\epsilon (v)=d

Et pseudo-perifert toppunkt er et toppunkt, som ethvert toppunkt har egenskaben til - hvis så langt fra som muligt, så så langt fra som muligt. Formelt set er et toppunkt pseudo-perifert, hvis det for et hvilket som helst toppunkt c , . $v$ $u$ $v$ $u$ $u$ $v$ $u$ $v$ $d(u,v)=\epsilon(u)$ $\epsilon (u)=\epsilon (v)$

Opdelingen af grafens toppunkter i delmængder i henhold til deres afstand fra et givet startpunkt kaldes grafens niveaustruktur .

Algoritme til at finde pseudo-perifere hjørner

Ofte kræver algoritmer for sparsomme matricer et startpunkt med høj excentricitet. Det ville være bedre at bruge et perifert toppunkt, men i en stor graf er det svært at finde det. I de fleste tilfælde kan pseudo-perifere hjørner bruges. Det pseudo-perifere toppunkt kan nemt findes ved hjælp af følgende algoritme:

Lad os vælge en top . $u$
Blandt alle hjørner længst væk fra , lad har minimumsgraden . $u$ $v$
Hvis , så tag og gå til trin 2, ellers er det et pseudo-perifert vertex. $\epsilon (v)>\epsilon (u)$ $u=v$ $v$

Se også

Noter

↑ Jérémie Bouttier, P. Di Francesco, E. Guitter. Geodætisk afstand i plane grafer. - 2003. - T. 663 , no. 3 . - S. 535-567 . - doi : 10.1016/S0550-3213(03)00355-9 .
↑ Weisstein, Eric W. Graph Geodesic . MathWorld - En Wolfram-webressource . Wolfram Research. - "Længden af grafen geodætisk mellem disse punkter d(u,v) kaldes grafafstanden mellem u og v". Hentet 23. april 2008. Arkiveret fra originalen 23. april 2008. (ubestemt)
↑ F. Harary. grafteori . - MA: Addison-Wesley, 1969. - S. 199 .