Zum Inhalt springen

Kurs:Diskrete Mathematik/16/Klausur mit Lösungen

Aus Wikiversity


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.

  1. Eine Relation zwischen Mengen M und N.
  2. Die Produktordnung zu einer Familie (Mi,≤i), i∈I, von geordneten Mengen.
  3. Ein beschränkter Verband.
  4. Ein Untergraph eines Graphen (V,E).
  5. Die disjunkte Vereinigung von zwei Graphen G=(V,E) und H=(W,F) mit disjunkten Knotenmengen V und W.
  6. Der Durchmesser eines zusammenhängenden Graphen  G=(V,E). 


Lösung

  1. Eine Relation R zwischen den Mengen M und N ist eine Teilmenge der Produktmenge M×N, also  R⊆M×N. 
  2. Die Produktordnung ist die Ordnung auf der Produktmenge  M=∏i∈IMi,  die durch
    (xi)i∈I≤(yi)i∈I,

    falls

    xi≤iyi

    für alle  i∈I,  gegeben ist.

  3. Ein Verband M heißt beschränkt, wenn es in ihm ein kleinstes Element 0 und ein größtes Element 1 gibt.
  4. Ein Graph (W,F) heißt Untergraph eines Graphen (V,E), wenn  W⊆V,   F⊆E  und die Kanten aus F nur Bezug auf Punkte aus W nehmen.
  5. Die disjunkte Vereinigung der beiden Graphen ist der Graph mit der Knotenmenge V⊎W und der Kantenmenge  E⊎F⊆𝔓(V⊎W). 
  6. Unter dem Durchmesser von G versteht man das Maximum über alle Abstände d(u,v) zu  u,v∈V. 


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über geordnete Mengen und Potenzmengen.
  2. Die universelle Eigenschaft der Quotientenmenge.
  3. Der Charakterisierungssatz für bipartite Graphen mittels Kreisen.


Lösung

  1. Es sei (M,≤) eine geordnete Menge und 𝔓(M) die Potenzmenge von M. Dann ist die Abbildung
    M⟶𝔓(M),x⟼{y∈M∣y≤x},

    ordnungsvolltreu und injektiv, wobei die Potenzmenge mit der Inklusion

    versehen ist.
  2. Es sei M eine Menge und ∼ eine Äquivalenzrelation auf M mit der Quotientenmenge M/∼. Es sei φ:M→W eine Abbildung mit  φ(x)=φ(y)  für alle x,y∈M mit x∼y. Dann gibt es eine eindeutig bestimmte Abbildung φ‾:M/∼→W mit  φ=φ‾∘q. 
  3. Ein Graph ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.


Aufgabe (2 Punkte)

E wurde ermordet. Es gelten folgende Sachverhalte.

  1. Der Mörder ist A oder B oder C oder D.
  2. Wenn C der Mörder ist, dann ist D nicht der Mörder oder A ist der Mörder.
  3. A,B,C,D sind alle verschieden.
  4. Es gibt genau einen Mörder.
  5. Wenn A nicht der Mörder ist, dann ist D nicht der Mörder.
  6. A ist genau dann der Mörder, wenn B der Mörder ist.

Wer ist der Mörder?


Lösung

Aus (6), (3) und (4) folgt, dass A und B beide nicht der Mörder sind, denn sonst wären beide der Mörder. Nach (5) ist somit auch D nicht der Mörder. Wegen (1) muss also C der Mörder sein. ((2) wird nicht verwendet.)


Aufgabe (3 Punkte)

Es seien M und N endliche Mengen mit m bzw. n Elementen und sei

f:M⟶N

eine injektive Abbildung. Wie viele Abbildungen

g:N⟶M

mit

g∘f=IdM

gibt es?


Lösung

Jedes  y∈N  muss durch g auf das aufgrund der Injektivität eindeutig bestimmte  x∈M  mit  f(x)=y  abgebildet werden. Für die restlichen n−m Elemente in N können die Bilder in M frei gewählt werden. Dies ergibt insgesamt

mn−m
Möglichkeiten.


Aufgabe (6 (1+1+1+3) Punkte)

Der VfB Stuttgart spielt gegen Bayern München und gewinnt auch in dieser Höhe verdient mit 8:3.

  1. Wie viele Möglichkeiten für die Torreihenfolge gibt es?
  2. Wie viele Möglichkeiten für den Spielverlauf gibt es, wenn man unter Spielverlauf die Torreihenfolge und den Halbzeitstand versteht.
  3. Das Spiel dauerte genau 90 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)?
  4. Wie viele Möglichkeiten für die Torreihenfolge gibt es, wenn man weiß, dass Stuttgart, abgesehen vom anfänglichen 0:0, stets in Führung lag.


