Problem des optimalen Netzes < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:29 Mo 29.05.2006 | | Autor: | Jupiter |
Hallo!
Ich bin gerade dabei ein Referat vorzubereiten. In dem Referat geht es um das "Problem des optimalen Netzes". Beim Durcharbeiten eines Textes bin ich dabei auf eine Zeile gestoßen, die ich nicht nachvollziehen kann. Vielleicht kann mir hierzu einer helfen. Da ich bis jetzt auch kein Hintergrundwissen durch eine Graphentheorie-Vorlesung habe, wäre ich euch sehr dankbar, wenn mir einer von euch bei dieser Zeile helfen könnte.
Hier ein zusammengefasster Ausschnitt des Textes:
Von Jakob Steiner stammt das Problem, n in der Ebene vorgegebene Punkte (Ecken) durch ein optimales Netz zu verbinden, dh. zu ermöglichen, dass jeder Punkt mit jedem Punkt durch einen Linienzug verbunden ist und dass die Gesamtlänge der Linien minimal ist. Ein solches Netz besteht aus Verbindungsstrecken (Kanten). In der Graphentheorie nennt man ein solches Netz einen Baum.
Für Bäume gilt, dass zwischen der Zahl e der Ecken und der Zahl k der Kanten die Beziehung e=k+1 besteht.
Die Anzahl der an einer Ecke ansetzenden (mit ihr inzidierenden) Kanten heißt Ordnung der Ecke.
Sei [mm] n_i [/mm] die Anzahl der Ecken mit der Ordnung i. Dann gilt
[mm] e=\summe_{i} n_i [/mm] und [mm] 2k=\summe_{i} i*n_i
[/mm]
Die erste Gleichung ist mir dabei klar, aber bei der zweiten habe ich den Tipp bekommen, dass dies aus zwei unterschiedlichen Zählungen der Inzidenzen Kante-Ecke folgt. Kann mir jemand von euch diese Gleichung genauer erklären und mir sagen, wie sie zustande kommt?
Gruß, Jupiter
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Tag,
[mm] n_i [/mm] ist also in deiner Notation die Anzahl der Knoten mit i inzidenten Kanten. In der zweiten Summe zählst Du also für
jeden solchen Knoten jede der inzidenten Kanten, also jede Kante genau zweimal (für ihre beiden Endknoten).
Gruss,
Mathias
|
|
|
|
