Zum Inhalt springen

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

Aus Wikiversity



Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ∑
Punkte 3 3 4 6 2 2 2 3 1 3 3 2 6 6 3 5 4 1 5 64




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein gemeinsamer Teiler von natürlichen Zahlen a1,…,ak.
  2. Ein Infimum zu einer Teilmenge  J⊆I  in einer geordneten Menge (I,≼).
  3. Ein Verband M.
  4. Der Kantengraph zu einem Graphen  G=(V,E). 
  5. Ein Weg in einem Graphen.
  6. Ein planarer Graph.


Lösung

  1. Eine natürliche Zahl t heißt gemeinsamer Teiler der a1,…,ak, wenn t jedes ai teilt für i=1,…,k.
  2. Ein Element  s∈I  heißt Infimum von J, wenn s die größte untere Schranke von J ist.
  3. Ein Verband ist eine geordnete Menge (M,≤) mit der Eigenschaft, dass für je zwei Elemente  x,y∈M  ein Infimum x⊓y und ein Supremum x⊔y existieren.
  4. Der Kantengraph ist derjenige Graph, dessen Knotenmenge die Kantenmenge E von G ist und bei dem zwei Knoten L1 und L2 (also Kanten aus G) genau dann durch eine Kante verbunden werden, wenn L1 und L2 einen gemeinsamen Punkt in V besitzen.
  5. Ein Weg ist eine Folge v1,v2,…,vm von Knoten derart, dass vivi+1 für alle i eine Kante ist.
  6. Ein Graph heißt planar, wenn er eine geometrische Realisierung im ℝ2 besitzt.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Restklassenkörper von ℤ.
  2. Der Satz über die Anzahl der Abbildungen mit vorgeschriebener Faseranzahl.
  3. Der Satz über nichtgeschlossene Eulerzüge.


Lösung

  1. Es sei n∈ℕ. Der Restklassenring ℤ/(n) ist genau dann ein Körper, wenn n eine Primzahl ist.
  2. Es sei A eine n-elementige Menge und seien (r1,…,rk) mit  ∑j=1krj=n  vorgegeben. Dann ist die Anzahl der Abbildungen f von A nach {1,…,k} mit der Eigenschaft, dass  #(f−1(j))=rj  für alle j ist, gleich
    (nr1,…,rk).
  3. In einem zusammenhängenden Graphen  G=(V,E)  gibt es genau dann einen nichtgeschlossenen Eulerzug, wenn es genau zwei Knotenpunkte mit ungeradem Grad gibt.


Aufgabe (4 (2+1+1) Punkte)

Folgende Aussagen seien bekannt.

  1. Der frühe Vogel fängt den Wurm.
  2. Doro wird nicht von Lilly gefangen.
  3. Lilly ist ein Vogel oder ein Igel.
  4. Für Igel ist 5 Uhr am Morgen spät.
  5. Doro ist ein Wurm.
  6. Für Vögel ist 5 Uhr am Morgen früh.
  7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

  1. Ist Lilly ein Vogel oder ein Igel?
  2. Ist sie ein frühes oder ein spätes Tier?
  3. Fängt der späte Igel den Wurm?


Lösung

  1. Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um 5 Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
  2. Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
  3. Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht den Wurm.


Aufgabe (6 (1+5) Punkte)

Es seien  1≤k≤n  natürliche Zahlen. Zu k bezeichnet Sk die Menge der Permutationen auf {1,…,k} und 𝔓k(n) bezeichnet die Menge der k-elementigen Teilmengen von {1,…,n}.

  1. Zeige
    #(Sn)=#(𝔓k(n))⋅#(Sk)⋅#(Sn−k).
  2. Man definiere eine explizite natürliche bijektive Abbildung
    Sn⟶𝔓k(n)×Sk×Sn−k.


