[Graphentheorie] Graphen aus Teilmengen von N

04.06.2013, 23:31	Hexenjaeger	Auf diesen Beitrag antworten »
[Graphentheorie] Graphen aus Teilmengen von N Folgende Aufgabe bereitet mir Schwierigkeiten: Sei $\begin{eqnarray} S \end{eqnarray}$ eine endliche nichtleere Teilimenge von $\begin{eqnarray} \mathbb{N} \end{eqnarray}$ und $\begin{eqnarray} M := max S \end{eqnarray}$ . Zeigen Sie: (a) Jeder Graph $\begin{eqnarray} (V,E) \end{eqnarray}$ mit der Valenzmenge $\begin{eqnarray} v(V) = S \end{eqnarray}$ hat mindestens $\begin{eqnarray} M+1 \end{eqnarray}$ Knoten. (b) Es gibt einen zusammenhängenden Graphen $\begin{eqnarray} (V,E) \end{eqnarray}$ mit $\begin{eqnarray} v(V) = S \end{eqnarray}$ und $\begin{eqnarray} \|V\| = M+1 \end{eqnarray}$ . Teilaufgabe (a) ist doch mehr oder weniger trivial, denn da $\begin{eqnarray} M \in S \end{eqnarray}$ muss es einen Knoten geben, der mit $\begin{eqnarray} M \end{eqnarray}$ anderen Knoten verbunden ist. Also existieren mindestens $\begin{eqnarray} M \end{eqnarray}$ andere Knoten und der Knoten selbst, also mindestens $\begin{eqnarray} M+1 \end{eqnarray}$ . Oder ist das vielleicht zu einfach gedacht und es gehört doch bisschen mehr dazu? Teilaufgabe (b): Kann das funktionieren wenn ich von einem Vollständigen Graphen mit \|V\| = M +1 der Reihe nach irgendwelche Kanten "lösche" so dass die geforderten Valenzen entstehen? Ich hab keine Idee wie ich das beweisen soll... viele Grüße, Hexenjaeger

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »