Rastojanje (teorija grafova)

Шаблон:Neprovereni seminarski U matematičkoj grani koja se zove teorija grafova, rastojanje između dva čvora u grafu je broj grana u najkraćem putu koji ih povezuje. Takođe, u grafu može da postoji više najkraćih puteva. Ako ne postoji put između dva čvora, na primer ako čvorovi pripadaju različitim komponentima povezanosti, smatra se da je njihovo rastojanje beskonačno.

U slučaju da je graf usmeren, rastojanje $d(u,v)$ izmedju dva čvora $u$ i $v$ je broj grana u najkraćem putu od čvora $u$ do čvora $v$, pod uslovom da bar jedan takav put postoji. Za razliku od neusmerenog grafa, kod usmerenog grafa ne mora da znači da je $d(u,v)$ isto što i $d(v,u)$, može čak i da se desi da je jedno rastojanje definisano dok drugo nije.

Srodni pojmovi

Metrika grafa

Prema definiciji $d(u,v)$ predstavlja funkciju $d:V\times V\to R$, koja se naziva funkcija rastojanja, odnosno metrika grafa $G$. Metrika grafa $G$ ima sledeće osobine:

 1)  $d(u,v)\ge 0$ pri cemu je $d(u,v)=0$ ako i samo ako je $u=v$ (nenegativnost rastojanja);
 2)  $d(u,v)=d(v,u)$ za svaki par čvorova $u,v\in V$ (simetričnost rastojanja);
 3)  $d(u,w)\le d(u,v)+d(v,w)$ za svaka tri čvora $u,v,w\in V$ (nejednakost trougla);
 4)  $d(u,v)$ je nenegativni ceo broj za svaki par čvorova $u,v\in V$;
 5)  ako je $d(u,w)\ge 1$ tada postoji čvor  $v$, različit i od  $u$ i od  $w$, takav da važi $d(u,w)=d(u,v)+d(v,w)$. 

Ekscentricitet čvora $u$, u oznaci $ecc(u)$, je najveće rastojanje od čvora $u$ do svih ostalih čvorova, tj. $ecc(u)=\underset{v\in V}{\max }d(u,v)$.

Dijametar grafa, u oznaci $D(G)$, je najveći ekscentricitet, $D(G)=\underset{u\in V}{\max }ecc(u)$.

Radijus grafa, u oznaci $r(G)$, je najmanji ekscentricitet, $r(G)=\underset{u\in V}{\min }ecc(u)$.

Centar grafa $G$ čine svi čvorovi čiji je ekscentricitet jednak radijusu grafa, analogno tome, periferiju grafa $G$ čine svi čvorovi čiji je ekscentricitet jednak dijametru grafa.

BFS algoritam za nalaženje najkraćeg puta

Ulaz: $G=(V,E)$(neusmereni povezan graf) i $v$ (čvor grafa $G$).

Izlaz: Zavisi od primene.

begin
  označi $v$;
  upiši $v$ u listu; {FIFO lista, privi unutra - prvi napolje}
  while lista je neprazna do
    skini privi čvor $w$ sa liste;
    izvrši ulaznu obradu na $w$; {ulazna obrada zavisi od primene BFS}
    for sve grane $(w,x)$ za koje $x$ nije označen do
      označi $x$;
      dodaj $(w,x)$ u stablo $T$;
      upiši $x$ u listu;
end

Put od korena $r$ BFS stabla do proizvoljnog čvora $w$ kroz BFS stablo najkraći je put od $r$ do $w$ u grafu $G$.

Vidi još

• Teorija grafova
• Pretraga u širinu

Spoljašnje veze

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web