Zum Inhalt springen

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

Aus Wikiversity


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 ∑
Punkte 3 3 2 8 2 1 6 3 5 10 5 8 8 64




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Der Binomialkoeffizient (nk).
  2. Ein angeordneter kommutativer Ring R.
  3. Ein kleinstes Element in einer geordneten Menge (I,≼).
  4. Ein vollständiger Graph.
  5. Die Exzentrizität eines Punktes  v∈V  eines zusammenhängenden Graphen  G=(V,E). 
  6. Die Inzidenzmatrix zu einem Graphen  G=(V,E). 


Lösung

  1. Der Binomialkoeffizient ist durch
    (nk)=n!k!(n−k)!

    definiert.

  2. Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung „≥ “ auf R gibt, die die beiden Eigenschaften
    1. Aus a≥b folgt a+c≥b+c für beliebige a,b,c∈R,
    2. Aus a,b≥0 folgt ab≥0,

    erfüllt.

  3. Ein Element  x∈I  heißt kleinstes Element von I, wenn  x≼y  für jedes  y∈I  gilt.
  4. Ein Graph heißt vollständig, wenn je zwei Punkte miteinander durch eine Kante verbunden sind.
  5. Die Exzentrizität von v ist
    e(v)=max⁡(d(u,v)|u∈V).
  6. Die Inzidenzmatrix zu G ist die V×E-Matrix, deren Einträge durch
    bv,e:={1,falls v∈e,0 sonst,

    gegeben sind.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Anzahl von bijektiven Abbildungen.
  2. Das Lemma von Euklid.
  3. Der Paarungssatz (Heiratssatz)


Lösung

  1. Es seien M und N endliche Mengen, die beide n Elemente besitzen. Dann gibt es n! bijektive Abbildungen von M nach N.
  2. Es sei p eine Primzahl und p teile ein Produkt ab von natürlichen Zahlen a,b∈ℕ. Dann teilt p einen der Faktoren.
  3. Es sei M eine Menge, es sei I eine endliche Indexmenge und zu jedem  i∈I  sei eine Teilmenge  Mi⊆M  gegeben. Zu einer Teilmenge  J⊆I  setzen wir
    MJ=⋃j∈JMj.

    Für jede Teilmenge  J⊆I  gelte

    #(MJ)≥#(J).

    Dann gibt es eine injektive Abbildung

    f:I⟶M

    mit

     f(i)∈Mi. 


Aufgabe (2 Punkte)

In einer Schulklasse gibt es 32 Kinder; es wurden vier identische Pizzen bestellt, die gerecht auf die Kinder verteilt werden sollen. Es steht ein beliebig langes Messer zur Verfügung. Zeige, dass man durch 10 Schnitte die Aufteilung erreichen kann (die Pizzen dürfen nicht übereinander gelegt werden, und die Pizzen dürfen im gesamten Schneidevorgang nicht bewegt werden).


Lösung erstellen


Aufgabe (8 Punkte)

Beweise den Satz über die Addition und endliche Mengen.


Lösung

Die Voraussetzung besagt, dass es eine bijektive Abbildung

ψ:{1,…,m}⟶M

und eine bijektive Abbildung

φ:{1,…,n}⟶N

gibt. Die Abbildung

{1,…,n}⟶{m+1,…,m+n},i⟼m+i,

ist nach Aufgabe 1.10 (Diskrete Mathematik (Osnabrück 2026)) bijektiv, es sei θ die Umkehrabbildung. Somit ist nach Aufgabe 3.27 (Mathematik für Anwender (Osnabrück 2020-2021))  (3)

φ∘θ:{m+1,…,m+n}⟶N

ebenfalls bijektiv. Wir definieren nun eine Abbildung

F:{1,…,m+n}⟶M∪N

durch

F(k)={ψ(k), falls k∈{1,…,m},φ(θ(k)), falls k∈{m+1,…,m+n}.

Diese Abbildung ist surjektiv, da jedes Element aus M durch den ersten Fall und jedes Element aus N durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn

k≠ℓ

gegeben sind, und das eine Element zu {1,…,m} und das andere zu {m+1,…,m+n} gehört, so ist  F(k)∈M  und  F(ℓ)∈N  (oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von M und N. Wenn hingegen k und ℓ aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von F(k) und F(ℓ) aus der Injektivität von ψ bzw. von φ∘θ. Insgesamt erhalten wir also eine bijektive Abbildung

{1,…,m+n}⟶M∪N,

sodass die Anzahl von M∪N gleich m+n ist.


Aufgabe (2 (1+1) Punkte)

Für eine Opernaufführung braucht man für die verschiedenen Rollen eine Altstimme, zwei Sopranstimmen, zwei Tenorstimmen und einen Bass. Im Ensemble stehen zwei Altstimmen, drei Sopranistinnen, vier Tenöre und drei Bässe zur Verfügung.

  1. Wie viele Besetzungsmöglichkeiten für die Rollen gibt es?
  2. Wie viele Möglichkeiten gibt es, die Mitwirkenden auszuwählen, ohne Berücksichtigung der Rolle?


Lösung

  1. Für die Altrolle gibt es 2, für die Sopranrollen gibt es 3⋅2, für die Tenorrollen gibt es 4⋅3 und für die Bassrolle gibt es 3 Möglichkeiten. Insgesamt gibt es also
    2⋅6⋅12⋅3=432

    Besetzungsmöglichkeiten.

  2. Wenn man sich fragt, wer überhaupt eingesetzt wird, so muss man aus den jeweiligen Stimmlagen eine passende Anzahl auswählen. Dies führt auf
    (21)⋅(32)⋅(42)⋅(31)=2⋅3⋅6⋅3=108

    Möglichkeiten.


Aufgabe (1 Punkt)

Zeige, dass zwischen den Binomialkoeffizienten (nk) und (nk+1) der Zusammenhang

(nk+1)=(nk)⋅n−kk+1

besteht.


Lösung

Es ist

(nk+1)=n⋅(n−1)⋅(n−2)⋯(n−k+2)⋅(n−k+1)⋅(n−k)(k+1)⋅k⋅(k−1)⋅(k−2)⋯2⋅1=n⋅(n−1)⋅(n−2)⋯(n−k+2)⋅(n−k+1)k⋅(k−1)⋅(k−2)⋯2⋅1⋅n−kk+1=(nk)⋅n−kk+1.


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

Wir betrachten die durch die Wertetabelle

x 1 2 3 4 5 6 7 8
F(x) 3 5 1 7 8 2 6 4

gegebene Abbildung F von

M={1,2,…,8}

in sich selbst.

  1. Erstelle eine Wertetabelle für  F2=F∘F. 
  2. Erstelle eine Wertetabelle für  F3=F∘F∘F. 
  3. Begründe, dass sämtliche iterierten Hintereinanderschaltungen Fn bijektiv sind.
  4. Bestimme für jedes  x∈M  das minimale  n∈ℕ+  mit der Eigenschaft, dass
    Fn(x)=x

    ist.

  5. Bestimme das minimale  n∈ℕ+  mit der Eigenschaft, dass
    Fn(x)=x

    für alle  x∈M  ist.


Lösung

  1. Es ist
    x 1 2 3 4 5 6 7 8
    F(F(x)) 1 8 3 6 4 5 2 7
  2. Es ist
    x 1 2 3 4 5 6 7 8
    F(F(F(x))) 3 4 1 2 7 8 5 6
  3. Aus der Wertetabelle kann man unmittelbar entnehmen, dass F bijektiv ist. Nach Satz . (Mathematik für Anwender (Osnabrück 2020-2021)) sind dann sämtliche Hintereinanderschaltungen der Abbildung mit sich selbst wieder bijektiv.
  4. Die Abbildungsvorschrift bewirkt
    1↦3↦1

    und

    2↦5↦8↦4↦7↦6↦2.

    Für x=1,3 ist also  n=2  und für  x=2,5,8,4,7,6  ist  n=6. 

  5. Bei  n=6  sind nach Teil (4) die Zahlen 2,5,8,4,7,6 wieder an ihrer Stelle, aber auch 1,3 sind an ihrer Stelle, da 6 ein Vielfaches von 2 ist.


Aufgabe (3 Punkte)

Es sei M eine Menge mit n Elementen. Bestimme die Anzahl der Relationen auf M, die

  1. reflexiv
  2. symmetrisch
  3. reflexiv und symmetrisch

sind.


Lösung

Es sei  M={1,…,n}.  Eine Relation R ist gegeben durch eine bestimmte Menge von geordneten Paaren (x,y), x,y∈M. Daher kann man sich eine Relation auf M so vorstellen, dass in einer n×n-Tabelle gewisse Stellen angekreuzt werden und andere nicht.

Bei einer beliebigen Relation gibt es keine weiteren Bedingungen, sodass es 2n2 Relationen gibt (das war nicht gefragt).

Bei einer reflexiven Relation muss auf der Diagonalen immer ein Kreuz sein, ansonsten hat man keine Bedingung, es gibt also  n2−n=n(n−1)  freie Stellen und daher 2n(n−1) reflexive Relationen.

Bei einer symmetrischen Relation hat man oberhalb der Diagonalen (einschließlich dieser) volle Freiheiten (unterhalb der Diagonalen muss sich der Eintrag wiederholen). Da gibt es  n2−n2+n=n2+n2  Plätze und somit gibt es 2n2+n2 symmetrische Relationen.

Bei einer symmetrischen und reflexiven Relation hat man echt oberhalb der Diagonalen volle Wahlfreiheiten. Davon gibt es n2−n2 Plätze, sodass es 2n2−n2 symmetrische und reflexive Relationen gibt.


Aufgabe (5 Punkte)

Zeige, dass die Untergruppen von ℤ genau die Teilmengen der Form

ℤd={kd∣k∈ℤ}

mit einer eindeutig bestimmten nicht-negativen Zahl d sind.


Lösung

Eine Teilmenge der Form ℤd ist aufgrund des Distributivgesetzes eine Untergruppe. Es sei umgekehrt  H⊆ℤ  eine Untergruppe. Bei  H=0  kann man  d=0  nehmen, sodass wir voraussetzen dürfen, dass H neben 0 noch mindestens ein weiteres Element x enthält. Wenn x negativ ist, so muss die Untergruppe H auch das Negative davon, also −x enthalten, welches positiv ist. D.h. H enthält auch positive Zahlen. Es sei nun d die kleinste positive Zahl aus H. Wir behaupten  H=ℤd.  Dabei ist die Inklusion  ℤd⊆H  klar, da mit d alle (positiven und negativen) Vielfachen von d dazugehören müssen. Für die umgekehrte Inklusion sei  h∈H  beliebig. Nach der Division mit Rest gilt

h=qd+r mit 0≤r<d.

Wegen h∈H und qd∈H ist auch  r=h−qd∈H.  Nach der Wahl von d muss wegen  r<d  gelten:  r=0.  Dies bedeutet  h=qd  und damit  h∈ℤd,  also  H⊆ℤd. 


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

Wir betrachten auf ℕ+ die Relation ∼, die durch

m∼n

festgelegt ist, falls m eine Potenz von n und n eine Potenz von m teilt.

  1. Zeige, dass ∼ eine Äquivalenzrelation ist.
  2. Bestimme, welche der folgenden Elemente zueinander äquivalent sind, welche nicht.
    100,1000,9,125,500,27,10,210.
  3. Es sei Q die Quotientenmenge zu dieser Äquivalenzrelation und es sei ℙ die Menge der Primzahlen mit der Potenzmenge 𝔓(ℙ). Zeige, dass es eine natürliche Abbildung
    φ:ℕ+⟶𝔓(ℙ)

    gibt, die zu einer injektiven Abbildung

    φ~:Q⟶𝔓(ℙ)

    führt. Ist φ~ surjektiv?

  4. Wie sieht ein besonders einfaches Repräsentantensystem für die Äquivalenzrelation aus?


Lösung

  1. Die Reflexivität ist klar, da n die erste Potenz  n=n1  teilt. Die Symmetrie ist von der Formulierung her klar. Zum Nachweis der Transitivität sei  ℓ∼m  und  m∼n.  Dann ist ℓ ein Teiler von mr für ein gewisses  r∈ℕ  und m ist ein Teiler von ns für ein gewisses  s∈ℕ.  Dann ist
    ℓa=mr

    und

    mb=ns

    und daraus folgt

    ℓabr=mrbr=(mb)r=(ns)r=nsr,

    sodass ℓ eine Potenz von n teilt. Die umgekehrte Teilbarkeitsbeziehung ergibt sich genauso.

  2. Es ist offenbar  10∼100∼1000∼500  (es kommen jeweils die Primfaktoren 2 und 5 vor) und  9∼27=33,  darüber hinaus sind  125=53  und  210=2⋅3⋅5⋅7  nur zu sich selbst äquivalent. Dies ergibt sich aus der Charakterisierung der Relation mit Primteilern aus dem folgenden Teil.
  3. Wir betrachten die Abbildung
    φ:ℕ+⟶𝔓(ℙ),n⟼{Primteiler von n},

    die einer natürlichen Zahl  n∈ℕ+  die Menge der in der Primfaktorzerlegung von n vorkommenden Primzahlen zuordnet. Es sei  m∼n.  Da in einer Potenz (zu einem positiven Exponenten) einer Zahl die gleichen Primfaktoren vorkommen (nur ihre Vielfachheit ändert sich) folgt aus der Eigenschaft, dass m eine Potenz von n teilt, dass die Primteiler von m in den Primteilern von n enthalten sein müssen. Aus m∼n folgt also, dass die Primteiler der beiden Zahlen überhaupt gleich sind. Nach Lemma 11.13 (Diskrete Mathematik (Osnabrück 2026)) gibt es daher eine zugehörige Abbildung

    φ~:Q⟶𝔓(ℙ).

    Diese ist injektiv, da wenn von m und n die Primteiler übereinstimmen, dann m eine hinreichend große Potenz von n teilt und umgekehrt. Diese Abbildung ist nicht surjektiv, da nur endliche Teilmengen der Primzahlen im Bild liegen, es aber unendlich viele Primzahlen gibt.

  4. Ein Repräsentantensystem besteht aus allen natürlichen Zahlen mit der Eigenschaft, dass sämtliche Exponenten in ihrer Primfaktorzerlegung gleich 1 sind.


Aufgabe (5 Punkte)

Auf Ruggetong heißt die Währung Riggating und es gibt nur zwei Münzen (mit vollen Riggatingbeträgen). Es kann jeder volle Geldbetrag damit bezahlt werden. Zeige, dass dann die minimale Darstellung eines jeden Geldbetrages eindeutig ist. Wie kann man sie berechnen?


Lösung

Da insbesondere der Betrag 1 beglichen werden kann, muss es eine 1-Riggating-Münze geben. Den Nennbetrag der zweiten Riggating-Münze nennen wir  d>1.  Wir behaupten, dass man die Darstellung des Riggating-Preises n mit der minimalen Anzahl von Münzen findet, wenn man

n=sd+r

mit r zwischen 0 und d−1 berechnet. Die Münzanzahl ist dann s+r. Die Darstellung kann man erhalten, indem man solange d-Münzen anhäuft, solange man unterhalb von n bleibt, mit der nächsten zusätzlichen d-Münze wäre man also schon drüber. Was dann noch fehlt füllt man mit 1-Münzen auf. Zum Nachweis der Eindeutigkeit: Es sei

n=td+u

eine weitere Darstellung mit

t≠s.

Wir behaupten zunächst

t<s.

Denn andernfalls wäre

t>s,

also

t≥s+1,

und dann wäre

td+u≥(s+1)d=sd+d>sd+r=n,

das wäre also keine Darstellung von n.

Für die Anzahl der in der zweiten Darstellung verwendeten Münzen gilt somit (dafür sei n≠1)

t+u=t+n−td=n−t(d−1)>n−s(d−1)=s+n−sd=s+r.

Bei  n=1  ist die Darstellung sowieso eindeutig.


Aufgabe (8 Punkte)

Beweise den Satz von Kirchhoff über die Anzahl der Spannbäume.


Lösung

Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist 1. Bei zwei Knoten und m verbindenden Kanten gibt es m Spannbäume. Die Adjazenzmatrix ist (0mm0) und die Gradmatrix ist (m00m). Daher ist die Laplace-Matrix gleich (m−m−mm). Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante m.

Es sei nun die Aussage für alle Multigraphen mit höchstens n−1 Knoten bewiesen, und sei ein Multigraph G mit n Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl m der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon sind die Nullmatrix mit Determinante 0. Es sei also die Aussage auch für alle Graphen mit n Knoten und mit weniger als m Kanten bewiesen, und G habe n Knoten und m Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werde eine Kante zwischen 1 und 2 herausgenommen (was für die Kontraktion bedeutet, dass alle parallelen Kanten auch kontrahiert werden). von denen es  a12≥1  gibt. Die Laplace-Matrix von G sei

(d1−a12−a13…−a1n−a12d2−a23…−a2n−a13−a23d3…−a3n⋮⋮⋮⋱⋮−a1n−a2n−a3n…dn).

Die Laplace-Matrix von G∖{e} ist

(d1−1−a12+1−a13…−a1n−a12+1d2−1−a23…−a2n−a13−a23d3…−a3n⋮⋮⋮⋱⋮−a1n−a2n−a3n…dn)

und die Laplace-Matrix zur Kontraktion G/e ist die (n−1)×(n−1)-Matrix

(d1+d2−2a12−a13−a23…−a1n−a2n−a13−a23d3…−a3n⋮⋮⋱⋮−a1n−a2n−a3n…dn).

Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach

(d2−a23…−a2n−a23d3…−a3n⋮⋮⋱⋮−a2n−a3n…dn),
(d2−1−a23…−a2n−a23d3…−a3n⋮⋮⋱⋮−a2n−a3n…dn)
(d3…−a3n⋮⋱⋮−a3n…dn).

Entwicklung nach der ersten Spalte (für die beiden ersten Matrizen) zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit Lemma 21.11 (Diskrete Mathematik (Osnabrück 2026)) aus den beiden Induktionsvoraussetzungen.


Aufgabe weiter


a) Erstelle einen Nachbarschaftsgraphen zu den Bundesländern.
b) Bestimme die Blätter.
c) Was ist der Abstand von Baden-Württemberg zu Niedersachsen?
d) Was ist der Maximalgrad und in welchem Bundesland wird er angenommen?
e) Was ist die Exzentrizität von Thüringen?
f) Ist Deutschland ein Baum?
g) Ist Deutschland hamiltonsch?
h) Ist Deutschland hamiltonsch, wenn man die Blätter herausnimmt?
i) Was ist der Umfang von Deutschland?


Lösung


a)
Achtung, im Bild fehlt Bremen und Berlin!!!


b) Die Blätter sind Bremen, Berlin, Saarland.
c) Der Abstand von Niedersachsen zu Baden-Württemberg ist 2. (über Hessen).
d) Der Maximalgrad ist 9, er wird in Niedersachsen angenommen.
e) Die Exzentrizität ist 3 (nach Berlin oder ins Saarland).
f) Deutschland ist kein Baum, da es den Kreis Niedersachsen-Hessen-Thüringen enthält.
g) Deutschland ist nicht hamiltonsch, da es Blätter enthält.
h) Ohne die Blätter ist Deutschland hamiltonsch, ein Hamiltonkreis ist

Niedersachsen – Hamburg – Schleswig-Holstein – Mecklenburg-Vorpommern – Brandenburg – Sachsen-Anhalt – Sachsen – Thüringen – Bayern – Baden-Württemberg – Hessen – Rheinland-Pfalz – Nordrhein-Westfalen.


i) Der Umfang ist 13. Wegen der drei Blätter kann er nicht größer sein, soeben wurde ein Kreis mit 13 Ländern angegeben.