Schlagwort-Archive: allgemeies

Allgemeines und Ergänzungen

zurück zu Allgemeines

Allgemeines

Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Viele algorithmische Probleme können auf Graphen zurückgeführt werden können und andererseits werden die Lösung graphentheoretischer Probleme oft in Algorithmen umgesetzt, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie und in der Netzwerktheorie von großer Bedeutung.

Ein Graph ist eine Menge von Punkten (Knoten oder Ecken), die durch Linien (Kanten bzw. Bögen) miteinander verbunden sein können. Prinzipiell unterscheidet man in:

  • endlichen Graphen, bei denen die Menge der Knoten und Kanten endlich ist
  • unendlichen Graphen
  • gerichteten Graphen, bei denen die Kanten gerichtet sein können (dargestellt durch Pfeile statt Linien)
  • ungerichteten Graphen

Komplexere Graphen sind z.B.: Multigraphen, bei denen im Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen und Hypergraphen, bei denen im Gegensatz zu einfachen Graphen Kanten mehr als nur zwei Knoten verbinden können. Knoten und Kanten können auch mit Farben oder Gewichten versehen werden (knoten- bzw. kantengefärbte oder -gewichtete Graphen).

Ergänzungen

Unter 3 Isomorphie wird die Darstellung in einer Adjazenzmatrix ausgeführt. Eine Alternative dazu wäre die Adjazenzlistendarstellung, wobei für jeden Knoten alle adjazenten Knoten in einer linearen Liste gespeichert werden. Diese ist geeignet, für Graphen mit wenigen Kanten. Linearer Speicheraufwand – gut; dfs gut, Rechenaufwand O(|V|+|E|); nicht geeignet zur Überprüfung von Adjazenzeigenschaften.

(316)