From Wikipedia, the free encyclopedia
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]
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.