Ogled vira Razdalja (teorija grafov)

'''Razdálja''' med dvema [[točka (teorija grafov)|točkama]] v [[graf (matematika)|grafu]] je v [[teorija grafov|teoriji grafov]] število [[povezava (teorija grafov)|povezav]] v [[problem najkrajše poti|najkrajši poti]], ki ju povezuje. Imenuje se tudi geodetska razdalja, saj predstavlja [[dolžina|dolžino]] [[geodetka|geodetke]] grafa med tema dvema [[točka (teorija grafov)|točkama]].<ref>{{sktxt|Bouttier|Di Francesco|Guitter|2003}}.</ref>{{efn|Z razdaljo je mišljena geodetska razdalja vzdolž grafa, namreč dolžina katerekoli najkrajše poti med dvema danima površinama.}} Če med dvema točkama ne obstaja povezovalna [[pot (teorija grafov)|pot]], oziroma, če točki pripadata različnima [[povezana komponenta (teorija grafov)|povezanima komponentama]], je po dogovoru razdalja definirana [[neskončnost|neskončna]].

Množica točk ([[neusmerjeni graf|neusmerjenega grafa]]) in funkcija razdalje tvorita [[metrični prostor]], [[če in samo če]] je graf [[povezani graf|povezan]].

[[Metrika]], definirana na množici točk v smislu razdalj grafa, definiranega na množici, se imenuje metrika grafa.

== Značilnosti grafov povezane z razdaljo ==
[[slika:Cuboctahedron graph 001.svg|thumb|right|200px|[[Kubooktaedrski graf]] ima največjo razdaljo (premer) 3]]

V smislu razdalje obstaja več drugih meril, oziroma [[invarianta grafa|invariant grafov]]:
* '''izsrednost''' ε točke ''v'' je največja geodetska razdalja med ''v'' in katerokoli drugo točko. Lahko se jo misli kot podatek kako daleč je točka od najbolj oddaljene točke v grafu.
* '''polmer''' grafa je najmanjša izsrednost poljubne točke.
* '''premer''' grafa je največja izsrednost poljubne točke v grafu. To pomeni največjo razdaljo med dvema poljubnima paroma točk. Za iskanje premera grafa se najprej poišče najkrajšo pot med vsakim parom točk. Največja dolžina od vseh teh poti je premer grafa.
* '''obrobna točka''' v grafu s premerom ''d'' je tista točka, ki je za razdaljo ''d'' oddaljena od druge točke, oziroma točka, ki doseže premer grafa.
* '''psevdoobrobna točka''' ''v'' ima značilnost, da za vsako točko ''u'', če je ''v'' oddaljena od ''u'' za kolikor je mogoče, velja, da je oddaljena od ''v'' za kolikor je mogoče. Formalno, če je razdalja od ''u'' do ''v'' enaka izsrednosti ''u'', je enaka izsrednosti ''v''.

[[Matrika]], ki podaja razdalje vseh točk grafa, je [[matrika razdalj]]. 
<!-- Matrika razdalj grafa na sliki je:
: <math> \begin{bmatrix}
0 & 1 & 2 & 1 & 1 & 2 & 2 & 3 & 2 & 2 & 1 & 2 \\
1 & 0 & 1 & 2 & 2 & 3 & 2 & 2 & 1 & 2 & 1 & 2 \\
2 & 1 & 0 & 1 & 2 & 2 & 1 & 2 & 1 & 2 & 2 & 3 \\
1 & 2 & 1 & 0 & 1 & 2 & 1 & 2 & 2 & 3 & 2 & 2 \\
1 & 2 & 2 & 1 & 0 & 1 & 2 & 2 & 3 & 2 & 2 & 1 \\
2 & 3 & 2 & 2 & 1 & 0 & 1 & 1 & 2 & 2 & 2 & 1 \\
2 & 2 & 1 & 1 & 2 & 1 & 0 & 1 & 2 & 2 & 3 & 2 \\
3 & 2 & 2 & 2 & 2 & 1 & 1 & 0 & 1 & 1 & 2 & 2 \\
2 & 1 & 1 & 2 & 3 & 2 & 2 & 1 & 0 & 1 & 2 & 2 \\
2 & 2 & 2 & 3 & 2 & 2 & 2 & 1 & 1 & 0 & 1 & 1 \\
1 & 1 & 2 & 2 & 2 & 2 & 3 & 2 & 2 & 1 & 0 & 1 \\
2 & 2 & 3 & 2 & 1 & 1 & 2 & 2 & 2 & 1 & 1 & 0 \end{bmatrix} </math> -->

== Algoritem za iskanje psevdoobrobnih točk ==

Velikokrat [[algoritem|algoritmi]] z [[redka matrika|redkimi matrikami]] potrebujejo začetno točko z veliko izsrednostjo. Obrobna točka bi bila idealna, vendar jo je običajno težko izračunati. V večini primerov se lahko uporabi psevdoobrobna točka. Lahko se določi z naslednjim algoritmom:

# Izberi točko <math>u</math>.
# Med vsemi točkami, ki so od <math>u</math> oddaljene kolikor je mogoče, na bo <math>v</math> z najmanjšo [[stopnja grafa|stopnjo]].
# Če je <math>\epsilon(v) > \epsilon(u)</math>, potem priredi <math>u=v</math> in nadaljuj s korakom 2, drugače je <math>v</math> psevdoobrobna točka.

== Glej tudi ==

* [[uporovna razdalja]]
* [[centralnost]]

== Opombe ==

{{notelist}}

== Sklici ==

{{sklici|1}}

== Viri ==

* {{citat|last1= Bouttier|first1= Jérémie|last2= Di Francesco|first2= P.|last3= Guitter|first3= E.|date= julij 2003|title= Geodesic distance in planar graphs|journal= [[Nuclear Physics B|Nucl. Phys. B]]|volume= 663|issue= 3|pages= 535–567|url= http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVC-48KW72R-1&_user=3742306&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061256&_version=1&_urlVersion=0&_userid=3742306&md5=86dd4de63373a7e72d23d16840947661|accessdate= 2008-04-23|doi= 10.1016/S0550-3213(03)00355-9}}

== Zunanje povezave ==

* {{MathWorld|urlname=GraphDistance|title=Graph Distance}}
* [http://planetmath.org/encyclopedia/RadiusOfAGraph.html distance (in a graph)] {{Webarchive|url=https://web.archive.org/web/20100628052044/http://planetmath.org/encyclopedia/RadiusOfAGraph.html |date=2010-06-28 }} na [[PlanetMath]] {{ikona en}}

{{math-stub}}

[[Kategorija:Teorija grafov]]