Graphentheorie: Beweis: Graph mit 2n Knoten ohne Dreieck hat n^2 Kanten?

31.12.2018, 17:56	Weißer Peter	Auf diesen Beitrag antworten »
Graphentheorie: Beweis: Graph mit 2n Knoten ohne Dreieck hat n^2 Kanten? Meine Frage: Hallo, die Aufgabe steht oben. Ich soll mittels vollständiger Induktion zeigen, dass ein Graph mit $\begin{eqnarray} 2n \end{eqnarray}$ Knoten höchstens $\begin{eqnarray} n^2 \end{eqnarray}$ Kanten besitzt, sofern dieser kein Dreieck enthält. Meine Ideen: Offenbar ist es ratsam, beim Induktionsschritt schon einen Graphen zu nehmen, der kein Dreieck enthält, und dann einen (oder gleich zwei?) Knoten zu entfernen. Dann hat man $\begin{eqnarray} 2(n-1) \end{eqnarray}$ Knoten übrig und muss überlegen, wieso es nur $\begin{eqnarray} (n-1)^2 \end{eqnarray}$ Kanten gibt. Das ist der Knackpunkt der Aufgabe. Zudem bin ich mir auch nicht ganz sicher, wie ich dann den Induktionsanfang gestalten soll. Wenn ich das ganze für $\begin{eqnarray} n = 1 \end{eqnarray}$ Beweise, und bei jedem Schritt um eins verringere, ist das ganze dann auch noch für $\begin{eqnarray} n > 1 \end{eqnarray}$ gezeigt? Oder müsste man nicht irgendwie den Induktionsanfang bei $\begin{eqnarray} n = \infty \end{eqnarray}$ ansetzen? Ich habe auch diesen alten Post auf Englisch gefunden: https://math.stackexchange.com/a/308111 Leider verstehe ich nicht ganz, was gemeint ist. "Wenn zwei Knoten durch eine Kante miteinander verbunden sind, dann müssen sich ihre Grade höchstens zu $\begin{eqnarray} 2n \end{eqnarray}$ addieren"? Das kann ich nicht nachweisen, wenn ich einen Graphen zeichne, so komme ich bei den Graden stets auf weit unter $\begin{eqnarray} 2n \end{eqnarray}$ .
01.01.2019, 09:53	PWM	Auf diesen Beitrag antworten »
RE: Graphentheorie: Beweis: Graph mit 2n Knoten ohne Dreieck hat n^2 Kanten? Hallo, zum Hinweis: Wenn G ein Graph mit $\begin{eqnarray} 2n \end{eqnarray}$ Knoten ohne Dreieck ist, dann seien $\begin{eqnarray} x,y \end{eqnarray}$ zwei benachbarte Knoten. Eventuelle Nachbarn von x und Nachbarn von y müssen disjunkt sein, weil sonst ein Dreieck entsteht. Wenn also x außer zu y zu k weiteren Knoten benachbart ist und y zu m weiteren Knoten, dann muss gelten: $\begin{eqnarray} k+m=2n-2 \end{eqnarray}$ . Damit kannst Du jetzt den Induktionsbeweis führen. Gruß pwm
01.01.2019, 16:32	Weißer Peter	Auf diesen Beitrag antworten »
RE: Graphentheorie: Beweis: Graph mit 2n Knoten ohne Dreieck hat n^2 Kanten? Ich bin mir etwas unsicher wie mir das helfen kann. Soweit bin ich jetzt: z.z. Graph mit $2(n+1)$ Kanten ohne Dreiecke hat höchstens $(n+1)^2$ Kanten nehmen einen solchen Graph entfernen 2 Knoten und ihre Kanten Graph hat immernoch kein Dreieck und nun nur $2n$ Knoten. Daher höchstens $n^2$ Kanten. Müssen nun die 2 Knoten wieder anfügen und zeigen, dass es höchstens $(n+1)^2$ Kanten werden Nun gibt es ja erstmal das Problem, dass u.U. kein Paar von Knoten miteinander benachbart sind. Dann kann man die beiden Knoten fast beliebig anhängen. Den ersten Knoten kann man maximal an alle existierenden Knoten anhängen, also bis zu $2n$ Kanten. Den zweiten Knoten auch, solange er nicht auch an den ersten Knoten angehangen wird (also wieder max $2n$ Kanten). Heißt dabei kommen höchstens $4n$ Kanten hinzu. Ist das nun kleiner oder gleich $(n+1)^2$? Der andere Fall ist der, zu dem du jetzt gleich gesprungen bist. Ich verstehe die Logik, weiß aber nicht wie ich diesen Fakt hier jetzt einsetzen soll. Sagen wir mal wir wollen den ersten Knoten wieder anhängen. Machen wir das z.B. indem wir ihn an alle Nachbarn von $x$ und alle Nachbarn von $y$ anhängen. Stellt sich die Frage, haben wir damit eine maximale Anzahl an Kanten erzeugt, oder gibt es einen weg, den Knoten so anzuhängen, dass NOCH MEHR Kanten entstehen (ohne Dreieck versteht sich)? Und dann bleibt die Frage, wie agieren wir mit dem zweiten Knoten ohne komplett die Übersicht zu verlieren?
02.01.2019, 10:00	PWM	Auf diesen Beitrag antworten »
RE: Graphentheorie: Beweis: Graph mit 2n Knoten ohne Dreieck hat n^2 Kanten? Hallo, warum willst Du wieder anhängen? Sei G ein Graph mit $\begin{eqnarray} 2n+2 \end{eqnarray}$ Knoten und k Kanten. Entferne zwei benachbarte Knoten und erhalte einen Graphen G' mit $\begin{eqnarray} 2n \end{eqnarray}$ Knoten und m Kanten. Die Anzahl der wegzunehmenden Kanten sei d. Dann gilt: $\begin{eqnarray} k=m+d \end{eqnarray}$ . m kannst Du aufgrund der Induktion nach oben abschätzen und d aufgrund des Hinweises. Gruß pwm

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »