Graphentheorie |
30.01.2019, 23:17 | Slexout | Auf diesen Beitrag antworten » | ||||||
Graphentheorie Hallo, ich bräuchte dringend Hilfe bei folgender Aufgabe sonst erhalte ich vermutlich meine Studienleistung nicht. (siehe Anhang) Meine Ideen: Ich bin nach den Angaben des Hinweises vorgegangen. Habe mir erstmal anhand eines Beispiels eine (nicht maximale) unabhängige Knotenteilmenge S und dann die maximale Knotenteilmenge S rausgesucht. Daraus habe ich jeweils die Menge B(v) = N(v) \cup {v} für v \in S gebildet, also die Kugeln vom Radius 1 bzgl. Abstandsmetrik im Graphen (so laut Hinweis). B(v) habe ich dann mit S geschnitten und gesehen, dass egal für welches Element v \in S immer wieder nur v raus kommt. Was ich daraus gelernt habe, ist dass die direkten Nachbarn eines Knoten (also Grad 1) trivialerweise nicht in der unabhängigen Knotenteilmenge S sein können. Ich denke das soll mir irgendwie erklären, wie ich diese Formel nun beweisen kann, aber ich komme einfach nicht drauf.. Was mich am meisten ärgert ist, dass ich anhand eines Beispiels erklären kann warum es so ist. Für ein Beweis würde es hierfür jedoch nicht ausreichen. Hier meine Erklärung: Ich könnte den "worst-case" betrachten, welcher für diese Formel möglich ist und mit diesem versuchen die Formel zu brechen. Also rechter Term größer als der linke. Hierfür müsste mein alpha(G) bzw. maximale unabhängige Knotenteilmenge S so klein wie möglich sein und der rechte Term so groß wie möglich. Also wähle ich 3 Knoten die von links nach rechts einfach miteinander verbunden sind und nenne sie a,b,c,d. {a,c} wäre die größte mögliche Knotenteilmenge da a und c nicht miteinander verbunden sind. So wäre alpha(G) = 2. Nun den rechten Term so groß wie möglich machen. Anzahl der Knoten könnte ich nun größer machen, jedoch würde ich so eine immer größere unabhängige Knotenteilmenge. Also bleibe ich bei a,b,c,d. |V| ist also = 4. Mein delta hab ich so klein wie möglich gehalten, indem ich ja die Knoten nur in einer Linie verbunden habe, damit nicht so viele Kanten aus einem Knoten heraus gehen. Also ist mein Delta = 2, da ein mittlerer Knoten 2 ausgehende Kanten hat. Rechter Term wäre 4/2+1, was kleiner gleich 2 ist. Für mich ist es offensichtlich warum diese Formel korrekt ist, kann es aber nicht begründen und schon gar nicht beweisen. Bitte helft mir. Viele Grüße Slexout |
||||||||
30.01.2019, 23:20 | Slexout | Auf diesen Beitrag antworten » | ||||||
Hier nochmal der Anhang, da er im ersten Post nicht funktionierte. Gerne nehme ich auch Hilfe über Discord oder ähnliches an. Viele Grüße |
||||||||
31.01.2019, 00:19 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
RE: Hilfe bei Graphentheorie
Das ist richtig. Nimm an, sei maximal. Was gilt dann für die Vereinigung über die Kugeln? |
||||||||
31.01.2019, 01:23 | Slexout | Auf diesen Beitrag antworten » | ||||||
RE: Hilfe bei Graphentheorie
Also wenn a und b beide in Abhänigkeit stehen hätte ich bei B(a) geschnitten B(b) = {a, b}. Wenn sie unabhängig voneinander sind, also keine direkte Kante, ist es die leere Menge? Du schriebst noch: Was gilt dann für die Vereinigung über die Kugeln? Genau diese Frage verstehe ich auch nicht in dem Hinweis des Aufgabenblatts. Über welche Kugeln soll ich Vereinigen ? B(v) wobei v von der maximalen Knotenteilmenge ist? Viele Grüße Slexout |
||||||||
31.01.2019, 01:32 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
RE: Hilfe bei Graphentheorie
Meinst du, wenn und benachbart sind? Das kann ja nicht sein, wenn beide Knoten aus einer unabhängigen Menge stammen. Insbesondere sind dann auch weder noch im Schnitt, sondern nur etwaige gemeinsame Nachbarn. Entscheidend ist das folgende:
Gemeint ist für eine maximal unabhängige Knotenmenge (die im übrigen nicht eindeutig sein muss). Welche Konsequenz hat hier die Maximalität? |
||||||||
31.01.2019, 11:38 | Slexout | Auf diesen Beitrag antworten » | ||||||
RE: Hilfe bei Graphentheorie
Wenn ich B(v), für alle v aus der maximalen Knotenmenge vereinige, dann habe ich ja alle meine Elemente des Graphen drinne, da bei der maximalen Knotenmenge, alle möglichen Knoten ohne direkten Nachbarn drinne sind und ich mit B(v) wieder die direkten Nachbarn einschließe. (Falls ich das richtig sehe). Nur irgendwie hilft es mir nicht weiter mit dem was ich beweisen soll. :/ Viele Grüße Slexout |
||||||||
Anzeige | ||||||||
|
||||||||
31.01.2019, 12:18 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
RE: Hilfe bei Graphentheorie
Alle *Knoten* des Graphen, ja. Damit haben wir . Das ist schonmal gut, weil wir die Menge ins Spiel gebracht haben. Wie könnte man jetzt nach oben abschätzen? |
||||||||
31.01.2019, 12:38 | Slexout | Auf diesen Beitrag antworten » | ||||||
Naja, wir haben ja noch keine Annahmen über andere Zahlen getroffen. Ich bin etwas schlecht was Variablen angeht. Das einzige was ich jetzt sagen könnte wäre, wenn wir ein Unabhängigkeitsgrad von n hätten (alpha(G)), wäre V aufjedenfall größer als n. Eventuell würde ich gerne irgendwie behaupten, dass zwischen zwei unabhängigen Knoten entweder 2 oder 0 Kanten liegen müssen und somit die Knotenanzahl |S| * 2 wäre, aber das ist irgendwie ziemlich schwammig. Deine Idee ist es V nach oben hin abzuschätzen und zu zeigen das selbst V/1 kleiner als alpha(G) ist oder? |
||||||||
31.01.2019, 13:23 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Seien Mengen. Wie kann man nach oben abschätzen? Edit: Am besten sollen noch alle endlich sein. |
||||||||
31.01.2019, 14:29 | Slexout | Auf diesen Beitrag antworten » | ||||||
Wie man im Allgemeinen die Kardinalität berechnet bzw. die Menge nach oben abschätzt habe ich verstanden. Nur ich weiß nicht wie ich |V| nach oben abschätzen soll, wenn ich keine anderen Informationen über meine unabhängige Knotenschnittmenge verfüge. Die Kardinalität der Vereinigung der Mengen A1 bis An, wären alle Elemente die in A1 bis An enthalten sind, jedoch ohne sie doppelt zu zählen. Als Beispiel: A1 = {a, b} A2 = {a, c} A3 = {b, c} dann wäre Union A1 bis A3 = {a,b,c} und die Kardinalität dessen = 3. Heißt ich hätte bei meinem Graphen |V| nach oben abgeschätzt = die Anzahl aller Knoten, jedoch wussten wir bereits das Union B(v) die Menge aller Knoten (V) ergibt |
||||||||
31.01.2019, 15:10 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Ansatz: Jetzt du! Tipp: Betrachte . |
||||||||
31.01.2019, 18:13 | Slexout | Auf diesen Beitrag antworten » | ||||||
| UNION Ai | ist <= Am mit m = max { | Ai | für i = {1, ... n} kann ich dann nicht Am, also meine Menge, welche die meisten Nachbarn enthält für mein delta benutzen? Das delta ist ja der maximale Knotengrad und ich könnte |Am| als maximalen Knotengrad -1 annehmen, weil es ja alle Nachbarn abzüglich des Elements selbst sind. Zwar könnte ein noch größeres existieren, da wir ja nur die Knotenteilmenge betrachten und nicht den ganzen Grafen, aber ist das dann nicht groß genug um |V|/delta+1 so klein zu halten das alpha(G) größer ist? Oder bin ich auf einem komplett falschen Weg ? Viele Grüße Slexout |
||||||||
31.01.2019, 19:16 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Was ist ? |
||||||||
31.01.2019, 19:56 | Slexout | Auf diesen Beitrag antworten » | ||||||
Wir hatten ja von "A" Mengen gesprochen. Das Am sollte jetzt auf B(m) bezogen sein, wobei m der Knoten mit der höchsten Gradzahl ist edit: ich merke gerade, dass das keinen Sinn ergibt.. Ich komm irgendwie nicht weiter |
||||||||
31.01.2019, 20:12 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Du scheinst dich lange mit der Aufgabe befasst zu haben, aber deine Beiträge sind an vielen Stellen verworren und technisch tlw. grob falsch oder zumindest fragwürdig. Ich weiß nicht, wie du deine Beweise in den Hausübungen o.ä. aufschreibst, aber in deinem eigenen Interesse empfehle ich dir sorgfältig auf klare Struktur und formale Korrektheit zu achten. Damit ist aus mehreren Gründen schon viel gewonnen. Zurück zur Aufgabe: Wir wollen die Vereinigung über die abschätzen. Offenbar besteht jedes aus höchstens Elementen. Wie viele gibt es insgesamt? Wogegen können wir folglich die Vereinigung abschätzen? Es ist wichtig, dass du zunächst diesen allgemeinen Fall verstehst, bevor es wieder an die konkrete Fragestellung zurückgeht. |
||||||||
31.01.2019, 20:26 | Slexout | Auf diesen Beitrag antworten » | ||||||
Ich verstehe es richtig, dass unser unser ist, nur mit Index statt Parameterübergabe ist oder?
Es gibt viele bzw. für
Da unsere maximal m Elemente haben können, hat unsere Vereinigung auch maximal m Elemente, also ist |
||||||||
31.01.2019, 20:35 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Es gibt viele , also...? |
||||||||
31.01.2019, 20:47 | Slexout | Auf diesen Beitrag antworten » | ||||||
Sorry, aber ich weiß echt nicht womit du darauf hinaus willst |
||||||||
31.01.2019, 21:11 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Das ist falsch. Siehst du, wieso? |
||||||||
31.01.2019, 21:16 | Slexout | Auf diesen Beitrag antworten » | ||||||
Ja stimmt, hab mir gerade ein Gegenbeispiel gefunden. A1 = {a,b,c} A2 = {c, d} UNION A = {a,b,c,d} D.h. also da ich über die unabhängigen Knoten und deren Nachbarn vereinige kann ich anhand der Vereinigung auf alle Knoten meines Graphen kommen, also ? Liege ich da richtig? |
||||||||
31.01.2019, 21:27 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Seien endliche Mengen mit . Dann gilt Edit: Deine Ungleichung stimmt zwar, aber an diesem Punkt nützt sie nichts. Vergiss für einem Moment das konkrete Problem mit den Graphen und konzentriere dich nur auf die mengentheoretischen Fragen, die ich dir stelle. |
||||||||
31.01.2019, 21:50 | Slexout | Auf diesen Beitrag antworten » | ||||||
? |
||||||||
31.01.2019, 21:53 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Ja. Wie verallgemeinert sich das nun für statt Mengen ? |
||||||||
31.01.2019, 21:58 | Slexout | Auf diesen Beitrag antworten » | ||||||
wobei ? |
||||||||
31.01.2019, 22:09 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Genau. Wir haben also , wobei . Jetzt betrachten wir die Situation aus der Aufgabe. Es ist für maximal unabhängig. Wie überträgt sich unsere Beobachtung nun hierauf? Edit: Latex korrigiert. |
||||||||
31.01.2019, 22:20 | Slexout | Auf diesen Beitrag antworten » | ||||||
Damit wissen wir, dass unser ist, wobei m aber unser ist edit: latex |
||||||||
31.01.2019, 22:29 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Ja, das ist richtig. Wie können wir noch beschreiben? Mit anderen Worten, wie lässt sich für Kugeln , die maximale Mächtigkeit haben, diese Mächtigkeit ausdrücken? (s. Aufgabentext). |
||||||||
31.01.2019, 22:39 | Slexout | Auf diesen Beitrag antworten » | ||||||
Ist es unser delta + 1? Würde aus diesem Grund Sinn machen, da der Grad ja die Anzahl der Nachbarn sind und die Addition von + 1 für das Element selbst stehen würde. Jedoch steht für mich im Weg, dass unser max ja nur aus unserer unabhängigen Menge S sein kann und unser delta in G, also in unserem gesamten Graphen ist Wir hatten ja gezeigt, das die Vereinigung von unseren gesamten Graphen entspricht, kann ich das also so nehmen? |
||||||||
31.01.2019, 22:59 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Fast. Es ist für alle (nicht nur die in ). Also gilt . (Gleichheit muss nicht gelten, wie man sich an einem minimalen Beispiel klarmachen kann.) Insgesamt sind wir damit aber am Ziel, denn somit ist .
Sowohl als auch hängen vom gesamten Graphen ab. Man könnte genauso gut auch schreiben. Sind und maximal unabhängige Mengen, dann gilt nach Definition . (Die Mengen müssen nicht eindeutig sein, wieder sieht man einem Minimalbeispiel, dass es mehrere maximal unabhängige Mengen geben kann. Diese haben dann aber notwendig die gleiche Mächtigkeit.) |
||||||||
31.01.2019, 23:01 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Damit das gilt, ist die Maximalität von entscheidend. |
||||||||
31.01.2019, 23:16 | Slexout | Auf diesen Beitrag antworten » | ||||||
Der Hammer Ich hätte nicht gedacht, dass ich diese Aufgabe gelöst bekomme. Anhand deiner Hilfe hab ich es doch geschafft und auch noch so, dass ich alles verstanden habe. Danke dir vielmals ! Viele Grüße Slexout |
||||||||
31.01.2019, 23:20 | zweiundvierzig | Auf diesen Beitrag antworten » | ||||||
Freut mich, dass ich helfen konnte. Viele Grüße, zweiundvierzig |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|