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.

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

2 Responses

Stephan says:

14/06/2010 at 20:50

Ich verstehe nix!

Gar nix!
Silvia says:

11/11/2017 at 14:01

Danke für die Zusammenfassung!

Graphentheorie 1×1

2 Responses