Lösung

  1. Es fallen insgesamt 11 Tore, die Torreihenfolge ist festgelegt, wenn man weiß, welche Tore davon von München erzielt wurden. Also ist die Anzahl der Möglichkeiten gleich
    (113)=11⋅10⋅93⋅2=11⋅5⋅3=165.
  2. Bei jeder der 165 Torreihenfolgen gibt es für die Pause 12 Möglichkeiten (vor dem ersten Tor, nach dem ersten Tor, nach dem zweiten Tor, ..., nach dem elften Tor), also ist die Anzahl gleich
    12⋅165=1980.
  3. Für jede der 165 Torreihenfolgen muss man noch festlegen, in welchen Minuten die Tore fielen. Für diese Torminuten gibt es (9011) Möglichkeiten, also gibt es 165⋅(9011) Möglichkeiten für den Spielverlauf im beschriebenen Sinn.
  4. 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 2:1. Wegen der Führungseigenschaft erzielt Stuttgart das vierte Tor und es steht 3:1. Für den weiteren Torverlauf gibt es somit  (72)=21  Möglichkeiten, und davon ist nur der Fall ausgeschlossen, dass München die beiden folgenden Tore schießt. Also gibt es in diesem Fall 20 Möglichkeiten. Stuttgart erzielt genau die ersten drei Tore. Dann erzielt München das vierte Tor und es steht 3:1. In diesem Fall gibt es dann wieder 20 Möglichkeiten. Stuttgart erzielt die ersten vier Tore. Dann ist bei jedem weiteren Torverlauf die Führungseigenschaft erfüllt. Davon gibt es  (73)=35  Möglichkeiten. Insgesamt gibt es also
    20+20+35=75

    mögliche Torreihenfolgen, die die Führungsbedingung erfüllen.


Aufgabe (5 Punkte)

Es sei

M={x∈ℚ∣0≤x≤1}.

Wir betrachten die beiden Verknüpfungen (Maximum und Minimum)

M×M⟶M,(a,b)⟼max⁡(a,b),

und

M×M⟶M,(a,b)⟼min⁡(a,b).

Zeige, dass M mit diesen beiden Verknüpfungen (mit welchen neutralen Elementen?) ein kommutativer Halbring ist.


Lösung

Die Kommutativität und die Assoziativität der beiden Verknüpfungen sind klar. Das neutrale Element des Maximums ist 0 und das neutrale Element des Minimums ist 1, 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)

min⁡(a,max⁡(b,c))=max⁡(min⁡(a,b),min⁡(a,c))

bedeutet. Dies beweisen wir durch eine Fallunterscheidung. Da die Situation in b und c symmetrisch ist, können wir  b≤c  annehmen. Bei

a≤b≤c

ergibt sich links a und rechts ebenfalls  max⁡(a,a)=a.  Bei

b≤a≤c

ergibt sich links

min⁡(a,max⁡(b,c))=min⁡(a,c)=a

und rechts ebenfalls

max⁡(min⁡(a,b),min⁡(a,c))=max⁡(b,a)=a.

Bei

b≤c≤a

ergibt sich links

min⁡(a,max⁡(b,c))=min⁡(a,c)=c

und rechts ebenfalls

max⁡(min⁡(a,b),min⁡(a,c))=max⁡(b,c)=c.


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.

  1. Die n-te Generation bestehe nur aus einem einzigen Geschlecht. Zeige, dass jede weitere Generation auch nur aus diesem Geschlecht besteht.
  2. Die n-te Generation bestehe nur aus zwei Individuen unterschiedlichen Geschlechts. Zeige, dass diese Geschlechter mit ihrer Generation aussterben.
  3. 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.
  4. 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?


Lösung

  1. Wenn die Generation nur aus dem Geschlecht X 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.
  2. Die Generation bestehe aus einem Individuum des Geschlechts X und aus einem Individuum des Geschlechts  Y≠X.  Die Folgegeneration besteht dann ausschließlich aus dem dritten Geschlecht Z und nach Teil (1) überträgt sich das auf alle folgenden Generationen.
  3. 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.
  4. Wenn drei gleichgeschlechtliche Individuen in einer Generation leben, so erzeugen die drei möglichen Paare stets wieder ebendieses Geschlecht. Die Möglichkeiten sind A,A,A oder B,B,B oder C,C,C und die Periodenlänge ist 1. Wenn drei unterschiedliche Geschlechter vertreten sind, so ist jedes Geschlecht durch genau ein Individuum vertreten, es liegt also A,B,C vor. Die drei Paarungen führen dann wieder zu A,B,C und die Periodenlänge ist ebenfalls 1. Wenn ein Geschlecht durch zwei Individuen vertreten ist und ein zweites Geschlecht durch ein Individuum, sagen wir X,X,Y, so wird daraus X,Z,Z und daraus Y,Y,Z und daraus X,X,Y. Die Periodenlänge ist also 3. Von diesem Typ gibt es zwei Generationsabfolgen, nämlich die mit A,A,B (mit A,C,C und B,B,C) und die mit A,B,B (mit B,C,C und A,A,C).


