Diskussion:Co-Graph

Das angegebene Beispiel

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)

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

$G=(1\times 1)\cup ((1\cup 1)\times (1\cup 1))$.

Der rechte Operand des äußeren $\cup$ ist hier das Quadrat. --Daniel5Ko 20:23, 29. Aug. 2011 (CEST)

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)

Danke! Das sollten wir im Artikel ausführen. Ich werde mich eventuell demnächst darum kümmern.--FerdiBf 21:04, 29. Aug. 2011 (CEST)

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)

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)

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)