Graphentheorie - Übersicht

Aus Lerngruppe Informatik
Wechseln zu: Navigation, Suche

Definitionen

* Hamiltonkreis: Kreis der Länge n (Jeder Knoten wird einmal durchlaufen <math>\Rightarrow G~ist~zusammenhängend~+~jeder~Knoten~hat~Grad~\ge~2</math>
* Eulertour: Eine Tour in der jede Kante einmal vorkommt <math>\Rightarrow G~hat~höchstens~eine~nicht-triviale~Komponente</math>

Formeln

Anzahl der Knoten: <math>|V|=n~</math>

Anzahl der Kanten: <math>|E|\le\binom{n}{2}</math>

Summe der Grade aller Knoten: <math>\sum_{v \in V}deg(v)=2|E|</math>

Sätze

Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Werkzeuge