Klausur (Diskrete Mathematik II) — Lösungen

Klausur (Diskrete Mathematik II) — L¨
osungen
Aufgabe 1. (10 Punkte)
Geben Sie eine Formel f¨
ur die folgende Summe an, mit
beliebigem n ∈ N (Ihre Formel soll idealerweise Potenzen enthalten):
n−1
X
i4 + 2i3 + 2i2 − 2i.
i=1
P
1
ur die xk = k+1
L¨
osung: Die Summation ist einfach f¨
ur die fallenden Faktoriellen xk , f¨
xk+1 gilt.
Man kann die Potenzen xk von Hand durch die
xk darstellen oder dies systematisch
PFaktoriellen
n
k
n
mit Hilfe der Stirlingzahlen 1. Art tun: x = k=0 Sn,k x . In jedem Fall wird
x1 = x1 ,
x2 = x2 + x1 ,
x3 = x3 + 3x2 + x1 ,
x4 = x4 + 6x3 + 7x2 + x1 .
Die diskrete Stammfunktion von
f (x) := x4 + 2x3 + 2x2 − 2x
= (x4 + 6x3 + 7x2 + x) + (2x3 + 6x2 + 2x) + (2x2 + 2x) − 2x
= x4 + 8x3 + 15x2 + 3x
ist somit
1
8
15
3
f (x) = x5 + x4 + x3 + x2
5
4
3
2
und mit den Stirling-Zahlen 2. Art (Basiswechsel von fallenden Faktoriellen zu Potenzen)
X
x5 = x5 −10x4 +35x3 −50x2 +24x, x4 = x4 −6x3 +11x2 −6x, x3 = x3 −3x2 +x, x2 = x2 −x
P
13
wird
f (x) = 51 x5 − 32 x2 + 10
x. Weil die obere Summengrenze in der Aufgabe n − 1 war, ist
n−1
X
i=1
3
13
1
i4 + 2i3 + 2i2 − 2i = n5 − n2 + n.
5
2
10
Aufgabe 2. (6 Punkte) Bestimmen Sie die Anzahl der M¨oglichkeiten, 4620 als Produkt
von drei Faktoren (ungleich 1 und der Gr¨oße nach geordnet) zu schreiben, d.h.
4620 = m1 · m2 · m3
mit m1 , m2 , m3 ∈ N und 1 < m1 ≤ m2 ≤ m3 .
L¨
osung: Die Primfaktorzerlegung ist 4620 = 2·2·3·5·7·11 und eine Produktdarstellung mit drei
Faktoren (ungleich 1) entspricht einer Partition der Menge {21 , 22 , 3, 5, 7, 11} in drei (nicht-leere)
Teilmengen. Es gibt S6,3 (Stirling-Zahl 1. Art) solcher Partitionen; diese Zahl l¨asst sich mit der
Rekursionsformel f¨
ur Stirling-Zahlen schnell berechnen:
n=1
2
3
4
5
6
k=1 2
3
4
1
1 1
1 3
1
1 7
6
1
1 15 25 10
1 31 90 . . .
1
Weil aber die Partitionen {21 }, {22 }, {3, 5, 7, 11} und {22 }, {21 }, {3, 5, 7, 11} dieselbe Faktorisierung
ergeben, l¨asst sich 4620 insgesamt auf 90 − 1 = 89 Weisen als Produkt mit drei Faktoren
schreiben.
Aufgabe 3. (10 Punkte) Berechnen Sie eine Formel f¨
ur die rekursiv definierten Folgenglieder
(an ) mit a0 = 0 und an = 2an−1 + n f¨
ur n > 0.
L¨
osung: Mit A(x) :=
A(x) =
n≥0 an x
n
an xn =
X
P
X
ist
(2an−1 + n)xn = 2x
an−1 xn−1 + x
n>0
n≥0
n≥0
X
X
nxn−1
n>0
1
= 2x · A(x) + x ·
,
(1 − x)2
also mit Umstellen und Partialbruchzerlegung
1
1
4
2x − 3
A(x) = x ·
·
=x
+
1 − 2x (1 − x)2
1 − 2x (1 − x)2
X
X
X
X
X
X
= 4x
2n xn + 2
nxn+1 − 3
nxn = 4x
2n xn + 2
(n − 1)xn − 3
nxn
n≥0
=
X
n≥0
n>0
n≥0
n≥0
n>0
(2n+1 − n − 2)xn
n≥0
und somit an = 2n+1 − n − 2, passend zu den Anfangsgliedern 0, 1, 4, 11, 26, . . .
Aufgabe 4. (4 Punkte)
Begr¨
unden Sie folgende Aussagen u
¨ber den Graphen G:
1) G hat wenigstens neun verschiedene Eigenwerte.
2) F¨
ur den Spektralradius (Perron-Frobenius-Eigenwert) λ0 (G) gilt 2 < λ0 (G) ≤ 4.
L¨
osung: 1) Der Graph G hat Durchmesser diam(G) = 8 und nach einem Satz aus der Vorlesung
hat G mindestens 1 + diam(G) = 9 verschiedene Eigenwerte.
2) In der Vorlesung wurden die Graphen mit Spektralradius ≤ 2 klassifiziert; es waren die
(erweiterten) Dynkin-Diagramme. G ist nicht darunter, also muss der Spektralradius λ0 (G) > 2
sein. Außerdem hat G Maximalgrad 4, also ist nach Aufgabe 6 auch λ0 (G) ≤ 4.
Aufgabe 5. (12 Punkte) Berechnen Sie das Spektrum des folgenden Graphen und einen
positiven Eigenvektor:
L¨
osung: Das charakteristische Polynom ist
t5 − 6t3 − 4t2 + √
5t + 4 = (t − 1)(t + 1)2 (t2 − t − 4).
√
Das Spektrum des Graphen ist damit 1−2 17 , −1, −1, +1, 1+2 17 .
√
Nur der Perron-Frobenius-Eigenwert λ := 1+2 17 hat einen positive Eigenvektor. Man kann die
Matrix A−λI in Zeilen-Stufen-Form bringen; etwas einfacher ist vielleicht, das Gleichungssystem
direkt zu analysieren: f¨
ur den Eigenvektor (x1 , x2 , x3 , x4 , x5 )t — die zentrale Ecke sei 3 —
−1
erhalten wir Gleichungen −λx1 + x2 + x3 = x1 − λx2 + x3 = 0, woraus sofort x1 = x2 = 1−λ
x3
−1
folgt. Analog ist x3 − λx4 + x5 = x + 3 + x4 − λx5 = 0, mithin x4 = x5 = 1−λ
x3 . Weiterhin
−4
ullt wegen λ(λ − 1) = 4.
0 = x1 + x2 − λx3 + x + 4 + x5 = ( 1−λ − λ)x3 ; diese Gleichung ist erf¨
Wir erhalten (1, 1, λ − 1, 1, 1)t = (1, 1,
√
17−1
, 1, 1)t
2
als Eigenvektor zu λ.
Aufgabe 6. (8 Punkte) Es sei G ein ungerichteter, endlicher, zusammenh¨angender
Graph. Wir bezeichnen mit λ0 (G) den Spektralradius (Perron-Frobenius-Eigenwert) von
G und mit maxdeg(G) den Maximalgrad des Graphen, also die maximale Anzahl von
Nachbarn unter allen Ecken. Zeigen Sie:
1) λ0 (G) ≤ maxdeg(G).
2) Gleichheit λ0 (G) = maxdeg(G) gilt genau dann, wenn G regul¨ar ist.
L¨
osung: Der Graph G habe n Ecken; wir schreiben k := maxdeg(G) und v := (1, 1, . . . , 1)t f¨
ur
den Vektor, dessen n Eintr¨
age alle 1 sind. Dann gilt A(G) · v ≤ kv, weil nach Definition von
A(G) der i-te Eintrag des Vektors A(G) · v genau der Grad der Ecke i ist. Daraus folgt wie
im Beweis von Perron-Frobenius (PF4), dass λ0 ≤ k. (Sei v0 bzw. w0 Rechts- bzw. Links-PFEigenvektoren f¨
ur A, also w0t A = µ0 w0t und Av0 = λ0 v0 mit λ0 , µ0 > 0 und w0 > 0, v0 > 0.
Dann ist 0 < µ0 w0t v = w0t Av ≤ kw0t v und somit µ0 ≤ k. Außerdem stimmen Links- und RechtsSpektralradien u
ur allgemeine irreduzible nicht-negative Matrizen, ist
¨berein, λ0 = µ0 ; das gilt f¨
hier aber evident, weil A = A(G) symmetrisch ist.)
Gleichheit wird ebenfalls behandelt wie in (PF4): λ0 = k =⇒ w0t (Av − kv) = 0, also Av = kv,
¨
da w0 > 0. Weiterhin folgt aus Av = kv, dass G ein k-regul¨arer Graph ist. (War Ubungsaufgabe.)
Die R¨
uckrichtung ist einfach: ist G k-regul¨ar, dann gilt Av = kv, womit k = λ0 der PF-Eigenwert
von G ist und insbesondere λ0 = k = maxdeg(G) gilt.

Download Report