|
|
| Zeile 1: |
Zeile 1: |
| − | ===Begriffserklärung===
| + | #[[Einführung in die Graphentheorie]] |
| − | Ein '''Graph''' ist ein Netzwerk aus Knoten und verbindenden Strecken, den so genannten Kanten.
| + | #[[Dijkstra-Algorithmus]] |
| − | Die '''Knoten''' (Kreise) stellen Orte, Bauteile oder Aktivitäten dar. Die '''Kanten''' (Linien) verbinden die Knoten untereinander und charackterisieren Entfernungen, zeitliche Abstände, oder Stückzahlen.
| + | |
| − | | + | |
| − | | + | |
| − | Kann ein Graph nur in einer Richtung durchlaufen werden, so spricht man von einem '''gerichteten''' Graphen. Die Kanten werden in diesem Fall als Pfeile dargestellt.
| + | |
| − | | + | |
| − | '''Vollständige''' Graphen zeichnen sich dadurch aus, dass alle Knoten direkt miteinander verbunden sind; andernfalls spricht man von unvollständigen Graphen.
| + | |
| − | | + | |
| − | Ein '''planarer''' Graph ist dadurch gekennzeichnet, dass sich alle Kanten überschneidungsfrei zeichnen lassen. Somit kann z.b. ein vollständiger Graph mit mehr als 4 Knoten niemals planar sein. Er wird als nichtplanar bezeichnet.
| + | |
| − | | + | |
| − | Des Weiteren wird ein Graph als '''Baum''' bezeichnet, wenn jeder Knoten des Graphen von jedem anderen aus über genau einen Weg zu erreichen ist.
| + | |
| − | | + | |
| − | | + | |
| − | '''Beispiele'''
| + | |
| − | *Dies ist ein vollständiger Graph mit 5 Knoten. Jeder Knoten ist direkt mit allen anderen Knoten verbunden. Da sich die Kanten überschneiden ist er nichtplanar.
| + | |
| − | | + | |
| − | | + | |
| − | {| class="center"
| + | |
| − | | [[bild:Graph1.jpg]]
| + | |
| − | |-
| + | |
| − | |''Abb. 1''
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | *Dies ist ein gerichteter Graph mit 6 Knoten. Die Kanten überschneiden sich nicht, somit ist er planar, allerdings unvollständig.
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | {| class="center"
| + | |
| − | | [[bild:Graph2.jpg]]
| + | |
| − | |-
| + | |
| − | |''Abb. 2''
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | ===Teile eines Graphen===
| + | |
| − | Graphen können wiederum in verschiedene Einzelteile untergliedert werden (vgl. HMM 7.1):
| + | |
| − | * '''Kette''': Der Graph ist ungerichtet und linear angeordnet (siehe Abbildung 3.1).
| + | |
| − | * '''Pfad''': Der Graph ist gerichtet und linear angeordnet (siehe Abbildung 3.2).
| + | |
| − | * '''Masche''': (siehe Abbildung 3.3).
| + | |
| − | * '''Schleife''': (siehe Abbildung 3.4).
| + | |
| − | | + | |
| − | | + | |
| − | {| class="center"
| + | |
| − | | [[bild:GraphenVersch.jpg]]
| + | |
| − | |-
| + | |
| − | |''Abb. 3''
| + | |
| − | |}
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | Die Anzahl der Kanten (m) eines Graphen ergeben sich bei einem Baum zu: <center>'''m = n-1'''</center>
| + | |
| − | | + | |
| − | Ein vollständiger Graph hat <center>'''m = n*(n-1) / 2''' </center> Kanten.
| + | |
| − | | + | |
| − | <center>(mit n = Anzahl der Knoten)</center>
| + | |
