Induziert « brianp.de

Artikel-Schlagworte: „Induziert“

Grundbegriffe der Graphentheorie

Donnerstag, 13. Mai 2010

Ein Graph wird definiert durch $G=\{V, E\}$ wobei V die Menge der Knoten (vertexes) und E die Menge der Kanten (edges) ist.

Induzierter Teilgraph
Ein Teilgraph, bei dem beliebige Knoten mit allen zugehörigen Kanten entfernt wurden. Allerdings bleiben alle Kanten zwischen Knoten erhalten, bei denen beide Knoten auch im Teilgraph enthalten sind!
azyklischen Graphen
Ein Graph ist azyklisch, wenn er gerichtet ist, und keine Zyklen enthält.
Knoten- und Kantenendlichkeit
knotenendlich: $|V| < \infty$
kantenendlich: $|E| < \infty$
-> Jeder knotenendliche Graph ist auch kantenendlich!
-> Nicht jeder kantenendliche Graph ist auch knotenendlich!
Adjazenz
Zwei Knoten heißen adjazent, wenn sie durch eine Kante verbunden sind.
schlichte oder einfache Graphen
Graphen ohne Mehrfachkanten oder Schlingen.
Vorgänger und Nachfolger von Knoten
Sei $v_3$ ein Knoten zu den Kanten von $v_1, v_2$ führen und Kanten zu dem Knoten $v_4$ abgehen.
Sind die Vorgänger (precessor) von $P(v_3) = \{v_1, v_2\}$ und
der Nachfolger (successor) $S(v_3) = \{v_4\}$
Grad eines Knoten
Der Grad eines Knoten ist die Anzahl der Kanten die diesen Knoten berühren, also sowohl ankommende als auch abgehende Kanten. Der Grad wird mit $d$ angegeben.
Bsp: Ein Knoten mit einer ankommenden und zwei abgehenden Kanten hat Grad $d=3$ .
Will man nur die Anzahl der ankommenden bzw. abgehenden Kanten wissen, so schreibt man $d^-$ für ankommende, bzw. $d^+$ für abgehende. So hätte der Knoten aus dem Beispiel $d^-=1$ und $d^+=2$ .
Regulärer Graph
Alle Knoten haben den selben Grad.
Vollständiger Graph
Jeder Knoten ist mit jedem verbunden.
Clique
Ist ein Teilgraph, der (maximal) vollständig ist.
isomorphe Graphen
Wenn zwei Graphen isomorph sind, so kann man jedem Knoten aus Graph 1 einen identischen Knoten in Graph 2 zuordnen. Das heißt insbesondere dass beide Graphen die selbe Anzahl von Knoten und Kanten und die selbe Anzahl von Knoten mit bestimmten Grad haben.
Wald und Baum
Ein Wald ist ein ungerichteter azyklischer Graph der nicht zusammenhängend sein muss. Ist er indes zusammenhängend, so spricht man von einem Baum.
Planarer Graph
In diesem Graph gibt es keine sich über kreuzenden Kanten. Siehe http://www.planarity.net/
(Minimaler) Spannbaum
Ein Spannbaum ist ein Teilgraph eines Graphen bei dem alle Knoten verbunden sind, aber mit minimaler Kantenanzahl. Bei einem minimalem Spannbaum wird auch noch die Gewichtung der Kanten beachtet so dass das Gesamtgewicht minimal ist.

von Wikipedia
Eulerkreis und Eulersche Linie
Ein Eulerkreis ist ein Zyklus in einem Graphen der jede Kante genau einmal enthält. Dabei muss der Startknoten auch der Endknoten sein, deshalb auch Kreis. Bei der Eulerschen Linie ist der Startknoten ungleich dem Endknoten.
Hamiltonkreis
Ist ein Weg in einem Graphen in dem jeder Knoten genau einmal enthalten ist.