nicht angemeldet
Graphentheorie, Radius, Zentrum
Hallo,
wie ist das Zentrum eines Graphen definiert, wenn der Radius dieses Graphen unendlich ist? (Der Radius ist dann unendlich, wenn der Graphaus mehreren Komponenten besteht).
Bei zusammenhängenden Graphen ist das Zentrum ja die Menge aller Knoten, die die kleinste Exzentrizität besitzen, aber ist der Graph nicht zusammenhängend, heißt das dann einfach nur per Definition, dass der Graph kein Zentrum besitzt?
Markus
-
Hi
laut http://www.informatik.uni-trier.de/~naeher/Professur/PROJECTS/vogt/Thema.html
beschränkt sich die Definition des Zentrums auf zusammenhängende Graphen.
Solltest du eine andere allgemeinere Definition kennen (bitte verlinken) dann müsste der gesamte Graph bzw. Wald sein Zentrum sein, da für alle Punkte gilt das die minimale Exzentrität (= Radius) eben unendlich ist.
Frage beantwortet?
Gegenfrage: Wie kommst du darauf dass hier Leute über Graphentheorie sprechen wollen/können???
tschüss
Ashanti-
Hallo,
laut http://www.informatik.uni-trier.de/~naeher/Professur/PROJECTS/vogt/Thema.html
Frage beantwortet?
Naja, ich habe selbst schon darüber philosophiert, wie man es denn von dem logischen Standpunkt zu betrachten hat:
Das Zentrum eines Graphen ist ja die Menge aller Knoten, deren Exzentrizität gleich dem Radius ist, und eine unendliche Exzentrizität gibt es ja nicht, da jeder Knoten zu sich selbst die Distanz 0 hat. Somit ist die Exzentrizität auf jeden Fall mindestens 0.
Es verwirrt mich allerdings, dass der Radius unendlich ist bei nicht zusammenhängenden Graphen, denn per Definition heißt es ja: Der Radius eines Graphen ist das Minimum der Exzentrizitäten der Knoten, und das Minimum von 0 ist in meinen Augen 0. Somit müsste doch das Zentrum ja Null sein, und nicht nicht exisitent, da das Zentrum jene Punkte sind, deren Radius der Exzentrizität entsprechen?Gegenfrage: Wie kommst du darauf dass hier Leute über Graphentheorie sprechen wollen/können???
Ich glaube, dass hier erstens die fähigsten Leute unterwegs sind, zweitens weiß ich nicht, wo ich eine derartige Frage sonst stellen könnte, und drittens hat dieses Problem durchaus viel mit der Informatik zu tun, zb bei Algorithmen.
Markus
-
Somit müsste doch das Zentrum ja Null sein, [...]
Ich wollte natürlich sagen, dass das Zentrum dann aus den Knoten bestehen müsste, die die Exzentrizität 0 haben.
-
Hallo *Markus,
Es verwirrt mich allerdings, dass der Radius unendlich ist bei nicht zusammenhängenden Graphen, denn per Definition heißt es ja: Der Radius eines Graphen ist das Minimum der Exzentrizitäten der Knoten
Genau, und die Exzentrität eines Knotens ist die größte Entfernung zu irgend einem anderen Knoten. In einem nicht zusammenhängenden Graphen gibt es zu jedem Knoten einen Knoten, der nicht erreichbar ist, zudem die Entfernung also unendlich ist.
Der entscheidende Punkt ist eben die Definition von Exzentrität. Die wird eben durch die Maximum-Bildung über die anderen Knoten durchaus unendlich.
Grüße
Daniel
-
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 0Pro 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 0Pro 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 0Hier 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
-
Hallo *Markus,
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?
Sicher, für eine Anzahl von Knoten und ein Zentrum dürfte es sehr viele Graphen mit dem gleichen Zentrum geben. Du kannst ja beliebig Kannten da rein basteln, die nichts an den Entfernungen ändern. Das wäre also kein Gegenargument.
Diese Definition ist ja nicht willkürlich sondern kommt vom Kreis her.
Die Exzentrizität eines Punktes in einem Kreis (also nicht bloß auf der Kreislinie) ist die Entfernung zu dem Punkt, der am weitesten weg ist (Liegt irgendwo auf der Kreislinie).
Die kleinste Exzentrizität hat der Mittelpunkt. Im Falle von unendlichen Exzentrizitäten ist der Radius unendlich und damit gibt es keinen Mittelpunkt mehr oder er liegt eben überall.Beim Graphen hat man nun nicht einen Mittelpunkt, von daher fände ich es legitim, in dem Fall einfach den ganzen Graphen als Zentrum zu nehmen.
Das führt auch zu keinem Widerspruch so weit ich das sehe.
Die rechtfertigung dafür, kein Zentrum anzugeben, wäre schlicht, dass die Definition eben nicht anwendbar ist.Wofür musst Du das definieren? Wenn es irgendwie darum geht, das zu implementieren, würde ich im Falle eines nicht-zusammenhängenden Graphen nichts zurückgeben, weil sonst der Aufrufer die Fälle nicht unterscheiden kann.
Grüße
Daniel
-
Hallo,
Im Falle von unendlichen Exzentrizitäten ist der Radius unendlich und damit gibt es keinen Mittelpunkt mehr oder er liegt eben überall.
Das ist letztendlich eben die Frage.
Beim Graphen hat man nun nicht einen Mittelpunkt, von daher fände ich es legitim, in dem Fall einfach den ganzen Graphen als Zentrum zu nehmen.
» Das führt auch zu keinem Widerspruch so weit ich das sehe.
Das sehe ich auch so.
Die rechtfertigung dafür, kein Zentrum anzugeben, wäre schlicht, dass die Definition eben nicht anwendbar ist.
Anwendbar ist sie ja. Sie führt eben nur zu dem Ergebnis, dass das Zentrum überall ist, was zwar ein bisschen meiner Logik widerspricht, aber wenn es so definiert ist, dann ist es eben so, vorausgesetzt, dass die Definition nun richtig interpretiert wurde.
Wofür musst Du das definieren? Wenn es irgendwie darum geht, das zu implementieren, würde ich im Falle eines nicht-zusammenhängenden Graphen nichts zurückgeben, weil sonst der Aufrufer die Fälle nicht unterscheiden kann.
Ich muss ein Programm schreiben, dass alles bishin zu den Zusammenhangskomponenten, Blöcken, Brücken, Artikulationen, und ev. eulerschen Linien berechnet. Da wäre es äußerst ärgerlich, wenn es falsche Ergebnisse liefern würde.
Ich glaube, dass das falsch wäre, da eben die Definition sagt, dass es ein Zetrum gibt. Außerdem gibt der Aufrufer selbst den Graphen ein, wodurch er sowieso weiß, wie der Graph aussieht.Markus
-
Hi
die Frage lässt sich eindeutig beantworten, wenn du eine eindeutige Definition angibst! Was Google zurückgibt ist leider zu schwach und Zentrum gehört wohl nicht zur graphentheoretischen Allgemeinbildung (zumindest meiner)
Logik ist keine Frage des Konsens irgendwelcher Poster, Definitionen können aber variieren.
Sei also so gut und schreib hier mal die Definition auf die sich dein Auftraggeber bezieht.
Steht dort was von "Zusammenhangskomponenten" o.ä. ist Zentrum genausowenig anwendbar wie die Wurzel einer negativen Zahl.
Wird aber die Definition "unendlicher Exzentrität" eingeschlossen, dann haben wir quasi eine Erweiterung des Ergebnisraumes um "imaginäre Zahlen" (um in der Wurzel-Analogie zu bleiben)
Entscheidend sind die Definitionen, schreibe sie hier bitte akkurat auf, dann brauchen wir nicht raten.
Salam
AshantiPS: Wenn undefiniert, dann solltest du auf keinen Fall eine "leere Menge" sondern eine Fehlermeldung ähnlich "Divison durch Null" schmeißen.
-
Hallo,
Logik ist keine Frage des Konsens irgendwelcher Poster, Definitionen können aber variieren.
Warum können Definitionen variieren? In der Mathematik kann ich ja auch nicht sagen, dass jetzt Strich vor Punkt gerechnet wird. Somit gibt es m.M.n. eine eindeutige Definition.
Sei also so gut und schreib hier mal die Definition auf die sich dein Auftraggeber bezieht.
Steht dort was von "Zusammenhangskomponenten" o.ä. ist Zentrum genausowenig anwendbar wie die Wurzel einer negativen Zahl.
Natürlich sind das verschiedene Dinge. Dennoch muss das Programm all diese Dinge ausgeben:
Eingabe über graphische Adjazenzmatrix
Ausgabe: Wegmatrix, Distanzmatrix, Knotengrade, Exzentrizitäten, Radius, Durchmesser, Zentrum, Komponenten, Zusammenhangskomponenten, Brücken, Blöcke, Artikulationen, ev. eulersche Linie.
Seit einigen Tagen beiße ich mir übrigens die Zähne an einem Algorithmus aus, mithilfe dessen ich zu den Blöcken, Brücken und Artikulationen komme, und der am Papier systematisch abgearbeitet werden kann. Ihn aber in einem Programm zu realisieren ist letztendlich doch schwerer als ich dachte.P.S. Spätestens Mittwoch spät Abends kann ich genau sagen, was nun richtig ist, da ich dann wieder meinen Abteilungsvorstand treffe, und er schließlich der "Auftraggeber" ist.
Markus
-
Hallo,
Logik ist keine Frage des Konsens irgendwelcher Poster, Definitionen können aber variieren.
Warum können Definitionen variieren?
Das Beispiel mit der Wurzel reicht dir nicht? Wieso?
Ich habe schon von Mathematischen Modellen gehört wo die Division durch Null definiert ist.
In der Mathematik kann ich ja auch nicht sagen, dass jetzt Strich vor Punkt gerechnet wird. Somit gibt es m.M.n. eine eindeutige Definition.
Vielleicht nicht in der Schulmathematik, wo Pädagogen es den Kindern leicht machen wollen.
Die Mathematik an sich ist aber eine Wissenschaft die seit bald 100 Jahren nur noch Axiomatisch aufgebaut wird. Mathematische Publikationen achten peinlich genau darauf entweder alle Begriffe zu definieren oder erschöpfend Publikationen zu referenzieren wo sie definiert werden.
Die Graphentheorie ist eine neue Disziplin, und mitunter konkurieren Schulen um die eleganteste Modellierung.
(stell dir vor es ginge um die Entwicklung einer Programmiersprache)
P.S. Spätestens Mittwoch spät Abends kann ich genau sagen, was nun richtig ist, da ich dann wieder meinen Abteilungsvorstand treffe, und er schließlich der "Auftraggeber" ist.
Tja wer so einen Auftrag gibt, ohne für alle Begrifflichkeiten mind eine Referenz vorzugeben ist schon etwas peinlich...oder sie habens getan und du blamierst dich.
Tschau
Ashanti
-
-
-
Hallo *Markus,
Im Falle von unendlichen Exzentrizitäten ist der Radius unendlich und damit gibt es keinen Mittelpunkt mehr oder er liegt eben überall.
Das ist letztendlich eben die Frage.Das entscheidet sich letztenendes von der Definition von "Abstand". Darauf bauen ja alle anderen Definitionen auf.
Abstand ist die Länge des kürzesten Weges. Wenn es keinen gibt, kann man den als unendlich definieren. Tut man das, besteht das Zentrum aus allen Knoten, tut man es nicht, ist die Definition nicht Anwendbar, weil Knoten in verschiedenen Zusammenhangskomponenten eben keinen Abstand haben.
An der Stelle kann man nicht sagen, was richtig und was falsch ist. Man muss sich einfach überlegen, was man haben will.Grüße
Daniel
-
Hallo,
ok, wenn beides quasi richtig ist, mache ich mir weiter keine Sorgen mehr darüber.
Danke für eure Hilfe.Markus
-
Hi
ok, wenn beides quasi richtig ist,
du kannst dir vieles aussuchen aber es ist ganz bestimmt nicht beides "richtig", das wäre fundamental unlogisch.
Du musst dich von der Vorstellung frei machen Mathematik wäre eine Naturwissenschaft und Mathematiker entdecken gottgewollte Strukturen.
Das Gegenteil ist der Fall, es ist eine Geisteswissenschaft und alles sind Hirngespinnste.
In diesem Fall verwette ich meinen Bronstein das das Zentrum NUR auf zusammenhängende Graphen definiert ist. Will man die Definition ausweiten, so wie bei den Wurzeln negativer Zahlen, muss man "herrumspinnen" was irgendwie Sinn machen würde.
Nehmen wir die Motivation aus dem Link den ich oben angegeben habe, man will in einem Haus eine Stadt-Feuerwehr bauen die minimalen Abstand zu allen anderen Häusern hat, deswegen ermittelt man das Zentrum des zugehörigen Graphen mit den Häusern als Knoten, und kann ein beliebiges Haus aus dem Zentrum auswählen.
Im unzusammenhängenden Fall, die Stadt erstreckt sich z.B. über mehrere unzusammenhängende Inseln, hat man Interpretationsspielraum. [*]
Fall a) Man darf auch mehrere Feuerwehren bauen, dann sollte das Zentrum jeder Zusammenhangskomponente einzeln ermittelt werden und jeweils eine Feuerwehr pro Insel gebaut werden.
Fall b) Man darf nur eine Feuerwehr bauen, dann besteht das Zentrum logischerweise aus allen Häusern, denn egal wo ich die Feuerwehr beheimate, verbessern kann man den Standort nicht, es gibt ja immer unereichbare Häuser. (wozu dann übehaupt eine Feuerwehr zu bauen ist ne andere Frage)
Fall c) man will trotzdem möglichst viele Häuser erreichen können....
Fall d) ... denk dir was aus...
Nun was beabsichtigt dein Arbeitgeber? Wieviele Feuerwehren will er bauen, was hat er dir für Bücher, Skripte Definitionen, oder auch nur Motivationen in die Hand gedrückt???
Wir wissen es nicht und du verrätst es uns auch nicht und wahrscheinlich hat dein Arbeitgeber wie die meisten Kunden auch keine Ahnung was er will.
Aber nochmal: es ist nicht "quasi egal"!!!
Es hängt davon ab was erreicht werden soll. Und davon hängt die Definition ab. Gott hat dazu aber keine feste Meinung.
Mit 99%iger Sicherheit wird dein gespräch mit der Abteilungsleitung zu folgender Antwort führen:
Wenn das Zentrum eines unzusammenhängenden Graphen ermittelt werden soll, muss dein Programm eine entsprechende Fehlermeldung zurückgeben.
Salam
Ashanti[*] Istambul gilt leider nicht, es gibt Straßen um das Schwarze Meer herum. :)
-
-
-
-
-
-
-
-