Diskussion:Co-Graph

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 13 Jahren von FerdiBf in Abschnitt Das angegebene Beispiel
Zur Navigation springen Zur Suche springen

Das angegebene Beispiel

[Quelltext bearbeiten]

Ich schlage vor, kurz den Aufbau des angegebenen Beispielgraphen an Hand der angegebenen Regeln zu beschreiben; handelt es sich überhaupt um ein korrektes Beispiel? Wie kann man das Quadrat mittels dieser Regeln erzeugen? --FerdiBf 18:53, 29. Aug. 2011 (CEST)Beantworten

Ich musste auch erst 'ne Weile überlegen, aber so geht's, den Graphen in der Abbidung zu erzeugen (1 bezeichne die Operation, die einen Graphen nach Regel 1 erzeugt, mit einem "frischen" Knoten und ohne Kanten):
.
Der rechte Operand des äußeren ist hier das Quadrat. --Daniel5Ko 20:23, 29. Aug. 2011 (CEST)Beantworten
Vielleicht wär's auch besser, den Graphen anders hinzumalen, etwa so:
o----o   1 x 1

o    o   <- diese Zeile ist 1 u 1
|\  /|
| \/ |   die Kanten hier entstehen durch die disjunkte Summe
| /\ |
|/  \|
o    o   <- diese Zeile ist 1 u 1
--Daniel5Ko 20:35, 29. Aug. 2011 (CEST)Beantworten
Danke! Das sollten wir im Artikel ausführen. Ich werde mich eventuell demnächst darum kümmern.--FerdiBf 21:04, 29. Aug. 2011 (CEST)Beantworten

Eine Bitte an den Autor Shager: Könntest Du bitte im Stile Deines letzten Beitrags auch eine Herleitung für das oben angegebene Beispiel eines Co-Graphen einfügen. Wie Du dieser Diskussion entnehmen kannst, war zumindest mir nicht unmittelbar klar, wie sich ein Quadrat konstruieren lässt. Vielleicht geht es anderen Lesern auch so. Dazu könnte man obige Herleitung von Daniel5Ko noch dahingehend verbessern, dass man die zwei 1 u 1 - Graphen nicht zeilenweise übereinander zeichnet sondern jeweils als diagonal gegenüberliegende Ecken eines Quadrates. Dann entsteht beim letzten Übergang zur disjunkten Summe das Quadrat als überkreuzungsfreier Graph, aber das natürlich nur Geschmachssache. --FerdiBf 21:42, 31. Aug. 2011 (CEST)Beantworten

Hmm, ich hatte es ja extra deswegen so hingemalt, weil bei der Bildung der disjunkten Summe jeder Knoten des einen Operanden mit jedem Knoten des anderen verbunden wird. Solche Graphen kann man fast auf einen Blick als solche identifizieren, und ab mehr als jeweils 2 Knoten geht's ohnehin nicht mehr kreuzungsfrei. --Daniel5Ko 22:49, 31. Aug. 2011 (CEST)Beantworten
Klingt vernünftig, dann stellen wir es mit Überkreuzung dar. Das hat auch den Vorteil, dass gleichzeigt deutlich wird, dass wir hier eigentlich über Isomorphieklassen von Graphen reden. Ich wiederhole meine Bitte an den Autor Shager, die Konstruktion des angegebenen Beispiels wie in seinem letzten Beitrag hinzuzufügen.--FerdiBf 20:51, 1. Sep. 2011 (CEST)Beantworten