Пређи на садржај

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.


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.[1]

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 .[2]

Референце

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

Spoljašnje veze

[уреди | уреди извор]