Aufspannende Bäume < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich würde gerne wissen,wie ich zeigen könnte, dass ein geweichteter Graph G (= [mm] K_{n}) [/mm] mit der Kostenfunktion w(ij) = i + j genau einen minimalen aufspannenden Baum enthält.
Da es klar ist, dass Kruskalls- oder Primsalgorithmus mit einem Graph G als Eingabe einen minimalen aufspannenden Baum ausgeben, hätte ich schon eine halbe Übung schon bewiesen aber anders ist die Eindutigkeit der Lösung.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Meine Idee ist zu beweisen, dass die Kostenfunktion nur ein Minimum hat.
Habt ihr andere Ideeen?
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:35 So 16.07.2006 | | Autor: | felixf |
Hallo branwijck!
> ich würde gerne wissen,wie ich zeigen könnte, dass ein
> geweichteter Graph G (= [mm]K_{n})[/mm] mit der Kostenfunktion w(ij)
> = i + j genau einen minimalen aufspannenden Baum enthält.
Die Ecken sind also $1, [mm] \dots, [/mm] n$, und zwischen je zwei Ecken gibts eine Kante? Der minimale aufspannende Baum ist wohl der Untergraph, der gerade alle Ecken hat, die Ecke #1 mit einer beliebigen anderen Ecke verbinden. Die Gewichtung ist dann [mm] $\sum_{i=2}^n w_{1i} [/mm] = [mm] \sum_{i=2}^n [/mm] (1 + i) = (n-2) + [mm] \sum_{i=1}^n [/mm] i = (n-2) + [mm] \frac{n (n + 1)}{2}$.
[/mm]
Um zu zeigen, dass dieser minimal ist: Nimm an, du hast einen anderen. Dieser hat ebenfalls $n-1$ Ecken, etwa [mm] $\{ i_k, j_k \}_{k=1,\dots,n-1}$. [/mm] Die Gewichtung des Baums ist also [mm] $\sum_{k=1}^{n-1} (i_k [/mm] + [mm] j_k)$. [/mm] Nun muss jeder Knoten als ein [mm] $i_k$ [/mm] oder [mm] $j_k$ [/mm] vorkommen, und das andere Ende der Ecke hat einen Knoten [mm] $\ge [/mm] 1$. Also ist [mm] $\sum_{k=1}^{n-1} (i_k [/mm] + [mm] j_k) \ge \sum_{i=1}^n [/mm] i + (n - 2)$. Also ist unserer Teilgraph oben schonmal kleinstmoeglich (von der Gewichtung her).
Angenommen, es sei [mm] $\sum_{k=1}^{n-1} (i_k [/mm] + [mm] j_k) [/mm] = [mm] \sum_{i=1}^n [/mm] i + (n - 2)$. Dann kommt jeder Knoten $> 1$ genau einmal vor, und der Knoten $1$ kommt $n-1$ mal vor. Aber das bedeutet gerade, dass der Baum der obige sein muss, da er ansonsten den Graphen nicht aufspannt (das musst du noch ein wenig ausfuehren).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:28 Di 18.07.2006 | | Autor: | branwijck |
Danke, es war eine große Hilfe.
|
|
|
|