Aufgabe (3 (1+2) Punkte)

Es sei K ein Körper und sei K[X] der Polynomring über K. Zeige, dass der Grad folgende Eigenschaften erfüllt.

  1. grad⁡(P+Q)≤max⁡{grad⁡(P),grad⁡(Q)}.
  2. grad⁡(P⋅Q)=grad⁡(P)+grad⁡(Q).


Lösung

Es seien

P=anXn+an−1Xn−1+⋯+a2X2+a1X+a0

und

Q=bmXm+bm−1Xm−1+⋯+b2X2+b1X+b0

mit  an,bm≠0,  also n=grad⁡(P) und m=grad⁡(Q). Bei  m≠n  ist max⁡(m,n) der Grad der Summe, bei  m=n  ist bei  an≠−bn  dies auch der Grad des Summenpolynoms, im andern Fall wird der Grad kleiner (die Summe kann 0 sein, dann ist die Aussage als erfüllt zu interpretieren). Wegen Lemma 5.15 (Diskrete Mathematik (Osnabrück 2026)) ist  anbm≠0  und somit ist anbmXn+m der Leitterm des Produktpolynoms PQ, dessen Grad somit gleich n+m ist.


Aufgabe (3 Punkte)

Zeige, dass der Kern eines Ringhomomorphismus

φ:R⟶S

ein Ideal in R ist.


Lösung

Es sei

I:=φ−1(0).

Wegen  φ(0)=0  ist  0∈I.  Es seien  a,b∈I.  Das bedeutet φ(a)=0 und φ(b)=0. Dann ist

φ(a+b)=φ(a)+φ(b)=0+0=0

und daher  a+b∈I. 

Es sei nun a∈I und r∈R beliebig. Dann ist

φ(ra)=φ(r)φ(a)=φ(r)⋅0=0,

also ist  ra∈I. 


Aufgabe (3 (1+2) Punkte)

Auf einer Baustelle gibt es eine große Waage mit zwei Schalen und (beliebig viele) Gewichte der Masse 12 bzw. 50 Kilogramm.

  1. Erläutere, wie man damit sechs Kilogramm Sand abwiegen kann.
  2. Bestimme, welche Massen man damit abwiegen kann.


Lösung

  1. Wegen
    3⋅50=6+12⋅12

    kann man 6 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.

  2. Da beide Zahlen Vielfache von 2 sind, kann man auch nur Vielfache von 2 abwiegen. Zwei kann man in der Tat abwiegen, wegen
    50=2+4⋅12.

    Indem man diese Situation vervielfacht, kann man jedes Vielfache von 2 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.

  1. Das 2×2-Brett.
  2. Das 3×3-Brett.
  3. Das 4×4-Brett.


Lösung

  1. Jeder Pferdsprung würde das 2×2-Brett verlassen, daher sind die vier einzelnen Felder die Äquivalenzklassen.
  2. Vom zentralen Feld aus würde jeder Pferdsprung das 3×3-Brett verlassen, dieses bildet somit für sich eine Äquivalenzklasse. Die acht übrigen Felder sind mittels Pferdsprüngen untereinander verbindbar, wie die Skizze zeigt.

  3. Die in der folgenden Matrix angegebene Zugreihenfolge
    (161510129257411141383)

    zeigt, dass alle Felder bis auf das links unten miteinander durch Pferdsprünge verbunden sind. Letzteres ist mit dem mit 9 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  xn=xn−1−xn−2  ü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  x0=0  und  x1=1 


Lösung


a) Die Rekursionsmatrix ist

(1−110).


b) Das charakteristische Polynom ist

det⁡(T−11−1T)=T(T−1)+1=T2−T+1.


c) Die Nullstellen des charakteristischen Polynoms sind

λ1,2=1±−32=1±3i2.


d) Eine Basis aus Eigenvektoren ist (1+3i2) und (1−3i2).

e) Wir schreiben

