Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:58 Sa 07.01.2006 | | Autor: | heine789 |
Hallo zusammen!
Habe zwei Fragen zur Graphentheorie:
1)
Wie kann ich zeigen, dass zwei Graphen NICHT isomorph sind obwohl sie
- gleiche Anzahl Knoten/ Kanten besitzen
- die Anzahl der Grade für jeden Knoten gleich ist
- Nichtbenachbarte Knoten sich auf Nichtbenachbarte Knoten abbilden lassen
Ich kann ja jetzt nicht alle Möglichkeiten durchprobieren (6 Knoten, 9 Kanten), es muss also noch eine Möglichkeit geben.
2)
Ich habe einen Graphen gegeben, und nun soll ich begründen, ob dieser planar oder nicht planar ist.
Planar hieße ja, dass sich keine Kanten in der graphischen Darstellung schneiden dürfen.
Ich müsste dazu bei meinem gegebenen Graphen eine Kante "biegen" um zu zeigen, dass der Graph planar ist.
Darf ich das machen? Ist die Begründung ausreichend?
Würde mich über eine Antwort sehr freuen!
Gruß heine
|
|
| |
|
Hallo heine789,
> 2)
> Ich habe einen Graphen gegeben, und nun soll ich
> begründen, ob dieser planar oder nicht planar ist.
Eine vollständige Antwort kann ich dir leider nicht geben. Aber über Google habe ich ![[]](/images/popup.gif) folgende Diskussion dazu gefunden. Die Stichwörter dort sind 'Satz von Kuratowski' und 'Eulerformel'. Eventuell könnte sich damit noch etwas finden lassen.
Viele Grüße
Karl
|
|
|
| |
|
Hallo,
zu (2) moechte ich Karl ausdruecklich zustimmen: Eine Charakterisierung planarer
Graphen gibt der Satz von Kuratowski, der sagt, dass ein Graph planar ist gdw. er keinen
[mm] K_5 [/mm] und keinen [mm] K_{3,3} [/mm] als Minor hat.
Zu (1): Letztlich bleibt im allg. nur Durchprobieren, da Graphenisomorphie ein
komplexitaetstheoretisch scheres Problem ist und effiziente Verfahren nicht bekannt
sind.
Um detailierter antworten zu koennen, muesste man Dein Beispiel kennen.
Komisch klingt ''die Anzahl der Grade fuer jeden Knoten gleich''. Leben die Graphen
[mm] G_1 [/mm] und [mm] G_2 [/mm] auf derselben Knotenmenge V ? Aber ein Isomorphismus muesste nicht notwendig die Identitaet auf V sein. Und [mm] \forall v,w\in [/mm] V [mm] deg_{G_1}(v)=deg_{G_1}(w)
[/mm]
hiesse bei 6 Knoten und 9 Kanten Knotengrad identisch gleich 3. Ist das gemeint ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:03 Mo 09.01.2006 | | Autor: | heine789 |
Ja, der Knotengrad aller Knoten von G1 und G2 ist 3.
Bei dem Graphen G1 handelt es sich sogar um den [mm] K_{3,3}.
[/mm]
G2 sieht so aus (ein Rechteck mit zwei Dächern):
0
/ | \
0 - - - - - - 0
| | |
| | |
| | |
0 - - - - - - 0
\ | /
0
Es soll also gezeigt werden, dass die Graphen nicht isomorph sind.
Hast du eine Idee?
Gruß heine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:07 Di 10.01.2006 | | Autor: | mathiash |
Hallo,
jou, das ist relativ schmerzfrei zu machen: [mm] K_{3,3} [/mm] als bipartiter Graph hat keine Kreise
ungerader Laenge, Dein anderer Graph hat aber Kreise der Laenge 3.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:18 Di 10.01.2006 | | Autor: | heine789 |
Vielen Dank für deine Hilfe!
Also kann man sagen, dass wenn ein Graph G1 Kreise der Länge n besitzt, ein isomorpher Graph G2 auch einen Kreis der Länge n besitzen muss.
Oder?
Gruß heine
|
|
|
| |
|
Absolut richtig. Genauer gesagt: Er muss dann genau so viele Kreise der Laenge n besitzen.
Gruss,
Mathias
|
|
|
|
