Nichtisomorphe Graphen finden

15.04.2010, 22:37

gitterrost4

Nichtisomorphe Graphen finden

Hallo. Ich habe hier eine Aufgabe und weiss nicht so recht, wie ich da rangehen soll. Die Aufgabe lautet:

Finde moeglichst viele nichtisomorphe Graphen mit 7 Knoten, sodass der Grad jedes Knotens 4 betraegt.

(Der Grad ist die Anzahl der adiazenten Kanten)
Hierzu ist noch zu sagen, dass wir Graphen stets schlingenfrei und ungerichtet betrachten. Ebenso duerfen keine Mehrfach-Kanten auftreten.

Ich habe durch Probieren schon 3 Graphen gefunden, die nicht isomorph sind. Ich weiss nur nicht, wie ich mehr finde oder beweise, dass es alle sind. Hierbei moechte ich moeglichst nicht alle Graphen durch Bruteforce erzeugen und auf isomorphie testen.

Zur Referenz die Kantenmengen der drei Graphen:

$\begin{eqnarray*} K_1=\{ (1,2),(1,4),(1,5),(1,7),(2,3),(2,5),(2,6),(3,4),(3,6),(3,7),(4,5),(4,7),(5,<br /> 6),(6,7)\} \end{eqnarray*}$
$\begin{eqnarray*} K_2=\{ (1,2),(1,3),(1,6),(1,7),(2,3),(2,4),(2,7),(3,4),(3,5),(4,5),(4,6),(5,6),(5,<br /> 7),(6,7)\} \end{eqnarray*}$
$\begin{eqnarray*} K_3=\{ (1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,7),(3,6),(3,7),(4,6),(4,7),(5,<br /> 6),(5,7)\} \end{eqnarray*}$

Aber wie finde ich weitere und vor allem: Wie beweise ich, dass ich alle habe?

(Wieso wird denn das tex so unmoeglich umgebrochen?)

Gruss gitterrost4

15.04.2010, 23:49

Abakus

Auf diesen Beitrag antworten »

RE: Nichtisomorphe Graphen finden

Zitat:

Original von gitterrost4
Aber wie finde ich weitere und vor allem: Wie beweise ich, dass ich alle habe?

Hallo!

Meine erste Idee hier ist wie folgt: um einen solchen Graphen zu bestimmen, musst du 14 Kanten aus 21 Kanten auswählen und dabei noch die Nebenbedingung mit dem Grad beachten.

Stattdessen könntest du auch nur die 7 "fehlenden" Kanten auswählen, wobei hier jeder Knoten den Grad 2 haben müsste. Jeder solche Graph würde genau einen der gesuchten Graphen bestimmen.

Vielleicht ist der Umgang mit diesen 7-kantigen Graphen ja einfacher, nachdenken müsstest du hier über ein Kriterium zur Isomorphie und natürlich die Anzahl der Möglichkeiten.

Grüße Abakus smile

16.04.2010, 09:07

gitterrost4

Auf diesen Beitrag antworten »

Auf die Idee, den Komplementgraphen zu betrachten, bin ich noch gar nicht gekommen. Wenn ich mich nicht taeusche, bekomme ich doch, wenn jeder Knoten Grad 2 hat, eine Menge von echten Kreisen? (der Koomplementgraph muss janicht mehr zusamenhaengend sein). Und je nach dem, wie viele Kreise ich bekomme und welche Laenge sie haben, sind die Graphen isomorph oder eben nicht.

Erstmal Danke dafuer!

Gruss, gitterrost4

16.04.2010, 09:17

Mystic

Auf diesen Beitrag antworten »

RE: Nichtisomorphe Graphen finden
Edit: Sorry, hier stand teilweise Unsinn.

16.04.2010, 09:29

gitterrost4

Auf diesen Beitrag antworten »

Meine Graphen waren bisher alle relativ regelmaessig. (Teilmengen der Diagonalen eines 7-Ecks). Allerdings hat sich (mithilfe der Komplementgraphen) gerade eine Bijektion zwischen zwei meiner Graphen ergeben, zwischen denen ich eine Bijektion ausgeschlossen hatte ( $\begin{eqnarray*} K_1\text{ und }K_2 \end{eqnarray*}$ ).

Die Loesung der Aufgabe ist nun so:
Da zwei Graphen isomorph sind genau dann wenn ihre Komplementgraphen isomorph sind, genuegt es zu betrachten, wie man disjunkte echte Kreise in einen Graphen mit 7 Knoten legen kann.

Ein echter Kreis hat mindestens 3 Knoten. Es bleiben also nur folgende Moeglichkeiten uebrig:

Der Komplementgraph besteht aus 1 Hamiltonkreis (wenn ich mich nicht taeusche) durch alle 7 Knoten: Dann ist der Graph isomorph zu $\begin{eqnarray*} K_1 \end{eqnarray*}$
oder
Der Komplementgraph besteht aus einem Kreis der Laenge 4 und einem Kreis der Laenge 3: Dann ist der Graph isomorph zu $\begin{eqnarray*} K_3 \end{eqnarray*}$

Danke fuer den Denkanstoss!

16.04.2010, 10:11

Reksilat

Auf diesen Beitrag antworten »

RE: Nichtisomorphe Graphen finden

Zitat:

Original von gitterrost4
(Wieso wird denn das tex so unmoeglich umgebrochen?)

Ein Leerzeichen im Code kann Wunder wirken. Augenzwinkern

$\begin{eqnarray*} K_1=\{(1,2),(1,4),(1,5),(1,7), (2,3),(2,5),(2,6),(3,4),(3,6),(3,7),(4,5),(4,7), (5,6),(6,7)\} \end{eqnarray*}$

Gruß,
Reksilat.

17.04.2010, 22:32

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von gitterrost4
Ein echter Kreis hat mindestens 3 Knoten. Es bleiben also nur folgende Moeglichkeiten uebrig:

Der Komplementgraph besteht aus 1 Hamiltonkreis (wenn ich mich nicht taeusche) durch alle 7 Knoten: Dann ist der Graph isomorph zu $\begin{eqnarray*} K_1 \end{eqnarray*}$
oder
Der Komplementgraph besteht aus einem Kreis der Laenge 4 und einem Kreis der Laenge 3: Dann ist der Graph isomorph zu $\begin{eqnarray*} K_3 \end{eqnarray*}$

Ja, bis dahin war ich auch. Das mit der Isomorphie hätte ich nochmal genauer anschauen müssen, aber das scheinst du hier gut gemacht zu haben. Insgesamt ist es überraschend, dass es doch nur 2 sind dann.

Grüße Abakus smile

17.04.2010, 23:09

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Abakus
Insgesamt ist es überraschend, dass es doch nur 2 sind dann.

Ist lustig, denn ich war eher überrascht, dass es immerhin 2 nichtisomorphe 4-reguläre Graphen mit 7 Knoten gibt... Augenzwinkern

Nachdem ich nämlich nach einem kurzen Blick auf $\begin{eqnarray*} K_1 \end{eqnarray*}$ und $\begin{eqnarray*} K_2 \end{eqnarray*}$ gesehen hatte, dass für sie der 2-reguläre Komplementgraph eulersch ist, war ich zunächst dem Fehlschluß erlegen, dass dies allgemein aus der 2-Regularität folgt...Tatsächlich müssen aber natürlich nur die Zusammenhangskomponenten eulersch (mit überschneidungsfreien Eulertouren) sein, was dann sofort auch auf den zweiten Fall führt...

Neue Frage »

Antworten »

Nichtisomorphe Graphen finden

Verwandte Themen