Lösung

  1. Die rechte Seite ist gemäß Korollar 2.5 (Diskrete Mathematik (Osnabrück 2026)) und Satz 2.11 (Diskrete Mathematik (Osnabrück 2026)) gleich
    (nk)⋅k!⋅(n−k)!=n!k!(n−k)!⋅k!⋅(n−k)!=n!,

    was mit der linken Seite übereinstimmt.

  2. Es bezeichne
    αk:{1,…,n−k}⟶{k+1,…,n},x⟼x+k,

    die Addition mit k, und zu einer ℓ-elementigen Teilmenge  J⊆{1,…,n}  bezeichne

    ιJ:{1,…,ℓ}⟶J

    die natürliche Nummerierung von J gemäß der Ordnung von {1,…,n}. Wir behaupten, dass die Abbildung

    Sn⟶𝔓k(n)×Sk×Sn−k,π⟼(π({1,…,k}),ιπ({1,…,k})−1∘π|{1,…,k},ιπ({k+1,…,n})−1∘π|({k+1,…,n})∘αk)

    bijektiv ist. Die Abbildung ist wohldefiniert, da in der ersten Komponente eine k-elementige Teilmenge von {1,…,n}, in der zweiten Komponente eine bijektive Abbildung von {1,…,k} nach {1,…,k} und in der dritten Komponente eine bijektive Abbildung von {1,…,n−k} nach {1,…,n−k} steht. Wir geben explizit eine Umkehrabbildung an. Zu  (J,σ,τ)∈𝔓k(n)×Sk×Sn−k  ist das Urbild die Permutation π auf {1,…,n}, die durch

    π(i):={(iJ∘σ)(i), falls i≤k,(i{1,…,n}∖J∘τ∘αk−1)(i), falls i≥k+1,

    gegeben ist. Hierbei gilt offenbar

    π({1,…,k})=J

    und

    ιπ({1,…,k})−1∘π|{1,…,k}=ιπ({1,…,k})−1∘iJ∘σ=σ

    und

    ιπ({k+1,…,n})−1∘π|({k+1,…,n})∘αk=ιπ({k+1,…,n})−1∘i{1,…,n}∖J∘τ=τ,

    daher wird π unter der ersten Abbildung auf dieses Dreiertupel abgebildet und die erste Abbildung ist surjektiv. Die Injektivität ergibt sich daraus und dem ersten Teil.


Aufgabe (2 Punkte)

Zeige, dass in einem kommutativen Halbring die Beziehung  0⋅0=0  gilt.


Lösung

Dies ergibt sich aus

0⋅0=0⋅0+0=0⋅0+0⋅1=0⋅(0+1)=0⋅1=0.


Aufgabe (2 Punkte)

Berechne

(−2x3+3x2+3x−2)2


Lösung

Es ist

(−2x3+3x2+3x−2)2=4x6−12x5−3x4+26x3−3x2−12x+4


Aufgabe (2 Punkte)

Bestimme, ob die durch die Relationstabelle

A B C D
A
B × ×
C ×
D × ×

beschriebene Relation R auf der Menge {A,B,C,D} reflexiv, symmetrisch, transitiv, antisymmetrisch ist.


Lösung

Die Relation ist nicht reflexiv, da A nicht zu sich selbst in Beziehung steht. Die Relation ist symmetrisch, da die einzige Relationsbeziehung zwischen verschiedenen Elementen die Relation zwischen B und D ist, und diese in beide Richtungen gegeben ist. Daher ist die Relation auch nicht antisymmetrisch. Die Relation ist transitiv. Die einzige zu überprüfende nichttriviale Voraussetzung ist BRD und DRB, wobei die Konklusion wegen BRB und DRD gilt.


Aufgabe (3 Punkte)

Bestimme in ℤ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von 10868 und 9243.


Lösung

Der Euklidische Algorithmus liefert:

10868=1⋅9243+1625
9243=4⋅1625+1118
1625=1⋅1118+507
1118=2⋅507+104
507=4⋅104+91
104=1⋅91+13
91=7⋅13+0.

Der größte gemeinsame Teiler von 10868 und 9243 ist also 13.


Aufgabe (1 Punkt)

Finde die Primfaktorzerlegung von

5⋅41+6⋅82+7⋅123.


Lösung

Es ist

5⋅41+6⋅82+7⋅123=5⋅41+6⋅2⋅41+7⋅3⋅41=(5+12+21)⋅41=38⋅41=2⋅19⋅41,

wobei 2,19,41 Primzahlen sind.


Aufgabe (3 Punkte)

Es sei K ein Körper und  U⊆Kn  ein Untervektorraum. Wir betrachten die Relation auf dem Kn, die durch

v1∼v2 genau dann, wenn v1−v2∈U

definiert ist. Zeige, dass diese Relation eine Äquivalenzrelation ist.


Lösung

Wegen

v−v=0∈U

ist  v∼v,  die Relation ist also reflexiv. Es sei nun  v∼u.  Dies bedeutet

v−u∈U.

Somit ist auch

u−v=−(v−u)∈U

und damit ist auch  u∼v,  was die Symmetrie bedeutet. Es sei schließlich  u∼v  und  v∼w.  Dies bedeutet

u−v∈U

und

v−w∈U.

Wegen der Abgeschlossenheit eines Untervektorraumes unter Addition gilt somit

(u−v)+(v−w)=u−w∈U,

was  u=w  bedeutet. Dies ergibt die Transitivität.


Aufgabe (3 Punkte)

Es sei G eine Gruppe. Zeige, dass sich Gruppenelemente  g∈G  und Gruppenhomomorphismen φ von ℤ nach G über die Korrespondenz

g⟼(n↦gn) und φ⟼φ(1)

entsprechen.


Lösung

Es sei  g∈G  fixiert. Dass die Abbildung

φg:ℤ⟶G,n⟼gn,

ein Gruppenhomomorphismus ist, ist eine Umformulierung der Potenzgesetze. Wegen  φg(1)=g1=g  erhält man aus der Potenzabbildung das Gruppenelement zurück. Umgekehrt ist ein Gruppenhomomorphismus φ:ℤ→G durch φ(1) eindeutig festgelegt, da  φ(n)=(φ(1))n  für n positiv und  φ(n)=((φ(1))−1)−n  für n negativ gelten muss.


Aufgabe (2 Punkte)

Zeige, dass es keinen Ringhomomorphismus von ℚ nach ℤ gibt.


Lösung

Nehmen wir an, dass

φ:ℚ⟶ℤ

ein Ringhomomorphismus ist. Dann ist  φ(1)=1.  In ℚ gilt  1=12+12,  daher gilt in ℤ

1=φ(12)+φ(12).

Das würde aber bedeuten, dass die Gleichung  2x=1  in ℤ eine Lösung besitzt, was nicht der Fall ist.


Aufgabe (6 Punkte)

Zeige, dass zwei Permutationen σ,τ auf M1 bzw. M2 genau dann zueinander konjugiert sind, wenn ihre Zyklendarstellung den gleichen Typ haben, d.h. wenn die Anzahl der Zyklen und deren Längen übereinstimmen.


Lösung

Es seien zunächst die Permutationen σ und τ zueinander konjugiert über die bijektive Abbildung

φ:M1⟶M2,

es gelte also

σ=φ−1∘τ∘φ.

Aus der Zyklendarstellung (einschließlich der Fixpunkte)

τ=τ1∘τ2∘⋯∘τk

ergibt sich gemäß Korollar 15.15 (Diskrete Mathematik (Osnabrück 2026))

σ=φ−1∘τ∘φ=φ−1∘τ1∘τ2∘⋯∘τk∘φ=(φ−1∘τ1∘φ)∘(φ−1∘τ2∘φ)∘⋯∘(φ−1∘τk∘φ).

Dabei sind die φ−1∘τi∘φ Zyklen der gleichen Länge wie τi und sie konstituieren zusammen die Zyklendarstellung von σ.

Es seien nun Permutationen σ und τ gegeben, die über den gleichen Typ (t1,…,tk) verfügen. Wir wählen aus dem Wirkungsbereich eines jeden Zyklus σi von σ ein Element  xi∈M1  heraus, und wir wählen aus dem Wirkungsbereich eines jeden Zyklus τi (mit der gleichen Länge wie σi) von τ ein Element  yi∈M2  heraus. Es besitzt jedes Element  x∈M1  eine eindeutige Darstellung

x=σj(xi)

mit einem i und einem j zwischen 1 und der Länge des Zyklus σi. Entsprechend besitzt jedes Element  y∈M2  eine eindeutige Darstellung

y=τj(yi).

Wir betrachten nun die bijektive Abbildung φ:M1→M2, die  x=σj(xi)  auf  y=τj(yi)  abbildet. Diese ist bijektiv und erfüllt

(φ−1∘τ∘φ)(x)=φ−1(τ(φ(x)))=φ−1(τ(φ(σj(xi))))=φ−1(τ(τj(yi)))=φ−1(τj+1(yi))=σj+1(xi)=σ(σj(xi))=σ(x),

sie stiftet also eine Konjugation zwischen σ und τ.


Aufgabe (6 (2+2+2) Punkte)

Es sei  vn+1=Mvn  eine Matrixrekursion über einem endlichen Körper K zur d×d-Matrix M.

  1. Zeige, dass die Lösungsfolge zu jedem Startvektor  v0∈Kd  letztlich periodisch ist.
  2. Zeige, dass bei  d=1  die Lösungsfolge von Anfang an periodisch ist.
  3. Zeige, dass bei  d≥2  die Lösungsfolge nicht von Anfang an periodisch sein muss.


Lösung erstellen


Aufgabe (3 Punkte)

Bestimme die erzeugende Funktion zur Folge der Quadratzahlen n2, n∈ℕ.


Lösung

Zur Folge der Quadratzahlen  an=n2  gehört als erzeugende Funktion die Potenzreihe ∑n=0∞n2zn. Wir gehen aus von der Identität

∑n=0∞nzn=z(1−z)2

aus Beispiel 17.9 (Diskrete Mathematik (Osnabrück 2026)). Ableiten ergibt daraus die Identität

∑n=0∞n2zn−1=(z(1−z)2)′=(1−z)2+2z(1−z)(1−z)4=(1−z)+2z(1−z)3=1+z(1−z)3.

Multiplikation mit z ergibt

z(1+z)(1−z)3.


Aufgabe (5 (1+1+1+2) Punkte)

Es seien R ein endlicher kommutativer Ring und es sei G der Nullteilergraph von R. Zu  f∈R  betrachten wir die Multiplikationsabbildung

μf:R⟶R,x⟼fx.
  1. Zeige, dass μf einen schwachen Graphhomomorphismus von G nach G induziert.
  2. Man gebe ein Beispiel, dass μf keinen (echten) Graphhomomorphismus induziert.
  3. Zeige, dass f genau dann eine Einheit in R ist, wenn μf einen Graphautomorphismus bewirkt.
  4. Man gebe ein Beispiel für einen endlichen kommutativen Ring R und einen Graphautomorphismus des Nullteilergraphen, der nicht von der Multiplikation mit einem Element herrührt.


Lösung

  1. Es seien  x1,x2∈R.  Aus  x1x2=0  folgt direkt
    (fx1)⋅(fx2)=f2x1x2=f2⋅0=0.

    Deshalb werden im Nullteilergraphen G verbundene Knotenpunkte auf einem gemeinsamen Punkt abgebildet oder aber auf ein Punktepaar, das ebenfalls verbunden ist. Dies bedeutet schwacher Homomorphismus.

  2. Es sei  R≠0  und  f=0.  Die zugehörige Multiplikationsabbildung ist die Nullabbildung, daher wird die Nullteilerkante zwischen 0 und 1 nicht auf eine Kante abgebildet, da die beiden Endpunkte vereinigt werden.
  3. Die Multiplikation mit f ist genau dann bijektiv, wenn f eine Einheit ist. In diesem Fall ist
    x1x2=0

    äquivalent zu

    fx1fx2=0,

    da man ja mit der Einheit f2 kürzen kann.

  4. Es sei  R=ℤ/(5),  im zugehörigen Nullteilergraphen ist 0 mit 1,2,3,4 verbunden, sonst gibt es keine Verbindungen. Daher ist jede Permutation auf 1,2,3,4 ein Graphautomorphismus. Davon gibt es 24, also kann schon allein aufgrund der Anzahl nicht jeder Graphautomorphismus von einer Multiplikation mit einer Einheit herkommen. Konkret ist die Transposition von 1 und 2 nicht durch eine Multiplikation gegeben, da eine Multiplikation, die 1 auf 2 abbildet, schon die Multiplikation mit 2 sein muss. Doch diese schickt 2 auf  2⋅2=4≠1. 


Aufgabe (4 Punkte)

Es sei G der Graph auf der Knotenmenge {a,b,c} mit der einzigen Kante {a,b}. Bestimme die Adjazenzmatrix A zu G sowie das charakteristische Polynom, die Eigenwerte mit Vielfachheiten und die Eigenräume zu A.


Lösung

Es ist  A=(010100000). 

Das charakteristische Polynom ist

det⁡(x−10−1x000x)=x3−x=x(x2−1)=x(x−1)(x+1).

Somit sind 0,1,−1 Eigenwerte mit algebraischer und geometrischer Vielfachheit 1.

Der Eigenraum zu 0 ist der Kern von (0−10−100000). Dieser ist

ℝ(001).

Der Eigenraum zu 1 ist der Kern von (1−10−110001). Dieser ist

ℝ(110).

Der Eigenraum zu −1 ist der Kern von (−1−10−1−1000−1). Dieser ist

ℝ(1−10).


Aufgabe (1 Punkt)

Begründe, dass der abgebildete Graph hamiltonsch ist.


Lösung erstellen


Aufgabe (5 Punkte)

Es sei  G=(V,E)  ein Graph, es sei  e∈E  eine Kante von G mit dem zugehörigen Kontraktionsgraphen G/e. Zeige, dass das chromatische Polynom die Gleichung

PG=PG∖{e}−PG/e

erfüllt.


Lösung

Es sei  e={u,v}.  Wir zeigen

PG∖{e}=PG+PG/e,

indem wir die zulässigen Färbungen analysieren. Eine zulässige Färbung von G ist eine zulässige Färbung f von G∖{e}, bei der auch die Bedingung  f(u)≠f(v)  erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von G∖{e} mit  f(u)=f(v)  den zulässigen Färbungen von G/e entsprechen. Über den surjektiven schwachen Graphhomomorphismus

φ:G⟶G/e

erhält man aus einer zulässigen Färbung f von G/e direkt eine (nichtzulässige) Färbung f∘φ von G mit identischem Wert auf u und v und damit direkt eine zulässige Färbung auf G∖{e} mit identischem Wert auf u und v. Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung

g:G∖{e}⟶B

mit  g(u)=g(v)  gegeben ist, so kann man dies direkt als eine Färbung auf G/e auffassen. Wenn d eine Kante von G/e ist, so liegt dieser Kante eine Kante d′ in G zugrunde, und daher überträgt sich die Zulässigkeit.