Determinante der Distanzmatrix eines Baumes

Neue Frage »

12.11.2012, 11:55	Heinzelmann3	Auf diesen Beitrag antworten »
Determinante der Distanzmatrix eines Baumes Hallo Leute, es geht um Graphentheorie. Gegeben sei ein Baum T auf n Knoten, die wir mit 1,...,n bezeichnen. $\begin{eqnarray} D=(d_{ij}) \end{eqnarray}$ sei die Distanzmatrix, also $\begin{eqnarray} d_{ij} \end{eqnarray}$ gibt die Anzahl der Kanten auf dem Weg von Knoten i zu Knoten j an. Zu beweisen ist nun, dass $\begin{eqnarray} det(D)=(-1)^{n-1}(n-1)2^{n-2} \end{eqnarray}$ . Ich habe leider noch nicht allzu viel dazu herausgefunden. Es handelt sich bei D jedenfalls um eine symmetrische Matrix mit Nullen auf der Hauptdiagonale... Gibt es für diesen Fall einen speziellen Trick zur Determinantenberechnung oder so? Oder muss man anders rangehen? Danke schonmal und viele Grüße, HM3
12.11.2012, 18:07	Heinzelmann3	Auf diesen Beitrag antworten »
RE: Determinante der Distanzmatrix eines Baumes Kann mir denn keiner weiterhelfen? Oder bin ich im falschen Raum?
12.11.2012, 18:11	Leopold	Auf diesen Beitrag antworten »
Kannst du die Matrix $\begin{eqnarray} D \end{eqnarray}$ konkret angeben? Denn ich fürchte, daß sich nicht allzu viel Experten in Graphentheorie hier tummeln.
12.11.2012, 18:23	Heinzelmann3	Auf diesen Beitrag antworten »
konkret angeben? Mit Zahlenwerten? Das sieht für jeden Baum bisschen anders aus... gilt ja für einen beliebige Baum.
12.11.2012, 18:24	RavenOnJ	Auf diesen Beitrag antworten »
soll das für einen beliebigen Baum gelten oder nur für einen binären? Gruß Peter
12.11.2012, 18:25	Leopold	Auf diesen Beitrag antworten »
Dann müßte es ja auch für jeden Baum eine neue Matrix geben. Das scheint hier aber nicht so zu sein. Also muß die Matrix ja eine spezielle Struktur besitzen.
Anzeige

12.11.2012, 18:45	Heinzelmann3	Auf diesen Beitrag antworten »
In der Aufgabenstellung ist von einem beliebigen Baum die Rede... und ja, es gibt für jeden Baum einen neue Matrix, aber das steht doch nicht im Widerspruch zur Behauptung? Unter der Aufgabenstellung steht noch der Hinweis, dass es bemerkenswert sei, dass die Determinante nur von n abhängt!
13.11.2012, 15:30	vq	Auf diesen Beitrag antworten »
Paper Das war ein Ergebnis von einem Paper vom Jahr 1971. Das Paper kann ich leider nicht finden..
13.11.2012, 19:51	Heinzelmann3	Auf diesen Beitrag antworten »
RE: Paper hm...schade sonst jemand ne Idee? LG
13.11.2012, 21:46	RavenOnJ	Auf diesen Beitrag antworten »
in welchem Rahmen sollst du das beweisen? Wenn darüber mal ein Paper geschrieben worden ist, dann ist das Problem offensichtlich alles andere als trivial. Ich bin bisher auf keine wirklich konstruktive Idee gekommen. Hab's mit Induktion versucht, indem ich von einem Baum der Knotenzahl n zu einem mit einem zusätzlichen Blatt übergehe. Meine Idee war, die Abstände von und zu diesem neuen Blatt ja dieselben sind wie von und zum parent + 1, dass also in der (n+1)-Matrix eine zusätzliche Spalte und Zeile auftaucht, die im wesentlichen einer schon existierenden entspricht, wobei die Einträge jeweils um 1 größer sind. Man kann in der (n+1)-Determinante dann fast alle Einträge dieser Spalte auf 1 setzen, da eine Determinante mit zwei gleichen Spalten ja = 0. Das hat mich aber bisher nicht weiter gebracht. Laplace-Entwicklung stößt auch auf Schwierigkeiten. Gruß Peter
14.11.2012, 23:10	Heinzelmann3	Auf diesen Beitrag antworten »
oh cool, danke trotzdem für deine Mühe! Es handelt sich dabei um eine Übungsaufgabe mit schlappen 5 Punkten... ich versteh es auch nicht! Das mit dem Paper kanns doch nicht sein...

Neue Frage »

Antworten »

Determinante der Distanzmatrix eines Baumes

Verwandte Themen