Avstånd (grafteori) - Distance (graph theory)

I matematisk området för grafteori , den avståndet mellan två hörn i en graf är antalet kanter i en kortaste vägen (även kallad en graf geodetisk ) som förbinder dem. Detta är också känt som det geodesiska avståndet eller det kortaste avståndet . Lägg märke till att det kan finnas mer än en kortaste väg mellan två hörn. Om det inte finns någon väg som förbinder de två hörnen, dvs om de tillhör olika anslutna komponenter , definieras avståndet konventionellt som oändligt.

När det gäller en riktad graf är avståndet mellan två hörn och definieras som längden på den kortaste riktade vägen från till bestående av bågar, förutsatt att minst en sådan väg existerar. Lägg märke till att, i motsats till fallet med oriktade grafer, inte nödvändigtvis sammanfaller med- så det är bara en kvasi-metrisk , och det kan vara så att den ena definieras medan den andra inte är det. ${\displaystyle d(u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)}$${\displaystyle d(v,u)}$

Relaterade begrepp

Ett måttrum definierat över en uppsättning punkter när det gäller avstånd i en graf definierad över uppsättningen kallas en grafmätare . Spetsuppsättningen (av en oriktad graf) och avståndsfunktionen bildar ett metriskt utrymme, om och bara om grafen är ansluten .

Den excentricitet av en vertex är största avståndet mellan och varje annan vertex; i symboler alltså . Det kan ses som hur långt en nod är från noden som är mest avlägsen från den i grafen. ${\displaystyle \epsilon (v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u)}$

Den radie av en kurva är den minsta excentricitet av något av hörnen eller, i symboler, . ${\displaystyle r}$${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)}$

Den diameter hos en kurva är den maximala excentricitet något av hörnen i grafen. Det vill säga det största avståndet mellan alla hörnpar eller alternativt . För att hitta diametern på en graf, hitta först den kortaste vägen mellan varje par hörn . Den största längden på någon av dessa banor är diagrammets diameter. ${\displaystyle d}$${\displaystyle d}$${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u)}$

En central toppunkt i en radiegraf är en vars excentricitet är - det vill säga en toppunkt som uppnår radien eller, på motsvarande sätt, en toppunkt så att . ${\displaystyle r}$${\displaystyle r}$${\displaystyle v}$${\displaystyle \epsilon (v)=r}$

En perifer toppunkt i ett diagram med diameter är en som är avstånd från någon annan toppunkt - det vill säga en toppunkt som uppnår diametern. Formellt är perifer om . ${\displaystyle d}$${\displaystyle d}$${\displaystyle v}$${\displaystyle \epsilon (v)=d}$

En pseudo-perifer vertex har den egenskapen att för varje toppunkt , om den är så långt ifrån som möjligt, så är den så långt ifrån som möjligt. Formellt är en hörn u pseudo-perifer, om för varje hörn v med håll . ${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)=\epsilon (u)}$${\displaystyle \epsilon (u)=\epsilon (v)}$

Den partition av en diagrammets hörn i underuppsättningar genom deras avstånd från en given start vertex kallas en nivå struktur av grafen.

En graf så att för varje par hörn finns en unik kortaste väg som förbinder dem kallas en geodetisk graf . Till exempel är alla träd geodetiska.

Det vägda kortaste banavståndet generaliserar det geodesiska avståndet till viktade grafer . I detta fall antas att vikten av en kant representerar dess längd eller, för komplexa nätverk av kostnaden av interaktionen, och den viktade kortaste-väg avstånd är det minsta summan av vikterna på alla de banor som förbinder och . Se det kortaste sökvägsproblemet för mer information och algoritmer. ${\displaystyle d^{W}(u,v)}$${\displaystyle u}$${\displaystyle v}$

Algoritm för att hitta pseudo-perifera hörn

Ofta behöver perifera glesa matrisalgoritmer ett startpunkt med hög excentricitet. En perifer toppunkt skulle vara perfekt, men är ofta svår att beräkna. I de flesta fall kan en pseudo-perifer toppunkt användas. En pseudo-perifer vertex kan lätt hittas med följande algoritm:

1. Välj en toppunkt .${\displaystyle u}$
2. Bland alla hörn som är så långt ifrån som möjligt, låt vara ett med minimal grad .${\displaystyle u}$${\displaystyle v}$
3. Om du sedan ställer in och upprepar med steg 2, är annars en pseudo-perifer toppunkt.${\displaystyle \epsilon (v)>\epsilon (u)}$${\displaystyle u=v}$${\displaystyle u}$

Se även

Anteckningar