WisFaq!

Grafentheorie

Zij D = (V, A) een sterk samenhangende gerichte graaf. Zij d-(u, v) de lengte van een kortste gerichte pad van u naar v. Voldoet d- aan de driehoeksongelijkheid? Zo ja, geef een bewijs. Zo nee, geef een tegenvoorbeeld.

Bob
27-5-2012

Antwoord

Neem een pad van kortste lengte van $u$ naar $v$ en eentje van $v$ naar $w$; dat geeft een gericht pad van $u$ naar $w$ van lengte $d(u,v)+d(v,w)$. Dus de lengte van het kortste pad van $u$ naar $w$ is ...

kphart
28-5-2012