Wie viele Kanten hat ein vollständiger (schlichter, schlingenfreier) Graph mit n Knoten?

Aufrufe: 1305     Aktiv: 26.01.2021 um 13:58
0

Laut definition ja: höchstens 1 Kante zwischen zwei Knoten und jede Kante verbindet 2 verschiedene Knoten.

Schlingenfrei ist klar, kein Knoten zeigt auf sich selbst.

War mir da jetzt ein bisschen unsicher, hab einfach mal einen Graphen für n=3 gezeichnet, und sicherheitshalber nochmal für n=5 und komme zum Schluss, das die Kantenzahl = n wäre.

Stimmt das? Habe leider keine Lösung

LG

Diese Frage melden
gefragt

Punkte: 14

 
Kommentar schreiben
2 Antworten
1

Das ist der vollständige Graph mit \(5\) Knoten. Wie du leicht sehen kannst, hat er mehr als \(5\) Kanten.

Überlege dir, wie viele Kanten von jedem Knoten ausgehen. Wie viele Kanten gibt es dann insgesamt? Bedenke, dass du dabei jede Kante doppelt zählst.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Ich komm gerade nicht so gerade zum springenden Punkt wenn ich ehrlich bin.
Evtl liegt es aber auch an meinem Verständnis von einem schlichten Graphen. Was wäre denn ein Beispiel nicht schlichter Graph? Auch das mit dem Kanten doppelt zählen leuchtet mir gerade nicht so ganz ein...   ─   sonti 26.01.2021 um 12:53
1
Ein schlichter Graph ist ein Graph ohne Mehrfachkanten oder Schleifen. Wenn wir im obigen Graph noch eine zusätzliche Kante einzeichnen, dann ist der Graph nicht mehr schlicht: Entweder wir zeichen eine Kante von einem Knoten zu sich selbst (eine Schleife), doer eine zweite Kante von einem Knoten zu einem anderen (eine Mehrfachkante). Der Name "vollständig" kommt eben von der Eigenschaft, dass man keine weitere Kante mehr ergänzen kann, sodass der Graph schlicht bleibt.

Zurück zur Aufgabe: Wie viele Kanten gehen von jedem Knoten aus? Wie viele Kanten gehen also von allen Knoten zusammen aus?   ─   stal 26.01.2021 um 12:57
Okay, das mit der Schleife ist einleuchtend, Mehrfachkante verstehe ich jetzt auch (hat mich erst verwirrt, weil ich es noch nicht gesehen habe aber kurze Google suche half.)

Von jedem Knoten gehen n-1 Kanten aus.
Denn sobald es N Kanten wären, könnte die Schlichtheit nicht mehr erfüllt werden.(eben wie du oben sagtest, da dann im Beispiel die 5te Kante entweder eine Schleife oder Mehrfachkante wäre.   ─   sonti 26.01.2021 um 13:08
1
Genau, also gehen von \(n\) Knoten jeweils \(n-1\) Kanten aus. Insgesamt kommen wir so auf \(n(n-1)\) Kanten. Dabei haben wir aber jede Kante doppelt gezählt, denn eine Kante, die Knoten \(A\) und \(B\) verbindet, haben wir als Kante, die von \(A\) ausgeht, und als Kante, die von \(B\) ausgeht, gezählt. Also müssen wir das Ergebnis noch durch \(2\) teilen.   ─   stal 26.01.2021 um 13:51
Vielen Lieben Dank jetzt leuchtet es mir ein!   ─   sonti 26.01.2021 um 13:57

Kommentar schreiben

2

Denk dabei nicht soviel an Graphen, sondern an Kombinatorik.

In einem vollständigen Graphen ist jedes Knotenpaar durch eine Kante verbunden. Wieviele Knotenpaare gibt es?

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.93K

 
--> Die Anzahl der Knotenpaare ist bei vollständigen Graphen immer halb so groß wie die Anzahl der Kanten?   ─   sonti 26.01.2021 um 13:12

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.