Graphentheorie

Neue Frage »

Slexout Auf diesen Beitrag antworten »
Graphentheorie
Meine Frage:
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
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
zweiundvierzig Auf diesen Beitrag antworten »
RE: Hilfe bei Graphentheorie
Zitat:
Original von Slexout
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.

Das ist richtig.

Nimm an, sei maximal. Was gilt dann für die Vereinigung über die Kugeln?
Slexout Auf diesen Beitrag antworten »
RE: Hilfe bei Graphentheorie
Zitat:
Original von zweiundvierzig
Zitat:
Original von Slexout
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.

Das ist richtig.

Nimm an, sei maximal. Was gilt dann für die Vereinigung über die Kugeln?


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
zweiundvierzig Auf diesen Beitrag antworten »
RE: Hilfe bei Graphentheorie
Zitat:
Original von Slexout
Also wenn a und b beide in Abhänigkeit stehen hätte ich bei B(a) geschnitten B(b) = {a, b}.

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:
Zitat:
Original von Slexout
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?

Gemeint ist für eine maximal unabhängige Knotenmenge (die im übrigen nicht eindeutig sein muss). Welche Konsequenz hat hier die Maximalität?
Slexout Auf diesen Beitrag antworten »
RE: Hilfe bei Graphentheorie
Zitat:
Original von zweiundvierzig
Zitat:
Original von Slexout
Also wenn a und b beide in Abhänigkeit stehen hätte ich bei B(a) geschnitten B(b) = {a, b}.

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:
Zitat:
Original von Slexout
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?

Gemeint ist für eine maximal unabhängige Knotenmenge (die im übrigen nicht eindeutig sein muss). Welche Konsequenz hat hier die Maximalität?


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
 
 
zweiundvierzig Auf diesen Beitrag antworten »
RE: Hilfe bei Graphentheorie
Zitat:
Original von Slexout

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).

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?
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?
zweiundvierzig Auf diesen Beitrag antworten »

Seien Mengen. Wie kann man nach oben abschätzen?

Edit: Am besten sollen noch alle endlich sein.
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
zweiundvierzig Auf diesen Beitrag antworten »

Ansatz:
Jetzt du!
Tipp: Betrachte .
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
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Slexout
| UNION Ai | ist <= Am mit m = max { | Ai | für i = {1, ... n}

Was ist ?
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
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.
Slexout Auf diesen Beitrag antworten »

Ich verstehe es richtig, dass unser unser ist, nur mit Index statt Parameterübergabe ist oder?

Zitat:

Wir wollen die Vereinigung über die abschätzen. Offenbar besteht jedes aus höchstens Elementen. Wie viele gibt es insgesamt?


Es gibt viele bzw. für

Zitat:
Wogegen können wir folglich die Vereinigung abschätzen?


Da unsere maximal m Elemente haben können, hat unsere Vereinigung auch maximal m Elemente, also ist
zweiundvierzig Auf diesen Beitrag antworten »

Es gibt viele , also...?
Slexout Auf diesen Beitrag antworten »

Sorry, aber ich weiß echt nicht womit du darauf hinaus willst verwirrt
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Slexout
Da unsere maximal m Elemente haben können, hat unsere Vereinigung auch maximal m Elemente, also ist

Das ist falsch. Siehst du, wieso?
Slexout Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
Zitat:
Original von Slexout
Da unsere maximal m Elemente haben können, hat unsere Vereinigung auch maximal m Elemente, also ist

Das ist falsch. Siehst du, wieso?


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?
zweiundvierzig Auf diesen Beitrag antworten »

unglücklich

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.
Slexout Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
unglücklich

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.


?
zweiundvierzig Auf diesen Beitrag antworten »

Ja. Wie verallgemeinert sich das nun für statt Mengen ?
Slexout Auf diesen Beitrag antworten »

wobei ?
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.
Slexout Auf diesen Beitrag antworten »

Damit wissen wir, dass unser ist, wobei m aber unser ist

edit: latex
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).
Slexout Auf diesen Beitrag antworten »

Zitat:
Original von zweiundvierzig
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).


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 verwirrt

Wir hatten ja gezeigt, das die Vereinigung von unseren gesamten Graphen entspricht, kann ich das also so nehmen?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Slexout
Zitat:
Original von zweiundvierzig
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).


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.

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 .

Zitat:
Original von Slexout
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 verwirrt

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.)
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Slexout
Wir hatten ja gezeigt, das die Vereinigung von unseren gesamten Graphen entspricht

Damit das gilt, ist die Maximalität von entscheidend.
Slexout Auf diesen Beitrag antworten »

Der Hammer Gott

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 ! Prost

Viele Grüße
Slexout
zweiundvierzig Auf diesen Beitrag antworten »

Freut mich, dass ich helfen konnte. smile

Viele Grüße,
zweiundvierzig
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »