Zum Inhalt springen

Kurs:Diskrete Mathematik/22/Klausur

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.



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.



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?



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.



Aufgabe * (2 Punkte)

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



Aufgabe * (2 Punkte)

Berechne

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



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.



Aufgabe * (3 Punkte)

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



Aufgabe * (1 Punkt)

Finde die Primfaktorzerlegung von

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



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.



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.



Aufgabe * (2 Punkte)

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



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.



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.



Aufgabe * (3 Punkte)

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



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.



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.



Aufgabe (1 Punkt)

Begründe, dass der abgebildete Graph hamiltonsch ist.



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.