Graphentheorie

11.06.2009, 17:55

eppi1981

Graphentheorie

Sei $\begin{eqnarray*} G=(E,K,\phi) \end{eqnarray*}$ ein schlichter Graph mit |E| = n Knoten, der aus m paarweise disjunkten Untergraphen $\begin{eqnarray*} G_{j} = (E_{j}, K_{j}, \phi|_{K_{j}}) \end{eqnarray*}$ für j =1,...,m besetzt.
Zeigen Sie, dass für die Menge K der Kanten des Graphen G die folgende Abschätzung gilt:
$\begin{eqnarray*} |K|\leq\frac{(n-m)(n-m+1)}{2} \end{eqnarray*}$

Kann mir jemanden helfen, ich habe keine Ahnung, wie das man zeigen kann.

11.06.2009, 19:19

Auf diesen Beitrag antworten »

Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ sieht vielversprechend aus.

11.06.2009, 19:21

eppi1981

Auf diesen Beitrag antworten »

kannst du bisschen genauer erklären?

11.06.2009, 19:29

Auf diesen Beitrag antworten »

Der Induktionsanfang $\begin{eqnarray*} m=1 \end{eqnarray*}$ sollte klar sein, da es in einem Graphen mit $\begin{eqnarray*} n \end{eqnarray*}$ Knoten höchstens $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ Kanten geben kann.

Tja, und dann der Induktionsschritt $\begin{eqnarray*} (m-1)\to m \end{eqnarray*}$ :

Da trennst du erstmal den Untergraphen $\begin{eqnarray*} G_m \end{eqnarray*}$ mit $\begin{eqnarray*} |E_m|=r \end{eqnarray*}$ Knoten ab und kannst für den Rest die Induktionsvoraussetzung nutzen, dann ergibt sich

$\begin{eqnarray*} |K| \leq \frac{((n-r)-(m-1))((n-r)-(m-1)+1)}{2} + \frac{r(r-1)}{2} \qquad (*) \end{eqnarray*}$

Jetzt musst du dir nur noch überlegen,

(a) welche Werte für $\begin{eqnarray*} r \end{eqnarray*}$ überhaupt nur in Frage kommen, und

(b) warum für all diese Werte $\begin{eqnarray*} r \end{eqnarray*}$ der Ausdruck rechts in (*) $\begin{eqnarray*} \leq \frac{(n-m)(n-m+1)}{2} \end{eqnarray*}$ ist,

dann ist der Induktionsbeweis vollbracht. Deutlicher kann ich nicht werden, also stell jetzt bitte erstmal keine Fragen mehr, sondern knie dich rein!

11.06.2009, 19:33

eppi1981

Auf diesen Beitrag antworten »

ein schlichter Graph hat $\begin{eqnarray*} |K|=\begin{pmatrix} n \\ 2 \end{pmatrix}=\frac{n(n-2)}{2} \end{eqnarray*}$
falls m=1

$\begin{eqnarray*} |K|=\begin{pmatrix} n \\ 2 \end{pmatrix}=\frac{n(n-2)}{2} \leq \frac{(n-1)(n-1+1)}{2} \end{eqnarray*}$

falls m=2

$\begin{eqnarray*} |K|=\begin{pmatrix} n \\ 2 \end{pmatrix}=\frac{n(n-2)}{2} \leq \frac{(n-2)(n-2+1)}{2} \end{eqnarray*}$
und das stimmt nicht unglücklich

11.06.2009, 19:43

Auf diesen Beitrag antworten »

Das stimmt in der Tat nicht, was du da geschrieben hast. Offenbar muss ich mich wiederholen:

Zitat:

Original von Arthur Dent
stell jetzt bitte erstmal keine Fragen mehr, sondern knie dich rein!

Neue Frage »

Antworten »

Graphentheorie

Verwandte Themen