Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 2. September 2014 

Wege, Pfade, Zyklen und Kreise in Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Definitionen

Sei G =( V E ) ein (gerichteter) (Multi-) Graph und W =( v 1 ... v n ) eine Folge von Knoten aus V mit der Eigenschaft dass für alle i aus {1 ... n -1} gilt:

d.h. v i und v i +1 sind durch eine Kante verbunden. Dann bezeichnet man W als ungerichteten Weg in G falls G ungerichtet ist und als gerichteten Weg in G falls G gerichtet ist. Eine andere Bezeichnung für ist Kantenfolge . Den Knoten v 1 nennt man Startknoten von W und den Knoten v n Endknoten von W . Ferner bezeichnet man W statt als Weg spezieller als

  • Pfad falls alle Knoten in der Folge W voneinander verschieden sind d.h. falls für i und j aus {1 ... n } gilt dass v i v j falls i j .
  • Zyklus falls Start- und Endknoten von W identisch sind d.h. falls v 1 = v n .
  • Kreis falls nur Start- und Endknoten von W identisch sind d.h. falls v 1 = v n und für alle i und j aus {1 ... n -1} gilt dass v i v j falls i j .

Bemerkung: Jeder Kreis Zyklus und Pfad einem Graphen G ist also auch ein Weg und Kreis ist auch ein Zyklus in G . Wege Pfade Zyklen und Kreise definiert alternativ auch über Kantenzüge oder Teilgraphen .

In ungerichteten Wegen und Pfaden bezeichnet den Startknoten meist ebenfalls als Endknoten. In und Kreisen verwendet man die Bezeichnungen Startknoten Endknoten meist nicht.

Sind A und B Teilmengen von V so bezeichnet man einen Weg als A-B-Weg falls der Startknoten in A und der Endknoten in B liegt. Statt von einem { v }-{ w }-Weg spricht man auch von einem v-w-Weg .

Zwei Wege W 1 =( v 1 1 ... v 1 k ) und W 2 =( v 2 1 ... v 2 l ) heißen kreuzungsfrei knotendisjunkt oder einfach nur disjunkt falls es kein Paar ( i j ) mit i aus {2 ... k -2} und j aus {2 ... l -2} gibt so dass v 1 i = v 2 j d.h. wenn sie keine inneren Knoten haben. Eine Menge von Wegen nennt man kreuzungsfrei knotendisjunkt oder disjunkt wenn die Wege paarweise disjunkt sind. Zwei Wege W 1 =( v 1 1 ... v 1 k ) und W 2 =( v 2 1 ... v 2 l ) heißen kantendisjunkt falls es kein Paar ( i j ) mit i aus {1 ... k -1} und j aus {1 ... l -1} gibt so dass v 1 i = v 2 j und v 1 i +1 = v 2 j +1 . Eine Menge von Wegen nennt man kantendisjunkt wenn die Wege paarweise kantendisjunkt sind. Eine Menge von a - B -Wegen nennt man einen a-B-Fächer wenn die Wege paarweise nur den a gemeinsam haben.

Ein Zyklus oder Kreis heißt trivial wenn er weniger als 3 Knoten Triviale Kreise oder Zyklen werden meist nicht

Ein Kreis der genau 3 Knoten nennt man oft Dreieck . Ein Graph ohne Dreieck nennt man dreiecksfrei .

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit n -1 die Länge eines Weges (oder Pfades) und mit n die Länge eines Zyklus (oder Kreises) ( v 1 ... v n ). Anschaulich zählt man also die Anzahl Kanten.

In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen

Als Taillenweite eines Graphen bezeichnet man die Länge kürzesten nicht trivialen Kreises. Falls der Graph Kreis besitzt so setzt man die Taillenweite unendlich.

Als Abstand oder Distanz zweier Knoten bezeichnet man die Länge kürzesten Weges zwischen diesen. Falls ein solcher existiert so setzt man den Abstand auf Man beachte dass in gerichteten Graphen der von der Richtung des Pfades abhängt. Im gibt es sogar nur in eine Richtung gerichteten Pfad. Den größten Abstand zwischen zwei in einem Graphen G nennt man Durchmesser von G .

Der Distanzgraph zu einem Graphen G =( V E ) bezeichnet den vollständigen (d.h. je zwei Knoten sind durch Kante verbunden ggf. in gerichteten Graphen in Richtungen wobei es aber keine Schleifen gibt) Graphen auf der Knotenmenge V der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten G zuordnet.

wichtige Algorithmen

Der Algorithmus von Dijkstra findet einen kürzesten Pfad zwischen zwei Knoten in einem (kantengewichteten) Graphen. Mit seiner lässt sich auch der Distanzgraph bestimmen indem ihm ausgehend von jedem Knoten den Abstand jedem anderen bestimmt. Für jeden Knoten ist nur ein Aufruf des Algorithmus Dijkstra nötig dieser auch den Abstand von einem Knoten allen anderen Knoten bestimmen kann.

Der Distanzgraph ist für das Problem des Handlungsreisenden interessant da dieser metrisch ist weshalb verschiedene Approximationsalgorithmen dieses Problem wenigstens annähernd lösen können die Lösung auf dem Distanzgraphen in der ausreicht.

Siehe auch: Zufallspfad



Bücher zum Thema Wege, Pfade, Zyklen und Kreise in Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Taillenweite_(Graphentheorie).html">Wege, Pfade, Zyklen und Kreise in Graphen </a>