Ψ Die Informatikseite

Menü
Unterabschnitte

Ungerichtete Graphen

Allgemeine Eigenschaften

  • $n\geq 2$ und $\vert E\vert<n-1$ $\Rightarrow$ $G$ ist nicht zusammenhängend
  • $E\geq n\geq 3$ $\Rightarrow$ $G$ ist zyklisch.

Äquivalente Aussagen

Folgende Aussagen sind äquivalent
  • $G$ ist zusammenhängend und zyklenfrei
  • $G$ ist azykklisch und $\vert E\vert=\vert V\vert-1$
  • $G$ ist zusammenhängend und $\vert E\vert=\vert V\vert-1$
  • Zu jedem Knotenpaar $(v,w)$ gibt es genau einen Pfad von $v$ nach $w$