Google
 
Web www.grundstudium.info
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Minimumheap Aufwärts: Hauptseite Algorithmen Vorherige Seite: Bäume   Inhalt

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$