TU Wien Diskussion:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 195
@mnemetz
Bezieht sich auf:
(Basierend auf den o.g. Links)
Wie muss ein Graph aussehen, in dem keine zwei Knoten denselben Knotengrad haben?
Der erste Knoten hat logischerweise den Knotengrad 1 - ein weiterer Knoten muss mindestens Kontengrad 2 haben.
Daraus ergibt sich, dass die weiteren "Knospen" immer weiter höhere Knotengrade haben müssn - der Graph kann dann nicht mehr endlich und damit einfach sein.
Probieren wir eine Verallgemeinerung: n = Knotenmenge, k = Kantenmenge
Also jeder knoten kann mit jedem verbunden werden, ausser sich selbst => n*(n-1) und jeweils 2 Knoten teilen sich eine Kante (A mit B verbunden und B mit A = 1 knoten) => /2
Überlegen wir uns noch, wie viele Verbindungen ein Graph ohne 2 Knoten mit gleichem Knotengrad haben muss.
Bei einem Graph mit 2 Knoten = 1 + 2 = 3, mit 3 knoten 1+2+3=6, ... ergibt sich:
n = knotenzahl des graphen
k.max = maximal mögliche Kantenzahl in einem einfachen Graph mit n knoten
k.max =
k.min = minimale Anzahl von kanten damit keine Knotengrade gleich sind.
k.min = 1+...+n
n = 2, k.max = 1, k.min = 3 => unmöglich
n = 3, k.max = 3, k.min = 6 => unmöglich
n = 4, k.max = 6, k.min = 10 => unmöglich
n = 5, k.max = 10, k.min = 15 => unmöglich
...
Lösung: Um einen Graphen zu erstellen, bei dem jeder Knoten einen anderen Knotengrad hat, werden demnach immer mehr Möglichkeiten benötigt um die Punkte zu verbinden als Punkte gibt, was in einem einfachen Graphen nicht möglich ist.
1) In deiner Lösung steckt glaub ich ein Fehler. Bei der Formel für k.max berechnest du die maximale Anzahl der Kanten, bei k.min aber die minimale Anzahl der Grade.
Beides ist aber nicht vergleichbar, denn Grad bedeutet ja nicht gleich Kantenanzahl
Stell dir nur folgenden Graphen vor:
A-B-C
A hat Grad 1, B Grad 2 und C Grad 1
Es sind nur 2 Kanten da, aber in Summe haben die Kanten den Grad 4, beides ist also nicht gleich.
Damit deine Berechnungen stimmen müsstest du k.min halbieren oder k.max verdoppeln. Tust du das aber so ist deine Beweisführung nicht mehr möglich, denn dann ist k.max immer größer als k.min.
2.) k.min = 1+...+n
kann so nicht stimmen da du ja maximal bis n-1 addieren kannst. Es gibt keine Schleifen also kann ein Knoten maximal zu n-1 anderen Knoten Kanten haben.
--Soymilk-drinker 15:37, 6. Dez 2005 (CET)