Graphentheorie - Anzahl der Kanten

09.03.2014, 19:09

DasBo

Graphentheorie - Anzahl der Kanten

Meine Frage:
Hey...ich habe Probleme bei einer Augabe, deren Lösung ich zwar habe, die mir zum Verständnis der Aufgabe jedoch nicht viel bringt. Vielleicht kann mir jemand helfen.
H1 sei ein Baum mit n Knoten
H2 sei ein vollständiger Graph mit 2n Knoten
Der Graph G entstehe dadurch, dass man jeden Knoten von H1 mit jedem Knoten von H2 durch eine Kante verbindet.
Wieviele Kanten besitzt G. Bestimmen sie reele Zahlen a,b und c für die gilt: G hat genau an²+bn+c Kanten. (mit dem Teil der Aufgabe habe ich Probleme)

Meine Ideen:
Also, da H1 ein Baum ist, hat dieser n-1 Kanten.
H2 hat als vollständiger Graph $\begin{eqnarray*} \begin{pmatrix} 2n \\ 2 \end{pmatrix} \end{eqnarray*}$ Kanten, bzw $\begin{eqnarray*} \frac{2n(2n-1)}{2} \end{eqnarray*}$ oder 2n²-n
Die hinzugefügten Kanten erhält man durch n*2n=2n²
Das heißt der entstandene Graph hat genau
n-1 + $\begin{eqnarray*} \frac{2n(2n-1)}{2} \end{eqnarray*}$ +2n² Kanten
Was aber bedeutet jetzt an²+bn+c aus der Aufgabe. Die Lösung die ich habe, lautet 4n²-1 bei a=4, b=0, c=-1
Danke schonmal im Voraus smile

10.03.2014, 09:29

Kasen75

Auf diesen Beitrag antworten »

RE: Graphentheorie - Anzahl der Kanten

Zitat:

Original von DasBo
n-1 + $\begin{eqnarray*} \frac{2n(2n-1)}{2} \end{eqnarray*}$ +2n² Kanten
Was aber bedeutet jetzt an²+bn+c aus der Aufgabe. Die Lösung die ich habe, lautet 4n²-1 bei a=4, b=0, c=-1

Hallo,

du musst jetzt nur noch $\begin{eqnarray*} n-1 + \frac{2n(2n-1)}{2}+2n² \end{eqnarray*}$ vereinfachen. Zum Beispiel $\begin{eqnarray*} \frac{2n(2n-1)}{2} \end{eqnarray*}$ kürzen. Und sonst weiter zusammenfassen.

Grüße

Neue Frage »

Antworten »

Graphentheorie - Anzahl der Kanten

Verwandte Themen