Zusammenhangskomponente (Graphen)

26.11.2007, 20:44	kruemel	Auf diesen Beitrag antworten »
Zusammenhangskomponente (Graphen) Hallo, also wir haben folgende Aufgabe aufbekommen: http://img231.imageshack.us/img231/5772/mathexx6.jpg und irgendwie häng ich gerade, wobei ich vermute, das es mit meinem Ansatz zusammenhängt. Also mein Ansatz lautet das für einen vollständigen Graph gilt (um die kanten zu berechnen): $\begin{eqnarray} \frac{n(n-1)}{2} \end{eqnarray}$ und für einen Baum gilt ja: $\begin{eqnarray} n-1 \end{eqnarray}$ danach muss man ja den vollständigen Graphen und den Baum addieren, aber meine lösung ist nicht ganz richtig ich hab am Ende immer $\begin{eqnarray} \frac{n² + n - 2}{2} \end{eqnarray}$ heraus. kann mir vielleicht jemand sagen, wo genau der Fehler liegt?
26.11.2007, 21:23	Dual Space	Auf diesen Beitrag antworten »
RE: Zusammenhangskomponente (Graphen) Die Aufgabe ist nicht so lang, als das man sie hier nicht hätten hinschreiben können. Das lockt Helfer nicht unbedingt an. *verschoben*
26.11.2007, 21:24	Mazze	Auf diesen Beitrag antworten »
Man verbindet n Knoten vollständig mit n weiteren Knoten. Dabei passiert folgendes : Für jeden Knoten aus $\begin{eqnarray} G_1 \end{eqnarray}$ kommen n Kanten dazu. Das heisst insgesammt kommen $\begin{eqnarray} n^2 \end{eqnarray}$ Kanten hinzu. Wir haben also $\begin{eqnarray} \underbrace{\frac{n(n-1)}{2}}_{G_1} + \underbrace{n-1}_{G_2} + \underbrace{n^2}_{\text{ die neuen Kanten }} \end{eqnarray}$ Kanten, und dabei kommt man genau auf das Ergebnis. Dein Ergebnis ist mir irgendwie unheimlich weil es nicht eine Summe oder Teilsumme der 3 Summanden ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »