Kanten in einem ungerichteten Graphen

Natascha · Anmeldungsdatum: 10.11.2005 Beiträge: 3

Hi,
Ich habe ein Problem.
Die Frage ist.
Wieviele Kanten hat ein ungerichteter Graph mit n Knoten maximal?
Beweisen sie die Gültigkeit ihrer Antwort.

"ein ungerichteter Graph mit n-Knoten hat auch n-Kanten", denke ich zumindestens
aber wie soll ich das jetzt beweisen, das ist die Frage. Habt ihr eine Idee

Senior Sanchez · Gast

Gast

Sobald es kein Baum mehr ist (zyklen zugelassen), stimmt das nicht mehr:

X
/ \
X--X

oder

X -- X
| \/ |
| /\ |
X -- X

Senior Sanchez · Gast

Im Grunde stellt diese Darstellung ja schleifen dar, die aber laut wikipedia-Definition bei ungerichteten Graphen oft ausgeschlossen werden.

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Nein. Mit Schleifen (Schlingen) sind Kanten gemeint, deren Start- und Endknoten gleich sind.

Das ist eine einfache kombinatorische Frage. Man nehme n Knoten.
Jetzt pickt man sich einen Knoten raus und verbindet ihn mit allen anderen Knoten (ergibt n-1 Kanten). Dann nehme ich einen zweiten Knoten und verbinde ihn wieder mit allen Kanten, zu denen er noch keine Verbindung hat (ergibt dann also n-2 Kanten) usw.

Das ergibt die Formel:

Ein anderer Ansatz ist: Wieviele Möglichkeiten gibt es, aus n Ecken zwei ohne Zurücklegen ohne Reihenfolge zu ziehen. Das sind

Gast