Graphen-Isomorphismus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:20 Do 15.12.2005 | | Autor: | heine789 |
Hallo Leute!
Wir haben an der FH jetzt mit der Graphentheorie begonnen, und nun habe ich ein paar Fragen dazu.
Ich muss bei zwei Grafen entscheiden, ob diese isomorph sind.
Anzahl der Knoten, Kanten und Grade ist bei beiden Grafen gleich.
Und zwar jeweils 4 Knoten mit Grad 2 und 4 Knoten mit Grad 3.
Mir ist klar, dass ich nun eine Abbildung finden muss. Aber wie mache ich dies nun am besten? Alle Knoten vom Grad 2 werden ja im zweiten Graphen auch auf Knoten vom Grad 2 abgebildet. Aber das macht 16 Möglichkeiten. Muss ich die wirklich alle probieren oder gibt es noch eine andere Möglichkeit? (Benachbarte Knoten hab ich ebenfalls überprüft. Also wenn z.B. Knoten vom Grad 2 im ersten Graph benachbart sind, so sind sie es auch im zweiten Graph)
2. Frage 
Ich soll alle nicht isomorphen und zusammenhängende Graphen mit vier Knoten zeichen.
Zusammenhängend heisst doch, dass ich bei einer Rechteck-Darstellung jeden Knoten mit jedem Knoten verbinden muss, oder? Somit erhalte ich 6 Kanten. Dann hat doch mein Graph 6 Äquivalenzrelationen, nämlich die Anzahl der Verbindungen (Kanten)???
Wäre sehr dankbar, wenn mir jemand Klarheit verschaffen könnte.
Gruß heine
|
|
| |
|
Hallo heine,
zu 1): Leider bleibt Dir momentan nichts essentiell besseres, als -potentiell- alle
Moeglichkeiten auszuprobieren. Du solltest allerdings versuchen, fruehzeitig zu erkennen,
wenn Dein jeweils momentaner Suchpfad nicht zu einem Isom. fuehrt (in dem Stile: '' wenn
ich Knoten a von Graph G auf a' von H mappe und .., dann wuerde z auf was abgebildet, das keinen Isom. mehr liefert.
Sowas nennt man Cut-verfahren: schneide Teilb"aume des Suchbaumes so frueh wie
moeglich ab.
Grund: Graphenisomorphie ist komplexitaetstheoretisch schwer in dem Sinne, dass ein
effizientes Verfahren fuer das Problem unerwartete komplexitaetstheor. Konsequenzen haette.
Zu (2): zush. heisst wegzusammenh., d.h.
o---o
|
o---o ist zushgd. und nicht isomorph zu
o
|
o--o
|
o
Hoffe, es hilft weiter !
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:35 Fr 16.12.2005 | | Autor: | heine789 |
Vielen Dank für die Beantwortung meiner Fragen.
Zu 1 habe ich die Lösung durch "probieren" gefunden.
Zu 2: Wenn ich das richtig verstehe, muss ich einfach nur alle möglichen Graphen mit vier Knoten finden, die nicht isomorph zueinander sind.
Gruß heine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:53 Sa 17.12.2005 | | Autor: | heine789 |
| Aufgabe | | Zeichnen Sie alle nicht isomorphen und zusammenhängende Graphen mit vier Knoten. Wie viele Äquivalenzklassen gibt es? |
Also: Ich habe 5 Möglichkeiten gefunden:
o - - - - - - o
|
|
|
o - - - - - - o
o - - - - - - o
| |
| |
| |
o - - - - - - o
o - - - - o
| \ /|
| \ / |
| / \ |
o o
o - - - - o
| \ /|
| \ / |
| / \ |
o - - - - o
o - - - - o
| \ /
| \ /
| / \
o o
Sind das nun auch meine Äquivalenzklassen???
Gruß heine
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:19 So 18.12.2005 | | Autor: | felixf |
> Zeichnen Sie alle nicht isomorphen und zusammenhängende
> Graphen mit vier Knoten. Wie viele Äquivalenzklassen gibt
> es?
> Also: Ich habe 5 Möglichkeiten gefunden:
>
> [...]
>
> Sind das nun auch meine Äquivalenzklassen???
Also, wenn schon, dann sind es Repraesentanten der Aequivalenzklassen. Eine Aequivalenzklasse hast du allerdings noch unerwaehnt gelassen (ist ein Graph mit 3 Kanten).
LG Felix
|
|
|
|
