Isomorphie: Graphisomorphien erkennen, Argumente für Nichtisomorphie von Graphen formulieren

Question

Aufgabe 1: Isomorphie
Anliegen der folgenden Aufgabenstellung ist es, Graphisomorphien zu erkennen bzw. Argumente für die Nichtisomorphie von Graphen zu formulieren.

a) Wieviele paarweise nichtisomorphe Graphen mit 6 Knoten gibt es, die zusammenhängend und bipartit sind? Stellen Sie eine Liste auf, in der jeder Isomorphietyp genau einmal vertreten ist.
Hinweis: Primäre Fallunterscheidung bezüglich der Kreise die in den Graphen auftreten
(Kreislänge und Anzahl).

b) Wieviele paarweise nichtisomorphe, zusammenhängende, induzierte Untergraphen
des Würfelgraphen Q₃ gibt es? Stellen Sie auch hier eine entsprechende Liste auf.
Hinweis: Primäre Fallunterscheidung bezüglich der Anzahl der Knoten in den Untergraphen.

Answer 1

Also im Prinzip steht die Lösung schon fast auf dem Übungszettel.

Schreib mal auf welche Kreise es geben kann in einem Graphen der Ordnung 6.

Welche davon kannst du sofort ausschließen? Stichwort hier wäre dann bipartit!

Und dann ist es gar nicht mehr so schwer, denn jetzt kommt es halt auf die Anzahl der Kreise an.

Gruß

Conde

Comments

ja...kannst du mir deine Lösungen zeigen, damit ich es mit meine vergleichen kann

und für b.)

---

Poste deine Lösung, dann kann ich dir vielleicht sagen ob sie richtig ist.

---

Hihi, glaube nicht, dass er da mit irgendeiner Lösung in Vorleistung geht ...

---

bin zwar nicht der Anon, wollte aber mal schauen was ihr sagt :]

 

Ps der obige Ahnung, ist quasi schon berühmt berüchtig ;)

---

Sehr schön. Ich denke, dass man hier nichts mehr ergänzen kann. Zweifarbige Knoten könnten noch zeigen, wie die Knoten auf die beiden Teilmengen aufgeteilt sind.

---

4 und 8 sind isomorph

---

Die meisten in dem Bild sind aber nicht bipartit. Oder irre ich mich?

---

Doch sind sie, kannst ja mal mit 2 farben knoten zu markieren.

Ja 4 und 8.... was nen fail, nicht gemerkt und sogar noch untereinander gemalt.

 

Naja habe gehört es soll 17 geben, fehlen also in der oberen Zeichnung noch 3 ;)

---

https://de.wikipedia.org/wiki/Bipartiter_Graph

Angesichts der erklärung auf wiki, verstehe ich auch nicht wie "._._._._._." bipartit sein soll. Wie soll ich denn da 2 teilmengen draus bilden?

 

Mir ists noch beim schreiben klargeworden..
 

hier für die ersten beiden kurzerhand, netterweise, unfarbig und schlampig in paint gemacht:

---

Wäre irgendwer so freundlich und erklärt was würfelgraphen sind? (aufgabenstellung b)

---

Also es steht schon im Skript gut erklärt, dann hast du anscheinend in der Vorlesung nicht gut aufgepasst:

Lass es mich so erklären

Derjenige Graph, der entsteht, wenn man die Elemente der Menge {0,1}^n (n feste natürliche Zahl) als Knoten interpretiert und je zwei von diesen genau dann durch eine Kante verbindet,

wenn sie sich in genau einer Komponente unterscheiden.

Dies entrspicht in der Geometrie den Ecken und Kanten eines Hyperwürfels.

 

Ich hoffe ich konnte dir helfen :)

---

Ah danke! Gefunden!

 

Nochmal zu a: Bin ich der einzige der da mittlerweile an die 20 möglichkeiten hat?

---

korrektur: an die 30