Glossar Graphentheorie

	Achtung!
	Der Glossar ist obsolet und wird dann gelöscht, wenn die anderweitige Unterbringung der Informationen und der Rückbau der Redundanzen (so weit wie sinnvoll) und das anschliessende Entlinken abgeschlossen ist. Die ursprüngliche Version des Glossars wurde nach Wikibooks exportiert.  Wikibooks: Mathematik-Glossar: Graphentheorie – Lern- und Lehrmaterialien

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht signifikant verbessert werden können. Bitte hilf mit und beteilige dich an der Diskussion!

Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen.

Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B

Bandbreite

Die Bandbreite (engl. bandwidth, siehe auch Bandbreite) eines endlichen, schlichten, ungerichteten Graphen ist wie folgt definiert: Sei $L: V \to\{1,\ldots,n\}$ eine eineindeutige Nummerierung der Knoten. Dann bezeichnet $\max_{\{i,j\}\in E} |L(i)-L(j)|$ die Bandbreite bezüglich $L$ und $\min_L \max_{\{i,j\}\in E} |L(i)-L(j)|$ die Bandbreite des Graphen $(V,E)$.

Die Ermittlung der Bandweite ist eines der wenigen Probleme, das auch für Bäume NP-vollständig ist.

D

Dichte

Die Dichte $dn(G)$ eines einfachen Graphen $G=(V, E)$ ist das Verhältnis seiner Kantenzahl zur Kantenzahl eines vollständigen Graphen auf gleichvielen Knoten, das heißt:

$dn(G)=\frac{2|E|}{|V|(|V|-1)}.$

F

Faktor

Ist $G=(V, E)$ ein Graph und $g$ eine Abbildung seiner Knoten auf natürliche Zahlen, ist ein $g$-Faktor $F$ ein Teilgraph von $G$ mit derselben Knotenmenge V wie $G$, in dem jeder Knoten $x$ von $F$ genau $g(x)$ Nachbarn hat, also den Grad $g(x)$ besitzt.

Gilt für alle Knoten $x$ die Bedingung $g(x) = a$, besitzen also alle Knoten genau $a$ Nachbarn, spricht man dementsprechend auch von einem $a$-Faktor.

Gilt dagegen für alle Knoten $x$ die Bedingung $a \leq g(x) \leq b$, besitzen also alle Knoten mindestens $a$ und gleichzeitig höchstens $b$ Nachbarn, spricht man entsprechend von einem $[a,b]$-Faktor.

Beispiele

Eine Paarung ist ein $[0,1]$-Faktor, also ein Teilgraph von $G$, in dem jeder Knoten $x$ höchstens einen Nachbarn hat, eine perfekte Paarung dagegen ein 1-Faktor, also ein Teilgraph von $G$, in dem jeder Knoten $x$ genau einen Nachbarn besitzt. Hamiltonsche Graphen schließlich besitzen 2-Faktoren, in denen jeder Knoten $x$ genau zwei Nachbarn hat.

Der 1-Faktor-Satz von Tutte besagt, dass man aus $G$ und $g$ einen Graphen $G^*$ konstruieren kann, welcher genau dann einen 1-Faktor besitzt, wenn $G$ einen $g$-Faktor besitzt. Dies ist die Definition einer Reduktion im Sinne der theoretischen Informatik. Da umgekehrt 1-Faktoren Spezialfälle von $g$-Faktoren sind, ist das $g$-Faktorproblem äquivalent zum 1-Faktorproblem.

Faktorisierung

Zerlegung eines Graphen $G$ in $g$-Faktoren, z. B. bei der 1-Faktorisierung in 1-Faktoren, d. h. Teilgraphen, deren Knoten nur jeweils genau einen Nachbarn haben.

Faktor-kritisch

Ein Graph $G$ mit $G\neq \emptyset$ heißt faktor-kritisch, wenn durch Wegnahme eines beliebigen Knoten eine perfekte Paarung möglich wird.

Fluss

