Diskrete Mathematik/Gemischte Satzabfrage/13/Aufgabe/Lösung

1. Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit ${}n$ Elementen ist

   $\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}.$

2. In einem Graphen ${}(V,E)$ gilt

   ${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$

3. Eine Paarung ${}P$ in einem Graphen ${}G$ ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

Zur gelösten Aufgabe