-
-
- 1 / 15
-
Flashcards
Def: (linearer Algorithmus)
\(T_A(n) = \mathcal{O}(n)\)
Def: (quadratischer Algorithmus)
\(T_A(n) = \mathcal{O}(n^2)\)
Def: (polynomiellen Algorithmus)
\(T_A(n) = \mathcal{O}(n^k), k\in \mathbb{N}\)
Def: (exponentieller Algorithmus)
\(T_A(n) = 2^{\mathcal{O}(n)}\)
\(f(n) = \mathcal{O}(g(n))\)
\(\limsup\limits_{n \rightarrow \infty}{\frac{|f(n)|}{|g(n)|}} < \infty\)
f(n) wächst höchstes so schnell wie g(n)
\(f(n) = \Omega(g(n))\)
\(\liminf\limits_{n \rightarrow \infty}{\frac{|f(n)|}{|g(n)|}} > 0\)
f(n) wächst mindestens so schnell wie g(n)
\(f(n) = \Theta(g(n))\)
\(f(n) = \mathcal{O}(g(n)) \land f(n) = \Omega(g(n))\)
f(n) wächst genauso schnell wie g(n)
\(f(n) = o(g(n))\)
\(\lim\limits_{n \rightarrow \infty}{\frac{|f(n)|}{|g(n)|}} = 0\)
f(n) wächst langsamer als g(n)
\(f(n) = \omega(g(n))\)
\(\frac{|f(n)|}{|g(n)|} \rightarrow \infty\)
f(n) wächst schneller als g(n)
Def: (Graph)
Ein Graph G ist ein Tupel (V,E) wobei V eine endliche ncihtleere Menge von Knoten ist. Die Menge E ist eine Teilmenge der zweielementigen Teilmenge von V, also:
\(E \subset \binom{V}{2}:= \{\{x,y\}|x,y \in V, x \neq y\}\)
Die Elemente der Menge E bezeichnet man als Kanten
Def: (Nachbarschaft)
Für einen Knoten \(v \in V\) eines Graphen G = (V,E) definieren wir die Nachbarschaft \(\Gamma(v)\) eines Knotens \(v \in V\) durch:
\(\Gamma(v) := \{u \in V | \{v,u\} \in E\}\)
der Grad von v nezeichnet die grösse der Nachbarschaft von v:
\(deg(v) := |\Gamma(v)|\)
Def: (k-regulär)
Ein Graph heisst k-regulär, falls für alle Knoten v in V gilt : deg(v) = k
Def: (adjazente Knoten)
Zwei Knoten heissen adjazent, wenns ie durch eine Kante verbunden sind.
Def: (inzident)
Einen Knoten u und eine Kante e heissen inzident, wenn u einer der Endknoten von e ist.
Satz: Für jeden Graphen G=(V,E) gilt:
\(\sum_{v \in V} deg(v) = \)
\(2|E|\)
