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

Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit ${}n$ Elementen ist
$\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}.$
In einem Graphen ${}(V,E)$ gilt
${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$
Eine Paarung ${}P$ in einem Graphen ${}G$ ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.