Kurs:Diskrete Mathematik/25/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	${}\sum$
Punkte	3	3	3	4	3	2	4	3	3	8	6	4	3	2	7	6	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Reflexivität einer Relation ${}R$ auf einer Menge ${}M$.
2. Das kleinste gemeinsame Vielfache von natürlichen Zahlen

   $a_{1},\ldots ,a_{n}.$

3. Die kanonische Projektion zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Der Restgraph ${}G\setminus F$ eines Graphen  ${}G=(V,E)$  zu einer Teilmenge  ${}F\subseteq E$  der Kantenmenge.
5. Die Zusammenhangskomponente zu einem Punkt  ${}v\in V$  in einem Graphen  ${}G=(V,E)$. 
6. Eine Knotenüberdeckung in einem Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Multinomialsatz für einen kommutativen Halbring.
2. Der Satz über die Anzahl der surjektiven Abbildungen mit Potenzprodukten.
3. Der Vier-Farben-Satz.

Aufgabe * (3 (1+1+1) Punkte)

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze ${}1,2,3,4$ nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz ${}3$ bestreiten. Von einer solchen Runde seien die Mannschaften ${}A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
3. unter welcher nicht?

Aufgabe * (4 (0.5+0.5+1+1+1) Punkte)

Wir betrachten die Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto a*b,$

die einem Paar ${}(a,b)$ diejenige Zahl zuordnet, die entsteht, wenn man im Zehnersystem die Zahl ${}b$ ${}a$-fach hintereinander schreibt.

1. Bestimme ${}7*6$.
2. Bestimme ${}4*13$.
3. Ist die Verknüpfung kommutativ?
4. Ist die Verknüpfung assoziativ?
5. Besitzt die Verknüpfung ein neutrales Element?

Aufgabe * (3 (1+2) Punkte)

Es sei ${}\left(G,\cdot ,1\right)$ eine Gruppe. Es seien  ${}a,b,c\in G$  Elemente mit

${}a\cdot b\cdot c=1\,.$

1. Zeige, dass das Inverse von ${}b$ gleich ${}c\cdot a$ ist.
2. Zeige, dass das Inverse von ${}b$ im Allgemeinen nicht gleich ${}a\cdot c$ ist.

Aufgabe * (2 Punkte)

Beweise, dass der Polynomring ${}K[X]$ über einem Körper ${}K$ selbst kein Körper ist.

Aufgabe * (4 (0.5+0.5+1+1+1) Punkte)

Wir betrachten die Relation im nebenstehenden Diagramm, wobei eine Pfeil ${}x\rightarrow y$ bedeutet, dass ${}x$ von ${}y$ gefressen wird.

1. Was frisst ein Polarbear?
2. Von wem wird ein Capelin gefressen?
3. Welche Tiere stehen an der Spitze der Nahrungskette?
4. Ist die Relation transitiv?
5. Ist die Relation antisymmetrisch?

Aufgabe * (3 Punkte)

Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.

1. Für jede natürliche Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede natürliche Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede natürliche Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,\left(rb+sc\right)$ für beliebige natürliche Zahlen ${}r,s$.

Aufgabe * (3 Punkte)

Bestimme in ${}\mathbb {Z}$ mithilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1085$ und ${}806$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.

Aufgabe * (8 (3+2+3) Punkte)

Wir betrachten auf der Menge ${}C$ aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$ die folgende Relation: Es ist ${}f\sim g$, falls es eine nullstellenfreie stetige Funktion ${}\alpha \colon \mathbb {R} \rightarrow \mathbb {R}$ mit

${}f=g\cdot \alpha \,$

gibt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Zeige, dass aus ${}f\sim g$ folgt, dass die Nullstellenmenge von ${}f$ und von ${}g$ übereinstimmen.
3. Zeige, dass die beiden Funktionen

   ${}f(x)=x\,$

   und

   ${}g(x)=x^{2}\,$

   nicht zueinander äquivalent sind.

Aufgabe * (6 (4+2) Punkte)

1. Finde den kleinsten Exponenten  ${}n\geq 2$  derart, dass die Potenzierung

   $\mathbb {Z} /(10)\longrightarrow \mathbb {Z} /(10),\,x\longmapsto x^{n},$

   die Identität ist.

2. Was bedeutet dies für die Endziffer im Zehnersystem beim Potenzieren von natürlichen Zahlen?

Aufgabe * (4 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen. Zeige, dass eine Äquivalenzrelation ${}\sim _{1}$ auf ${}M$ genau dann konjugiert-isomorph zu einer Äquivalenzrelation ${}\sim _{2}$ auf ${}N$ ist, wenn beide Äquivalenzrelationen das gleiche Klassenanzahltupel besitzen.

Aufgabe * (3 Punkte)

Man erläutere die wesentlichen Konzepte und Objekte in Satz 17.13 (Diskrete Mathematik (Osnabrück 2026)) für den Fall  ${}d=1$. 

Aufgabe * (2 Punkte)

Es sei ${}{\mathcal {M}}$ ein Matroid auf einer Menge ${}E$ und  ${}B_{1},B_{2}\in {\mathcal {M}}$  Basen. Zeige

${}{\#\left(B_{1}\right)}={\#\left(B_{2}\right)}\,.$

Aufgabe * (7 (3+2+2) Punkte)

1. Bestimme die linearen Rekursionen mit der Eigenschaft, dass ihre zugehörige Matrix gleich der Adjazenzmatrix eines Graphen ist. Wie sieht in diesen Fällen die Matrix, wie der Graph, wie die lineare Rekursion aus?
2. Bestimme das charakteristische Polynom, die Eigenwerte und die Eigenvektoren in diesen Fällen.
3. Wie sieht die Lösung der linearen Rekursion zu einem beliebigen Startwerttupel in diesen Fällen aus?

Aufgabe * (6 Punkte)

Beweise den Satz über nichtgeschlossene Eulerzüge.