Ein Fluss zu einem gerichteten Graphen und Kantenkapazitäten ist eine Funktion $f$ von den gerichteten Kanten auf die nichtnegativen reellen Zahlen. Ein Fluss darf jeder Kante nur einen Wert zuweisen, der höchstens so groß ist wie die Kapazität der Kante.

Spricht man von einem s-t-Fluss, muss ferner für jeden Knoten $x$ (außer für die Quelle $s$ und die Senke $t$) gelten, dass die Summe der Flüsse auf den hineinführenden Kanten gleich der Summe der Flüsse auf den hinausführenden Kanten ist.

Formal: $\forall x\in V\setminus \{ s,t \} : \sum_{e\in \delta^-(x)}f(e) = \sum_{e\in \delta^+(x)}f(e)$

Anschaulich: aus keinem Knoten (außer $s$ und $t$) kann mehr herausfließen als hineinfließt und alles, was in einen Knoten hineinfließt, fließt auch wieder heraus.

G

Geordneter Baum

Ein geordneter Baum ist ein Wurzelbaum, in dem für die Söhne jedes Knotens eine Ordnungsrelation definiert ist. Anschaulich legt die Ordnung fest, in welcher Weise die Nachfolger eines Knotens in der grafischen Darstellung des Baumes angezeigt werden (z. B. von links nach rechts gemäß Ordnungskriterium). Formal wird durch die Ordnung festgelegt, in welcher Reihenfolge die Knoten bei unterschiedlichen Traversierungsverfahren (preorder, inorder, postorder) durchlaufen werden.

Gradfolge

Als Gradfolge eines Graphen $G = (V, E)$ mit den Knoten $v_1, v_2, \ldots, v_n \in V$ bezeichnet man die Folge natürlicher Zahlen $d_1, d_2, \ldots, d_n$, welche jeweils den Grad der einzelnen Knoten angeben, d. h. $deg(v_i) = d_i$ für alle $i = 1, 2, \dots, n$. Eine solche Folge natürlicher Zahlen heißt auch graphisch, wenn tatsächlich mindestens ein Graph existiert, der diese Gradfolge aufweist.

Graphisch

Als graphisch bezeichnet man eine Folge natürlicher Zahlen, welche die Gradfolge eines Graphen ist.

H

Hamiltonabschluss

Der Hamiltonabschluss (oder Hülle; $n$-Hülle) eines Graphen $G=(V, E)$ ist der Obergraph (oder Supergraph) von $G$ mit identischer Knotenmenge und zusätzlich iterativ eingefügten Kanten, welche nicht-adjazente (oder nicht-benachbarte; nicht-verbundene) Knoten mit Gradsumme $\geq n=|V|$ miteinander verbinden, so lange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

Homöomorphie

Zwei Graphen heißen homöomorph, falls sie isomorph sind oder einen gemeinsamen Unterteilungsgraphen haben. Zwei Graphen sind genau dann homöomorph, wenn ihre Homöomorphie-Ursprünge isomorph sind. Anschaulich bedeutet dies, dass zwei homöomorphe Graphen aus einem gemeinsamen Ursprungsgraphen durch Einfügen neuer Knoten vom Grad 2 in bereits existierende Kanten hervorgehen.

Homöomorphie-Ursprung

Der Homöomorphie-Ursprung $HU(G)$ eines Graphen $G=(V, E)$ ist der kleinste Graph, zu dem $G$ homöomorph ist. Man berechnet $HU(G)$ mit dem folgenden Algorithmus:

1. Falls $G$ keinen Knoten vom Grad 2 besitzt (abgesehen von isolierten Knoten die nur eine Schleife besitzen) so ist $HU(G)=G$.
2. Wähle einen Knoten $x$ vom Grad 2 (außer isolierte Knoten mit einer Schleife) mit den beiden Nachbarn $y$ und $z$ (auch $y=z$ ist möglich)
3. Entferne $x$, füge dafür eine Kante von $y$ nach $z$ ein.
   Formal: $G \leftarrow (V\setminus \{x\},E\cup \{\{y,z\}\})$
4. gehe zu 1

I

Inzidenzrelation

