TU Wien:Algebra und Diskrete Mathematik VU (Panholzer)/Prüfung 2014-04-02

Angabe

Aufgabe 1 [8 Punkte]

Man zeige durch vollständige Induktion, dass $9^{n}-1$ für alle $n\in \mathbb {N}$ durch 8 teilbar ist.

Aufgabe 2 [8 = 2(1.)+3(2.)+3(3.) Punkte]

Im folgenden betrachten wir Wörter endlicher Länge, gebildet aus den Buchstaben $a$, b und c.

1. Sei $x_{n}$ die Anzahl aller solcher Wörter der Länge $n$. Wie groß ist $x_{n}$, für $n\in \mathbb {N}$?
2. Sei $y_{n}$ die Anzahl solcher Wörter der Länge $n$, in denen je zwei aufeinanderfolgende Buchstaben verschieden sind (d.h., die keine Teilwörter aa, bb oder cc enthalten). Wie groß ist $y_{n}$, für $n\geq 1$? Hinweis: Man überlege sich, wie viele Möglichkeiten es für den 1. Buchstaben, dann den 2. Buchstaben, dann den 3. Buchstaben, etc. eines solchen Wortes gibt.
3. Sei $z_{n}$ die Anzahl solcher Wörter der Länge $n$, die keine zwei aufeinanderfolgende $a$ und keine zwei aufeinanderfolgende b enthalten (d.h., die keine Teilwörter aa und bb enthalten). Es läßt sich leicht zeigen, dass $z_{n}$die folgende Differenzengleichung erfüllt (braucht hier aber nicht nachgewiesen werden):
   $$z_{n}=2z_{n-1}+z_{n-2},\quad n\geq 2,\quad z_{0}=1,\quad z_{1}=3$$
   Man löse diese Differenzengleichung und ermittle so eine allgemeine Formel für $z_{n}$, $n\in \mathbb {N}$,

Aufgabe 3 [8 = 4(1.)+4(2.) Punkte]

Achtung, Aufgabenstellung wahrscheinlich fehlerhaft!

Gegeben sind die folgenden drei Vektoren ${\vec {x}},{\vec {y}},{\vec {z}}\in \mathbb {R} ^{3}$:

$${\vec {x}}={\begin{pmatrix}-1\\-2\\-3\end{pmatrix}},\quad {\vec {y}}={\begin{pmatrix}2\\w\\2\end{pmatrix}},\quad {\vec {z}}={\begin{pmatrix}1\\w\\w\end{pmatrix}},\quad mit\ w\in \mathbb {R} .$$

1. Man bestimme alle Werte $w\in \mathbb {R}$ für welche die drei Vektoren linear unabhängig sind.
2. Für jeden dieser in Aufgabe (1) gefundenen Werte $w$ gebe man eine nicht-triviale Linearkombination der drei Vektoren an, welche den Nullvektor liefert, d.h. man finde Skalare $\lambda _{1}$, $\lambda _{2}$, $\lambda _{3}$ mit $(\lambda _{1},\lambda _{2},\lambda _{3})\neq (0,0,0)$, sodass
   $$\lambda _{1}{\vec {x}}+\lambda _{2}{\vec {y}}+\lambda _{3}{\vec {z}}={\vec {0}}.$$

Anmerkung: Es wird verlangt, dass die Aufgaben mit den in der Vorlesung kennengelernten Methoden der Linearen Algebra systematisch gelöst werden und nicht durch "Herumprobieren"!

Aufgabe 4 [8 = 3(1.)+2(2.)+3(3.) Punkte]

1. Man formuliere die "Euler'sche Polyederformel" für planare Graphen. Die verwendete Notation muss unbedingt definiert werden!
2. Man gebe das sogenannte "Handschlaglemma" für einfache ungerichtete Graphen an.
3. Man formuliere für gerichtete Graphen den Satz, welcher charakterisiert, wann diese eine geschlossene Euler'sche Linie besitzt.

Aufgabe 5 [8 Punkte]

---TBD---

Lösung

---TBD---