Graphentheorie 1×1

04 Jun



Begriff

Erklärung

Abstand

Die Länge des kürzesten Weges von einem Knoten zum anderen oder unendlich, falls kein solcher Weg existiert.

adjazent

Zwei Knoten sich durch eine Kante verbunden (benachbart).

Algorithmus

Systematisches Rechenverfahren, das zu einer Eingabe nach endlich vielen Schritten ein Ergebnis liefert.

Ameisenintelligenz“

Globale Eigenschaft durch lokale Betrachtung bestimmen.

bipartit

Die Knotenmenge lässt sich in zwei disjunkte Teilmengen aufsplitten, wobei die Kanten nur zwischen den Mengen und nicht in den Mengen verlaufen.

Briefträgertour

Es existiert ein Weg, der jede Kante mindestens einmal durchläuft und zum Ausgangspunkt zurückkehrt.

Brücke

Eine Kante, deren Entfernen eine Komponente in zwei einzelne Komponenten aufspaltet.

 d^-(v)

Ingrad von v (Anzahl der Kanten, die auf v zeigen; nur bei gerichteten Graphen)

d(v)

Knotengrad von v (Anzahl der inzidenten Kanten; nur bei ungerichteten Graphen)

 d^+(v)

Außengrad von v (Anzahl der Kanten, die ihren Ursprung in v haben; nur bei gerichteten Graphen)

DAG

Directed Acyclic Graph; ein Digraph, welcher keine gerichteten Kreise enthält

Digraph

gerichteter Graph

Durchmesser

Der maximale Abstand zwischen zwei Knoten

E

endliche Kantenmenge (eng: edge)

eulersch

alle Knotengrade sind gerade

Eulertour

Es existiert ein Kreis, der jede Kante genau einmal durchläuft.

gerichteter Graph

die Kanten bestehen aus Pfeilen, mit einem Anfangs- und einem Endpunkt (auch Digraph)

Graph

G = (V,E); V = endliche Knotenmenge; E = endliche Kantenmenge, zweielementige Teilmengen von V

Handschlaglemma

Prinzip des doppelten Abzählens

 \sum_{v \in V} \ d(v) 			= 2 \ |E|

inzident

Zwei Kanten haben einen gemeinsamen Knoten. Auch: Eine Kante berührt einen Knoten.

isomorph

Zwei Graphen heißen isomorph, falls sie bis auf die Benennung der Knoten den gleichen Graphen abbilden. (ACHTUNG: Sie können unter Umständen auf den ersten Blick völlig verschieden aussehen.)

Kante

Verbindung zwischen zwei Knoten (auch gerichtet)

Knoten

Anfangs- und/oder Endpunkt einer Kante

Komponente

Ein zusammenhängender (Unter-) Graph

Kreis

Ein Kreis ist ein Weg bei dem der Startknoten gleich dem Endknoten ist.

Multigraph

Es sind auch mehrere Kanten zwischen den gleichen Knoten erlaubt.

negative Gewichte

Um den längsten Weg in einem Graphen zu bestimmen, multipliziert man einfach alle Kantengewichte mit (-1). Jetzt kann man wieder das Kürzeste – Wege – Problem lösen.

Wenn man in einer Route einen Zwischenhalt nur dann anfahren will, wenn er nicht länger als x dauert. Dann belegt man den Zwischenhalt mit einem negativen Knotengewicht -x.

regulär

Ein Graph ist r-regulär, falls alle Knotengrade gleich r sind.

Schlinge

Verbindung eines Knoten mit sich selbst. e = (v,v)

stark zusammenhängend

ein gerichteter Graph bei dem jeder Knoten von jedem anderen aus erreicht werden kann

Teilgraph

besteht aus einer Teilmenge der Knotenmenge und einer Teilmenge der Kantenmenge des Graphen

Untergraph

enthält eine Teilmenge der Knotenmenge und alle im Graphen dazwischen laufenden Kanten

V

endliche Knotenmenge (engl. vertex)

vollständig

Ein Graph heißt vollständig, wenn er alle möglichen Kanten besitzt. Man schreibt  			K_{|V|}

Weg

Ein Weg in G besteht aus einer Folge von Knoten die über Kanten nach und nach durchlaufen werden. Die Länge des Weges ist die Anzahl der durchlaufenen Kanten.

zusammenhängend

Es ist möglich, über die vorhandenen Kanten von jedem Knoten zu jedem anderen Knoten zu gelangen.

Lemmata

  • Ein Graph G mit |V| >= 2 ist genau dann bipartit, wenn er keine Kreise ungerader Länge als Teilgraphen enthält.

Algorithmen

Eulertour- Algorithmus von Fleury

  • EINGABE: Eulerscher Multigraph  G = (V, E)
  • S1  Wähle einen beliebigen Knoten  v_0 und setze  W_0 = v_0
  • S2  Sei  W_i ein Kantenzug von  v_0 bis  v_i . Wähle die nächste Kante so, dass sie mit  v_i verbunden ist. Solange es Alternativen gibt, wähle die nächste Kante so, dass der Zusammenhang des Graphen nicht zerstört wird. (Also keine Brücke wählen.)
  • S3  Führe S2 solange durch, bis alle Kanten abgelaufen wurden.
  • AUSGABE: Eulertour in G

 

 

 

 

 

 

One Response

  1. Stephan says:

    Ich verstehe nix!

    Gar nix!

Leave a Reply