Rastojanje (teorija grafova)

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.[1] 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 izmedju dva čvora i je broj grana u najkraćem putu od čvora do čvora , pod uslovom da bar jedan takav put postoji. Za razliku od neusmerenog grafa, kod usmerenog grafa ne mora da znači da je isto što i , može čak i da se desi da je jedno rastojanje definisano dok drugo nije.


Srodni pojmoviУреди

Metrika grafaУреди

Prema definiciji   predstavlja funkciju  , koja se naziva funkcija rastojanja, odnosno metrika grafa  . Metrika grafa   ima sledeće osobine:

 1)    pri cemu je   ako i samo ako je   (nenegativnost rastojanja);
 2)    za svaki par čvorova   (simetričnost rastojanja);
 3)    za svaka tri čvora   (nejednakost trougla);
 4)    je nenegativni ceo broj za svaki par čvorova  ;
 5)  ako je   tada postoji čvor   , različit i od    i od   , takav da važi  . 

Ekscentricitet čvora  , u oznaci  , je najveće rastojanje od čvora   do svih ostalih čvorova, tj.  .

Dijametar grafa, u oznaci  , je najveći ekscentricitet,  .

Radijus grafa, u oznaci  , je najmanji ekscentricitet,  .

Centar grafa   čine svi čvorovi čiji je ekscentricitet jednak radijusu grafa, analogno tome, periferiju grafa   čine svi čvorovi čiji je ekscentricitet jednak dijametru grafa.[2]

BFS algoritam za nalaženje najkraćeg putaУреди

Ulaz:  (neusmereni povezan graf) i   (čvor grafa  ).

Izlaz: Zavisi od primene.

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

Put od korena   BFS stabla do proizvoljnog čvora   kroz BFS stablo najkraći je put od   do   u grafu  .[3]

Vidi jošУреди

РеференцеУреди

  1. ^ Stevanović, Dragan; Ćirić M.; et al. (jul 2007). „Osnove kombinatorike i teorije grafova”. Приступљено 11-05-2015.  Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)
  2. ^ Stevanović, Dragan; Ćirić M.; et al. (jul 2007). „Osnove kombinatorike i teorije grafova”. Приступљено 11-05-2015.  Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)
  3. ^ Živković, Miodrag. „Algoritmi” (PDF). Приступљено 11-05-2015.  Проверите вредност парамет(а)ра за датум: |access-date= (помоћ)

Spoljašnje vezeУреди