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==
bla

==Kreise==
bla

=Vollständige Graphen=
bla
==Definition==
xxkj
==Kantenanzahl==
xkdkf

==Adjazenz- und Inzidenzmatrix==
sffg
=Teilgraph=