91Ó°ÊÓ

\(26.12\) - Bestimmen Sie für das in Abbildung \(26.25\) dargestellte Netrwerk \((G, w)\) einen Entfernungsbaum \(z u\) dem Knoten \(v_{3}\).

26.13 of Es seien \(M\) und \(N\) endliche Mengen, \(|N|=n\) und \(|M|=m\). Bestimmen Sie die Anzahl (a) aller Abbildungen \(f: M \rightarrow N\), (b) aller injektiven Abbildungen \(f: M \rightarrow N\), (c) aller surjektiven Abbildungen \(f: M \rightarrow N\), (d) aller bijektiven Abbildungen \(f: M \rightarrow N\).

\(26.14\) oo Gegeben ist die rekursiv definierte Folse \(\left(a_{n}\right)_{n} \in \mathbb{N}_{0}\), wobei $$ a_{0}=1 \text { und } a_{n+1}=2 a_{n}+n $$ Bestimmen Sie eine explizite Darstellung der Folgenglieder \(a_{n}\) mittels einer erzeugenden Funktion.

Beweisaufgaben \(26.15\) - Beweisen Sie die folgende Aussage: Hat in einem einfachen Graphen \(G\) mit \(n\) Knoten jeder Knoten \(w\). einen Girad deg \(v \geq \frac{n}{2}\), so ist \(G\) zusammenhängend.

\(26.16\) on Beweisen Sie, dass es in jeder Ansammlung von 6 Personen mindestens drei gibt, die paarweise einander kennen, oder drei, die paarweise einander nicht kennen.

\(26.18\) - Beweisen Sie: Ist \(G\) ein planarer zusammenh?ngender und einfacher Graph, \(s 0\) ist die Kantenzahl \(m\) gegeniber der Knotenzahl \(n\) durch die Gieichung \(m \leq 3 n-6\) begrenzL

\(26.19\) - Beweisen Sie die folgende Aussage: Wen in einem bewerteten einfachen Graphen \((G, w)\) keine zwei Kanten denselben Wert haben, ist der minimale Spannbaum eindeutig.