Растојање (теорија графова)

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

У математичкој грани која се зове теорија графова, растојање између два чвора у графу је број грана у најкраћем путу који их повезује.^[1] Такође, у графу може да постоји више најкраћих путева. Ако не постоји пут између два чвора, на пример ако чворови припадају различитим компонентима повезаности, сматра се да је њихово растојање бесконачно.

У случају да је граф усмерен, растојање $d(u,v)$ измедју два чвора $u$ и $v$ је број грана у најкраћем путу од чвора $u$ до чвора $v$ , под условом да бар један такав пут постоји. За разлику од неусмереног графа, код усмереног графа не мора да значи да је $d(u,v)$ исто што и $d(v,u)$ , може чак и да се деси да је једно растојање дефинисано док друго није.

Сродни појмови[уреди | уреди извор]

Метрика графа[уреди | уреди извор]

Према дефиницији $d(u,v)$ представља функцију $d\colon V\times V\to R$ , која се назива функција растојања, односно метрика графа $G$ . Метрика графа $G$ има следеће особине:

 1)   $d(u,v)\geq 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)\leq 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)\geq 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)$ .

Ексцентрицитет чвора $u$ , у ознаци $ecc(u)$ , је највеће растојање од чвора $u$ до свих осталих чворова, тј. $ecc(u)=\max _{v\in V}d(u,v)$ .

Дијаметар графа, у ознаци $D(G)$ , је највећи ексцентрицитет, $D(G)=\max _{u\in V}ecc(u)$ .

Радијус графа, у ознаци $r(G)$ , је најмањи ексцентрицитет, $r(G)=\min _{u\in V}ecc(u)$ .

Центар графа $G$ чине сви чворови чији је ексцентрицитет једнак радијусу графа, аналогно томе, периферију графа $G$ чине сви чворови чији је ексцентрицитет једнак дијаметру графа.^[1]

БФС алгоритам за налажење најкраћег пута[уреди | уреди извор]

Улаз: $G=(V,E)$ (неусмерени повезан граф) и $v$ (чвор графа $G$ ).

Излаз: Зависи од примене.

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

Пут од корена $r$ БФС стабла до произвољног чвора $w$ кроз БФС стабло најкраћи је пут од $r$ до $w$ у графу $G$ .^[2]

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

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

Spoljašnje veze[уреди | уреди извор]

[#1-1] а ^б Стевановић, Драган; Ћирић 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= (помоћ)

[1]

[2]