AuK/Graphrepräsentationen WS13-14

Wiki-Quelltext dieser Seite.

;Autoren
:[mailto://s3hakret@stud.hszg.de Hannes Kretschmer]<br/>
:[mailto://s3juhils@stud.hszg.de Julian Hilsberg]


=Grundbegriffe der Graphentheorie=


=Datenstrukturen für Graphen=

==Operationen für Graphen==
Die Wahl der Darstellung eines Graphen muss immer im Bezug auf die mit den Daten durchzuführenden Operationen erfolgen. Die Operationen sind problemabhängig. 
Die wichtigsten Operationen für Graphen sind:
<ul>
<li>Feststellen, ob ein Paar von Ecken benachbart ist.</li>
<li>Bestimmung der Nachbarn einer Ecke.</li>
<li>Bestimmung der Nachfolger und Vorgänger einer Ecke in einem gerichteten Graphen.</li>
</ul> 

Neben der Effizienz der Operationen spielt auch der Speicherplatzverbrauch eine große Rolle, bei der Wahl einer Datenstruktur.