Dualität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:01 Di 21.02.2006 | | Autor: | Tyr7 |
Hallo Zusammen,
ich habe eine Frage zur Dualität, abstrakter Dualität und Whitney Dualität.
Ganz genau interessiert es mich, wo die einzelnen Unterschiede zwischen den drei Arten liegen.
(F - Fläche, E - Kanten, V - Knoten)
G - normaler Graph
G* - dualer Graph
Dualität ist ja so definiert, dass es eine Bijektion zwischen F -> V*, E -> E* und V -> F* gibt, und dass Kreise in G zu inklusionsminimalen Schnitten in G* werden und umgekehrt.
Abstrakte Dualität ist so definiert, dass es eine Bijektion zwischen E -> E* gibt und ebenso Kreise in G zu Schnitten in G* werden.
Liegt der Unterschied zwischen Dualität und abstrakter Dualität nur darin, dass bei abstrakter Dualität keine Bijektion zwischen F -> V* und V -> F* verlagt wird? Sonst scheint es für mich das Gleiche zu sein...
Bei der Whitney Dualität wird ebenfalls eine Bijektion zwischen den Kanten verlangt und die Erfüllung einer Formel mit der zykomatischen Zahl und der kozyklomatischen Zahl.
Dass Kreise in G zu Schnitten in G* werden folgt aber aus einem Beweis, dass wenn G* abstrakt dual ist, so ist G* auch Whitney dual und umgekehrt.
Es wäre schön, wenn mir jemand paar erklärende Worte zu dem Zusammenhang zwischen den drei Arten geben könnte und vielleicht wozud as ganz gut ist.
Vielen Dank und viele Grüße
Tyr
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
also zuerst gibt es die Dualitaet bei planaren Graphen, wie Du sie auch als erstes beschrieben hast.
(1) Dualitaet planarer Graphen
[mm]G=(V,E)[/mm] planarer Graph, [mm]F[/mm] die Menge der Flaechen, dann ist
[mm]G^{\star} =\left(V^{\star},E^{\star}\right)[/mm] mit [mm]F^{\star}[/mm] der duale Graph mit
[mm]V^{\star} =F[/mm]
[mm]E^{\star} =\left\{\left\{f_1,f_2\right\}\: |\: f_1,f_2\in F\texttt{ haben gemeinsame Kante}\right\}[/mm]
Dann gilt aber nicht immer, dass [mm]E[/mm] auf [mm]E^{\star}[/mm] bijektiv abgebildet werden kann
(Bsp: Graph mit drei beschraenkten und einer äusseren Flaeche, zwei der beschraenkten Flaechen umschliessen
die dritte und haben zwei Kanten gemeinsam:
[Dateianhang nicht öffentlich]
[....]
Hab jetzt ein bißchen geschmökert, also bei obigem Beispiel kriegt der Duale Graph dann zwei Kanten zw. den
beiden umschliessenden Flaechen (sog. Pseudo-Graph).
Also bei mathworld findet man die Begriffe zusammengefasst:
Obiges heisst Geom. Dual, und man definiert zunaechst, dass ein Graph [mm]H[/mm] abstrakt dual (combinatorial dual graph)
zu einem Graphen [mm]G[/mm] ist, falls das gilt, was Du auch in Deiner Frage schreibst:
(aus Mathworld)
[mm]G^{\star}[/mm] comb. dual of [mm]G[/mm] iff there is a one-to-one correspondence of [mm]E[/mm] and [mm]E^{\star}[/mm] (d.h. Bijektion) such that
for every choice of subsets [mm]Y[/mm] from [mm]E[/mm] and corresponding [mm]Y^{\star}[/mm] from [mm]E^{\star}[/mm],
[mm]m^{\star}(G-Y)=m^{\star}(G)-m\left(G^{\star}\left[Y^{\star}\right]\right)[/mm]
wobei [mm]m(G)[/mm] der cycle rank ist, [mm]m^{\star}(G)[/mm] der cocycle rank, [mm]G-Y[/mm] ist der Graph mit Knotenmenge [mm]V[/mm] und Kantenmenge
[mm]E\setminus Y[/mm], und [mm]G^{\star}\left[Y^{\star}\right][/mm] ist der Teilgraph von [mm]G^{\star}[/mm] mit Kantenmenge [mm]Y^{\star}[/mm].
Whitney hat nun gezeigt, dass die Begriffe Geometrisches Dual und Kombinatorisches Dual aequivalent sind.
Insbesondere ist ein Graph planar genau dann, wenn er einen kombinatorisch dualen Graphen hat.
ggf. spaeter noch mehr dazu.
Gruss,
Mathias
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:47 Mi 22.02.2006 | | Autor: | Tyr7 |
Hallo und vielen Dank,
ich habe die Sachen aus Mathworld gesehen, aber irgendwie hilft mir das nicht weiter, um die Zusammenhänge zwischen den Arten der Dualität zu verstehen.
Meine Überlegung ist, dass die Dualität dazu benutzt wird, um entscheiden zu können, ob ein Graph planar ist oder nicht.
Dabei ist egal welche Art der Dualität ist benutze, da alle aequivalent sind.
Da gibt es einmal die "normale" (planare) Dualität, für die es nur eine Konstruktionsvorschrift gibt.
Durch diese Konstruktion wird bei einem planaren und zusammenhängendem Graphen eine Bijektion zwischen den Kanten und zwischen Knoten und Flächen erzeugt. Das geht nur bei planaren und zusammenhängenden Graphen. Bei nicht zusammenhängenden Graphen kann die Knoten bzw. Flächenanzahl unterschiedlich sein. Die Kantenzahl bleibt aber gleich nach der Konstruktion (oder doch nicht? @Mathiash: konnte das an dem Graphen, den Du gemalt hast, ganz gut hinbekommen). Bei nicht planaren Graphen ist die Kantenzahl unterschiedlich.
Daher führe ich den Begriff der akstrakten Dualität, wo ich nur eine Bijektion zwischen den Kanten verlange. Falls das zutrifft, so kann ich sagen, dass der Graph planar ist. (Hier muss noch diese Beziehung zwsichen den Kreisen und Schnitten vorhanden sein, die auch bei der normalen Dualität vorhanen ist) Also: hat G ein abstraktes Dual, so ist G planar.
Um das Ganze etwas greifbarer zu machen, gibt es jetzt eine Whitney-Dualität, die verlangt, dass es eine Bijektion zwsichen den Kanten gibt, so dass für jeden aufspannenden Teilgraphen H [mm] \subseteq [/mm] G und dem Bild H* [mm] \subseteq [/mm] G* gilt:
m(H) + m*(!H*) = m*(G*)
(für m und m* verwende ich die Definition aus mathworls, also m = zyklomatische zahl, m* = kozyklomatische Zahl)
!H* ist das Komplement von H* bzgl. G*
Also wird hier erstmal keine Planarität vorausgesetz wie es bei der normalen Dualität der Fall war und ich muss nicht die Kreise und Schnitte untersuchen.
Falls bei jedem Teilgraphen von G diese Bedingung erfüllt ist, so kann ich sagen, dass der Graph G Whitney-dual ist und somit auch abstrakt-dual und damit auch planar.
Macht diese Überlegung einen Sinn?
Was mich ein wenig stört, ist die Aussage vom Dozenten, dass die Begriffe abstrakte Dualität und Whitney-Dualität eingeführt wurden, um die Beschränkung auf planare Graphen auszuweiten, was aber nicht gelungen ist. Somit gilt es für jede Art von Dualität, dass der Graph planar sein muss. Also ist das eine andere Vorgehensweise oder Motivation, als die, die ich oben beschrieben habe.
Viele Grüße
Tyr
|
|
|
| |
|
Hallo nochmal,
also ich werde mich bemuehen, nochmal ausfuehrlich zu antworten, aber dazu wird es erst heute spaeter oder morgen frueh kommen. Vorab aber schon mal: Also meiner Kenntnis nach wird Dualitaet nicht direkt fuer Planaritaetstests benutzt.
Dualitaet ist einfach ein ganz natuerliches und altes Konzept, ich werde mal recherchieren, ob es da DIE Motivation
fuer Graph-Dualitaet gibt.
Gruss + bis bald,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:47 Do 23.02.2006 | | Autor: | mathiash |
Hallo nochmal,
auch noch keine umfassende Antwort, aber eine Erklaerung dessen, was laut Deiner Schilderung
Euer Dozent gesagt hat:
Zunaechst gibt es ja die Dualitaet planarer Graphen: Flaechen werden zu Knoten, Kanten entsprechen Kanten und Knoten werden zu Flaechen. Das kann man einfach malen.
Frage war dann: Kann man auch fuer nicht-planare Graphen einen sinnvollen Begriff des Dualen Graphen definieren ?
Versuch war dann die abstrakte und Whitney-Dualitaet. Das schien sinnvoll zu sein.
Allerdings stellte sich heraus, dass abstr. Dualitaet im wesentlichen dasselbe ist wie die planarer Graphen, und ein
Graph hat genau dann einen abstrakt dualen Graphen, wenn er planar ist.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:27 Do 23.02.2006 | | Autor: | Tyr7 |
Hallo Mathiash,
genau so wurde aus auch ausgedrueckt, wie Du es gesagt hast. :)
Da man die Dualitaet auf eine groessere Klasse der Graphen ausweiten wollte, hat man die abstrakte Dualitaet eingeführt. Nach meiner Idee, muessten in diesem Fall die Kriterien etwas lockerer sein als bei der planaren Dualitaet. Dort galt:
1) V -> F*
2) F*-> V
3) E -> E*
4) Kreise -> Schnitten*
5) Schnitte -> Kreise*
Die Abschwaechung bei der abstrakten Dualitaet sehe ich in dem Wegfall von Bedingung 1) und 2). Haette ja auch Sinn machen koennen, da bei nicht planaren Graphen mehr Flaechen vorhanden sind, wenn sich die Kanten schneiden.
Da aber bewiesen wurde dass:
G hat abstraktes dual <-> G ist planar
wurde noch die Whitney Dualitaet eingefuehrt, wo auch die Bedingung 4) und 5) nicht vorhanden sind, stattdessen aber diese Formel mit zyklomatischen und kozykolmatischen Zahl. Das Ergebnis war aber das Gleiche.
Langsam wird mit der Sinn des Ganzen im Skript klar. Es sollte einfach dargestellt werden, was es fuer Arten von Dualitaet gibt ohne diesmal einen praktischen Nutzen darzustellen (alle anderen Beweise bis jetzt lieferten als Endresultat eine Loesung eines Problems).
Ich habe wohl in die falsche Richtung gedacht und wollte unbedingt ein Problem finden, was durch dei Dualitaet geloest werden kann, damit es in mein Bild passt :)
Aber falls ich mich bei meinen Ueberlegungen nicht irgendwo vertan habe, so koennte man doch mit der Whitney Dualitaet die Planaritaet pruefen, ohne malen zu muessen. Dann haette ich "mein Problem", nur dass es nicht die Motivation fuer die Ganzen Ueberlegungen war.
Nochmals herzlichen Dank :) und
Viele Gruesse
Tyr
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:13 Sa 25.03.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
