• Increase font size
  • Default font size
  • Decrease font size

Graphen

Drucken
Graphen können als geordnete Paare (E, K) aufgefasst werden, wobei die Werte des Paares einmal die endliche Menge der Ecken E und die endliche Menge der Kanten K sind. Jede Kante ist eindeutig durch 2 Ecken definiert und stellt deren Verbindung dar. Es werden weiterhin gerichtete und ungerichtete Graphen unterschieden. Gehören 2 Ecken zu einer Kante, so heißen die Ecken adjazent (benachbart).


Die Nachbarn der Knoten innerhalb eines Netzes lassen sich über eine Adjazenzmatrix bzw. über eine Adjazenzliste erfassen. Das Haus des Nikolaus wäre ein Beispiel für einen ungerichteten Graphen Eine Adjazenzliste für dieses Beispiel würde folgende Form haben. Dabei wäre die Adjazenzliste aus Implementierungsgründen geordnet.

0 -- 1, 2, 3, _              |0 1 1 1 0|
1 -- 0, 2, 3, _              |1 0 1 1 0|
2 -- 0, 1, 3, 4              |1 1 0 1 1|
3 -- 0, 1, 2, 4              |1 1 1 0 1|
4 -- 2, 3, _, _              |0 0 1 1 0|                                        
                                                                                                  
Um eine Implementierung durchzuführen, ist es möglich eine Klasse Matrix zu generieren oder entsprechende Funktionen zu importieren. In diesem Zusammenhang bietet sich die Bibliothek numpy an, welche Operatoren für Matrizen zur Verfügung stellt. Die beispielhaften Implementierungen basieren auf dem Import dieser Bibliothek.

Tiefensuche

Um zu überprüfen, ob alle Knoten im Graphen erreichbar sind, ist es notwendig, den Graphen zu traversieren. Die bekanntesten Suchverfahren sind hierbei die Breitensuche und die Tiefensuche. Eine Umsetzung der Tiefensuche in vereinfachten Pseudocode hätte folgendes Aussehen.

        besuche (Startknoten)
       
        markiere der besuchten Knoten als abgearbeitet
        und wiederhole für alle Nachbarn des Knotens
               wenn der Knoten nicht bereits abgearbeitet wurde dann    besuche (Nachbarn)

Damit wäre die rekursive Implementierung möglich, die im Endeffekt folgendes Aussehen in Python hätte.

                                                                                                                                                       

01   def ts (self) :  
02                 self.abgearbeitet = []  
03                 for i in range (0,9): self.abgearbeitet.append(0)  
04                 return self.__besuche(1)   
05  
06   def __besuche (self)    :  
07                 self.abgearbeitet  = 1  
08                 aktuell               = self.l .get_start() # Adjazenzliste 
09                    
10                 while aktuell != None :  
11                      if not self.abgearbeitet [aktuell.get_value()]:       
12                                            self.__besuche (aktuell.get_value())    
13                      aktuell = aktuell.next 

Auch die iterative Variante ist für die Tiefensuche kein Problem. Allerdings wird hier eine Datenstruktur zum Verwalten der Nachfolger verwendet, der Stack. Ein Import dieses Objektes ist folgerichtig notwendig. Beginnend mit einem Startknoten, werden dessen Nachbarn auf einen Stack gepackt, der Startknoten selber in eine Liste für abgearbeitete Knoten. Im Anschluß daran wird der oberste Knoten vom Stack genommen, der Liste zugefügt und seine Nachbarn werden auf den Stack gepackt. Ist der Stapel leer wird die Suche beendet.

Die nichtrekursive Tiefensuche entspricht dem preorder Durchlauf. Allerdings kommt es durch die Bearbeitung der Nachfolger mittels eines Stacks zu einer Verdrehung der Nummern.


   Script zur Graphentheorie [unvollständig]

 

(c) g-ymnasium.de 2006 - 2013 + Administrator