wolti
12-12-2002, 02:26
Für eine Metrik müssen ja folgende Sachen gelten.
1) d(x,y) >= 0, d(x,y) = 0 <=> x=y
2) d(x,y) = d(y,x)
3) d(x,z) <= d(x,y) + d(y,z)
Die Beweise 1 und 2 sind trivial.. Haben wir in der Vorlesung auch beim Baron gemacht. Beweis 3 ist komplizierter und den habe ich wie folgt angesetzt.
Beweis 3:
x= <x1, ..., xn>
y= <y1, ..., yn>
z= <z1, ..., zn>
Zu zeigen ist.
d(x,z) <= d(x,y) + d(y,z)
mit d(x,z) = max_{1 <=i <= n} di(xi,zi)
mit d(x,y) = max_{1 <=i <= n} di(xi,yi)
mit d(y,z) = max_{1 <=i <= n} di(yi,zi)
WIr schreiben an:
max_{1 <=i <= n} di(xi,zi) <= max_{1 <=i <= n} di(xi,yi) + max_{1 <=i <= n} di(yi,zi).
Ich nehme nun ohne Einschränkung an, dass der Index j ein Maximum für dj(xj, zj) liefern würde. Ist sicherlich richtig, da j ja noch alles sein kann.
dj(xj, zj) <= max_{1 <=i <= n} di(xi,yi) + max_{1 <=i <= n} di(yi,zi).
Wir untersuchen nun 2 Fälle.
1) Die Terme max_{1 <=i <= n} di(xi,yi) und max_{1 <=i <= n} di(yi,zi) liefern auch für den Index j ein maximum. Dann gilt.
dj(xj, zj) <= dj(xj, yj) + dj(yj, zj). Dies stimmt, da wir ja in dj eine Metrik auf Xj definiert haben, diese also die Dreiecksungleich erfüllt.
2) Die Terme liefern für einen anderen Index ein Maxium.
dj(xj, zj) <= dr(xr, yr) + ds(ys, zs)
Es gilt nun aber auf jedenfall, dass dr(xr, yr) > als dj(xj, yj) ist, da er sonst ja bei der Maximum Funktion nicht aufgetaucht wäre. Des weiteren gilt für ds(ys, zs), dass dieser auch größer als dj(yj, zj) ist, da er auch sonst nicht aufgetaucht wäre.
dj(xj, zj) <= (dr(xr, yr), wobei dieser Ausdruck größer ist als dj(xj, yj)) + (
ds(ys, zs) , wobei dieser Ausdruck größer ist als dj(yj, zj)
D.h. Die Gleichung bleibt also auf jedenfall richtig. Sie wird nur noch "WAHRER"
Grüße,
Wolti
1) d(x,y) >= 0, d(x,y) = 0 <=> x=y
2) d(x,y) = d(y,x)
3) d(x,z) <= d(x,y) + d(y,z)
Die Beweise 1 und 2 sind trivial.. Haben wir in der Vorlesung auch beim Baron gemacht. Beweis 3 ist komplizierter und den habe ich wie folgt angesetzt.
Beweis 3:
x= <x1, ..., xn>
y= <y1, ..., yn>
z= <z1, ..., zn>
Zu zeigen ist.
d(x,z) <= d(x,y) + d(y,z)
mit d(x,z) = max_{1 <=i <= n} di(xi,zi)
mit d(x,y) = max_{1 <=i <= n} di(xi,yi)
mit d(y,z) = max_{1 <=i <= n} di(yi,zi)
WIr schreiben an:
max_{1 <=i <= n} di(xi,zi) <= max_{1 <=i <= n} di(xi,yi) + max_{1 <=i <= n} di(yi,zi).
Ich nehme nun ohne Einschränkung an, dass der Index j ein Maximum für dj(xj, zj) liefern würde. Ist sicherlich richtig, da j ja noch alles sein kann.
dj(xj, zj) <= max_{1 <=i <= n} di(xi,yi) + max_{1 <=i <= n} di(yi,zi).
Wir untersuchen nun 2 Fälle.
1) Die Terme max_{1 <=i <= n} di(xi,yi) und max_{1 <=i <= n} di(yi,zi) liefern auch für den Index j ein maximum. Dann gilt.
dj(xj, zj) <= dj(xj, yj) + dj(yj, zj). Dies stimmt, da wir ja in dj eine Metrik auf Xj definiert haben, diese also die Dreiecksungleich erfüllt.
2) Die Terme liefern für einen anderen Index ein Maxium.
dj(xj, zj) <= dr(xr, yr) + ds(ys, zs)
Es gilt nun aber auf jedenfall, dass dr(xr, yr) > als dj(xj, yj) ist, da er sonst ja bei der Maximum Funktion nicht aufgetaucht wäre. Des weiteren gilt für ds(ys, zs), dass dieser auch größer als dj(yj, zj) ist, da er auch sonst nicht aufgetaucht wäre.
dj(xj, zj) <= (dr(xr, yr), wobei dieser Ausdruck größer ist als dj(xj, yj)) + (
ds(ys, zs) , wobei dieser Ausdruck größer ist als dj(yj, zj)
D.h. Die Gleichung bleibt also auf jedenfall richtig. Sie wird nur noch "WAHRER"
Grüße,
Wolti