Zur Definition sehr allgemeiner, nämlich ungerichteter Graphen mit Schlingen (Kanten von einem Knoten zu sich selbst) und parallelen Kanten (Mehrfachkanten) reicht die vereinfachende Graphendefinition $G = (V, E)$ mit $e \in E := \{u, v\}$ mit $u, v \in V$ nicht aus, denn hier müssten z. B. in $E$ Duplikate erlaubt sein. Man führt daher eine Inzidenzrelation ein und benennt die Elemente aus $E$ mit einem eindeutigen Namen $e \in E$, der nicht von den Knoten der Kante abhängt. Mittels solcher eindeutiger Elemente können nun auch Mehrfachkanten und Schlingen definiert werden. Die Inzidenzrelation wird dann definiert als $I \subseteq V \times E$, d. h. zu jedem Knoten wird für jede Kante, die ihn berührt, ein Element $\{v, e\}$ mit $v \in V$ und $e \in E$ in $I$ aufgenommen. Schlingen werden somit über jeweils ein Element der Inzidenzrelation, zwei parallele Kanten über vier Elemente der Inzidenzrelation eindeutig repräsentiert.

K

k-Baum

Ein ungerichteter Graph heißt k-Baum, wenn er wie folgt rekursiv erzeugbar ist:

• Der vollständige Graph $K_k$ ist ein k-Baum.
• Fügt man zu einem k-Baum $G$ einen neuen Knoten $v$ hinzu, indem man $v$ mit allen Knoten einer Clique der Größe k aus $G$ verbindet, so ist dieser neue Graph ebenfalls ein k-Baum.

Ein partieller $k$-Baum entsteht durch die Entfernung von Kanten aus einem $k$-Baum: Ist $G = (V, E)$ ein $k$-Baum, so ist $H = (V, F)$ mit $F \subseteq E$ ein partieller $k$-Baum.

Gelegentlich werden auch Bäume mit dem maximalen Grad $k$ als $k$-Bäume bezeichnet. Korrekter ist in diesem Fall die Bezeichnung $k$-närer Baum.

Kantenfeld

Ein Kantenfeld ist eine Darstellungsart für gerichtete Graphen nach folgendem Schema:

$|V|, |E|, E_1,\ldots, E_{|E|}$

wobei $|V|$ die Anzahl der Knoten, $|E|$ die Anzahl der Kanten und $E_1, \ldots, E_{|E|}$ die Kanten sind mit $E_i = (v, w) \in E$.

Kantenüberdeckung

Eine Kantenüberdeckung in einem ungerichteten Graphen $G = (V, E)$ ist eine Menge $E' \subseteq E$ mit der Eigenschaft, dass jeder Knoten von $V$ in einer Kante aus $E'$ enthalten ist.

$E'$ ist Kantenüberdeckung in $G$ gdw. $\forall v \in V, \exists w \in E': v \in w$.

Kantenunterteilung

Eine Unterteilung einer Kante ist das Einfügen eines Knotens in die Kante

Formal: Ist $G=(V, E)$ ein Graph und $k=\{x, y\} \in E$, so entsteht $G'$ durch Unterteilung von $k$ als $G'=(V \cup \{z \notin V\}, E \setminus \{k\} \cup \{\{z,x\},\{z,y\}\})$. Die Voraussetzung $z\notin V$ ist für die formale Korrektheit notwendig.

Knotenfeld

Ein Knotenfeld ist eine Darstellungsart für gerichtete Graphen mit folgendem Aufbau:

$|V|, |E|, \text{ag}(V_1), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_1)}, \ldots, \text{ag}(V_{|V|}), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_{|V|})}$

wobei $|V|$ die Anzahl der Knoten, $|E|$ die Anzahl der Kanten und $ag(V)$ Ausgangsgrad des Knotens sind.

P

Partieller k-Baum

Siehe: k-Baum.

Partition

Sei $G=(V, E)$ ein Graph. Eine Zerlegung (Partition) der Knotenmenge $V$ in $p$ disjunkte Teilmengen $V_1...V_p$ heißt $p$-Partition, falls keine adjazenten Ecken in einem gemeinsamen $V_i$ liegen. (Anschaulich heißt das: Alle Kanten verlaufen zwischen diesen Teilmengen, keine innerhalb einer der Teilmengen.)

