Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

 
Aug 01, 2017 - 06:47 PM


Select language
Preferred language:


Online
There are 1 unlogged user and 0 registered users online.

You can log-in or register for a user account here.

Anmeldung




 


 Log in Problems?
 New User? Sign Up!



Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Author Message
rgerhardsOffline
Post subject: Geordneter Graph als Tupel  PostPosted: Nov 30, 2008 - 04:25 PM



Joined: Sep 25, 2006
Posts: 688

Status: Offline
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 Wink

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 Wink) 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 Wink

Viele Grüße,
Rainer
 
 View user's profile Send private message  
Reply with quote Back to top
Display posts from previous:     
Jump to:  
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Powered by PNphpBB2 © 2003-2007 The PNphpBB Group
Credits
:: RSS Feed: ::
Page created in 0.133412837982 seconds.

Ferientips - das Urlaubsweb - Jan Gerhards - Ulrike Gerhards - Ulrike Gerhards Foto Site