Изворни код странице Rastojanje (teorija grafova)

{{Neprovereni seminarski}}
U [[matematika|matematičkoj]] grani koja se zove [[teorija grafova]], '''rastojanje''' između dva čvora u [[graf]]u je broj grana u najkraćem putu koji ih povezuje.<ref name="#1">{{cite web |url=http://www.scribd.com/doc/126035863/Diskretna-matematika-Osnove-kombinatorike-i-teorije-grafova#scribd |title=Osnove kombinatorike i teorije grafova |accessdate=11-05-2015 |last=Stevanović |first=Dragan |author2=Ćirić M. |display-authors=etal |date=jul 2007 |archive-date=18. 05. 2015 |archive-url=https://web.archive.org/web/20150518150909/https://www.scribd.com/doc/126035863/Diskretna-matematika-Osnove-kombinatorike-i-teorije-grafova#scribd |url-status= }}</ref> 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 [[Komponente povezanosti (teorija grafova)|komponentima povezanosti]], smatra se da je njihovo rastojanje beskonačno.

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


== Srodni pojmovi ==
=== Metrika grafa ===
Prema definiciji <math>d(u,v)</math> predstavlja funkciju <math>d\colon V \times V \to R</math>, koja se naziva '''funkcija rastojanja''', odnosno ''' metrika''' grafa <math>G</math>. Metrika grafa <math>G</math> ima sledeće osobine:
  1)  <math>d(u,v) \geq 0 </math> pri cemu je <math> d(u,v) = 0 </math> ako i samo ako je <math>u = v</math> (nenegativnost rastojanja);
  2)  <math>d(u,v) = d(v,u) </math> za svaki par čvorova <math>u,v \in V </math> (simetričnost rastojanja);
  3)  <math>d(u,w) \leq d(u,v)+ d(v,w) </math> za svaka tri čvora <math>u,v,w \in V </math> (nejednakost trougla);
  4)  <math>d(u,v) </math> je nenegativni ceo broj za svaki par čvorova <math>u,v \in V </math>;
  5)  ako je <math>d(u,w) \geq 1 </math> tada postoji čvor  <math>v</math>, različit i od  <math>u</math> i od  <math>w</math>, takav da važi <math>d(u,w) = d(u,v)+ d(v,w) </math>. 

'''Ekscentricitet''' čvora <math>u</math>, u oznaci <math>ecc(u)</math>, je najveće rastojanje od čvora <math>u</math> do svih ostalih čvorova, tj. <math> ecc(u)= \max_{v \in V} d(u,v) </math>.

'''Dijametar''' grafa, u oznaci <math>D(G)</math>, je najveći ekscentricitet, <math> D(G)= \max_{u \in V} ecc(u) </math>.

'''Radijus''' grafa, u oznaci <math>r(G)</math>, je najmanji ekscentricitet, <math> r(G)= \min_{u \in V} ecc(u) </math>.

'''Centar''' grafa <math>G</math> čine svi čvorovi čiji je ekscentricitet jednak radijusu grafa, analogno tome, '''periferiju''' grafa <math>G</math> čine svi čvorovi čiji je ekscentricitet jednak dijametru grafa.<ref name="#1"/>

== BFS algoritam za nalaženje najkraćeg puta ==
'''Ulaz:''' <math>G = (V,E)</math>(neusmereni povezan graf) i <math>v</math> (čvor grafa <math>G</math>).

'''Izlaz:''' Zavisi od primene.

 '''begin'''
   označi <math>v</math>;
   upiši <math>v</math> u listu; {FIFO lista, privi unutra - prvi napolje}
   '''while''' lista je neprazna '''do'''
     skini privi čvor <math>w</math> sa liste;
     izvrši ulaznu obradu na <math>w</math>; {ulazna obrada zavisi od primene BFS}
     '''for''' sve grane <math>(w,x)</math> za koje <math>x</math> nije označen '''do'''
       označi <math>x</math>;
       dodaj <math>(w,x)</math> u stablo <math>T</math>;
       upiši <math>x</math> u listu;
 '''end'''
Put od korena <math>r</math> '''BFS''' stabla do proizvoljnog čvora <math>w</math> kroz '''BFS''' stablo najkraći je put od <math>r</math> do <math>w</math> u grafu <math>G</math>.<ref>
{{cite web |url=http://poincare.matf.bg.ac.rs/~ezivkovm//nastava/algoritmi.pdf |title=Algoritmi |accessdate= 11-05-2015 |last=Živković|first=Miodrag}}
</ref>
 
== Vidi još ==
* [[Teorija grafova]]
* [[Pretraga u širinu]]

== Референце ==
{{reflist}}

== Spoljašnje veze ==
* {{cite web | url=https://en.wikipedia.org/wiki/Distance_(graph_theory)| title= Distance (graph theory) - Engleska Wikipedija}}
* {{cite web | url=https://en.wikipedia.org/wiki/Quantum_graph#Metric_graphs| title= Metric graph - Engleska Wikipedija}}
* {{cite web | url=https://en.wikipedia.org/wiki/Distance_matrix| title= Distance matrix - Engleska Wikipedija}}

{{normativna kontrola}}

[[Категорија:Теорија графова]]
[[Категорија:Рачунарски проблеми у теорији графова]]