Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Anzahl der Kanten, damit ein neuer K_10 entsteht
Autor
Universität/Hochschule J Anzahl der Kanten, damit ein neuer K_10 entsteht
DrTobi
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.12.2020
Mitteilungen: 6
  Themenstart: 2022-04-13

Hallo, ich habe vor einiger Zeit eine Übungsaufgabe bekommen, welche mir einige Probleme bereitet. Die Aufgabe lautet: "Sei G=(V,E) ein zufälliger Graph auf n $\geq$ 10 Knoten. Nun nehmen wir an, wann immer wir eine Kante e zu G hinzufügen, entsteht in G ein neuer vollständiger Graph auf 10 Knoten. Oder anders ausgedrückt: Die Anzahl von vollständigen $K_{10}$ steigt. Zu zeigen ist nun das G mindestens 8n-36 Kanten hat. Als Tipp wurde gesagt wir sollen den Satz über die Größe von (k,l)-Systemen nutzen. https://matheplanet.com/matheplanet/nuke/html/uploads/b/53991_kl-System.png https://matheplanet.com/matheplanet/nuke/html/uploads/b/53991_Satz_zu_kl-Systemen.png Als weiteren Tipp habe ich noch bekommen, dass ich $A_i :=$ Ecken einer nicht genutzten Kante $e_i$ und $B_i$ als fehlende Ecken zu einem neuen $K_{10}$. Ich habe nun schon etwas rumgetüftelt und folgende Sachen herausgefunden: 1) $\sum \limits_{i=n-8}^{n-1}i = 8n-36$ 2) Mit den als Tipp gegebenen $A_i$ und $B_i$ erhält man ein (k,l)-System somit ist der Satz anwendbar. Dabei ist $k=2$ und $l=8$. Zudem erhält man für h eine Abschätzung der Form $h \leq \binom{10}{2}=45$ Da h nun aber die Anzahl der nicht genutzten Kanten abschätzt muss ich alle Kanten minus h rechnen um auf meinen Wert zu kommen den ich benötige. Das Problem was ich nun habe ist das ich nicht weiß wie ich von $\sum \limits_{i=1}^{n-1}i - 45$ auf die $8n-36$ komme. Was ich mir noch vorstellen könnte ist das ich den Tipp mit dem $B_i$ nicht richtig mir gemerkt habe. Ich Danke schonmal im Voraus für Hilfe. Tobi


   Profil
sonnenschein96
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 700
  Beitrag No.1, eingetragen 2022-04-13

Hallo Tobi, ich habe es noch nicht im Detail durchdacht, aber ich denke nicht, dass \(h\) durch eine von \(n\) unabhängige Konstante beschränkt sein kann. Ich glaube, dass bei Dir die Bedingung \(A_i\cap B_j\neq\emptyset\) für \(i\neq j\) im Allgemeinen nicht erfüllt ist. Vielleicht könntest Du aber stattdessen \(B_i\) als das Komplement der Knoten eines \(K_{10}\) wählen, der entsteht, wenn man \(e_i\) hinzufügt. Dann wäre \(|B_i|=n-10\) und daher \(h\leq\binom{n-8}{2}=\frac{(n-8)(n-9)}{2}=\sum_{i=1}^{n-9}i\). Daher ist \[\sum_{i=1}^{n-1}i-h\geq\sum_{i=1}^{n-1}i-\sum_{i=1}^{n-9}i=\sum_{i=n-8}^{n-1}i=8n-36.\] Du müsstest Dir dann noch überlegen, ob tatsächlich \(A_i\cap B_i=\emptyset\) und \(A_i\cap B_j\neq\emptyset\) für \(i\neq j\).


   Profil
DrTobi
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.12.2020
Mitteilungen: 6
  Beitrag No.2, vom Themenstarter, eingetragen 2022-04-13

Hallo sonnenschein96, ja das ergibt tatsächlich viel mehr Sinn. Ich denke das mit den Voraussetzungen für das (k,l)-System sollte man sich relativ fix überlegen können. Und das ist zumindest ein Ansatz auf den ich noch nicht gekommen war. Daher auf jeden Fall vielen Dank :D Ich werde mir das morgen noch einmal im Detail überlegen und gucken wie es hinhaut. Falls es mit dem Ansatz klappt schließe ich dann den Beitrag ab. Mit freundlichen Grüßen, Tobi


   Profil
DrTobi
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.12.2020
Mitteilungen: 6
  Beitrag No.3, vom Themenstarter, eingetragen 2022-04-15

So ich habe es jetzt einmal alles überlegt und es ist tatsächlich sehr leicht sich das logisch zu überlegen weshalb $F=\{A_i,B_i\}$ ein $(k,l)$-System ist. Somit habe ich die Aufgabe gelöst. Vielen Danke nochmal. MfG, Tobi


   Profil
DrTobi hat die Antworten auf ihre/seine Frage gesehen.
DrTobi hat selbst das Ok-Häkchen gesetzt.
DrTobi wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]