minimaler Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:44 Do 20.08.2009 | | Autor: | Pacapear |
Hallo zusammen!
Ich verstehe die Bedeutung der Eigenschaft minimal bei Graphen nicht so wirklich.
Hier habe ich einen kleinen Auszug, in dem der Begriff vorkommt:
Wegen seines hübschen Beweises bringen wir noch einen Satz über die Anzhal von Graphen $G$, die minimal sind mit der Eigenschaft, dass $G$ bei jeder 2-Kantenfärbung ein einfarbiges Exemplar eines vorgegebenen Graphen $H$ enthält - einen zu $H$ isomorphen Teilgraphen also, dessen Kanten alle die gleiche Farbe tragen. Solche Graphen $G$ nennen wir Ramsey-minimal für $H$.
Vielleicht erstmal zum ersten "minimal".
Was bedeutet das?
Geht es da um den kleinsten Graphen, den man finden kann, der bei jeder 2-Kantenfärbung (was das ist, weiß ich noch nicht) ein solches einfarbiges Exemplar enthält?
Oder ist etwas ganz anderes gemeint?
Vielen Dank und LG, Nadine
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:46 Do 20.08.2009 | | Autor: | Bastiane |
Hallo Pacapear!
> Hallo zusammen!
>
> Ich verstehe die Bedeutung der Eigenschaft minimal bei
> Graphen nicht so wirklich.
>
> Hier habe ich einen kleinen Auszug, in dem der Begriff
> vorkommt:
>
> Wegen seines hübschen Beweises bringen wir noch einen Satz
> über die Anzhal von Graphen [mm]G[/mm], die minimal sind mit der
> Eigenschaft, dass [mm]G[/mm] bei jeder 2-Kantenfärbung ein
> einfarbiges Exemplar eines vorgegebenen Graphen [mm]H[/mm] enthält
> - einen zu [mm]H[/mm] isomorphen Teilgraphen also, dessen Kanten
> alle die gleiche Farbe tragen. Solche Graphen [mm]G[/mm] nennen wir
> Ramsey-minimal für [mm]H[/mm].
>
> Vielleicht erstmal zum ersten "minimal".
>
> Was bedeutet das?
>
> Geht es da um den kleinsten Graphen, den man finden kann,
> der bei jeder 2-Kantenfärbung (was das ist, weiß ich noch
> nicht) ein solches einfarbiges Exemplar enthält?
Ich glaub', ja. Allerdings bin ich nicht ganz sicher. Soll das denn oben quasi die Definition sein, also soll es heißen, dass sich das "mit der Eigenschaft" auf die Definition des minimalen Graphen bezieht? Zuerst hatte ich es nämlich so verstanden, dass man Graphen betrachtet, die sowohl minimal sind, als auch die danach erklärte Eigenschaft haben. Was das minimal dann bedeuten sollte, wüsste ich aber auch nicht.
Eine Kantenfärbung sollte einfach eine Färbung der Kanten sein (du kannst dir also einfach bunte Stifte nehmen und jede Kante färben). Bei einer 2-Kantenfärbung nimmst du dementsprechend 2 Farben.  Wenn es um eine gültige 2-Kantenfärbung gilt (bin nicht sicher, ob das hier gemeint ist), dann dürften zwei benachbarte Kanten, die also einen Knoten gemeinsam haben, nicht dieselbe Farbe haben. Im Prinzip das Gleiche wie bei einer Knotenfärbung, nur halt für Kanten.
Hilft dir das?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:33 Do 20.08.2009 | | Autor: | Pacapear |
Hallo Bastiane!
> Ich glaub', ja. Allerdings bin ich nicht ganz sicher. Soll
> das denn oben quasi die Definition sein, also soll es
> heißen, dass sich das "mit der Eigenschaft" auf die
> Definition des minimalen Graphen bezieht? Zuerst hatte ich
> es nämlich so verstanden, dass man Graphen betrachtet, die
> sowohl minimal sind, als auch die danach erklärte
> Eigenschaft haben. Was das minimal dann bedeuten sollte,
> wüsste ich aber auch nicht.
Also ich weiß es auch nicht so genau.
Das Ganze ist eine Aussage, die vor einem Satz kommt.
Ich schreib mal den Satz auf, vielleicht hilft das weiter?
Ist $T$ ein Baum, aber kein Stern, so gibt es unendlich viele für $T$ Ramsey-minimale Graphen.
So, das ist der Satz.
Das Ganze ist übrigens aus dem Buch von Diestel ("Graphentheorie", S. 213, Prop. 7.2.3)
Ich hab auch überhaupt keine Ahnung, wie das gemeint sein soll.
Das Problem ist, dass ich unter anderem über diesen Satz einen Vortrag im Seminar halten muss...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:38 Do 20.08.2009 | | Autor: | Pacapear |
Hallo Bastiane.
> Ich glaub', ja. Allerdings bin ich nicht ganz sicher. Soll
> das denn oben quasi die Definition sein, also soll es
> heißen, dass sich das "mit der Eigenschaft" auf die
> Definition des minimalen Graphen bezieht? Zuerst hatte ich
> es nämlich so verstanden, dass man Graphen betrachtet, die
> sowohl minimal sind, als auch die danach erklärte
> Eigenschaft haben. Was das minimal dann bedeuten sollte,
> wüsste ich aber auch nicht.
Also je mehr ich darüber nachdenke, desto weniger verstehe ich das gerade, wie du das gemeint hast.
Was meinst du mit dass sich das "mit der Eigenschaft" auf die Definition des minimalen Graphen bezieht
Und was meinst du mit Zuerst hatte ich es nämlich so verstanden, dass man Graphen betrachtet, die sowohl minimal sind, als auch die danach erklärte Eigenschaft haben.
Irgendwie seh ich dazwischen grad keinen Unterschied mehr... :-(
LG, Nadine
|
|
|
| |
|
Hallo Pacapear!
> Hallo Bastiane.
>
> > Ich glaub', ja. Allerdings bin ich nicht ganz sicher. Soll
> > das denn oben quasi die Definition sein, also soll es
> > heißen, dass sich das "mit der Eigenschaft" auf die
> > Definition des minimalen Graphen bezieht? Zuerst hatte ich
> > es nämlich so verstanden, dass man Graphen betrachtet, die
> > sowohl minimal sind, als auch die danach erklärte
> > Eigenschaft haben. Was das minimal dann bedeuten sollte,
> > wüsste ich aber auch nicht.
>
> Also je mehr ich darüber nachdenke, desto weniger verstehe
> ich das gerade, wie du das gemeint hast.
Oje. Meinst du, ich weiß jetzt noch, wie ich das gestern verstanden habe? ...
> Was meinst du mit dass sich das "mit der Eigenschaft" auf
> die Definition des minimalen Graphen bezieht
Also, hiermit meinte ich wohl, dass das, was da steht, die Definition des minimalen Graphen ist. So nach dem Motto: "Ein Graph heißt minimal, wenn er die folgende Eigenschaft hat..."
> Und was meinst du mit Zuerst hatte ich es nämlich so
> verstanden, dass man Graphen betrachtet, die sowohl minimal
> sind, als auch die danach erklärte Eigenschaft haben.
Naja, und hier wäre die Definition für minimal schon woanders gegeben gewesen, so dass man sie hier voraussetzt und einen Graphen nimmt, der sowohl minimal ist, als auch die folgende Eigenschaft hat. Demnach wären das zwei Eigenschaften, nämlich die der Minimalität und die im Zitat erwähnte. Im anderen Fall wäre es nur eine einzige Eigenschaft, nämlich die der Minimalität, die hier aber erst definiert wird.
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:04 So 23.08.2009 | | Autor: | felixf |
Hallo Nadine,
> Ich verstehe die Bedeutung der Eigenschaft minimal bei
> Graphen nicht so wirklich.
>
> Hier habe ich einen kleinen Auszug, in dem der Begriff
> vorkommt:
>
> Wegen seines hübschen Beweises bringen wir noch einen Satz
> über die Anzhal von Graphen [mm]G[/mm], die minimal sind mit der
> Eigenschaft, dass [mm]G[/mm] bei jeder 2-Kantenfärbung ein
> einfarbiges Exemplar eines vorgegebenen Graphen [mm]H[/mm] enthält
> - einen zu [mm]H[/mm] isomorphen Teilgraphen also, dessen Kanten
> alle die gleiche Farbe tragen. Solche Graphen [mm]G[/mm] nennen wir
> Ramsey-minimal für [mm]H[/mm].
>
> Vielleicht erstmal zum ersten "minimal".
>
> Was bedeutet das?
>
> Geht es da um den kleinsten Graphen, den man finden kann,
> der bei jeder 2-Kantenfärbung (was das ist, weiß ich noch
> nicht) ein solches einfarbiges Exemplar enthält?
Ja, genau das ist gemeint.
LG Felix
|
|
|
|
