Graphentheorie

Neue Frage »

RVD Auf diesen Beitrag antworten »
Graphentheorie
hi, ich bin auch nochmal da und habe diesmal fragen zur graphentheorie. ich hoffe auch es macht nichts, dass ich mal 3 aufgaben gleichzeitg schreibe, sind alles 3 solche "zeige"/"beweise" aufgaben und da fehlt mir irgendwie immer die idee wie.


zum einen: Zeigen Sie: In jedem (endlichen) Graphen mit mindestens zwei Knoten gibt es zwei Knoten von gleichem Grad.

klingt und ist ja irgendwie logisch, aber wie zeigt man das?


zum zweiten: Ein Automorphismus auf einem Graphen G ist ein Isomorphismus zwischen G und sich selbst. Ein Graph heißt asymmetrisch, wenn die identische Abbildung (die jeden Knoten auf sich selbst abbildet) der einzige Automorphismus ist.
Finden Sie ein Beispiel für einen asymmetrischen Graphen mit 6 Knoten.


was ein asymmetrischer graph ist hat und ist bei uns auch sonst nirgendwo erklärt. was gibt es denn für einen sinn einen graf zu finden, der sich identisch auf sich selbst abbildet?! ist doch dann exakt der gleiche graf mit anderer bezeichnung der knoten oder wie?


und zu guter letzt: Zeigen Sie, dass jeder Baum ein tripartiter Graph ist.

das is für mich sogar falsch, weil ich nicht wüsste wie ich größere bäume zb der höhe 5 wo jeder knoten 4 nachfolger hat, in 3 dusjunkte mengen aufteilen sollte, dessen kannten nie innerhalb einer dieser gruppen verlaufen.


ich weiß ein bischen was auf einmal, aber ich denke jemandem, der es weiß dürften diese sachen nicht schwer fallen und die fragen vielleicht sogar peinlich finden. danke auf ejden fall schonmal für jede hilfe und anregung =)
WebFritzi Auf diesen Beitrag antworten »

Du hast eindeutig ins falsche Forum gepostet, denn Graphentheorie ist nicht Algebra. Das nächste mal bitte in "Sonstiges" posten. Danke. smile
RVD Auf diesen Beitrag antworten »

nuja gehört bei uns zur linearen algebra, also sowohl im "fach" als auch in meinem lehrbuch wusste also nicht wohin sonst. graphen lassen sich ja auch zb in adjazensmatrizen "umschreiben". aber tut mir leid
Huggy Auf diesen Beitrag antworten »
RE: Graphentheorie
Zitat:
Original von RVD
zum einen: Zeigen Sie: In jedem (endlichen) Graphen mit mindestens zwei Knoten gibt es zwei Knoten von gleichem Grad.

Da würde sich ein Widerspruchsbeweis anbieten.
Zunächst ist offensichtlich, dass es genügt, den Beweis für Graphen ohne Knoten vom Grad 0 zu führen. Das sei im folgenden angenommen.
Wenn alle Knoten verschiedenen Grad hätten, kann man eine Untergrenze für den maximalen Knotengrad angeben. Andererseits kann von jedem Knoten nur eine begrenzte Zahl von Kanten ausgehen, womit man eine Obergrenze für den maximalen Knotengrad hat.

Zitat:
was ein asymmetrischer graph ist hat und ist bei uns auch sonst nirgendwo erklärt.

Die Definition hast du doch selber gerade geben.

Zitat:
was gibt es denn für einen sinn einen graf zu finden, der sich identisch auf sich selbst abbildet?! ist doch dann exakt der gleiche graf mit anderer bezeichnung der knoten oder wie?

Und trotzdem haben solche Automorphismen eine große Bedeutung. Finden sollst du einen Graphen, der außer der Identität keinen weiteren Automorphismus besitzt.

Zitat:
und zu guter letzt: Zeigen Sie, dass jeder Baum ein tripartiter Graph ist.

Da bin ich im Moment ziemlich verwirrt, weil ich den Eindruck habe, dass jeder Baum sogar ein bipartiter Graph ist.
Man unterteile den Baum, beginnend mit einem Endknoten in Ebenen. der Endknoten ist die Ebene 0. Die Menge seiner Nachfolger bilden die Ebene 1, die Menge von deren Nachfolgern die Ebene 2 usw.
Jeder Knoten gehört nur zu einer Ebene, sonst enthielte der Baum einen Kreis. Jetzt sollen die Knoten der Ebenen mit gerader Nummer die Menge A bilden und die der Ebenen mit ungerader Nummer die Menge B.
Innerhalb der Mengen A bzw. B können keine Kanten verlaufen. Denn zwischen Knoten auf einer Ebene können keine Kanten verlaufen, sonst enthält der Graph einen Kreis. Und zwischen Knoten, deren Ebenennummer sich um mehr als 1 unterscheidet, können auch keine Kanten verlaufen, sonst hätte man wieder einen Kreis in dem Graphen
RVD Auf diesen Beitrag antworten »

