Razdalja (teorija grafov)
Razdálja med dvema točkama v grafu je v teoriji grafov število povezav v najkrajši poti, ki ju povezuje. Imenuje se tudi geodetska razdalja, saj predstavlja dolžino geodetke grafa med tema dvema točkama. Če med dvema točkama ne obstaja povezovalna pot, oziroma, če točki pripadata različnima povezanima komponentama, je po dogovoru razdalja definirana neskončna.

Množica točk (neusmerjenega grafa) in funkcija razdalje tvorita metrični prostor, če in samo če je 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 

V smislu razdalje obstaja več drugih meril, oziroma 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.

Algoritem za iskanje psevdoobrobnih točk 

Velikokrat algoritmi z 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 .
 Med vsemi točkami, ki so od  oddaljene kolikor je mogoče, na bo  z najmanjšo stopnjo.
 Če je , potem priredi  in nadaljuj s korakom 2, drugače je  psevdoobrobna točka.

Glej tudi 

 uporovna razdalja
 centralnost

Opombe

Sklici

Viri

Zunanje povezave 

 
 distance (in a graph)  na PlanetMath 

Teorija grafov
Razdálja med dvema točkama v grafu je v teoriji grafov število povezav v najkrajši poti , ki ju povezuje . Imenuje se tudi geodetska razdalja , saj predstavlja dolžino geodetke grafa med tema dvema točkama . Če med dvema točkama ne obstaja povezovalna pot , oziroma , če točki pripadata različnima povezanima komponentama , je po dogovoru razdalja definirana neskončna . Množica točk ( neusmerjenega grafa ) in funkcija razdalje tvorita metrični prostor , če in samo če je 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 V smislu razdalje obstaja več drugih meril , oziroma 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 . Algoritem za iskanje psevdoobrobnih točk Velikokrat algoritmi z 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 \ . Med vsemi točkami , ki so od oddaljene kolikor je mogoče , na bo z najmanjšo stopnjo . Če je , potem priredi in nadaljuj s korakom drugače je psevdoobrobna točka . Glej tudi uporovna razdalja centralnost Opombe Sklici Viri Zunanje povezave distance ( in a graph ) na PlanetMath Teorija grafov