Die Metrik des Königs Robert

Im Reich des Königs Robert gibt es mehrere Firmen, die Botendienste anbieten. Die Firmen bieten verschiedene Tarife an. Robert hat drei Bedingungen aufgestellt, denen alle Tarife genügen müssen.
Bezeichnen A, B, C Orte in Roberts Reich und d(A,B) den Preis, um eine Botschaft von A nach B zu bringen, so lauten Roberts Bedingungen:
  1. d(A,A) = 0 für jeden Ort A (ohne Bewegung der Boten kein Geld)
  2. d(A,B) = d(B,A)>0 für B≠A (jeder Weg wird bezahlt; gleiche Kosten für Hin-und Rückweg)
  3. d(A,C) ≤ d(A,B) + d(B,C) (Der direkte Weg von A nach C darf nicht mehr kosten als ein Weg, der von A über eine Station B nach C führt)
Bezahlt wird in der Währungseinheit Caramba ( Ca). Ein Ca ist viel wert, und so bietet eine Firma den folgenden Tarif D (A,B) an, um einen bestehenden Tarif d (A,B) zu unterbieten.
D(A,B) = min(d(A,B); 1). In Worten: D(A,B) ist das Minimum der beiden Zahlen d(A,B) und 1. Das bedeutet, dass der Tarif d(A,B) "gedeckelt" werden soll. D(A,B) ist so lange gleich d(A,B), wie d(A,B)< 1 Ca. Erreicht oder übersteigt d(A,B) 1Ca, so ist D(A,B) = 1 Ca.

Aber ist der Tarif D zulässig, erfüllt er König Roberts Bedingungen?

Wir zeigen, dass der Tarif D König Roberts Bedingungen erfüllt.

1) D(A,A) = min(d(A,A); 1) = min ( 0; 1) = 0

2) D(A,B) = min(d(A,B);1) = min(d(B,A);1) = D(B,A)

3) D(A,C) = min( d(A,C);1) ≤ min(d(A,B)+d(B,C);1) ≤ min(d(A,B);1)+min(d(B,C);1) =

= D(A,B) + D(B,C)

Wir müssen die beiden in 3) stehenden Ungleichungen beweisen.

Seien x ≥ 0, y≥ 0

Zur ersten der beiden Ungleichungen. Zu zeigen ist: min(x;1) ≤ min(y;1) , wenn y≥x

Im Fall x≥1 ist min(x;1) = 1; wegen y≥x ist y≥1 und min(y;1) = 1.

Im Fall x <1 ist min(x;1) =x. Nun ist min(y;1) =1 >x =min(x;1) oder min(y;1) = y ≥x =min(x;1).

Zur zweiten der beiden Ungleichungen. Wir zeigen: min(x+y;1) ≤ min(x;1) + min(y;1)

Im Fall x+ y ≤1 ist min(x+y;1) = x + y = min(x;1) + min(y;1)

Im Fall x+y >1 ist min(x+y;1) = 1

Falls dann x,y beide kleiner als 1 sind gilt: min(x+y;1)=1 < x+ y = min(x;1) + min(y;1)

Falls dann wenigstens eine der beiden Zahlen x, y ( z.B. x) größer als 1 ist, gilt:

min(x+y;1) =1 ≤ 1 + min(y ;1) = min(x ;1) + min(y ;1)