• Besitzt ein Graph $G$ eine $p$-Partition, so sagt man auch „$G$ ist $p$-partit“ oder „$G$ ist ein $p$-partiter Graph“.
• Die chromatische Zahl von $G$ ist das kleinste $p$, sodass $G$ eine $p$-Partition besitzt (färbe alle Elemente einer Partitionsmenge mit der gleichen Farbe).
• In der Praxis arbeitet man häufig mit Paarungen in bipartiten (2-partiten) Graphen.

Perfekte Eliminationsordnung

Als perfekte Eliminationsordnung bezeichnet man eine Knotenreihenfolge $(v_1, v_2, \ldots, v_n), V = \{v_1, v_2, \ldots, v_n\}$ des Graphen $G = (V, E)$, so dass für jeden Graphen mit der (durch Eliminierung der Knoten $v_1$ bis $v_{i-1}$) eingeschränkten Knotenmenge $G_i = (\{v_i, \ldots, v_n\}, E_i)$ gilt: $v_i$ ist simplizial in $G_i$. Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in $G_i$ bildet also mit seinen Nachbarn eine Clique. Dies gilt beispielsweise für alle Blätter eines Baums, so dass ein sukzessives Eliminieren von Blättern eines Baums eine perfekte Eliminationsordnung für diesen Baum liefert.

R

Rückwärtskante

Siehe: Vorwärtskante.

S

Sehne

In einem Graphen $G$ bezeichnet Sehne eine Kante von $G$, die zwei Knoten eines Kreises in $G$ verbindet, selbst jedoch nicht Teil des Kreises ist.

Semieulerscher Graph

Ein Graph heißt semieulersch, wenn in ihm ein Eulerweg existiert. Eine Eulertour ist zwar ebenfalls ein Eulerweg, aber in der Regel meint man mit „semieulersch“ dass keine Eulertour existiert, da man in diesem Fall von einem eulerschen Graphen sprechen würde.

U

Unterteilungsgraph

Ein Unterteilungsgraph F eines Graphen G entsteht aus diesem durch Kantenunterteilung.

V

Valenzsequenz

Siehe: Gradfolge.

Vergleichbarkeitsgraph

Ein (gerichteter) Vergleichbarkeitsgraph ist ein gerichteter Graph, dessen Kanten einer Ordnungsrelation auf seinen Knoten entsprechen. Sei beispielsweise $O = (V, <)$ eine Halbordnung auf der Knotenmenge $V$ des Graphen $G = (V, E)$, so gilt für jede Kante $(u, v) \in E$ die Beziehung $u < v$.

Von einem ungerichteten Vergleichbarkeitsgraphen spricht man, wenn für jede Kante $(u, v) \in E$ gilt: ($u < v$ oder $v < u$).

Vorwärtskante

Der Begriff Vorwärtskante hat ebenso wie die Begriffe Rückwärtskante, Querkante und Baumkante im Kontext der Tiefensuche in Graphen eine Bedeutung. Bei einer Tiefensuche werden die Kanten des Graphen, welche vom Tiefensuche-Algorithmus zum Durchlaufen des Graphen benutzt werden, als Baumkanten bezeichnet. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche später besucht wird, heißen Vorwärtskanten. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche bereits vorher besucht wurde, heißen Rückwärtskanten. Diejenigen Kanten, die „quer“ von einem Teilbaum zu einem anderen Teilbaum verlaufen, heißen Querkanten. Innerhalb des Tiefensuchbaums würde der Pfad zwischen zwei über eine Querkante verbundenen Knoten zunächst ein Auf- und dann ein Absteigen im Baum erfordern. Vorwärtskanten, Rückwärtskanten, Querkanten und Baumkanten ergeben insgesamt die Kantenmenge des Graphen.

W

Wegüberdeckung

Eine Menge disjunkter Wege in einem gerichteten Graphen $G$ mit der Eigenschaft, dass jeder Knoten von $G$ auf einem dieser Wege liegt, heißt Wegüberdeckung.