Anmeldung: 25. Sep 2006
Beiträge: 688
|
|
Diesen Beitrag habe ich in der FU Newsgroup geschrieben, möchte ihn aber für mich archivieren. Ausgangspunkt war, was die Definition eines geordneten Graphen G=(N,E) denn eigentlich sei (die Aufgabenstellung wird später nochmals klar, einfach weiter lesen, ich will nicht alles wiederholen...)
Lass mich mal mit G=(N,E) aufgreifen. Ich versuche es kurz und griffig zu definieren, darunter leidet aber bestimmt die Korrektheit 
Das Ganze wird hier in Tupel-Schreibweise aufgeführt. Ein Tupel ist dabei eine "Auflistung" von Elementen. Die einzelnen Elemente heissen Komponenten. Tupel können verschiedene Anzahlen von Komponenten haben. Sie heissen nach der Anzahl (n) n-Tupel. Beispielsweise ist ein 2-Tupel ein Tupel, das aus 2 Komponenten besteht, ein 4-Tupel ein solches, das aus 4 Komponenten besteht. Das 2-Tupel heisst auch geordnetes Paar. Auch für die anderen Tupel gibt es Namen, das 4-Tupel ist z.B. das Quadrupel, das 8-Tupel das Oktet (der Begriff findet sich übrigens in RFCs häufiger als Synonym für "Byte", was will uns das wohl sagen?). Ein geordnetes Paar wird mit runden Klammern geschrieben, und Kommata zwischen den einzelnen Komponenten (also z.B. "(1,2)" für ein 2-Tupel aus 2 Ganzzahlen). Ein bekanntes Beispiel für geordnete Paare in der Mathematik sind Abbildungen. Zum Beispiel könnte (1,2) ein Tupel aus der Abbildungsmenge f(x) = 2x sein.
Der gerichtete Graph G ist nun ein Tupel, dessen einzelne Komponenten wiederum Mengen sind. Wichtiger Unterschied: Nicht die Menge ist ein geordnetes, sondern die einzelnen Elemente der Menge sind geordnete Paare. Um erst mal bei den Integern zu bleiben. So eine Menge wäre das dann z.B. {(1,2),(2,3),(3,4)}.
Die Funktion f(x) = 2x über den natürlichen Zahlen ist bei mengentheoretischer Betrachtung nichts anderes als eine Menge, deren Elemente geordnete Paare sind, und zwar die folgende: {(1,2),(2,4),(3,6),...} Überlege Dir die Konsequenzen noch einmal genau: die Funktion IST also diese Menge. Es gibt nicht zwingend ein prozedurales Element. Die Menge beschreibt vollständig die Funktion.
Nun zum gerichteten Graphen: auch der wird vollständig von einer Menge beschrieben. Definition 9.1.1.1 sagt, dass ein gerichteter Graph eben nichts anderes ist, als ein geordnetes Paar, dessen beide Komponenten wiederum aus Mengen bestehen. Also ähnlich, aber "anders rum" als bei der Funktion f(x) = 2x! So etwas macht man ganz oft in der Informatik, das wird dir immer wieder begegnen (daher lohnt es sich, hier Zeit zu investieren). Die Komponenten sind hier natürlich nicht mehr Ganzzahlen, sondern die erste Komponenten, ist die Menge der Knoten (hier N genannant, oft auch V[Vertex]) und die Zweite die der Kanten (hier E genannt, woanders auch oft genau so).
Die Kantenmenge E selbst ist nun eine Menge, deren einzelne Elemente geordnete Paare sind (diesmal genau wie bei der Funktion f(x) = 2x). Sie stellt eine Teilmenge des kartesischen Produkts von zwei Knotenmengen dar. Ein Paar beschreibt genau eine Kante, und zwar durch den Knoten, von dem sie ausgeht (erste Komponente) und den Knoten, in dem sie mündet (zweite Komponente).
Im Endeffekt wird in der Menge G also nur beschrieben, welche Knoten enthalten sind, und welche Verbindungen zwischen ihnen bestehen.
Mach wir mal ein simples Beispiel mit nur einem Knoten A, der keinerlei Verbindung hat.
Dann ist G = ({A},{}) - beachte, dass {} die leere Menge ist, d.h. es gibt keine Verbindungen (und das war ja unser Ziel).
Nun nehmen wir einen Knoten B dazu und Verbinden A mit B, und zwar in dieser *Richtung*. Nun gilt:
G = ({A,B},{(A,B)})
Beachte, dass die Menge E aus Tupeln besteht. Betrachte den Unterschied zu folgendem Graphen:
G' = ({A,B},{(B,A)})
Was genau ist hier der Unterschied? Dazu muss man beachten, dass Tupel, im Gegensatz zu Mengen, eine Ordnung ihrer Elemente kennen (A,B) ist also verschieden von (B,A). Wir hatten definiert, dass die erste Komponente des Tupels (auch geordnetes Paar genannt ) der Knoten ist, von dem die Kante ausgeht und die Zweite der Knoten, an dem sie "ankommt". Daher geht in G' der Pfeil von B nach A aus, also in umgekehrte Richtung!
Wenn wir nun Pfeile von A nach B und B nach A haben, dann ist das Tupel wieder ein anderes:
G = ({A,B},{(A,B),(B,A)})
... und so kannst Du immer weiter fortfahren. Wichtig ist es, die Bedeutung der Klammern zu beachten: Geschweifte Klammern umschliessen Mengen, runde Tupel.
So, ich hoffe nun, dass es Dir hilft und das es ausserdem noch hinreichend korrekt ist
Viele Grüße,
Rainer |
|
|
| |
|
FAQ
Suchen
Registrieren
Einloggen, um private Nachrichten zu lesen
Login
Forum Maximieren
::