Kurs:Diskrete Mathematik/16/Klausur mit Lösungen
| Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Punkte | 3 | 3 | 2 | 3 | 6 | 5 | 7 | 3 | 3 | 3 | 3 | 7 | 3 | 4 | 5 | 2 | 2 | 64 |
Aufgabe (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Eine Relation zwischen Mengen und .
- Die Produktordnung zu einer Familie , , von geordneten Mengen.
- Ein beschränkter Verband.
- Ein Untergraph eines Graphen .
- Die disjunkte Vereinigung von zwei Graphen und mit disjunkten Knotenmengen und .
- Der Durchmesser eines zusammenhängenden Graphen .
- Eine Relation zwischen den Mengen und ist eine Teilmenge der Produktmenge , also .
- Die
Produktordnung
ist die Ordnung auf der
Produktmenge
,
die durch
falls
für alle , gegeben ist.
- Ein Verband heißt beschränkt, wenn es in ihm ein kleinstes Element und ein größtes Element gibt.
- Ein Graph heißt Untergraph eines Graphen , wenn , und die Kanten aus nur Bezug auf Punkte aus nehmen.
- Die disjunkte Vereinigung der beiden Graphen ist der Graph mit der Knotenmenge und der Kantenmenge .
- Unter dem Durchmesser von versteht man das Maximum über alle Abstände zu .
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
- Der Satz über geordnete Mengen und Potenzmengen.
- Die universelle Eigenschaft der Quotientenmenge.
- Der Charakterisierungssatz für bipartite Graphen mittels Kreisen.
- Es sei eine
geordnete Menge
und die
Potenzmenge
von . Dann ist die Abbildung
ordnungsvolltreu und injektiv, wobei die Potenzmenge mit der Inklusion
versehen ist. - Es sei eine Menge und eine Äquivalenzrelation auf mit der Quotientenmenge . Es sei eine Abbildung mit für alle mit . Dann gibt es eine eindeutig bestimmte Abbildung mit .
- Ein Graph ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.
Aufgabe (2 Punkte)
wurde ermordet. Es gelten folgende Sachverhalte.
- Der Mörder ist oder oder oder .
- Wenn der Mörder ist, dann ist nicht der Mörder oder ist der Mörder.
- sind alle verschieden.
- Es gibt genau einen Mörder.
- Wenn nicht der Mörder ist, dann ist nicht der Mörder.
- ist genau dann der Mörder, wenn der Mörder ist.
Wer ist der Mörder?
Aus (6), (3) und (4) folgt, dass und beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch nicht der Mörder. Wegen (1) muss also der Mörder sein. ((2) wird nicht verwendet.)
Aufgabe (3 Punkte)
Es seien und endliche Mengen mit bzw. Elementen und sei
eine injektive Abbildung. Wie viele Abbildungen
mit
gibt es?
Jedes muss durch auf das aufgrund der Injektivität eindeutig bestimmte mit abgebildet werden. Für die restlichen Elemente in können die Bilder in frei gewählt werden. Dies ergibt insgesamt
Aufgabe (6 (1+1+1+3) Punkte)
Der VfB Stuttgart spielt gegen Bayern München und gewinnt auch in dieser Höhe verdient mit .
- Wie viele Möglichkeiten für die Torreihenfolge gibt es?
- Wie viele Möglichkeiten für den Spielverlauf gibt es, wenn man unter Spielverlauf die Torreihenfolge und den Halbzeitstand versteht.
- Das Spiel dauerte genau Minuten und in jeder Minute fiel höchstens ein Tor. Wie viele Möglichkeiten für den Spielverlauf gibt es, wenn man darunter versteht, welche Mannschaft in welcher Minute ein Tor geschossen hat (hier genügt eine Formel)?
- Wie viele Möglichkeiten für die Torreihenfolge gibt es, wenn man weiß, dass Stuttgart, abgesehen vom anfänglichen , stets in Führung lag.
- Es fallen insgesamt Tore, die Torreihenfolge ist festgelegt, wenn man weiß, welche Tore davon von München erzielt wurden. Also ist die Anzahl der Möglichkeiten gleich
- Bei jeder der Torreihenfolgen gibt es für die Pause Möglichkeiten
(vor dem ersten Tor, nach dem ersten Tor, nach dem zweiten Tor, ..., nach dem elften Tor),
also ist die Anzahl gleich
- Für jede der Torreihenfolgen muss man noch festlegen, in welchen Minuten die Tore fielen. Für diese Torminuten gibt es Möglichkeiten, also gibt es Möglichkeiten für den Spielverlauf im beschriebenen Sinn.
- Da Stuttgart stets
(bis auf den Anfang)
in Führung liegt, muss Stuttgart das erste und das zweite Tor erzielen. Wir berechnen die Möglichkeiten je nachdem, ob Stuttgart genau die ersten zwei Toren, genau die ersten drei Tore oder zumindest die ersten vier Tore erzielt.
Stuttgart erzielt genau die ersten beiden Tore. Dann erzielt München das dritte Tor und es steht . Wegen der Führungseigenschaft erzielt Stuttgart das vierte Tor und es steht . Für den weiteren Torverlauf gibt es somit
Möglichkeiten, und davon ist nur der Fall ausgeschlossen, dass München die beiden folgenden Tore schießt. Also gibt es in diesem Fall Möglichkeiten.
Stuttgart erzielt genau die ersten drei Tore. Dann erzielt München das vierte Tor und es steht . In diesem Fall gibt es dann wieder Möglichkeiten.
Stuttgart erzielt die ersten vier Tore. Dann ist bei jedem weiteren Torverlauf die Führungseigenschaft erfüllt. Davon gibt es
Möglichkeiten. Insgesamt gibt es also
mögliche Torreihenfolgen, die die Führungsbedingung erfüllen.
Aufgabe (5 Punkte)
Es sei
Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)
und
Zeige, dass mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.
Die Kommutativität und die Assoziativität der beiden Verknüpfungen sind klar. Das neutrale Element des Maximums ist und das neutrale Element des Minimums ist , da ja nur Elemente aus dem rationalen Einheitsintervall vorkommen. Es bleibt also noch das Distributivgesetz zu zeigen, welches bei den gegebenen Verknüpfungen (wir setzen das Maximum als Addition und das Minimum als Multiplikation an)
bedeutet. Dies beweisen wir durch eine Fallunterscheidung. Da die Situation in und symmetrisch ist, können wir annehmen. Bei
ergibt sich links und rechts ebenfalls . Bei
ergibt sich links
und rechts ebenfalls
Bei
ergibt sich links
und rechts ebenfalls
Aufgabe (7 (1+1+2+3) Punkte)
Der Planet Trigeno wird von einer einzigen Tierart bevölkert, den Trigos. Diese Tierart besitzt drei Geschlechter: Antilopen (A), Büffel (B) und Cnus (C). Bei der Paarung treffen zwei Individuen zusammen und erzeugen ein neues Individuum. Wenn das Paar gleichgeschlechtlich ist, so ist das Ergebnis wieder dieses Geschlecht, wenn das Paar gemischtgeschlechtlich ist, so ist das Ergebnis das dritte unbeteiligte Geschlecht. Alle Tiere gehören einer eindeutigen Generation an, es finden nur Paarungen innerhalb der gleichen Generation statt.
- Die -te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
- Die -te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
- Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf. Zeige, dass die Tierart genau dann aussterben muss, wenn es in einer Generation höchstens zwei Individuen gibt.
- Es gelte nun die zusätzliche Bedingung, dass jedes Paar nur einen Nachkommen erzeugen darf, und in jeder Generation gebe es genau drei Individuen. Beschreibe die möglichen Generationsabfolgen. Welche Periodenlängen treten auf?
- Wenn die Generation nur aus dem Geschlecht besteht, so sind nur Paarungen innerhalb dieses Geschlechts möglich und das Ergebnis gehört stets diesem Geschlecht an. Mit Induktion folgt, dass dies über alle folgenden Generationen so bleibt.
- Die Generation bestehe aus einem Individuum des Geschlechts und aus einem Individuum des Geschlechts . Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
- Wenn es nur ein oder kein Individuum gibt, so ist keine Paarung möglich und die nächste Generation ist leer. Wenn es zwei Individuen gibt, so ist nur eine Paarung möglich und es gibt nur einen Nachkommen, der sich allein nicht fortpflanzen kann. Wenn es dagegen mindestens drei Individuen, egal welchen Geschlechts, gibt, so sind auch mindestens drei Paarungen möglich und die nächste Generation besitzt mindestens wieder drei Individuen.
- Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind oder oder und die Periodenlänge ist . Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also vor. Die drei Paarungen führen dann wieder zu und die Periodenlänge ist ebenfalls . Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir , so wird daraus und daraus und daraus . Die Periodenlänge ist also . Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit (mit und ) und die mit (mit und ).
Aufgabe (3 (1+2) Punkte)
Es sei ein Körper und sei der Polynomring über . Zeige, dass der Grad folgende Eigenschaften erfüllt.
Es seien
und
mit , also und . Bei ist der Grad der Summe, bei ist bei dies auch der Grad des Summenpolynoms, im andern Fall wird der Grad kleiner (die Summe kann sein, dann ist die Aussage als erfüllt zu interpretieren). Wegen Lemma 5.15 (Diskrete Mathematik (Osnabrück 2026)) ist und somit ist der Leitterm des Produktpolynoms , dessen Grad somit gleich ist.
Aufgabe (3 Punkte)
Es sei
Wegen ist . Es seien . Das bedeutet und . Dann ist
und daher .
Es sei nun und beliebig. Dann ist
also ist .
Aufgabe (3 (1+2) Punkte)
Auf einer Baustelle gibt es eine große Waage mit zwei Schalen und (beliebig viele) Gewichte der Masse bzw. Kilogramm.
- Erläutere, wie man damit sechs Kilogramm Sand abwiegen kann.
- Bestimme, welche Massen man damit abwiegen kann.
- Wegen
kann man Kilo Sand abwiegen, indem man in die eine Schale dreimal das Fünfzigergewicht und in die andere zwölfmal das Zwölfergewicht drauflegt und die letzte Schale mit Sand auffüllt.
- Da beide Zahlen Vielfache von sind, kann man auch nur Vielfache von abwiegen. Zwei kann man in der Tat abwiegen, wegen
Indem man diese Situation vervielfacht, kann man jedes Vielfache von abwiegen.
Aufgabe (3 (1+1+1) Punkte)
Bestimme die Äquivalenzklassen zur Äquivalenzrelation, die durch die möglichen Züge des Springers im Schach gegeben ist, und zwar auf den folgenden Schachbrettern.
- Das -Brett.
- Das -Brett.
- Das -Brett.
- Jeder Pferdsprung würde das -Brett verlassen, daher sind die vier einzelnen Felder die Äquivalenzklassen.
-
Vom zentralen Feld aus würde jeder Pferdsprung das -Brett verlassen, dieses bildet somit für sich eine Äquivalenzklasse. Die acht übrigen Felder sind mittels Pferdsprüngen untereinander verbindbar, wie die Skizze zeigt.
- Die in der folgenden Matrix angegebene Zugreihenfolge
zeigt, dass alle Felder bis auf das links unten miteinander durch Pferdsprünge verbunden sind. Letzteres ist mit dem mit markierten Feld durch einen Pferdsprung verbunden. Also sind alle Felder zueinander äquivalent und es gibt nur eine Äquivalenzklasse.
Aufgabe (7 (1+1+1+2+2) Punkte)
Wir betrachten die
lineare Rekursion
über .
a) Erstelle die
Rekursionsmatrix
zu dieser Rekursion.
b) Bestimme das
charakteristische Polynom
zu dieser Rekursion.
c) Bestimme die Nullstellen des charakteristischen Polynoms.
d) Bestimme die Eigenvektoren zur Rekursionsmatrix.
e) Bestimme die explizite Lösung zu dieser Rekursion für die Anfangsglieder und
a) Die Rekursionsmatrix ist
b) Das charakteristische Polynom ist
c) Die Nullstellen des charakteristischen Polynoms sind
d) Eine Basis aus Eigenvektoren ist
und .
e) Wir schreiben
Dieses lineare Gleichungssystem besitzt die Lösung
Daher ist
gemäß Satz 16.6 (Diskrete Mathematik (Osnabrück 2026)) die explizite Lösung.
Aufgabe (3 Punkte)
Zeige, dass ein Graph zu einer Relation auf einer Menge isomorph (als eine Relation zwischen Mengen) sein kann, ohne dass selbst ein Graph ist.
Es sei mit der verbindenen Kante und es sei mit der identischen Relation, was kein (schleifenfreier) Graph ist. Wir legen die Bijektionen
durch
und
fest. Dem Paar entspricht dabei das Paar und dem Paar entspricht dabei das Paar . Es liegt also eine Isomorphie von Relationen vor.
Aufgabe (4 (2+2) Punkte)
Wir betrachten den Nullteilergraphen zu einem endlichen kommutativen Ring .
- Zeige für einen endlichen Körper , dass der zugehörige Nullteilergraph ein Sterngraph ist.
- Man gebe ein Beispiel für einen endlichen kommutativen Ring, der kein Körper ist, für den aber der Nullteilergraph ein Sterngraph ist.
- In einem Körper ist
sodass jedes mit verbunden ist. Alle Elemente sind Einheiten und daher ist , es gibt also keine weiteren Kanten.
- Wir betrachten
.
Es ist
,
deshalb ist dies kein Körper. Es ist
sodass mit im Nullteilergraphen verbunden sind. Dagegen ist , , , sodass es keine weiteren Kanten gibt.
Aufgabe (5 Punkte)
Beweise den Satz über die Potenzen der Adjazenzmatrix.
Wir beweisen die Aussage durch Induktion über , wobei der Induktionsanfang für unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge sind (bei stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge gibt und die -te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge von nach startet mit einer Kante gefolgt von einem Weg von nach der Länge . Es gilt also unter Verwendung der Induktionsvoraussetzung
Aufgabe (2 (1+1) Punkte)
Es sei ein bipartiter Graph und sei eine Kante.
- Ist wieder bipartit?
- Ist wieder bipartit?
- Wenn bipartit ist, ist auch wieder bipartit bezüglich der gleichen bipartiten Zerlegung der Knotenmenge.
- Nur weil bipartit ist, muss im Allgemeinen nicht bipartit sein. Betrachte dafür beispielsweise als den Rundgang auf Knoten. Dieser ist offensichtlich bipartit, allerdings entspricht der Kontraktionsgraph dem Rundgang auf Knoten und ist damit nicht bipartit.
Aufgabe (2 Punkte)
Man gebe ein Beispiel für einen Rundgang , einen Graphen und einen Graphhomomorphismus , der sowohl knoten- als auch kantensurjektiv ist, derart, dass nicht eulersch ist.
Es sei der Rundgang mit den Punkten und es sei der lineare Graph mit zwei Knoten und einer Kante. Es sei
und
Dabei sind offenbar alle geforderten Eigenschaften erfüllt.
