Ungerichtete Graphen

  Ein  ungerichteter Graph umfaßt eine endliche Menge von  Knoten V und eine endliche Menge von  ungerichteten Kanten E. Jede ungerichtete Kante $e\in E$ verbindet entweder zwei verschiedene Knoten $u,v\in V$ miteinander oder im Falle einer  ungerichteten Schlinge einen Knoten $v\in V$ mit sich selbst.

Die Beziehungen zwischen einer ungerichteten Kante und den durch sie verbundenen Knoten werden durch die Funktionen   $this, that:E\tfun V$ausgedrückt. this(e) ist einer der beiden durch Kante e verbundenen Knoten, that(e) der andere Knoten. Falls e eine Schlinge ist, gilt this(e)=that(e). Auch in ungerichteten Graphen sind  Mehrfachkanten erlaubt.