Razdalja (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m robot Dodajanje: es, fa, fr, he, pl |
m + |
||
Vrstica 1:
'''
Množica točk ([[neusmerjeni graf|neusmerjenega grafa]]) in funkcija razdalje tvorita [[metrični prostor]], [[če in samo če]] je graf [[povezani graf|povezan]].
Vrstica 7:
Obstaja več drugih meril v smislu razdalje:
'''Izsrednost''' ε točke ''v'' je največja geodetska razdalja med ''v'' in katerokoli drugo točko. Lahko si jo mislimo 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 najprej poiščemo 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]].
== Glej tudi ==
* [[uporovna razdalja]]
* [[centralnost]]
{{math-stub}}
| |||