(10)=a(1+3i2)+b(1−3i2).

Dieses lineare Gleichungssystem besitzt die Lösung

(ab)=(−3i63i6).

Daher ist

xn=(1+3i2)n⋅−3i6⋅2+(1−3i2)n⋅3i6⋅2=(1+3i2)n⋅−3i3+(1−3i2)n⋅3i3

gemäß Satz 16.6 (Diskrete Mathematik (Osnabrück 2026)) die explizite Lösung.


Aufgabe (3 Punkte)

Zeige, dass ein Graph  G=(V,E)  zu einer Relation S auf einer Menge M isomorph (als eine Relation zwischen Mengen) sein kann, ohne dass (M,S) selbst ein Graph ist.


Lösung

Es sei  V={x,y}  mit der verbindenen Kante xy und es sei  M={a,b}  mit der identischen Relation, was kein (schleifenfreier) Graph ist. Wir legen die Bijektionen

φ,ψ:V⟶M

durch

a=φ(x)=ψ(y)

und

b=φ(y)=ψ(x)

fest. Dem Paar (x,y) entspricht dabei das Paar  (φ(x),ψ(y))=(a,a)  und dem Paar (y,x) entspricht dabei das Paar  (φ(y),ψ(x))=(b,b).  Es liegt also eine Isomorphie von Relationen vor.


Aufgabe (4 (2+2) Punkte)

Wir betrachten den Nullteilergraphen zu einem endlichen kommutativen Ring R.

  1. Zeige für einen endlichen Körper K, dass der zugehörige Nullteilergraph ein Sterngraph ist.
  2. Man gebe ein Beispiel für einen endlichen kommutativen Ring, der kein Körper ist, für den aber der Nullteilergraph ein Sterngraph ist.


Lösung

  1. In einem Körper ist
    0⋅x=0,

    sodass jedes  x≠0  mit 0 verbunden ist. Alle Elemente  x,y≠0  sind Einheiten und daher ist  xy≠0,  es gibt also keine weiteren Kanten.

  2. Wir betrachten  R=ℤ/(4).  Es ist  2⋅2=0,  deshalb ist dies kein Körper. Es ist
    0⋅1=0⋅2=0⋅3=0,

    sodass 1,2,3 mit 0 im Nullteilergraphen verbunden sind. Dagegen ist  1⋅2=2,   1⋅3=3,   2⋅3=6=2,  sodass es keine weiteren Kanten gibt.


Aufgabe (5 Punkte)

Beweise den Satz über die Potenzen der Adjazenzmatrix.


Lösung

Wir beweisen die Aussage durch Induktion über ℓ, wobei der Induktionsanfang für  ℓ=1  unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge 1 sind (bei ℓ=0 stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge 0 gibt und die 0-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge ℓ+1 von u nach v startet mit einer Kante {u,w} gefolgt von einem Weg von w nach v der Länge ℓ. Es gilt also unter Verwendung der Induktionsvoraussetzung

#( Weg von u nach v der Länge ℓ+1)=∑{u,w}∈E#( Weg von w nach v der Länge ℓ)=∑{u,w}∈E(Aℓ)(w,v)=∑w∈VA(u,w)(Aℓ)(w,v)=(A⋅Aℓ)(u,v)=(Aℓ+1)(u,v).


Aufgabe (2 (1+1) Punkte)

Es sei G ein bipartiter Graph und sei e eine Kante.

  1. Ist G∖e wieder bipartit?
  2. Ist G/e wieder bipartit?


Lösung

  1. Wenn G bipartit ist, ist auch G∖e wieder bipartit bezüglich der gleichen bipartiten Zerlegung der Knotenmenge.
  2. Nur weil G bipartit ist, muss G/e im Allgemeinen nicht bipartit sein. Betrachte dafür beispielsweise G als den Rundgang auf 4 Knoten. Dieser ist offensichtlich bipartit, allerdings entspricht der Kontraktionsgraph G/e dem Rundgang auf 3 Knoten und ist damit nicht bipartit.


Aufgabe (2 Punkte)

Man gebe ein Beispiel für einen Rundgang R, einen Graphen G und einen Graphhomomorphismus φ:R→G, der sowohl knoten- als auch kantensurjektiv ist, derart, dass G nicht eulersch ist.


Lösung

Es sei R der Rundgang mit den Punkten 1,2,3,4 und es sei G der lineare Graph mit zwei Knoten a,b und einer Kante. Es sei

φ(1)=φ(3)=a

und

φ(2)=φ(4)=b.

Dabei sind offenbar alle geforderten Eigenschaften erfüllt.