0 Daumen
1,7k Aufrufe

Hallo :) Wir haben gerade mit Graphentheorie in der VO begonnen und ich konnte leider nicht anwesend sein. Jetzt sitze ich einwenig ratlos vor einigen der Aufgaben. Ein paar Tipps wären super. Vor allem wie zeigt man überhaupt, dass ein Graph zusammenhängend ist?

Aufgabe:

Sei G ein Graph mit n Knoten und q Kanten. Zeige, dass G zusammenhängend ist, falls q > ((n-1) über 2) gilt. Gibt es einen unzusammenhängenden Graphen mit q = ((n-1) über 2) Kanten?

Avatar von

Hab noch einwenig weiter überlegt. Kann ich die Aussage über Induktion von (n-1) -> n zeigen? Also annehmen, dass es für n-1 stimmt (induktionsanfang) und dann zeigen, dass beim hinzufügen eines knoten mind. eine neue kante notwendig ist?

1 Antwort

+1 Daumen
 
Beste Antwort

Ich denke, dass man das für einfache Graphen (ohne Mehrfachkanten und Schleifen) zeigen soll. Ansonsten ist es nämlich nicht richtig, siehe zum Beispiel der Graph mit 3 Knoten und 2 > (2 über 2) = 1 Kanten, wobei sich die beiden Kanten jeweils zwischen denselben Knoten befinden. Dann ist der dritte Knoten unverbunden, damit der Graph nicht zusammenhängend.

Für einfache Graphen mit n Knoten gibt es maximal (n über 2) Kanten, das kann man sich leicht kombinatorisch überlegen: jede Kante verbindet zwei Knoten, dabei ist eine Kante zwischen Knoten A und Knoten B dasselbe wie eine Kante zwischen Knoten B und Knoten A. Eine Kante ist also eindeutig bestimmt, wenn man die beiden Knoten, die sie verbindet aus den n möglichen Knoten ausgewählt hat.

Nehmen wir nun an, der Graph wäre unzusammenhängend. Das hieße, es gäbe zwei Teile des Graphen mit k und n-k Knoten, die also jeweils zusammengenommen maximal (k über 2) und (n-k über 2) Knoten haben. Damit lautet die maximal Knotenzahl eines solchen unzusammenhängenden einfachen Graphen

$$q_\text{max}(k) = \begin{pmatrix} k \\ 2\end{pmatrix} +\begin{pmatrix} n-k \\ 2\end{pmatrix}$$

hierbei muss die Definition (1 über 2) = 0 benutzt werden. Die Behauptung ist nun

$$q_\text{max}(k) \leq \begin{pmatrix}n-1\\2\end{pmatrix}$$

für k = 1, 2, ..., n-1.

Diese Behauptung ist äquivalent zu

$$ k(k-1) + (n-k)(n-k-1) \leq (n-1)(n-2)$$

und nach Umformung zu

$$ k^2 + n \leq kn + 1.$$

Betrachtet man beide Seiten für festes n als Funktionen von k, dann beschreibt die linke Seite eine nach oben offene Parabel und die rechte eine Gerade mit Steigung n. Es lässt sich leicht nachrechnen, dass beide Seiten für k = 1 und für k = n-1 (die natürlich eigentlich dieselbe Situation beschreiben) identisch sind - damit folgt direkt die Richtigkeit der Aussage.

Das ergibt auch automatisch die Fälle, die die Ungleichung saturieren: für einen Graphen mit n Knoten, besitzt der Graph mit einem isolierten Knoten bei dem alle anderen Knoten jeweils miteinander verbunden sind genau (n-1 über 2) Knoten.

Avatar von 10 k

oha danke für die Antwort :o

Auf die Lösung wäre ich glaub ich nicht gekommen O.o

Ist die Argumentation denn klar? Ich zerlege eben den Graphen in zwei unverbundene Teile und schaue, wie viele Kanten es dann maximal geben kann. Für das letzte Argument mag es Sinn machen, die beiden Seiten der Ungleichung einmal für irgendein n zu plotten.

Ja macht perfekt Sinn :) Danke

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community