nicht angemeldet
Hallo,
Der entscheidende Punkt ist eben die Definition von Exzentrität. Die wird eben durch die Maximum-Bildung über die anderen Knoten durchaus unendlich.
Angenommen wir haben einen Graphen mit 3 Knoten ohne Kanten, dann würde die Distanzmatrix hierzu so aussehen (u für unendlich).
0 u u
u 0 u
u u 0
Pro Zeile würde die Exzentrizität unendlich sein. Die Minimum-Exzentrizität wäre also auch unendlich.
Laut Definition ist das Zentrum jene Knotenmenge, bei der die kleinsten Exzentrizitäten vorkommen, also "unendlich", da es die einzig vorkommende Exzentrizität ist, was wiederum bedeutet, dass das Zentrum nun alle 3 Knoten sind, da bei allen Knoten "unendlich" vorkommt, und doch nicht, dass kein Zentrum exisitert?
Anderes Beispiel:
Graph mit 3 Knoten, wobei Knoten 1 mit 2 mit einer Kante verbunden ist. Die Distanzmatrix sähe hierzu so aus:
0 1 u
1 0 u
u u 0
Pro Zeile ist die Exzentrizität wieder unendlich, denn unendlich ist ja "größer" als 1.
Somit würde das Zentrum wieder aus allen 3 Knoten bestehen. Kann das stimmen?
Wäre jeder Knoten mit jedem verbunden, würde die Distanzmatrix so aussehen:
0 1 1
1 0 1
1 1 0
Hier würde das Zentrum wieder aus allen 3 Knoten bestehen. Hier weiß ich aber, dass diese Definition stimmt. Bei den oberen Zweien bin ich mir aber nicht sicher. Drei verschiedene Graphen und das selbe Zentrum?
Markus
