Graphen, Bäume Kanten berechnen

Aufrufe: 1455     Aktiv: 27.02.2020 um 17:45
0

Hallo Freunde der Mathematik.

Ich habe folgende Aufgabenstellung: Von einem GraphenG= (V, E) ist bekannt, dass er genau 10 Knoten besitzt, und sein Komplement ein Baum ist. Berechnen Sie die Anzahl Kanten von G.

Ich habe nicht wirklich eine Ahnung, was ich tun soll.

Mein Lösungsansatz: Das Komplement hat die selbe Anzahl an Knoten, |V(Baum)|=|V(G)|. Desweiteren kann man |E(baum)| durch |V(baum)|-1 berechnen, also gibt es 9 Kanten im Baum. Jetzt weiß ich jedoch nicht, wie ich daraus die Kanten des Ausgangsgraphen berechnen soll. Der Baum muss ja, da er Komplement von G ist die selbe Struktur haben, mit anderen Kanten. Da das Komplement isomorph sein müsste wäre er ja selbstkomplementär und der Ausgangsgraph hätte somit 9*2 Kanten. Stimmt das? Sind Komplemente immer isomorph zum Ausgangsgraph?

Ich würde mich sehr über Hilfe freuen.

Mfg Lori.

Diese Frage melden
gefragt

Punkte: 17

 
Kommentar schreiben
1 Antwort
1

Ich gehe jetzt mal von einem zusammenhängenden Graphen aus.

Wie du schon richtig bemerkt hast, hat ein Baum \(n-1\) Kanten wobei \(n \) für die anzahl der Knoten steht. 

Ein ungerichteter Graph hat maximal \(\frac{n(n-1)}{2}\) Kanten (im gerichteten Fall hat man die doppelte Anzahl). Wie du auch schon richtig gesagt hast, hat das Komplement eines Graphen die selben Knoten und alle "nicht-Kanten" werden zu Kanten und umgekehrt.

Das Komplement, in diesem Fall der Baum, hat \(n-1\) Kanten. Diese \(n-1\) Kanten werden in unserem ursprünglichen Graphen zu "nicht-Kanten" und müssen deswegen von der maximal möglichen Anzahl der Kanten, nämlich \(\frac{n(n-1)}{2}\), abgezogen werden. Somit erhalten wir \(\frac{n(n-1)}{2} - (n-1)\) Kanten.

Diese Antwort melden
geantwortet

Student, Punkte: 235

 

Kommentar schreiben