hi und danke schonmal. also was du mir mit der ersten aufgabe sagen willst, bin ich mir nicht so ganz sicher. es geht also nicht, dass jeder knoten unterschiedlichen grad hat, weil? wieso könnte man eine untergrenze für den maximalen grad angeben?


bei der zweiten aufgabe, weiß ich, dass die definition gegeben war, aber wir hatten dazu kein beispiel und ich wusste nicht was ich mir darunter vorstellen soll. der einzige graph, der mir dann dazu einfällt wäre ein graph, der einfach aus 6 knoten und keinen kannten besteht, weil der einzig mögliche automorphismus darin besteht die knoten auf sich selbst abzubilden. oder seh ich das falsch?


bei der dritten aufgabe hast du irgendwie schon recht. garnicht so eine dumme idee, die ebenen alternierend in 2 Gruppen aufzuteilen, nicht schlecht, bin ich so nicht drauf gekommen. bipartit macht aber ja wie du sagst schon eher sinn, weil tripartit ja nur eine "erweiterung" wäre. vielleicht wurde tripartit genommen, weil es das größtmögliche unter k-partitionen ist, in die sich ein baum auf jeden fal immer einteilen lässt.
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von RVD
hi und danke schonmal. also was du mir mit der ersten aufgabe sagen willst, bin ich mir nicht so ganz sicher. es geht also nicht, dass jeder knoten unterschiedlichen grad hat, weil? wieso könnte man eine untergrenze für den maximalen grad angeben?

Na überleg doch mal. Wenn du n Knoten hast, die alle verschiedenen Knotengrad haben, dann muss der maximale Knotengrad mindestens n sein. Man hätte dann die Knotengrade 1, 2, ..., n. Andererseits kann kein Knoten mit mehr als allen anderen, also maximal n -1, verbunden sein. Der höchste Knotengrad kann höchstens n - 1 sein.
Widerspruch!

Zitat:
bei der zweiten aufgabe, weiß ich, dass die definition gegeben war, aber wir hatten dazu kein beispiel und ich wusste nicht was ich mir darunter vorstellen soll. der einzige graph, der mir dann dazu einfällt wäre ein graph, der einfach aus 6 knoten und keinen kannten besteht, weil der einzig mögliche automorphismus darin besteht die knoten auf sich selbst abzubilden. oder seh ich das falsch?

Das ist falsch. Der geht doch bei jeder Vertauschung der Knoten in sich selbst über, weil vorher jeder Knoten mit keinem anderen verbunden ist und nachher auch nicht.
Ein Beispiel wäre ein Dreick, bei der an einer Ecke noch ein Knoten hängt und an einer zweiten Ecke eine Kette von zwei Knoten.
 
 
RVD Auf diesen Beitrag antworten »

ah, also ist das ein graph, der, wie man es auch dreht und wendet, durch seine vorschriften bzw die nachbarschaftsbeziehungen immer exakt gleich bleibt? in deinem beispiel haben die 3 knoten des dreiecks (nennen wir sie A, B, C) sich als nachbarn und eben 0 bis 2 weitere nachbarn. zb hat A nur B und C als nachbarn, C hat A, B und E als nachbarn und C hat A,B, F und G als nachbarn. es gibt dann also keine möglichkeit die knoten anders anzuordnen oder zu vertauschen.

jetzt richtig verstanden? wie findet man sowas raus? ausprobieren, reine erfahrung oder gibts da doch ein mittel?
Huggy Auf diesen Beitrag antworten »

Ich glaube, die hast meinen Vorschlag leicht mißverstanden. Meine Idee sah so aus:

[attach]10832[/attach]

Wenn man oben statt der 2er-Kette beide Knoten direkt an den Dreiecksknoten anhängt, kann man die beiden angehängten Knoten vertauschen und alle Knoten hätten unverändert dieselben Nachbarn.

Ich kenne für so was kein Rezept. Ich hab einfach etwas herumprobiert.
RVD Auf diesen Beitrag antworten »

ah ok, dann hatte ich es verstanden, aber falsch beschrieben, sorry =)

aber wenn man jetzt bei der zweierkette die beiden knoten vertauscht, ändert sich doch ein nachbar, nämlich der obere dreiecksknoten wechselt doch dann seinen nachbarn
Huggy Auf diesen Beitrag antworten »

Völlig richtig. Aber genau deshalb wäre diese Vertauschung ja kein Automorphismus, weil sich dann bei den Nachbarbeziehungen etwas ändert. Und gesucht ist doch ein Graph, der nur die Identität als Automorphismus hat. Graphen, die mehr Automorphismen haben, sind ja viel leichter zu finden.
Neue Frage »
Antworten »



Verwandte Themen

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