www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Graphen-Isomorphismus
Graphen-Isomorphismus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graphen-Isomorphismus: Fragen zu isomorphen Graphen
Status: (Frage) beantwortet Status 
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

        
Bezug
Graphen-Isomorphismus: Antwort
Status: (Antwort) fertig Status 
Datum: 08:20 Fr 16.12.2005
Autor: mathiash

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

Bezug
                
Bezug
Graphen-Isomorphismus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Graphen-Isomorphismus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Graphen-Isomorphismus: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]