Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

Frank Ehrlich,
Ralf Zücker



=Wege und Kreise=
bla

==Was ist ein Weg?==
Ein Weg ist ein Graph, der aus aneinander gehängten Kanten besteht. Damit gibt es bei einem Weg zwei ausgezeichnete Knoten.

Definition eines Wegs
Für n ≥ 2 nennt man einen Graphen Pn mit der Knotenmenge V (Pn) = {v0,v1,...,vn} und
der Kantenmenge
E(Pn) = {{v0,v1},{v1,v2},...,{vn−1,vn }}
einen Weg (oder Pfad) der Länge n, sofern keine Kante mehrfach durchlaufen wird. Knoten
hingegen dürfen bei einem Weg mehrfach vorkommen (d. h. die Knoten vi müssen nicht
notwendig paarweise verschieden sein). Lässt man auch mehrfach durchlaufene Kanten
zu, so spricht man von einem Kantenzug. Eine häufig genutzte Notation für einen solchen
Weg ist die Tupelschreibweise seiner Knoten mithilfe runder Klammern:
Pn = (v0,v1,...,vn).
Meist fordert man zusätzlich explizit, dass v0 
= vn gelten muss, der Weg also offen ist.




==Zusammenhängend==
Wir nennen einen Graphen G zusammenhängend, falls es zu je zwei verschiedenen Knoten
v,w ∈ V (G) einen Weg auf G mit v und w als Endknoten gibt. Ein maximaler zusammen-
hängender Teilgraph von G heißt Zusammenhangskomponente von G.

==Kreise==
Für n ≥ 3 heißt der Graph Cn mit V (Cn) = {v0,v1,...,vn = v0} und
E(Cn) = {{v0,v1},{v1,v2},...,{vn−1,v0}}
Kreis der Länge n.

=Vollständige Graphen=
bla
==Definition==
Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig. Für n ≥ 2 bezeichnen
wir den vollständigen Graphen auf n Knoten mit Kn .
==Kantenanzahl==
xkdkf

==Adjazenz==
Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E =
{e1,...,em} verstehen wir unter der Adjazenzmatrix von G die (n × n)-Matrix A(G), deren
Eintrag an der Stelle (i, j) gleich der Anzahl der Kanten zwischen den Knoten vi und vj ist.

=Inzidenzmatrix=
Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E =
{e1,...,em} verstehen wir unter der Inzidenzmatrix von G die (n × m)-Matrix I(G), deren
Eintrag an der Stelle (i, j) gleich 1 ist, wenn der Knoten vi zur Kante ej gehört, und andern-
falls gleich 0.


=Teilgraph=
Es sei G = (VG ,EG ) ein Graph. Ein Teilgraph von G ist ein Graph H = (VH ,EH ), dessen Kno-
tenmenge VH eine Teilmenge von VG und dessen Kantenmenge EH eine Teilmenge von EG
ist. Wir nennen einen Teilgraphen H ⊆ G darüber hinaus induziert, falls mit jedem Knoten
v von H auch sämtliche mit v inzidenten Kanten zu H gehören.