Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


2. Základní pojmy / Vzdálenost / metrika

Ohodnocení hran

Již v úvodu k teorii grafů jsme si ukázali, že hrany k sobě mohou mít přiřazené číslo, které si lze představit jako vzdálenost mezi městy nebo např. cenu, kterou musíme zaplatit za průchod hranou. Říkáme, že graf má ohodnocené hrany.

Příklad: vzdálenosti měst v grafu
Obr. č. 2.28 - Znázornění vzdáleností mezi městy pomocí grafu

Definice ohodnocení

Funkci, která k hranám přiřadí čísla (budeme pro jednoduchost pracovat s kladnými reálnými čísly) nazveme ohodnocením hran a označíme ji w.

w: E(G) → (0, +nekonečno)

Grafová vzdálenost / metrika

Úvod

Pokud máme ohodnocené hrany, jsme schopni říct, jaká je vzdálenost mezi každými dvěma městy (reprezentovanými vrcholy). (Musíme se ovšem umět z jakéhokoliv města dostat do jiného (např. cestou přes nějaké třetí) - graf musí být souvislý.) Funkci, která nám dosadí k vrcholům nejkratší vzdálenosti, nazveme metrika.

Definice vzdálenosti v grafu

Nechť G = (V,E) je souvislý graf. Pro vrcholy v, v' definujme číslo dG(v,v') jako délku nejkratší cesty z v do v' v grafu G. Číslo dG(v,v') se nazývá vzdálenost vrcholů v a v' v grafu G.

Vlastnosti metriky

Funkce dG: V × V → R0+, kterou nazýváme metrika grafu G, má následující vlastnosti:

  • dG(v,v') je větší nebo rovno 0 pro každou dvojici v, v'
  • dG(v,v') = 0 právě tehdy, když v = v' pro každou dvojici v, v'
  • dG(v,v') = dG(v',v) pro každou dvojici v, v'
  • dG(v,v'') je menší nebo rovno dG(v,v') + dG(v',v'') pro každou trojici v, v', v''

Poslední vlastnost je tzv. trojúhelníková nerovnost - říká nám, že jsme v grafu získali vždy nejkratší vzdálenosti - pokud bychom se pokusili jít z města (vrcholu) v do v'' přes v', bude cesta stejně dlouhá nebo delší (→ v tabulce metriky známe nejkratší cesty).

Příklad metriky

Pro ukázkový graf (Obr. č. 25) by výsledek metriky vypadal následovně:

-MostKladnoPrahaKolín
Most06396157
Kladno63033102
Praha9633069
Kolín157102690

Poznámka: Všimněte si, že grafová vzdálenost vyšla menší než standardní (přímá) vzdálenost - algoritmus pro hledání nejkratší cesty sám správně spočítal, že např. cesta z Kladna do Kolína nemusí měřit 111km, ale 102km (33+69), pokud by cesta vedla přes Prahu.

Více informací o hledání nejkratší cesty v kapitole Vybrané problémy.


Úvod

Základní pojmy

Vybrané problémy

Procvičování