286 Lösungen

Lösungen zu ausgewählten Übungen

1.3 Angenommen A ~ N ist ein Gegenbeispiel. Wir betrachten das Inzidenzsystem (A, N ........ A, I) mit alb {:} la-bi = 9. Für 1O:S a :S 91 ist r(a) = 2, ansonsten r(a) = l. Es gilt daher 2: r(a) ~ 92, und andererseits 2: r(b):S 90, Widerspruch. Für

aEA bEN,A

lAI = 54 nehmen wir sechs 9'er Blocks, jeweils 10 auseinander.

1.5 Jede Partei hat zwischen 1 und 75 Sitze. Hält die erste Partei i Sitze, so gibt es für die zweite Partei die Möglichkeiten 76 - i, ... ,75. Die Gesamtzahl ist also 75

2: i = C26 ). i=l

1.9 Nach Induktion gilt M(i) :S M(j) für 1 :S i :S j :S n. Sei 2 :S k :S M(n). Dann ist Sn+1,k - Sn+1,k-l = (Sn,k-l - Sn,k-2) + k(Sn,k - Sn,k-d + Sn,k-l > 0 nach Induktion. Ebenso schließt man Sn+1,k - Sn,k+1 > 0 für k ~ M(n) + 2.

1.10 Für gegebenes n sei m die Zahl mit m! :S n < (m + I)! und am maximal mit 0 :S n - amm!. Es folgt 1 :S am :S mund n - amm! < m!. Die Existenz und Eindeutigkeit folgt nun mit Induktion nach m.

1.13 Der Trick ist, die n - k fehlenden Zahlen zu betrachten. Schreiben wir sie als senkrechte Striche, dann können die k Elemente in die n - k + 1 Zwischenräume plaziert werden, und die Menge ergibt sich von links nach rechts. Zu b) zeigt man, daß 2: fn,k die Fibonacci Rekursion erfüllt.

k

1.16 Es gibt 12 Möglichkeiten, daß die erste und letzte Karte eine Dame ist und 50! Möglichkeiten dazwischen. Die Wahrscheinlichkeit ist daher 12· 50!/52! = 2~1 .

1.19 Von n+ 1 Zahlen müssen zwei aufeinanderfolgen, also sind sie relativ prim. Zum zweiten Problem schreibe jede Zahl in der Form 2k m, m ungerade, 1 :S m :S 2n - l. Es müssen also zwei Zahlen in einer Klasse {2 k m : k ~ O} liegen. {2, 4, ... 2n} und {n + 1, n + 2, ... ,2n} zeigen, daß beide Behauptungen für n Zahlen falsch sind.

1.21 Sei (k, C) der größte gemeinsame Teiler von kund C. Für dln sei Sd = {k-ä' : (k,d) = 1,1 :S k :S d}, also ISdl = cp(d). Aus k-ä' = k'-{j; folgt kd' = kId, und daher k = k', d = d'. Die Mengen Sd sind also paarweise disjunkt. Sei umgekehrt m:S n, (m,n) = -ä', so ist mE Sd,und wir erhalten S = 2: Sd.

dln 2

1.24 Sei r wie im Hinweis, dann gilt r :S; < n(n - 1) wegen n ~ 4. Die Anzahl der Einsen in der Inzidenzmatrix spaltenweise gezählt ist daher (n - 2)!r < n!. Es muß also eine Zeile mit lauter Nullen vorkommen.

1.28 Seien Rund R' zwei Spaltenmengen mit IRI = IR'I = r. Es ist leicht, eine Bijektion zwischen allen Wegen mit den r Diagonalen in R bzw. R' herzustellen. Wir können uns also auf die ersten r Spalten beschränken. Die Wege sind dann durch die r Diagonalen in den ersten r Spalten eindeutig bestimmt. Ersetzen wir die Diagonalen durch Waagerechten, so erhält man eine Bijektion auf die Wege im

n n x (n - r)-Gitter, und es folgt für die Gesamtzahl 2: (~) enn-r).

r=O

Lösungen 287

1.29 Sei f(n, i) die Anzahl mit i am Anfang. Die folgende Zahl ist dann i + 1 oder i-I mit den Anzahlen f +, f _. Identifizieren wir i mit i + 1 und erniedrigen alle Zahlen> i + 1 um 1, so sehen wir 1+ = f(n -1, i), und analog f- = f(n -1, i-I). Die Zahlen fn,i erfüllen also die Binomialrekursion mit f(n, 1) = 1. Es gilt daher f(n, i) = (~~n, L- f(n, i) = 2n- 1 •

i

1.32 Klarerweise ist 0 :::; bj :::; n - j. Da es höchstens n! Folgen b1 , ..• ,bn Folgen gibt, bleibt zu zeigen, daß es zu einer Folge b1 , •.. , bn eine Permutation 7r gibt. 7r

wird von hinten aufgebaut. Ist bn - 1 = 1, so steht n - 1 hinter bn , ansonsten vor n. Nun wird n - 2 je nach bn - 2 plaziert, usf.

1.36 Fügen wir n in eine Permutation 7r von {I, ... , n - I} ein, so erhöhen wir die Anzahl der Anstiege um 1 oder O. Hat 7r k - 1 Anstiege, so erhöhen wir 7r genau dann um 1, wenn n in einen der n - k - 1 Nicht-Anstiege oder am Ende eingefügt wird. Eine Permutation 7r mit k Anstiegen wird genau dann nicht erhöht, wenn n in einen der k Anstiege oder am Anfang eingefügt wird.

1.39 Aus r&(r - ~)& = r(r -1) ... (r - k+ 1)(2r -1) ... (2r - 2k+ 1)/2k = (2r)2k /22k

folgt m c~t) = (;D e:) /22k . Mit r = k = n erhalten wir (n~t) = e:) /22n und durch Negation (-!(2) = (- ~)n e:). 1.40 Wir betrachten wie im Hinweis die Wege von (0,0) nach (a + b, a - b). Die erlaubten Wege müssen (1,1) als ersten Punkt benutzen. Insgesamt gibt es (a~~~l) Wege von (1,1) nach (a + b, a - b), da sie durch die Positionen der a - 1 Stimmen für A eindeutig bestimmt sind. Wir müssen nun alle Wege W abziehen, die die x­Achse berühren. Zu einem solchen W konstruieren wir einen Weg W' von (1, -1) nach (a + b, a - b), indem wir alle Stücke zwischen Punkten mit x = 0 unter die x­Achse reflektieren und am Ende unverändert lassen. Man sieht sofort, daß W -+ W' eine Bijektion auf alle Wege von (1, -1) nach (a + b, a - b) ist, und wir erhalten als Ergebnis (a+b-1) _ (a+b-1) = a-b (a+b).

a-1 a a+b a n/2

1.42 Es sei n gerade. Aus (~) = I (~=~) folgt an = 1 + L- [(~) -1 + (n-~+l) -1] = k=l

n/2 1 + ~ L- [k(~=~)-l + (n - k + 1)(~=!)-1] und mit (~=~) = (~=!), an = 1 +

k=l n/2 -1

n;t1 L- (~=~) = 1 + ~an-1 . Der Fall n ungerade geht analog. Für die ersten k=l

Werte haben wir ao = 1, a1 = 2, a2 = ~,a3 = a4 = ~ > a5 = 153. Ist an-i> 2+ n~l' so folgt a > !!:±.l(2 + _2_) + 1 = 2 + l(l + !!:±.l) > 2 + 1. oder _n_a > 1. Für n 2n n-1 n n-1 n' 2n+2 n an+! - an gilt daher an+! - an = (2:-;"22 - l)an + 1 = -2n~2an + 1 < 0, somit an+1 < an für n ;::: 4 durch Induktion. Der Grenzwert existiert daher und ist 2.

1.44 Ist n = 2m > 2, so steht 1 in Zeile m und Spalte 2m ohne Kreis. Sei also n ungerade. Angenommen, n = p > 3 ist prim. Die Zeilen k, welche Einträge in Spalte p liefern, erfüllen 2k :::; p :::; 3k, und der Eintrag in Spalte p ist (P~2k). Aus ~ :::; k :::; ~ folgt 1 < k < p, also sind kund p relativ prim und daher auch kund

288 Lösungen

p-2k. Nun haben wir (p!2k) = p!2k (p!2k~l) oder (p-2k) (p!2k) = k(p!2k~1)' und

es folgt kl (p!2k)' das heißt, jeder Eintrag in Spalte p ist umkreist. Sei n = p(2m + 1) eine zusammengesetzte ungerade Zahl, p Primzahl, m ~ 1, dann erfüllt k = pm die Bedingungen 2k ::; n ::; 3k, und man sieht leicht, daß (n!2k) = (P;) kein Vielfaches von k ist.

1.45 Sei die Verteilung (Pl, ... ,P6). Dann gilt 1 = (I:Pi)2 ::; 6 I:p~ (direkt beweisen oder Übung 2.22).

1.49 Sei X : 'Ir -+ N die Zufallsvariable mit X = k, falls das zweite As in der k-ten n-l

Karte liegt, somit p(X = k) = (k -1)(n - k)/(;) mit I: (k -1)(n - k) = (;). Sei k=2

n-l S = (;)EX = I: k(k - l)(n - k). Ersetzen wir den Laufindex k durch n + 1 - k,

k=2 n-l

so erhalten wir 2S = (n + 1) I: (k - l)(n - k), somit EX = !!f!. k=2

1.51 Wir können annehmen, daß x zwischen 0 und 1 liegt. Es sei kx = q + rk mit q E N,O < rk < 1. Wir klassifizieren die Zahlen kx nach ihren Resten rk. Falls rk ::; ~ oder rk ~ n~l ist, so sind wir fertig. Die n - 1 Reste fallen also in eine der n - 2 Klassen ~ < r ::; ~, ... , n~2 < r ::; n~l. Es gibt also kx, lx (k < l) mit Iri - rkl < ~, und (l- k)x ist die gesuchte Zahl.

1.53 Sei A das Ereignis wie im Hinweis, dann ist p(A) = Tm, also U p(A)::; IAI=k

(~) Tm. Aus (~) < n k /2k- l folgt mit n < 2k/2, (~) < 2 k22 -k+1, also U p(A) <

IAI=k 2-t+1 ::; ~ wegen k ~ 4. Aus Symmetrie gilt auch p( U B) < ~, wobei B das

IBI=k Ereignis ist, daß alle Personen in B paarweise nicht bekannt sind. R(k, k) ~ 2k / 2

folgt.

1.55 Sei s wie im Hinweis. Wir nennen ai, i > s, einen Kandidaten, falls ai > aj ist für alle j ::; s. Die Strategie, ai als Maximum zu erklären, ist erfolgreich, wenn (A) ai = Max ist und (B) aj, s < j < i, keine Kandidaten sind. Die Wahrscheinlich­keit für (A) ist ~ und für (B) i~l' also ist die Strategie für ai mit Wahrscheinlich­keit ~ i~l erfolgreich. Summation über i = s + 1, s + 2, ... ergibt als Gewinnchance

n p(s) = I: '! i~l = '!(Hn- l - Hs-d '" '! log;. Maximierung von f(x) = ~ logx

i=s+l

ergibt x = e und somit f(xmax ) '" ~ '" 0.37. Die Rundung von X max zur nächsten rationalen Zahl ; ändert das Ergebnis nur unwesentlich.

2.1 Multiplikation mit 2n- l /n! ergibt mit Sn = 2nTn/n! die Rekursion Sn = Sn-l + 3· 2n - l = 3(2n - 1) + So. Also ist die Lösung Tn = 3 . nL

2.4 Sei Tn die n-te Zahl. Wir haben To = 1, Tl = 0 und nach Vorschrift Tn

nTn- l + (_I)n. Dies ist genau die Rekursion für die Derangement Zahlen.

Lösungen 289

n-l n 2.6 Mit partieller Summation haben wir E (k+1~tk+2) = E H xx-2 = _x- l Hxlf+

k=l I n n E(x + l)-l x-1 = _x- l Hxlf + Ex-2 = -x-I(Hx + 1)lf = 1 - ~+11. I I

n n 2.9 Zu beweisen ist xn = '" lli (n-l) x/!;. oder (x+n-l) = '" (n-l) (X) aber dies ist

L.J k! k-l n L.J n-k k' k=O k=O

genau die Vandermondesche Formel. Die Inversionsformel folgt nun durch x -+ -x.

2.13 Sei S die Menge aller r-Untermengen, und Ei die Eigenschaft, daß i nicht in A liegt, i E M. Dann gilt N(Ei1 ••• E ik ) = (~)(n;k), und die Formel folgt.

2.17 Sei PH die Wahrscheinlichkeit, kein Herz zu erhalten, dann ist PH = (~~) / a~), analog für die anderen Farben. Die Wahrscheinlichkeit PHK ohne Herz und Karo ist PHK = (~~)/(~~), und schließlich PHKP = 1/(~~) ohne Herz, Karo, Pik. Inklusion­Exklusion besorgt den Rest. Frage b) geht analog.

2.18 Wir können die n-te Scheibe nur bewegen, wenn der (n -1)-Turm in richtiger Ordnung auf B liegt. Dies ergibt die Rekursion Tn = 2Tn- 1 + 1, Tl = 1, also Tn = 2n - 1. In b) erhalten wir Sn = 3Sn- 1 + 2, SI = 2, also Sn = 3n - 1. Die Rekursion für Rn ist Rn = 2Rn-l + 2, RI = 2, also Rn = 2n+1 - 2 = 2Tn.

2.20 Sei 2n gegeben. In der ersten Runde scheiden 2,4, ... ,2n aus. Die nächste Run­de beginnt wieder bei 1, und durch die Transformation 1,2,3, ... , n -+ 1,3,5, ... , 2n-1, erhalten wir J (2n) = 2J (n) -1. Die Rekursion für J(2n + 1) wird analog bewiesen. Sei n = 2m + e, 0 ~ e < 2m , dann folgt mit Induktion nach m, J(n) = 2t' + 1.

2.22 Wir haben S = E (ak -aj)(bk -bj) = E (ak -aj)(bk -bj), also 2S = E(ak-j<k k<j j,k

n n n aj)(bk -bj) = Eakbk - Eakbj - Eajbk+ Eajbj = 2n E akbk -2( E ad( E bd·

j,k j,k j,k j,k k=1 k=1 k=1 Es folgt (E ak)(E bk) = nE akbk - S. Falls al ~ ... , ~ an, b1 ~ ... ~ bn gilt, so

k k k ist S ~ o. 2.24 Induktion nach n. Wir betrachten den Hof H 1 und legen durch ihn eine Gerade, auf der kein weiterer Hof oder Brunnen liegt. Durch Drehen dieser Geraden läßt sich stets erreichen, daß in einer der entstehenden Halbebenen gleichviele Höfe und Brunnen liegen, und zwar zusammen mindestens 2 und höchstens 2(n - 1).

2.26 Eine Strecke PQ mit Länge d nennen wir einen Durchmesser. Angenommen, von P gehen drei Durchmesser PA, PB, PC aus. Die Punkte A, B, C liegen auf einem Kreis um P vom Radius d, und da d maximal ist, auf einem Bogenstück der Länge ~ df. Sei B zwischen A und C auf diesem Bogen, dann geht von B außer BP kein weiterer Durchmesser aus. Damit haben wir zwei Möglichkeiten: Entweder von jedem Punkt gehen genau zwei Durchmesser aus, oder es gibt einen Punkt, von dem höchstens ein Durchmesser ausgeht. Im ersten Fall sind wir fertig mit zweifachem Abzählen, im zweiten durch Induktion.

2.29 Die Gleichung folgt aus (3) und (12) in Abschnitt 2.2. In b) setze f(x) = (n~x).

290 Lösungen

2.30 Ist n = k + (k + 1) + ... + (f - 1), so folgt wie im Hinweis 2n = (f - k)(f + k - 1). Einer der beiden Faktoren ist gerade, der andere ungerade.Ist 2n = xy eine Zerlegung, so erhalten wir mit k = ~Ix - yl, f = ~(x + y) + ~ eine Zerlegung 2n = (f - k) (f + k - 1). Die gesuchte Anzahl ist also gleich der Anzahl der ungeraden Teiler von n, das heißt I1(ki + 1) mit n = 2m I1Pi >2 Pfi nach Übung 1.2.

2.33 Wir haben (-1)k+1(k~1)-1 - (-1)k(;r 1 = (_1)k+1(n;;1)-1[~ + n~k] =

(_1)k+1(n;;1)-1 n;1, also I:(-1)XC)-1 = ~(_1)X-1(n;1)-1. Mit Summation n 1

folgt I: (_l)k (;) - = ~t~ [( _1)n + 1] = 2~ [n = gerade]. k=O

b -1 n-1 2.37 Es gilt I:xm = Sm(b) - Sm(a). Aus I: km = (_l)m I: km = (_1)m.

a k=-n+1 k=1 o

Sm(n) folgt (-l)mSm(n) = I: xm = Sm(O) - Sm(1- n) = -Sm(l - n), also a). -n+1

Daraus resultiert (-l)mSm(l) = 0 und (-l)mSm(~) = -Sm(~), also die weiteren Behauptungen.

n 2.39 Mit bk = k!ak resultiert n! = I: (;)bk, und daraus mittels Binomialinversion

k=O bn = Dn (Derangementzahl), somit an = ~.

2.42 Sei P3(n) die erste Anzahl und p::;2(n) die zweite. Im ersten Fall sei Ei die Eigenschaft, daß 3i als Summand vorkommt. Mit Inklusion -Exklusion erhalten wir P3(n) = p(n) - p(n - 3) - p(n - 6) - .. . +p(n - 3 - 6) +p(n - 3 - 9) + ... Im zweiten Fall sei Ei die Eigenschaft, daß der Summand i dreimal vorkommt, und es resultiert dieselbe alternierende Summe. Allgemein gilt Pd(n) = p::;d-1(n).

2.45 Ist Ei die Eigenschaft, daß i Fixpunkt ist, so gilt N(Ei1 ... Eik ) = (n - k)! für n-t n-t .

k ~ t, also ist die gesuchte Zahl Ft = I: (_l)i (tti)(t~i)(n - t - i)! = W I: (-i~)' = i=O i=O

(7)Dn- t . Die Gleichung Ft = G)Dn- t ist natürlich auch unmittelbar klar.

3.2 Wir haben f(O) = 1, f(l) = 2. Sei A dick. Falls n ~ A ist, so ist A dick in { 1, ... , n - I}, falls n E A ist, so ist {i - 1 : i E A " n} dick in {I, ... , n - 2} bzw. 0, falls A = {n}. Es folgt f(n) = f(n -1) + f(n - 2), also f(n) = Fn+2 . Die dicken k­Mengen von {I, ... , n -I} sind genau die k-Untermengen von {k, ... , n - I}, somit

n Fn+1 = I: (n;;k). c) ist nach a) äquivalent zu (n+1)+ I: (~~~)f(k-1) = f(2n). Sei

k k=1 A = {I, ... , n - I}, B = {n, ... , 2n}, dann folgt c) durch Klassifikation der dicken Mengen X mit IX n BI = n - k.

3.5 Es ist LnFn = Fn- 1Fn + FnFn+1. Andererseits sieht man F2n = Fn-1Fn + FnFn+1 durch wiederholte Anwendung der Fibonacci Rekursion (siehe Übung 3.33). Einsetzen in Fn = ~(</>n - Jn) ergibt Ln = </>n + Jn.

3.9 Betrachten wir die erste Zahl. Ist sie 1 oder 2, so können wir sie mit f(n - 1) Wörtern der Länge n - 1 kombinieren, ist sie 0, so muß die zweite 1 oder 2 sein,

Lösungen 291

und wir können den Rest auf f(n - 2) Arten wählen. Die Rekursion ist also f(n) = 2(f(n - 1) + f(n - 2)) + [n = 0] + [n = 1] mit f(O) = 1. Für die erzeugende Funktion F(z) ergibt dies F(z) = l-if-='2z2 und mit der üblichen Methode f(n) = ~(1 + V3)n + 3-~y'3"(1- V3)n.

3.12 Es ist ak = bn = nl>., also A(z) = E (~)zk = (1 + z)n und B(z) = E ':t~zn = k n~k

'" zn _ k '" zn-k _ k z L...J (n-k)! - Z L...J (n-k)! - z e . n~k n~k

3.14 Wir verwenden die Rekursion Sn+l,m+1 = E (~)Sk,m aus Übung 1.35. Es gilt k

also eZSm(z) = E (E (~)Sk,m)~~ = E Sn+1,m+1 ~~, somit S:n+1(z) = eZSm(z). n>O k n>O

Mit So(z) = 1 folgt Si(z) = eZ, also Sl(Z) = eZ-1 (wegen Sl(O) = 0). Mit Induktion erhalten wir Bm(z) = (e%~~)">, E Sm(Z)tm = et(e%-l).

m~O

3.16 Es gilt E F2n z2n = !(F(z)+F(-z)) = !(1-':-z2 + 1+~~z2) = 1-3~~+Z4 nach n~O

der vorigen Übung, also E F2nZn = 1-3~+z2' n

3.17 G(z) - 1 ist die Konvolution von G(z) und E n zn = (l-='Z)2' Somit gilt n~l

G(z) = ~=;~t~~ = 1 + 1-3~+z2 und nach der vorigen Übung gn = F2n für n 2: 1.

3.20 Sei x fest, dann ist F(z)X = exp(xlogF(z)) = exp(xlog(l + E akzk)) = k~l

~ t '" ~ exp(x E - t ( E ak zk ) ) = E ~! (E - t ( E akzk)t)m. Also ist [zn]F(z)x t~l k~l m~O t~l k~l

ein Polynom Pn(x) vom Grad n mit Pn(O) = 0 für n > O. Die erste Konvolution folgt aus F(z)X F(z)Y = F(z)x+y, die zweite durch Vergleich des Koeffizienten von zn-l in F'(z)F(z)x-IF(z)Y = F'(z)F(z)x+Y-l, da F'(z)F(z)X-l = X-I tzF(zY = X-I E nPn(x)zn-l ist.

n~O

3.24 EX = E npn, PHz) = EnPnzn-1, also EX = P~(1). VX = EX2 -n>l

(EX? = En2Pn - (EnPn)2 = En(n -1)Pn + EnPn - (EnPn)2, also VX = P~(l) + P~(1) - (P~(1))2. c) ist klar.

3.26 Sei k die Anzahl "Kopf", 0 :::; k :::; n. Dann ist p(X = k) = (~)2-n, also Px(z) = 2-n E G) = (~)n. Aus Übung 3.24 folgt EX = ~, VX = ~.

k

3.28 Wir haben p(Xn = k) = ~. Durch Klassifikation nach der Position von

n folgt In,k = In-1,k + ... + In- 1,k-n+1, also Pn(z) = l+z+':,/zn-l Pn-1(z), so-n . 1 n· 1

mit Pn(z) = I11+z+.:/r , da P1(z) = 1 ist. Mit P~(z) = E (I11+ z+ .. :+ zJ - ). i=l i=l j#i J

1+2Z+ ... ~(i-l)Zi-2 berechnet man EX = P~(1) = f= i;l = n(~-l). Analog für V X i=l

292 Lösungen

nach Übung 3.24.

3.29 Betrachte die linke 3 x 1-Kante. Entweder sie enthält einen senkrechten Do­minostein (oben oder unten), dann können wir mit B n - I Möglichkeiten fortsetzen. Oder alle drei Steine sind waagerecht und wir setzen auf An - 2 Arten fort. Die Rekursion ist daher An = 2Bn- 1 + An- 2 + [n = 0], und durch eine analoge Über­legung Bn = An- I + Bn- 2. Daraus erhalten wir durch Eliminierung von B(z), A(z) = 1-~~i:Z4' Wir erkennen A2n+l = 0, was natürlich klar ist. Behandeln wir

l-z . "bl' h 'bt . h A (2+V3)n (2-V3t I-4z+z2 WIe u IC , so ergl SIC 2n = 3-,,13 + 3+,,13

3.31 Wie in Übung 3.22 erhalten wir A(z) = (I-Z)(I-}2)(I-z4) ... , also A(z2) =

(1 - z)A(z). Für B(z) folgt B(z) = ~~zl, also B(Z2) = ~~z:) = ~f;' Somit gilt A(z) = (1 + Z)B(Z2), das heißt a2n = a2n+1 = bn.

3.34 Wir wissen L (~)wk = (1 + w)n, also nach Übung 3.15, L (2k~I)W2k+l = k k

(l+W)n;(I-Wt . Klammern wir links waus und setzen w 2 = Z, so erhalten wir

VzL ( n )zk - (l+v'Zt-(I-v'Zt und mit z = 5 L ( n )5k = 2n - 1 F k 2k+1 - 2' , k 2k+1 n·

3.38 Sei F(x, y) = L fm,nxmyn. Aus den Anfangsbedingungen erhält man L fO,nyn m,n n

- I '" f m - I d d '" f m n - l-xy F" > 1 - l-y' L...J m,OX - I-x' un araus L...J m,nX Y - (I-x)(l-y)' ur m, n _ m mn=O

ergibt die Rekursion L fm,nxmyn = y(F(x, y) - I~Y) + (q - 1)xy F(x, y), wor-m,n~l

aus F(x, y) = I~X . l-(l+(~-I)X)Y folgt. Somit ist [yn] F(x, y) = (1 + (q - 1)x)n = n L (~) (q - 1 )kxk. Multiplikation mit I~X (das heißt Summation der [xk]) ergibt

k=O m

schließlich fm,n = L (~)(q -1)k. k=O

3.40 Mit Konvolution haben wir G(z) = -2zG(z) + (G(Z))2 + z, also G(z) =

1+2Z-~ (da das Pluszeichen wegen G(O) = 0 nicht geht). Verwenden wir Übung

1.39, so ergibt dies g2n+l = 0, g2n = (_1)n (2~)! e:"::-12). Siehe dazu Abschnitt 8.4.

3.42 Wir setzen f(O) = 1 und haben f(1) = f(2) = 0, also f(n) + f(n + 1) = D n für n :::; 1. Durch Einfügen von n + 1 in die Permutationen von {1, ... , n} beweist man leicht die Rekursion f(n + 1) = (n - 2)f(n) + 2(n -1)f(n -1) + (n -1)f(n - 2) (n 2: 2). Umformen ergibt für f(n) + f(n + 1) genau die Rekursion für Dn. Aus

Übung 3.13 erhalten wir F(z) + F'(z) = D(z) = ~=:' F(O) = 1. Mit dem Ansatz

F(z) = c(z)e- Z ergibt sich die Lösung F(z) = c(z)e- Z , c(z) = -log(1- z) + 1. Nun ~ ~ n

ist f(n) = F(o)(n). Aus c(k)(O) = (k -1)!, F(z)(n) = L (-1)kG)c(n-k)(z)e- Z folgt k=O

n-l n-I k

f(n) = L (-1)k(~)(n - k -1)! + (-1)n = n! L k\;llk) + (-1)n. k=O k=O

Lösungen 293

n-l n-l n-l

3.45 S(z,n) = L L km~ = L L (k:,.r = L ekz = een:~/ = en:-1B(z) m::::O k=O k=O m::::O k=O

nach der vorigen Übung. Em(x) ist die Konvolution von (Em) und (xm), also erhal-ten wir B(z,x) = B(z)eXZ = :;~'l' und somit B(z,n) - B(z,O) = :;~~ - e'~l = zS(z, n). Koeffizientenvergleich für zm+! ergibt ~! Sm(n) = (m~l)! (Em+! (n) -

( )) _ 1 (" (m+l) m+l-k ( ) _ 1 ~ (m+l) m+l-k Em+! 0 - (m+!)! L.J k Ek n -Em+!), Sm n - m+! L.J k Ek n . k k=O

4.2 Wenn alle Funktionen positiv sind, so ist dies sicher richtig. Im anderen Fall könnten wir als Beispiel h(n) = n2,91(n) = n3 + n,h(n) = 0, 92(n) = -n3 haben.

4.4 Zum Beispiel Vffhf. 4.6 Aus der Annahme T(~):::; e~ folgt T(n):::; (e+1)n mit einer neuen Konstanten e + l. 4.10 Eine Addition kann das bisher größte Element höchstens verdoppeln, also ist ae :::; 2e und somit R( n) 2: 19 n. Für n = 2e ist natürlich R( n) = 19 n. Sei n = 2m + ... die Binärdarstellung von n. Mit m Additionen erzeugen wir alle Potenzen 2k (k :::; m) und mit höchstens m weiteren die Zahl n.

4.12 Der Ausdruck k2 + O(k) ist die Menge aller Funktionen k2 + J(k,n) mit IJ(k, n)1 :::; Ck für 0 :::; k :::; n. Die Summe ist daher die Menge aller Funktionen

f: (k2 + J(k, n)) = ,;3 + ~2 + ~ + J(O, n) + ... + J(n, n). Nun schließen wir I ~2 + ~ + k=O J(O,n)+ ... + J(n,n)l:::; ~2 +~+C(O+l+ ... +n) = ~2 +~+C~+C~2 < (C+1)n2, also ist die Gleichung richtig.

4.15 In a) haben wir L IJ(k)1 = L k-a < 00 und J(n - k) = (n - k)-a = k::::O k::::O

n n/2 n O(n-a) für 0 :::; k :::; ~. Es folgt L akbn-k = L O(f(k))O(f(n))+ L O(f(n))·

k=O k=O k=n/2 O(f(n - k)) = 20(f(n)) L IJ(k)1 = O(f(n)). In b) setze an = bn = a-n, dann gilt

k::::O n L akbn-k = (n + l)a-n -IO(a-n).

k=O 4.18 Die erste Rekursion steuert n bei. Nach der ersten Rekursion zerfällt TUn, T( 3t) in T( ~), T( ~~), T( ~~), T( i~) und der Beitrag ist ~+ 34n = n. In jedem Schritt wird n addiert, insgesamt haben wir 19 n Runden, also folgt T(n) = O(n 19 n).

4.20 Nach Satz 4.1 haben wir T(n) = n1g7 . Betrachten wir Sen) = aS(~) +n2. Für a< 16 ergibt Satz 4.1(c) Sen) = 6(n2) -< T(n), und für a = 16 ergibt Satz 4.1(b) Sen) = 6(n2 1g n) -< T(n). Im Fall a) ist a > 16 mit Sen) = 6(n1og4 "'). Sen) -< T(n) ist also genau für a < 49 erfüllt.

4.23 Angenommen T(k) = O(k), T(k) :::; ek. Dann haben wir rekursiv T(n) :::; n-l

~ L k + an + b = (e + a)n - e + b > en für n 2: no wegen a > O. Genauso schließt k=O

man für T(k) = f!(k2).

294 Lösungen

4.25 Wir beweisen umgekehrt, daß eine Berechnung von ggT(a, b), a > b , die n Schritte benötigt, b 2: Fn+l und a 2: Fn+2 zur Folge hat. Für n = 1 ist dies richtig, und der allgemeine Fall folgt induktiv aus der Fibonacci Rekursion. Mit a = Fn+2 , b = Fn+l sehen wir, daß das Ergebnis nicht verbessert werden kann. Sei Fn+2 die kleinste Fibonacci Zahl> b, dann wissen wir, daß die Laufzeit ~ n ist. Aus b 2: Fn+l 2: ~ folgt n = O(logb). Die letzte Behauptung besagt, daß für b < 10m

die Laufzeit höchstens 5m ist. Nun folgt aus Übung 3.33 leicht F5m+2 2: 10m , und somit die Aussage aus dem ersten Teil.

4.26 Wie im Hinweis braucht der Kellner höchstens 2 Flips, um n, n-1, ... ,3 an den Schluß zu bringen, und dann höchstens einen weiteren Flip. Zur unteren Schranke: Wir sagen, i ist benachbart zu i + 1 (i = 1, ... , n - 1), und n ist benachbart zum Schluß. Ein Flip kann die Anzahl der Nachbarschaften höchstens um 1 erhöhen. Hat die Ausgangspermutation also keine Nachbarschaften, so brauchen wir jedenfalls n Flips. Solche Permutationen sind für n 2: 4 leicht zu finden. Für n = 3 prüft man f(3) = 3 direkt nach.

4.29 Transferiere die obersten (~) Scheiben auf B (W(;) Züge), die restlichen n

nach D (ohne Benutzung von B, also Tn Züge), und schließlich die Scheiben von B nach D. Für Un = (W(nt1) - 1)/2n erhalten wir mit Tn = 2n - 1 (Übung 2.18) die

Rekursion Un ~ Un- l + 1, also W(nt1) ~ 2n (n - 1) + 1. Übrigens ist kein besserer Algorithmus bekannt.

4.32 Ist NI = ak ... al in Binärdarstellung gegeben, so gilt N = 2N1 + ao. Das heißt, mit Division durch 2 erhalten wir ao. Insgesamt benötigen wir also k Schritte (die letzten beiden Stellen ab ak-l ergeben sich in einem Schritt). Hat N n Dezi­malstellen, so gilt 2k ~ N < IOn, also f(n) = O(n).

5.1 Haben alle n Ecken verschiedenen Grad, so müssen die Grade die Zahlen 0,1, ... , n - 1 sein. Die Grade 0 und n - 1 schließen einander aber aus.

5.4 Für n = 4 haben wir K 4 • Ein 3-regulärer Graph G auf n 2: 4 Ecken enthält ein Paar nichtinzidenter Kanten k = uv, k' = u'v'. Wir entfernen k,k', verbinden u,v mit einer neuen Ecke a, u' und v' mit einer neuen Ecke a' und schließlich a mit a'.

5.8 Sei A unabhängig mit lAI = a(G), dann ist N(A) = E " A, also IN(A)I = n - a(G) ~ a(G)L\.

5.11 Jede der X(G) Farbklassen ist eine unabhängige Menge Ai mit E Ai = E. Es folgt n = E IAil ~ a(G)x(G). K n erfüllt Gleichheit.

5.13 Zunächst ist klar, daß G zusammenhängend ist. Sei Km auf {UI,""Um} ein größter vollständiger Untergraph. Ist m < n, so muß ein v tt {UI, ... ,Um } zu mindestens einer Ecke in Km benachbart sein, und damit zu allen, Widerspruch.

5.16 B <;;;; E trifft alle Kanten genau dann, wenn S" B unabhängig ist. Sei A eine kleinste solche Menge, lAI = m, m + a(G) = n. Wir haben IKI ~ E d(u), da

uEA jede Kante rechts mindestens einmal gezählt wird. Da G keine Dreiecke enthält, gilt d(u) ~ a, und somit IKI ~ E d(u) ~ ma ~ (mta )2 = ~2. Ist IKI = ~2, so müssen

uEA

Lösungen 295

alle Ungleichungen Gleichungen sein, und K n / 2,n/2 resultiert.

5.19 Alle k-Mengen, die 1 enthalten, kommen in Farbklasse 1, alle, die 2 enthalten (aber nicht 1), in Klasse 2 usf., bis n - 2k + 1. Es bleiben alle k-Mengen aus {n - 2k + 2, ... , n} übrig, und diese haben paarweise nicht leeren Schnitt. Übrigens gilt immer Gleichheit. K(5,2) ist der Petersen Graph.

5.20 Seien 8,T die definierenden Eckenmengen mit 181 = m ~ n = ITI. In einer optimalen Numerierung müssen 1 und m+n auf derselben Seite sein. Seien 1, m+n in T, b die Bandbreite und k bzw. K die kleinste bzw. größte Nummer in 8. Dann gilt K - k 2 m - 1, K - 1 ~ b, m + n - k ~ b, woraus b 2 m + r~l - 1 folgt. Der Fall 1, m + n E 8 ergibt analog b 2 n + r-W-l - 1, unsere ursprüngliche Wahl war also besser. Geben wir L ~ J + 1, ... , L ~ J + m in 8, den Rest in T, so erhalten wir b=m+r~l-I. 5.24 Numeriere die Ecken Vi, ... ,Vn . Gib Vi die Farbe 1 und induktiv Vi die klein­ste Farbe, die nicht unter den Nachbarn von Vi in {Vi, ... ,Vi-tl erscheint. Da Vi

höchstens .6. Nachbarn hat, brauchen wir niemals mehr als .6. + 1 Farben.

5.26 Induktion nach n. Angenommen X(H) + X(H) ~ n für alle Graphen auf n - 1 Ecken. Sei G Graph auf n Ecken, V E E mit d(v) = d. Für H = G '- v,H = G '- V

gilt X(G) ~ X(H) + 1, X(G) ~ X(H) + 1. Der einzig interessante Fall tritt auf, wenn in beiden Fällen Gleichheit gilt. Dann gilt aber X(H) ~ d, X(H) ~ n - 1 - d, also wieder X(G) + X(G) ~ n + 1. Die zweite Ungleichung folgt aus Übung 5.11.

5.27 Es seien Cl, ... , Ck die Farbklassen einer k-Färbung. Orientieren wir al­le Kanten von links nach rechts, d.h. mit aufsteigendem Index der Farbklassen, so ist die Bedingung erfüllt, da für je k - 1 aufeinanderfolgende Kanten in einer Richtung immer eine in der anderen Richtung folgen muß. Umgekehrt wählen wir Uo E E fest. Für V f::. Uo betrachten wir alle Kantenzüge P von Uo nach V und versehen die Kanten mit dem Gewicht 1 bzw. -(k - 1) wie im Hinweis. w(P) sei das Gesamtgewicht. Da das Gewicht eines Kreises nach Voraussetzung ~ 0 ist, gibt es einen Zug Pv mit maximalem Gewicht w(Pv ). Ist nun V -t v', so gilt w(Pv') 2 w(Pv ) + 1, w(Pv ) 2 w(Pv') - (k - 1), also 1 ~ w(Pv') - w(Pv ) ~ k - 1. Wählen wir die Farbe 0 für Uo und für V die Farbe r mit w(Pv ) = qk+r, 0 ~ r ~ k-1, so erhalten wir eine k-Färbung.

5.29 a) Ct, b) Kk+l, c) Kk,k, d) Petersen Graph (1(3,5) 2 10 folgt aus der unteren Formel, die Eindeutigkeit bedarf einiger Sorgfalt). Eine Ecke hat k Nachbarn, jeder Nachbar k-1 weitere Nachbarn usf. Wegen t = 2r+1 sind alle Ecken bis zur (r-1)-

r-l sten Iteration verschieden, und es folgt f(k, 2r + 1) 2 1 + k L (k _ l)i = k(k~~); -2.

i=O Der Fall t = 2r geht analog.

5.32 Die Endecken jedes längsten Weges sind keine Schnittecken.

5.34 Sei u eine Ecke mit maximalem Aus-Grad d+(u) = d. Für V ~ N+(u) haben wir v -t u und daher v -t w für höchstens d - 1 Ecken aus N+(u). Also gibt es einen Weg u -t Wo -t v.

296 Lösungen

5.36 Graphen mit Brücken können offenbar nicht geeignet orientiert werden. Umge­kehrt entfernen wir eine Äquivalenzklasse der Relation ~ (siehe Übung 5.33). Nach Induktion kann der Restgraph stark zusammenhängend orientiert werden. Die Kan­ten der Äquivalenzklasse orientieren wir zyklisch und erhalten so eine gewünschte Orientierung.

6.2 Sei E = {Ul,"" U2m} und Pi ein Weg von Ui nach Ui+m (i = 1, ... , m). K' ent­halte alle Kanten, die in einer ungeraden Anzahl der Pi's erscheinen. G'(E, K') hat dann die gewünschte Eigenschaft. K 3 + K 3 ist ein Gegenbeispiel für unzusammen­hängende Graphen.

6.5 In L: d( u, v) sind n - 1 Terme gleich 1 und alle anderen mindestens 2. Das ui'v

Minimum wird also erreicht, wenn alle anderen Terme gleich 2 sind, und dies ergibt den Stern K1,n-l . Im anderen Fall erhalten wir den Weg der Länge n - 1 durch Induktion nach n.

6.9 Angenommen T und T' sind verschiedene optimale Bäume und k = uv E K(T) '- K(T'). Auf dem eindeutigen Weg in T', welcher U mit v verbindet, liegt eine Kante k', welche die beiden Komponenten von T '- {k} verbindet. Nun hat entweder (T '- {k}) U {k'} oder (T' '- {k'}) U {k} geringeres Gewicht als T.

6.11 Sei 7k die Menge aller Bäume mit den) = k. Zu jedem T E 7k erzeugen wir n -1- k Bäume in 7k+1 auffolgende Weise: Wir betrachten eine mit n nichtinzidente Kante uv (wobei d(n,v) = d(n,u) + 1 ist), löschen uv und hängen v an n an. Umgekehrt sieht man leicht, daß zu T' E 7k+1 genau k(n-1) Bäume aus 7k gehören. Durch Entwickeln der Rekursion erhalten wir G(n, k) = (~:::~)(n - l)n-l-k und t(n) = nn-2 nach dem Binomialsatz.

6.12 Laut Hinweis haben wir detMii = L:detN· detNT = L:(detN)2, wobei N alle (n-1) x (n-1)-Untermatrizen von G-{Zeile i} durchläuft. Die n-1 Spalten von N korrespondieren zu einem Untergraphen von G mit n - 1 Kanten, und es bleibt zu zeigen, det N = ±1 ist, falls G ein Baum ist, und 0 sonst. Angenommen, die n-1 Spalten ergeben einen Baum. Dann gibt es eine Ecke Vl "I Vi (Vi korrespondiert zur i-ten Zeile) vom Grad 1; es sei k1 die inzidente Kante. Wir entfernen Vl, k1 und erhalten wiederum einen Baum. Es gibt wieder eine Ecke V2 "I Vi vom Grad I, usf. Permutieren der Zeilen und Spalten in N ergibt eine Dreiecksmatrix N' mit ±1 in der Hauptdiagonale, also det N = ± det N' = ±l. Angenommen, die n - 1 Spalten ergeben keinen Baum. Dann gibt es eine Komponente, die Vi nicht enthält. Da die entsprechenden Spalten jeweils eine 1 und eine -1 enthalten, summieren die Zeilen dieser Komponente zu 0 und sind daher linear abhängig.

6.15 Jede Kante von K n ist in derselben Anzahl a von aufspannenden Bäumen. Zweifaches Abzählen ergibt a(;) = nn-2(n - 1), also a = 2nn- 3, und wir erhalten t(G) = nn-3(n - 2).

6.16 Sei an die Anzahl der aufspannenden Bäume in G(2,n), also ao = 0, al = I, a2 = 4, und bn die Anzahl der aufspannenden Wälder mit genau zwei Komponenten, von denen eine U n , die andere Vn enthält. Eine Fallunterscheidung, wie U n, Vn an G(2, n - 1) angehängt sind, zeigt an = 3an-l + bn- 1 + In = 1], bn = 2an-l + bn- 1 +

Lösungen 297

[n = IJ. Eliminierung von B(z) = L: bnzn ergibt A(z) = L: anzn = 1-4~+z2 und mit den Methoden aus Abschnitt 3.2 erhalten wir an = 2~((2+ V3)n - (2 - V3)n).

6.18 Sei A die Kantenmenge des durch den Algorithmus konstruierten Baumes und {b1 , ... , bn-d die Kantenmenge eines beliebig anderen Baumes. Sei bi = UiVi, dann gibt es einen eindeutigen Schritt unseres Algorithmus, bei dem die zweite der Ecken Ui, Vi zu S hinzugefügt wird, und die Schritte sind für bi =P bj verschieden. Da bi in diesem Augenblick eine Kandidatenkante ist, folgt w(ai) :S w(bi ) für die entsprechende A-Kante.

6.20 a) ist klar, da alle Basen gleichmächtig sind. b) folgt aus Axiom 3) für Matroide angewandt auf A " {x} und B. Erfüllt umgekehrt 13 die Bedingungen, so definiert man U = {A : A ~ B für ein B E 13} und weist die Axiome für U nach.

6.23 Die minimal abhängigen Mengen in M = (K, W) sind die Kantenmengen von Kreisen. Für M* nehmen wir an, daß G zusammenhängend ist (allgemein kompo­nentenweise ). A ist genau dann unabhängig in M * , wenn K" A einen aufspannenden Baum enthält (siehe die vorige Übung), also ist B minimal abhängig in M*, wenn B minimale Schnittmenge ist.

6.26 Angenommen A,B E U, IBI = lAI + 1 und Au {x} ~ U für alle xE B" A. Sei w : S -+ lR definiert durch w(x) = -lAI - 2 für x E A, w(x) = -lAI - 1 für x E B" A, w(x) = 0 sonst. Es sei X die vom Greedy konstruierte Lösung. Dann ist A ~ X, X n (B" A) = 0, somit w(X) = -IAI(IAI + 2) > -(lAI + 1)2 ~ weB), also liefert der Greedy nicht das Optimum.

6.29 Ist C ein Kreis mit negativem Gesamtgewicht, so können wir C beliebig oft durchlaufen und jedesmal den Abstand senken. Wie im Hinweis sei induktiv bereits bewiesen, daß E(Vi-d = d(u, vi-d nach der (i - I)-sten Runde ist. In der i-ten Runde prüfen wir an einer Stelle E(Vi-d + W(Vi-l,Vi) gegen das bisherige E(Vi) und erhalten E(Vi) = E(Vi-d + W(Vi-l, Vi) = d(u, Vi-l) + W(Vi-l, Vi) = d(u, Vi). Da jede Ecke V =P U höchstens den Graphenabstand lEI - 1 hat, sind wir nach lEI - 1 Iterationen fertig.

6.31 Ergänze den Bellman-Ford Algorithmus nach IEI-I Durchläufen durch: Prüfe für jede Kante (x, y), E(y) gegen E(x) + w(x, y). Falls für eine Kante E(y) > E(x) + w(x, y) gilt, drucke "Kein kürzester Weg".

7.3 Nach Satz 7.2 müssen wir IN(A)I ~ m - n + lAI für alle A ~ S zeigen. Sei lAI = r, IN(A)I = s, dann gilt (m - I)n < IKI :S rs + (n - r)n :S n(s + n - r), also m - 1 < s + n - r oder s ~ m - n + r. Der Graph Km-1,n plus eine Kante von einer neuen Ecke Um ES nach T zeigt, daß m nicht verbessert werden kann.

7.6 Sei U1Vl, ... ,UmVm ein Maximum Matching. Angenommen m < n/2, dann bilden die restlichen Ecken {u, V, ... } eine unabhängige Menge. Aus d( u) + d( v) ~ n - 1 > 2m folgt, daß es ein Paar Ui, Vi gibt, zu dem drei Kanten von u, V führen. Also existiert ein Matching in {u, V, Ui, Vi}.

7.7 Offenbar muß mn gerade sein. Sei m gerade, dann finden wir ein Matching in jedem der n Wege. Die Anzahl der I-Faktoren in G(2, n) ist Fn+l (Fibonacci Zahl).

298 Lösungen

7.12 Sei 0 ein Hamiltonscher Kreis. Wenn wir A entfernen, dann bleiben höchstens lAI zusammenhängende Stücke auf O. 7.16 Sei n ~ 3 ungerade. Färben wir die Käsestücke abwechselnd weiß und schwarz wie auf einem Schachbrett, so muß der Weg zwischen weiß und schwarz alternieren. Die linke untere Ecke und die Mittelecke sind verschieden gefärbt, also hat jeder solche Weg ungerade Länge. Da n 3 ungerade ist, müßte er aber gerade Länge haben.

7.19 Das Komplement eines Trägers in G ist eine unabhängige Menge in G, also ein vollständiger Untergraph in G (siehe die Lösung zu Übung 5.16). Dies beweist die Äquivalenz. Daß z.B. das Cliquenproblem in NP liegt, ist klar.

7.20 a) ===} b). ISI = ITI ist klar. Angenommen IN(A)I :S lAI für 0 f A f S. Da G einen I-Faktor hat, muß IN(A)I = lAI sein. Es gibt eine Kante k, welche N(A) mit S \ A verbindet, da G zusammenhängend ist, und diese Kante k ist in keinem I-Faktor. b) ===} c). Sei A ~ S \ {u}, dann gilt INa\{u,v}(A)1 ~ INa(A)I- 1 ~ lAI. c) ===} a). Angenommen G ist nicht zusammenhängend. Sei Gi eine Komponente mit IE(Gt} n SI :S IE(Gi ) n TI. Sei u E E(Gt} n S, v E T \ E(Gt}, dann hätte G \ {u, v} keinen I-Faktor. Sei nun k = uv eine Kante, dann existiert ein I-Faktor in G \ {u, v}, also mit k ein I-Faktor in G.

7.23 Wenn G einen I-Faktor hat, dann wählt der zweite Spieler immer einen Matching Partner. Im anderen Fall wählt der erste Spieler ein Maximum Matching M und beginnt mit Ui außerhalb M. Spieler 2 muß nach M hineingehen, und der erste Spieler wählt den Matching Partner. Der zweite Spieler kann auf diese Weise nie M verlassen, da wir ansonsten einen alternierenden Wege hätten.

7.25 Wir beweisen die Aussage allgemeiner für alle bipartiten Graphen G(S+T, K), ISI = ITI = n, welche einen I-Faktor besitzen, mit d(u) ~ k für alle u E S U T. Für n = k haben wir G = Kk,k' Die I-Faktoren in Kk,k entsprechen den k! Permutationen. Sei n > k. A ~ S heißt kritisch, falls lAI = IN(A)I ist. 0 und S sind natürlich immer kritisch. Fall a. 0 und S sind die einzigen kritischen Mengen. Sei uv E K und G' = G \ {u,v}. Wegen lAI< IN(A)I für A f 0, S gilt in G' stets lAI :S IN(A)I· Nach Induktion besitzt G' mindestens (k - I)! verschiedene 1-Faktoren, welche wir mit den Kanten UVi, •.. , UVk ergänzen können. Fall b. A f 0, S ist kritische Menge. Jeder I-Faktor muß dann genau A mit N(A) und daher S \ A mit T \ N(A) verbinden. Nach Induktion besitzt bereits der bipartite Graph auf A + N(A) k! I-Faktoren, die alle auf ganz G ergänzt werden können.

7.28 Sei d(G) = min (lAI: A Träger), dann ist d(G) + a(G) = n. Nach Satz 7.3 haben wir d( G) = m( G) und nach der vorigen Übung m( G) + ß( G) = n. Für den Kreis 0 5 gilt a = 2, ß = 3.

7.31 Wir betrachten den vollständigen bipartiten Graphen Km,n auf Z +S mit allen Kanten gerichtet von Z nach S, Z = {I, ... , m}, S = {I, ... , n}. Die Kapazität c ist auf allen Kanten 1, das Angebot in i E Z ist ri, die Nachfrage in j E S ist Sj. Ein zulässiger Fluß nimmt dann die Werte 0,1 an (Satz 7.9), und wegen l: ri = l: Sj entsprechen die I-Werte einer gewünschten Matrix. Wir müssen also die Bedingung (1) am Ende von Abschnitt 7.3 nachprüfen. Sei (X, Y) ein Schnitt mit Zn Y = I, Sn Y = J. Genau die Kanten zwischen Z", I und J steuern die

Lösungen 299

Kapazität 1 bei, so daß wir die Bedingung L S j :::; L Ti + I Z " 111 JI für alle 1 ~ Z, JEJ iEI

J ~ S erhalten. Unter den k-Mengen J ~ S ist die schärfste Bedingung links wegen SI ~ ... ~ Sn durch J = {I, ... , k} gegeben, und man sieht sofort, daß für IJI = k die schärfste Bedingung rechts für 10 = {i E Z : Ti :::; k} resultiert. Dann ist aber

m

L Ti + k IZ" 10 1 = L min(Ti, k). iE10 i=1

7.32 Wir numerieren die Städte so, daß f 1 ~ ... ~ f n gilt, wobei f i die Länge der Kante ist, die bei (N N) an i angehängt wird. Copt ~ 2f1 folgt sofort aus der Dreiecksungleichung. Sei Sk = {I, ... ,2k} und T k die Tour durch Sk in derselben zyklischen Ordnung wie in der optimalen Tour. Aus der Dreiecksungleichung folgt Copt ~ c(Tk ). Sei ij eine Kante in Tk . Falls i in (NN) vor j eingefügt wurde, so folgt Cij ~ fi, andernfalls Cji = Cij ~ f j , also Cij ~ min(fi,fj ). Summation liefert Copt ~

C(Tk) ~ LCij ~ Lmin(fi,fj ) ~ 2(fk+1 + ... + f 2k ), da ein Minimum höchstens n

zweimal in der Summe erscheint. Genauso folgt Copt ~ 2 L f j . Wählen wir j=rn/21+1

k = 1,2, ... , 2f!gnl-2 und summieren wir alle Ungleichungen, so resultiert (flgnl + n

l)copt ~ 2 L f i = 2CNN. i=1

7.33 Sei A = min lAI, J-L = max IWI, dann gilt offenbar J-L :::; A. Wir betrachten das Netzwerk G(E, K) wie im Hinweis. Die Kapazität eines Schnittes (X, Y) ist wegen C == 1, c(X, Y) = IS(X, Y)I (Bezeichnung wie in Lemma 7.7). Da jedes S(X, Y) trennende Menge ist, folgt A :::; c(X, Y). Nach Satz 7.8 bleibt zu zeigen, daß w(f) :::; J-L für jeden zulässigen Fluß f gilt. Es ist klar, daß die Addition von afp (Bezeichnung wie in Satz 7.8) genau einem gerichteten Weg von U nach v entspricht, so daß wegen C == 1, w(f) :::; J-L folgt.

7.36 Eckendisjunkte S, T-Wege entsprechen Matchings, trennende Eckenmengen entsprechen Trägern, also resultiert Satz 7.3.

7.38 Sei G(E,K) =f. K n wie im Hinweis gewählt. Dann ist G U {uv} Hamiltonsch für jedes Paar uv t/:. K. G besitzt also einen Weg u = Ul,U2, ... ,Un = v. Sei A = {Ui : UUi+1 E K}, B = {Uj : UjV E K}, also lAI = d(u), IBI = d(v). Da v t/:. Au B ist, gilt n :::; d(u) + d(v) = lAI + IBI = IA U BI + IA n BI< n + IA n BI, daß heißt es gibt ein Uk E An B. Nun erhalten wir aber den Hamiltonschen Kreis U = Ul, ... , Uk, V = Un , Un -l,.··, Uk+l, u.

7.41 Jemand gibt einen Isomorphismus cp : G -t H an. Dann muß für jede 1 oder o in der Adjazenzmatrix von G geprüft werden, ob der entsprechende Eintrag in der Adjazenzmatrix von Hebenfalls 1 oder 0 ist. Dies kann mit O(n2 ) Operationen durchgeführt werden.

7.43 Nach der vorigen Übung gilt P ~ co - NP. Sei P = NP und A E co - NP. Betrachten wir A' mit den Wahrheitswerten 1 und 0 ausgetauscht, so ist A' E NP = P, also A E P, da P = co - P ist. Es folgt co - NP = P = NP.

8.2 Wir haben den Suchbereich S = {lL' ls, ... , nL, ns} wie in Abschnitt 8.1, also

300 Lösungen

L ~ flOg3 2n 1. Angenommen 2n = 3k - 1, k ~ 1. Wenn der erste Test links und rechts je e Münzen auf die Schalen legt, so wird S in die Mengen Si mit U, U und 2n - 4e Elemente zerlegt. Da ISil jeweils gerade ist, folgt max ISil ~ 3k - 1 + 1, somit L ~ k + 1, also L ~ flog3(2n + 2)l Die Umkehrung folgt leicht durch Induktion.

8.4 Die Formel gilt für n = 1,2. Entfernen wir aus einem Baum T E Y(n,2) eine Gabel, wobei die Blätter Länge e haben, so erhalten wir e(T) = e(T') + e + 1, i(T) = i(T') + e - 1, also mit Induktion e(T) - i(T) = e(T') - i(T') + 2 = 2(n - 1).

8.8 Wir können die Anzahl der Kandidaten in jeder Runde höchstens halbieren, woraus L ~ flg n 1 folgt. Haben wir umgekehrt s Kandidaten, so können wir durch disjunkte Vergleiche L~J Kandidaten eliminieren.

8.11 Lo(n) = n - 1 ist klar; ebenso L I (l) = 0,L I (2) = 1. Wir haben L I (3) = 1, indem wir zuerst x* = 1 testen. Sei n ~ 4. Testen wir zuerst x* = 2, so ist nach Induktion L :S 1 + max(l, rn ;31) = r~l Umgekehrt enthält jeder Teilbaum mit s Blättern immer einen Unterbaum mit mindestens s - 3 Blättern. Mit einer analogen Überlegung erhält man L 2 (n) = r~l + 1 für n = 5t,5t + 3,5t + 4 (n ~ 3) und L 2 (n) = r~l für n = 5t + 1, 5t + 2 (n ~ 12).

8.13 Seien A die lO-Mark Leute und B die 20-Mark Leute. Eine Folge von A's und B's ist unzulässig, falls an einer Stelle mehr B's als A's sind. Sei 2m - 1 die erste Stelle, wo dies passiert. Bis zu dieser Stelle gibt es also m - 1 A's und m B's. Vertauschen wir diese A's und B's, so erhalten wir eine Folge von n + 1 B's und n -1 A's. Ist umgekehrt eine Folge von n + 1 B's und n -1 A's gegeben, so gibt es eine erste Stelle, wo die B's eins mehr sind als die A's. Tauschen wir wieder die A's und B's aus, so ergibt sich eine unzulässige Folge. Man sieht sofort, daß dies eine Bijektion der unzulässigen Folgen auf die (n2.~.\) Folgen von n + 1 B's und n -1 A's

ist, und wir erhalten e:) - (n2~\) = n~l e:)· 8.15 Folge c), da nach 48 die Suche im linken Unterbaum stattfindet, 60 aber im rechten ist.

8.17 Für L = 1 kann der Graph höchstens 2 Kanten haben. Angenommen, u E E ist die erste Testecke. Sei L die optimale Suchlänge. Falls d( u) = d > L ist, und die Antwort ist "ja", dann ist die zweite Endecke von k* unter den Nachbarn von u und wir brauchen d(u) - 1 ~ L weitere Tests. Also muß d(u) :S L gelten. Es gibt eine mit u nichtinzidente Kante, da ansonsten G = KI,d und u nicht optimal wäre. Ist nun die Antwort "nein", dann ist das Problem auf G' = G" {u} mit L(G') :S L-1 reduziert. Nach Induktion haben wir IK(G)I = d+IK(G')1 :S (Lt l ) +1. Analog zeigt

man b). Auflösung der Schranken ergibt L ~ r J 2IK I- i - ~ 1, L ~ r J2n - i - ~l 8.20 a) ist klar, da k ~ ~ keine Einschränkung an die Tests bedeutet. Sei fk(n) = L::;k (n), fk (n) ist monoton steigend in n. Sei nämlich Al, A2 , ... die Testfolge in einem optimalen Algorithmus für S, dann bildet Al n T, A2 nT ... eine erfolgreiche Testfolge für T ~ S. Sei Al die erste Test menge , lAd = e :S k. Betrachten wir die Unterbäume verwurzelt in Al und S" Al, so erhalten wir die Rekursion fk(n) = 1 + max(Jk(e), h(n - e)) = 1 + fk(n - e) ~ 1 + fk(n - k). Daraus folgt fk(n) ~ t + flg(n - tk)l mit t = r~l - 2. Umgekehrt nehmen wir als erste Testmengen

Lösungen 301

Al = {al, ... ,ad, A 2 = {ak+!, .. ·,a2d, ... ,At = {a(t-l)k+!, ... ,atd· Falls x* E U Ai ist, so sind wir mit flg k 1 weiteren Tests fertig, im anderen Fall benötigen wir flg(n - tk)l weitere Tests.

8.23 Die einzige Alternative zu elementweiser Suche ist S = {a, b} als erste Testmen­ge. Wir erhalten Sn X* = 0 mit Wahrscheinlichkeit (1 - p)2. In diesem Fall sind wir fertig, im anderen Fall testen wir {a}. Jetzt hat die Antwort X* n {a} = 0 Wahrscheinlichkeit p(l - p), und wir erhalten X* = {b}. Im anderen Fall te­ste {b}. Mit Wahrscheinlichkeit p brauchen wir also 3 Tests, und wir erhalten L = (1 - p)2 + 2p(1 - p) + 3p = _p2 + 3p + 1, und dieser Ausdruck ist ~ 2 genau für p ~ 3-2,,15.

8.25 Ersetze in einem optimalen Baum T E T(n + 1, 2) eine Gabel wie im Huffman Algorithmus, wobei die Blätter Länge € haben, so daß T' E T(n,2) resultiert. Für e(T), e(T') wie in Übung 8.4 erhalten wir e(T) = e(T')+€+ 1. Es gilt h(n+ 1) = ~:J, h(n) ~ e(~/), also ~h(n + 1) = e(~) ~ h(n) + t;f, und somit h(n + 1) ~ h(n) + ~ + ~(€ - h(n + 1)). Gleichheit gilt daher, wenn n + 1 = 2k für ein k ist.

8.29 Der Suchbereich ist S = {Yl, ... , Yn, Zo,···, zn}, wobei Zi bedeutet, daß Yi < x* < Yi+l ist. Man konstruiert nun einen vollständigen binären Baum TE T(n+1, 2) mit Zi in den Blättern und Yi in den inneren Ecken und füllt die Ecken von T in In-Order. Ist x* = Yi, so ist die Anzahl der Tests €(Yi) + 1, ist x* = Zi, so erhalten wir €(Zi), und somit L = flg(n + 1)1. 8.30 Wir führen l ~ J disjunkte Vergleiche durch und bestimmen das Maximum der l~J größeren Elemente bzw. das Minimum der l~J kleineren. Dies ergibt L ~ f32n 1 - 2. Zur unteren Schranke: Mit Maxi bezeichnen wir die Menge der Maxi­mumskandidaten nach i Vergleichen, analog Mini. Sei Si = I Maxi I + IMinil. Am Anfang haben wir So = 2n und am Ende S L = 2. Sei x : Y der (i + 1 )-ste Vergleich. Erhalten wir die Antwort x< y, falls x E Mini oder y E Maxi (mit einem beliebigen Ausgang in den anderen Fällen), so folgt Si+! ~ Si - 1, außer wenn x, Y bisher noch in keinem Vergleich waren. In diesem Fall ist Si+! = Si - 2. Dieser zweite Fall kann aber höchstens l ~ J -mal eintreten, und es resultiert 2 ~ 2n - L - l ~ J . 8.32 Vergleichen wir immer die Minima der aktuellen Listen, so sind wir in 2n -1 Vergleichen fertig. Umgekehrt müssen in der gemeinsamen Liste {Zl < Z2 < ... < Z2n} alle Vergleiche Zi : Zi+l durchgeführt worden sein, da sie nicht durch Transitivität erzwungen werden können. Also gilt M(n,n) = 2n - 1.

8.35 Ein j mit bj > 0 wird mit dem größten k > j, das vor j kommt, ausge-n

tauscht, also gilt bj = bj - 1. A = l: bj folgt unmittelbar, und ebenso D = j=l

1 + max(b l , ... ,bn ), wobei 1 für den letzten Durchgang gezählt wird. Sei (bj) die Inversionstafel nach i-I Durchgängen. Ist bj = bj - i + 1 ~ 0, so hat j bj Vorgänger> j. Sei j das letzte Element, das ausgetauscht wird. Dann "bubbiet" das größte k vor j in die Position bj + j. Im i-ten Durchgang benötigen wir also Ci = max(bj + j - 1 : bj - i + 1 ~ 0) = max(bj + j : bj ~ i-I) - i Vergleiche.

8.36 Die Wahrscheinlichkeit D ~ k ist gleich ;h mal der Anzahl der Inversionstafeln

302 Lösungen

mit bi :S k - 1 für alle i, also gleich k! ~-k • Die Wahrscheinlichkeit p(D = k) ist

daher ;h(k! k n-k-(k-l)! (k_1)n-k+1) und wir erhalten E(D) = n+l- t k!~-k. k=O

8.39 Es sei En,k = E(Ck(7r)) auf {I, ... ,n}. Wir beweisen zunächst En,k = En-l,k+ n+Lk für k < n. Die Nummer i ist mit Wahrscheinlichkeit ~ die Wurzel. Unter­

k-l scheiden wir die Fälle i < k bzw. i > k so erhalten wir En,k = ~ L: (1 + En-i,k-i) +

i=l n k-l n

~ L: (1 + Ei-l,k), also nEn,k = n - 1 + L: En-i,k-i + L: Ei-l,k. Schreiben i=k+l i=l i=k+l

wir dieselbe Gleichung für n - 1 anstelle n und ziehen die zweite von der ersten ab, k-l

so resultiert mit Induktion nEn,k - (n -1)En- l ,k = 1 + L: n-~+1 + En-l,k, also i=l

En,k = En-l,k+ n-~+l. Auflösung der Rekursion ergibt En,k = Ek,k +(Hn+l - k -1).

Aus Symmetriegründen ist Ek,k = Ek,l = Hk - 1 (siehe vorige Übung) und wir er­halten E(Ck(7r)) = Hk + H n+1-k - 2.

8.41 Die Ungleichung von Jensen gilt für beliebiges c > 0, wir brauchen wie in Abschnitt 8.4 nur Xi = cYi zu setzen. Führen wir dieselbe Analyse wie dort durch, so

halt . (2) - () - (n-1+2c)(n-2+2c) ... (2+2c)c - (1 + 2c-l) (1 + 2c-l) er en WH g - c, g n - n(n-l) ... 3 - n· . . 3 c. Da c :S 1 + 2c;l ist und 1 + x :S eX für jedes x E IR gilt, resultiert gen) :S exp((2c-1)(Hn - 1)) < exp((2c - 1) logn) = n 2c- l . Daraus ergibt sich wie in Abschnitt 8.4, E(L(n)) :S ~~~~ logn. Der Minimalwert für ~~~~ wird für die Lösung der Gleichung

2logc - 2 + ~ = 0 erreicht, und für dieses Co gilt ~~~~: ~ 4.311. Übrigens ist E(L(n)) = 8(co logn).

2 9.1 Sei n gerade. Wir unterteilen das Brett in ~ Quadrate der Seitenlänge 2. In jedes Quadrat kann höchstens ein König plaziert werden. Wählen wir jedesmal die rechte untere Ecke, so resultiert ~2 • Für n ungerade erhält man (n~l)2 . 9.3 Ist eine Dame in einer Ecke plaziert, so müssen die anderen drei Ecken frei bleiben.

9.5 Zählen wir für die Additionen und die Vergleiche in (1) jeweils nur 1, so erhalten n-l

wir für die Laufzeit die Rekursion T(n) ~ L: (T(k) + T(n - k + 1) + 1) + 1 = k=2

n-l

2 L: T(k) + (n -1) für n ~ 3, T(2) = O. Daraus folgt mit Induktion T(n) ~ 2· 3n- 3 .

k=2

9.8 Die Greedy Methode nimmt km maximal mit kmcm :S n, dann km- l maximal mit km_1cm- 1 :S n - kmcm usf. Sei nun (Co, ... ,Cm ) eine optimale Lösung, dann gilt Ci :S c - 1 für i < m. Es sei io der größte Index mit Cio :f:. kio ' dann ist Cio < kio nach der Greedy Konstruktion. Es muß also einen größten Index jo < io geben mit Cjo > kjo.IstI = {i: ki > Ci}' J = {j: Cj > k j }, so gilt L:(ki-Ci)Ci = L:(Cj-kj)cj .

iEI jEJ Andererseits ist L:(ki-Ci)Ci ~ cio und L: (Cj-kj)cj :S cjo+1-1 < Cio wegenjo < io.

iEI jEJ

Lösungen 303

Der Greedy Algorithmus liefert also sogar das eindeutige Optimum.

9.11 In der Matrix (~ ~) konstruiert der Greedy Algorithmus X1l = X22 = 1 mit W = 5, während Wo pt = 6 ist.

9.15 Es seien A, B, G die Männer und a, b, e ihre Frauen. Wir beschreiben eine Situation durch die Personen menge diesseits des Ufers. Die möglichen Mengen sind ABGabe, ABGab, ABGae, ABGbe, ABGa, ABGb, ABGe, ABab, AGac, BGbe, ABG und ihre Komplementärmengen. Wir können den Transport in naheliegender Weise durch einen Graphen beschreiben. Gesucht ist also ein Weg ungerader Länge von ABGabe nach 0. Lösung: ABGabe, ABGa, ABGab, ABG, ABGa, Aa, ABab, ab, abe , a, ab, 0. Für vier Paare gibt es keine Lösung.

9.17 Illustration für n = 3, m = 4. Seien a1 < a2 < a3 die Marken. Dann gilt a1 = 1, 2 :::; a2 :::; 5, a2 < a3 :::; 4a2 + 1. Wir starten den Baum mit a1 = 1, a2 = 2 und testen der Reihe nach a3 = 3 bis 9. Dabei notieren wir das jeweilige N, z.B. N(l, 2, 3) = 12, N(l, 2, 4) = 14, und gehen zurück zu a2 = 3. Das Optimum ist N = 26 für {I, 5, 8}.

9.18 Jede Färbung J von G+ oder G- ist auch Färbung von G, indem wir dieselben Farben verwenden, also X(G) :::; X(G+), X(G-). Ist umgekehrt J eine Färbung von G, so ist J eine Färbung von G+ (falls J(u) i- J(v)) oder von G- (falls J(u) = J(v)). Sei weG) die Eckenzahl eines größten vollständigen Untergraphen von G, dann ist X(G) ~ weG). Nach dem Branching von G in G+, G- erhalten wir die neuen Schranken w(G+),w(G-). Am Schluß haben wir H = Km, X(H) = m, und verfolgen den Baum zurück.

9.21 Sei 91 = 1, 92 = n, W1 = 2, W2 = n, G = n. Dann ist w* = 2, Wopt = n, und 't * 2 (1) f" 2 som1 W = :nWopt < - € Wopt ur n > 1-E'

9.22 Sei (Xl"" ,Xn ) E {a, l}n eine optimale Lösung, das heißt Xi = 1 oder 0, je nachdem ob das i-te Element im Rucksack ist oder nicht. Wegen Tt- ~ ... ~ ~

k n n k gilt W t < "w·x· + " Wk±1 9'x' = Wk±l "9' X ' + "(w· - Wk±l 9 ·)x· < op _ L..J J J . L..J 9k±1 J J 9k±1 L..J J J L..J J 9k±1 J J -

J=l J=k+1 J=l J=l k k k

Wk±1 G + 2: (Wj - WHI 9j) = 2: Wj + Wk±1 (G - 2: 9j). Sei k der größte Index mit 9k±1 j=l 9k±1 j=l 9k±1 j=l

k k 2: 9j :::; G, dann haben wir a :::; G - 2: 9j < 9k+l und somit Wo pt :::; w* + Wk+l' j=l j=l

9.24 Für die Jobs Ji gelte e1 :::; ... :::; en . Sei A = Pk,"'} eine optimale Lösung. Falls k i- 1 ist, so ist wegen e1 :::; ek auch (A \ Pd) u Pd eine optimale Lösung. Iteration zeigt, daß der Greedy Algorithmus funktioniert.

10.3 Nach Definition der Minterme gilt J(X1,"" xn ) 2: X~l ... x~n, also C:f(C)=O

nach de Morgan J(X1, ... , xn ) = 2: X~l ... x~n = I1 (XYl + ... + x~n). C:f(C)=O C:f(C)=O

10.8 Sei M die Anzahl der Elemente in einer längsten Kette und m die minimale Anzahl von Antiketten, in die P zerlegt werden kann. Offenbar gilt M :::; m. Umge-

304 Lösungen

kehrt sei i(x) die Anzahl der Elemente einer längsten Kette, die in x endet. Dann M

ist Ak = {x E P : i(x) = k} eine Antikette und P = E Ak • k=l

10.9 Der bipartite Graph G(S + F, K) ist ein Baum. Es gilt also IKI = E !PI = FE:F

ISI + IFI - 1. 10.11 In einem Minterm der DNF können wir x durch 1 EI7 x ersetzen. Da für jedes x mit f(x) = 1 nur ein Minterm den Wert 1 hat, können wir die ODER­Summe E durch E EI7 ersetzen. Jede Boolesche Funktion hat daher eine RSE­Darstellung, und da die Anzahl 22n der Booleschen Funktionen gleich der Anzahl der Koeffizientenfolgen (a/) ist, folgt die Eindeutigkeit.

10.13 Wir müssen x finden mit (f EI7 g) (Xl, ... ,Xn ) = 1. Sei die RSE von f EI7 9 = Ec/x/. Ist i minimal mit CL = 1, ILI = i, dann ist x mit Xi = 1 für i E L, Xj = 0 für j f/. L, ein gewünschtes x.

10.15 Es sei f(x) monoton und X = {x : f(x) = I}. Zu x E X assoziieren wir wie üblich die Menge Ax ~ {I, ... ,n} und setzen x' = Xii" .Xit mit Ax = {il , ... ,id. Ist X' die Menge der minimalen Vektoren in X, so gilt f(x) = Ex'.

XEX'

10.17 g(x, y, z, w) = zw+xyw+xyzw. Eine Karnaugh Abbildung für vier Variablen ist

y y y y X[]: X z x z x z

w w W W

10.20 Ein optimales logisches Netz mit fan-out 1 hat als zugeordneten gerichteten Graphen einen Baum mit einer eindeutigen Senke (= 1). Gehen wir zurück, so sehen wir, daß die Anzahl der Gatter, d.h. Ln(f), höchstens 1 + r + ... + rd - l = r:::l ist. Es folgt Dn(f) ~ logr((r - l)Ln(f) + 1).

10.22 Die Anzahl der Booleschen Funktionen in B(n), welche wesentlich von j Varia­blen abhängen, ist N(j), woraus die Formel folgt. Daraus berechnen wir N(l) = 2,

n-l N(2) = 10, N(3) = 218, N(4) = 64594. Zum Grenzwert haben wir E N(j)(~) ~

j=O J

22n - 1 2n , lim(22n-l+n/22n) = 0, und somit limN(n)/22n = 1.

10.24 Die untere Schranke folgt aus Übung 10.23, da Cno (gj) ~ n -1 ist (alle Varia­blen sind wesentlich). Zur oberen Schranke haben wir den Minterm gi = xgo ••• X~~ll

. . H' . S' d d j(n/2)( ) j(n/2) ( ) WIe 1m mWeIs. el n gera e, un T XO,···, X n /2-l, T Xn /2,"" Xn-l

bereits durch logische Netze realisiert. Dann existieren die entsprechenden Min-terme, und die 2n Minterme von f~n) können durch UND-Kombinationen aller

möglichen Paare realisiert werden. Es folgt Cno(f~n)) ~ 2n + 2Cno(f~n/2)). Eine

Lösungen 305

direkte Realisierung der Minterme von fi-n/2l benötigt ~2n/2 - 1 Gatter, und es

folgt Co.o (f~n)) :s; 2n + n2n/2 - 2. Für ungerades n ersetzen wir ~ durch r~ 1-10.26 Sei n gerade und A eine Antikette mit lAI = (n/2). Wir setzen Al = {A E A : n tf. A}, A2 = {A E A: n E A}. Dann sind Al, A~ = {A '-.{n} : A E A2} Antiketten in S '-. {n}. Es folgt lAll, IA21 :s; (~/i), also muß wegen (n/2) = (~/i) + (~/i) und Induktion Al = (S,-{n}) oder (S,-{n}) und A' = (S,-{n}) oder (S,-{n}) sein Man n/2 n/2-1 2 n/2-1 n/2 . sieht sofort, daß nur die Kombination Al = (S~j;}) und A~ = (~/2~{) möglich ist. Analog schließt man für ungerades n.

10.29 Angenommen t < n, dann folgt n - IFI > t - IFI ~ t - d(u) für jedes Paar

u tf. F, also n!!;'~1 < t~~(~)· Summieren wir diese Ungleichungen über alle Paare

u tf. F, so erhalten wir L:(n -IFD n!!;'~1 < L:(t - d(u)) t~~(b, also L: IFI < L: d(u), F u F u

was nicht geht, da wir hier Gleichheit haben.

10.32 Sei F ein Filter, dann bilden die minimalen Elemente in Feine Antikette. Ist umgekehrt A Antikette, dann ist F = {x : x ~ a für ein a E A} ein Filter, und die Abbildung ist eine Bijektion.

11.3 Aus 33 == 27 == 1 (mod 13) folgt 315 = (33 )5 == 1 (mod 13). Da 15 == 2 (mod 13) ist, können wir uns auf 283 beschränken. Aus 26 == 64 == -1 (mod 13) folgt 283 = (26 ) 1325 == -32 == 7 (mod 13).

11.6 Sei Z die Summe der Zehnerstellen, E die Summe der Einerstellen. Dann gilt lOZ + E = 100 und somit Z + E == 1 (mod 9). Andererseits ist Z + E = 45 == 0 (mod 9), die Sache geht also nicht.

11.8 Ist x 2 + ax + b reduzibel, so gilt x 2 + ax + b = (x - a)(x - ß) mit a + ß = -a, aß = b. Wir müssen also nur die Additions- und Multiplikationstafel durchgehen, um geeignete a, b zu finden, für die es keine a, ß gibt, z.B. a = b = 1. Also ist x 2 +x+1 irreduzibel. Die Elemente von GF(25) werden mit ax + ß (a, ß = 0,1, ... ,4) identifiziert mit Addition und Multiplikation modulo x 2 + x + 1.

11.10 Die Werte seien J,D,K,A und die Farben 1,2,3,4. Normieren wir die erste Zeile in dieser Reihenfolge, so sieht man, daß bis auf Vertauschung die einzigen orthogonalen 4 x 4-Quadrate, die auch die Diagonalbedingungen erfüllen, wie folgt aussehen:

J D K A 1 2 3 4 K A J D 4 3 2 1 A K D J 2 1 4 3 D J A K 3 4 1 2

Horizontal gesehen, müssen 1,3 eine Farbe, 2,4 die andere haben. Vertikal stoßen aber z.B. 1 und 3 aneinander. Eine Schachbrettanordnung ist also nicht möglich.

11.12 Wir können nicht mehr als n2 Türme plazieren, da in jeder Schicht nur n Türme aufgestellt werden können. Ein Arrangement mit n2 Türmen entspricht einem Lateinischen Quadrat, indem wir die Türme in Schicht i in die Positionen von i plazieren. Durch zyklisches Vertauschen der Ziffern sieht man, daß im nd-Brett

306 Lösungen

n d- I Türme aufgestellt werden können.

11.15 Aus xDy = xDz folgt xy-I = xz- I , also y = z, und ebenso y = z aus yDx = zDx. Das heißt, L(x,y) = xDy ergibt ein Lateinisches Quadrat. In einer Gruppe ungerader Ordnung hat x 2 = 1 nur die Lösung x = 1 (siehe Übung 11.29). Die Abbildung x I--t x 2 ist also eine Bijektion. Betrachten wir das Gleichungssystem xy-I = a, xy = b, so folgt x2 = ab, y2 = ba-I. Das Paar (x,y) ist somit eindeutig bestimmt.

P 11.18 Wir haben (a + b)P = L (~)akbP-k. Für 0 < k < P ist m ein Vielfaches

k=O von p, und es folgt (a + b)P == aP + bP (modp). Zweiter Beweis. Für a == 0, b == 0 oder a + b == 0 (modp) ist die Aussage richtig. Sind alle drei Zahlen ~o (modp), so haben wir nach dem Satz von Fermat (a + b)P == a + b == aP + bP (modp).

11.20 Für p == 3 (mod4) ist ~ ungerade. Aus n2 == -1 (modp) folgt daher

(n2 )9 == -1 (modp), im Widerspruch zum Satz von Fermat. Für p == 1 (mod4) sei n = (~)!. Aus k == -(p- k) (modp) für k = 1, ... , ~ folgt n 2 == (-1)9(p­I)! == -1 (modp) nach Übung 11.19.

11.24 Sei B 2 2: 1, dann ist f(m,n) = 2. Für B 2 = 0 erhalten wir f(m,n) = n + 1. In diesem Fall ist B = 0, das heißt m(n+ 1) = n!+ 1 oder n! == -1 (mod n+ 1). Nach Übung 11.19 folgt, daß f(m,n) = n + 1 Primzahl ist. Umgekehrt ist f(l,l) = 2. Für eine ungerade Primzahl p setzen wir n = p - 1, m = (P-~)!H (was nach Übung 11.19 zulässig ist). Mit dieser Wahl ist B = 0 und daher f(m, n) = n + 1 = p. Die Eindeutigkeit folgt aus der Beobachtung, daß f(m, n) = 2 oder f(m, n) = n + 1 ist.

11.25 Hat die Zahl n genau k Stellen, so gilt 10k - 1 :S n < lOk, also k-1 :S 10giO n < k. Für n = 44444444 haben wir 10giO n = 444410gI0 4444 und wegen 4444 < 104 also 10giO n < 4444·4 < 20000. Für A folgt daher A < 9·20000< 199999 und daraus B < 46. Die Quersumme S von B kann daher höchstens 12 sein (z.B. für B = 39). Nun gilt n == A == B == S (mod9). Aus 4444 == -2 (mod 9) berechnet man sofort n == 7 (mod 9) und daraus S = 7 wegen S:S 12.

11.29 Sei a E G. Mit 9 E G durchläuft auch ag die ganze Gruppe, und wir erhalten rr 9 = rr (ag), also 1 = an. Sei d = ord(a), dann wissen wir aus dem eben

gEG gEG

Bewiesenen d :S n. Schreiben wir n = qd + r, O:S r < d, so gilt 1 = an = (ad)qaT = aT , also r = 0 wegen der Minimalität von d.

11.31 Wir bemerken zunächst 1 -:j:. -1 wegen q ungerade, und daher a -:j:. -a für alle a -:j:. O. Jedes Paar {a, -a} erzeugt ein Quadrat a2. Ist a2 = b2, so folgt (a+b)(a-b) = 0, somit b = a oder b = -a, und daraus IQI = ~. Fassen wir die Elemente b -:j:. 0,1, -1 paarweise {b, b-I } zusammen, so erhalten wir rr b = -1. Wählen wir

b#O

aus jedem Paar {b, -b} ein Element aus, so ergibt dies (-1)9 rr b2 = -1. Für b2 EQ

q == 1 (mod4) ist also a2 = -1 mit a = rr b. Existiert umgekehrt a mit a2 = -1, b2 EQ

so ist ord (a) = 4 in der multiplikativen Gruppe des Körpers GF(q). Nach Übung

Lösungen 307

11.29 folgt q - 1 == 0 (mod 4). Resultat: -1 E Q {:} q == 1 (mod 4).

11.34 Seien Lo und Li orthogonale Lateinische Quadrate jeweils gefüllt mit 0, 1, ... , n-1. Durch M(i,j) = Lo(i,j)+nLi(i,j) erhalten wir ein halbmagisches Quadrat mit den Zahlen 0,1, ... , n 2 - 1. Addieren wir 1 zu jedem Eintrag, so resultiert ein halbmagisches Quadrat auf 1, ... ,n2 • Erfüllen Lo, Li auch die Diagonalbedingung, so erhalten wir ein magisches Quadrat. Übung 11.10 gibt ein Paar solcher Lateini­scher Quadrate der Ordnung 4. Ordnung 5 läßt sich leicht konstruieren.

11.36 Die Notwendigkeit ergibt sich aus bk = VA. Umgekehrt sei 8 eine Menge mit V Elementen, b = VkA. Wir müssen eine v x b-Inzidenzmatrix M konstruieren mit genau A Einsen in jeder Zeile und k Einsen in jeder Spalte. Sei Meine Inzidenzmatrix mit k Einsen in jeder Spalte. Angenommen, nicht alle Zeilensummen sind A. Dann muß es i,j geben mit ri > A > rj. Es gibt also eine Spalte S mit Si = 1, Sj = O. Tauschen wir diese 0 und 1 in Spalte s, so erhalten wir eine neue Matrix M' mit r~ = ri - 1, rj = rj + 1. Wiederholung dieses Austauschschrittes liefert die gewünschte Matrix.

11.38 Daß M MT von der angegebenen Form ist, folgt aus der Definition. Die De­terminante von MMT ist leicht berechnet: detMMT = (r + A(V -1))(r - A)V-i. Wegen k < v ist r > A, somit det M MT =I o. Da der Rang einer Matrix nicht größer als die Spaltenzahl ist, folgern wir v = rg(M MT) ::; rg(M) ::; b.

11.42 Sei B* = {Ui' ... ' UnH} die aus der projektiven Ebene entfernte Gerade. Definieren wir in der affinen Ebene (8, B) die Klasse Bi als jene Geraden, die in der projektiven Ebene den Punkt Ui enthielten, so sind die Aussagen erfüllt.

11.44 Aus Übung 11.31 wissen wir IQI = 2n + 1. Sei a E Q, a = a 2, dann ist a durch eine Anzahl ra von Differenzen a = x2 - y2 darstellbar. Wir müssen zeigen, daß ra = rb ist für alle b =I O. Sei a = x2 - y2 und b E Q, b = ß2. Dann gilt b = (ßa- i )2a 2 = 'Y2a, 'Y = ßa- i , und wir erhalten die Darstellungb = (-yX)2_(-yy)2. Verschiedene Darstellungen von a entsprechen verschiedenen Darstellungen von b, also gilt ra = rb. Ist b Ft Q, so folgt -b E Q wegen -1 Ft Q (Übung 11.31), und wir können analog schließen mit -b = ß2. Die Gesamtzahl der Differenzen aus Q ist (2n + 1)2n, also tritt jedes Element =I 0 genau n-mal als Differenz auf.

11.46 Daje zwei Punkte einer projektiven Ebene in genau einem Block liegen, folgt, daß die Taillenweite von G mindestens 6 ist. Jedes Dreieck ergibt andererseits einen Kreis der Länge 6. Die untere Schranke für f(q + 1,6) in Übung 5.29 ergibt gerade die Eckenzahl 2(q2 + q + 1) von G.

6 12.2 Wir verwenden die Kraftsehe Ungleichung L: 2-li ::; 1 (Satz 8.2). Der erste

i=i Code existiert nicht, den zweiten gibt es.

12.5 G = {OOOOOO, 111000, 100110,010101, 001011}. Mit Länge 5 gibt es keinen 1-fehlerkorrigierenden Code G mit IGI = 5.

12.7 Sei G E C(n,2d - 1), IGI = M(n,2d - 1). Wir konstruieren G*, indem wir an jedes Codewort einen Parity-check anhängen. Gilt ßc(a, b) = 2d - 1, so hat die Anzahl der 1 'en in a verschiedene Parität von der Anzahl der 1 'en in b, so daß ßc. (a*, b*) = 2d gilt, und somit M(n+l, 2d) ~ M(n, 2d-l). Umgekehrt lassen wir

308 Lösungen

eine Stelle weg. Zu b) betrachten wir die letzte Stelle. Die Codewörter mit derselben Ziffer bilden mit den ersten n - 1 Stellen einen Code in C(n - 1, d).

12.9 Mit Induktion haben wir IC(r + 1, m + 1)1 = IC(r + 1, m)IIC(r, m)1 = 2b+c

r+l r r+l mit b = L (':'), c = L (7), also a = b + c = L (mti). Nach Übung 12.8 gilt mit

i=O i=O i=O Induktion d(C(r + 1, m + 1)) = 2m - r .

12.11 Der Code C1- hat Basis {221O, 2101}. In der (4 x 2)-Matrix (~i ~ ~( sind je zwei Zeilen linear unabhängig, also folgt nach Satz 12.2, d(C) ~ 3. Mit ICI = 9, n = 4, q = 3, ist die Hammingschranke mit Gleichheit erfüllt.

12.15 Angenommen wir ersetzen im Huffman Algorithmus eine Gabel mit den Blättern u, v, f(u) = f(v) = m. Ist L die Gesamtlänge des ursprünglichen Bau­mes und L' die des neuen so gilt L' = L - m - 1 ~ L - n wegen m ::; n - 1. Für L' gilt also L ::; L' + n und somit L ::; n + (n - 1) + ... + 2 = n2 +2n-2. Für eine Verteilung (PI ~ ... ~ Pn) mit Pi > L Pj gilt Gleichheit.

j>i

12.18 Nach Satz 12.2 müssen wir Vektoren UI, ... ,Un E GF(q)n-k finden, von denen je 2t linear unabhängig sind. Für UI nehmen wir irgendeinen Vektor "I O. Angenommen, wir haben schon h Vektoren UI, ... , Uh mit dieser Eigenschaft kon-struiert. Betrachten wir eine i-Menge U ~ {UI, . .. ,Uh}. Die Anzahl der Vektoren, die von U (aber keiner Teilmenge ) abhängig sind, ist höchstens (q - 1) i. Solange also (~)(q - 1) + (~)(q - 1)2 + ... + (2t~I)(q - 1)2t-1 < qn-k - 1 ist, können wir einen weiteren Vektor UhH hinzufügen.

12.22 Sei A = {O, I} und w(c) das Gewicht von c E An. Wegen 0 E C gilt w(a) ~ 2t + 1 für 0 "I a E C. Jedes Wort c E An mit w(c) = t + 1 liegt demnach in gen au einer Kugel Bt(a), a E C, w(a) = 2t+ 1. Ist h2tH die Anzahl der a E C mit w(a) = 2t+ 1, so folgt durch zweifaches Abzählen h2t+1 Cttt/) = (t~l)' Identifizieren wir a E C, w(a) = 2t+1 mit Ua = {i: ai = I}, so bilden die Ua ein Steiner System StH (n, 2t + 1). Analog wird die Behauptung für 8 gezeigt.

12.24 Aus n2 + n = 2rH - 2 folgt (2n + 1)2 = 2r+3 - 7. Nach der Bemerkung haben wir die folgenden Lösungspaare (n, r) : (0,0), (1, 1), (2, 2), (5, 4), (90, 12). Die ersten drei Paare sind ausgeschlossen. Das Paar n = 5, r = 4 ergibt den binären Wiederholungscode. Das letzte Paar würde nach Übung 12.22 ein Steiner System S3(90, 5) ergeben. Nach Übung 12.23 gilt n + 1 == ° (mod t + 1), im Widerspruch zu 3f91.

12.26 Aus g(x) I a(x), g(x) I b(x) folgt g(x) I a(x) + b(x), also ist C ein linearer Code. Sei a E C, also g(x) I a(x) = an_IXn- 1 + ... + ao . Daraus folgt g(x) I xa(x) = an_2Xn-1 + ... + aox + an_IXn = an_2Xn-1 + ... + aox + an_I(Xn -1) + an-l und somit g(x) I an_2Xn-1 + ... + aox + an-l wegen g(x) I xn - 1.

12.28 Wir haben a E C {:} g(x) I a(x) {:} a(x) = g(x)k(x), k(x) E K[x] {:} a(x)h(x) = g(x)h(x)k(x) {:} a(x)h(x) == ° (modxn - 1). Setzen wir h(x) = xk + hk_1xk- 1 + .. . +ho, so gilt gi+hk-lgi+l +hk- 2gi+2+ . . . +higk = ° für i = 0, ... , r-1. Die Kontrollmatrix ist eine r x n-Matrix mit (0, ... ,0, ho, ... ,hk-I, 1) als erste Zeile,

Lösungen 309

und die weiteren durch Rotation von vorne nach hinten.

12.30 H l = (1), H 2 = G -D. Sei n ~ 3. Durch Multiplikation der Spalten mit -1 (dies ändert nichts an der Hadamard Eigenschaft) können wir annehmen, daß die erste Zeile aus lauter 1 'en besteht. Aus H H T = nEn folgt, daß jede weitere Zeile gleichviele l'en und -l'en enthält, also n == 0 (mod2). Aus hi· hj = 0 für je zwei Zeilen i,j ~ 2 folgt daraus n == 0 (mod4). Aus HHT = nEn folgt H-l = n-lHT ,

also H T H = nEn . c) und d) sind klar.

12.32 Wir ersetzen -1 durch O. A besteht aus allen Zeilen von H n , mit der ersten Spalte entfernt. B besteht aus A zusammen mit allen Komplementen, C aus allen Zeilen von H zusammen mit den Komplementen. B s ist unser alt bekannter Fano­Code, Cs = Es im Sinne von Übung 12.20.

12.34 Die Codierung ist Potenzierung, also leicht. Die Decodierung geht in zwei Schritten vor: Zuerst wird K berechnet aus K == yj == aXjk == (ak)Xj == C~j (modp), dann M == C2 /K (modp). Also ist die Decodierung bei Kenntnis von Xj leicht. Ohne Kenntnis von Xj wird vermutet, daß das Problem äquivalent zum diskreten Logarithmus ist.

12.36 K = 9, Cl = 49, C2 = 9·30 == 57 (mod 71), also M = (49,57). Aus 2 == 7k '

(mod 71) folgt k' = 6, K = 19, also C2 = 2.

13.2 Da M opt konvex ist, ist mit x f. y E M opt auch die Strecke xy in M oPt ' also kann es so ein Programm nicht geben.

13.4 Offensichtlich sind Xl > 0, X2 > 0, also folgt nach 13.8, daß im dualen Pro­gramm die bei den Ungleichungen mit Gleichheit erfüllt sind. Daraus berechnen wir Y2 - Y3 = ~, und es folgt leicht Y2 > 0, Y3 > O. Es sind also die zweite und dritte Gleichung im primalen Programm mit Gleichheit erfüllt, woraus Xl = 4, X2 = 1, Wert (I) = 3 resultiert. Da nun die erste Gleichung mit Ungleichung erfüllt ist, schließen wir Yl = 0, und daraus Yl = 0, Y2 = ~, Y3 = ~, Wert (1*) = 3.

13.7 Eine optimale Lösung ist X14 = 3, X22 = 5, X3l = 2, X33 = 4, X34 = 1 mit Wert = 65. Mit vier Routen geht es nicht.

13.9 Offensichtlich gilt U.l.l 2 U. Wir nehmen als Spalten von A eine Basis von U, dann bedeutet b (j: U, daß Ax = b nicht lösbar ist. Also gibt es eine Lösung von ATy = 0, bTy = -1. Die Bedingung ATy = 0 impliziert y E U.l und bTy = -1, daher b (j: U .1.1.

13.11 Daß (A) und (B) nicht zugleich lösbar sind, folgt unmittelbar. Angenommen,

(B) ist nicht lösbar. Mit C = (f), c = (~l) bedeutet dies, daß Cy = c, y ~ 0,

nicht lösbar ist. Nach Satz 13.4 existiert daher (z,o:) E IRn +! mit Az + o:b ~ 0, 0: > o. Dann ist aber x = -! Lösung von (A).

13.13 Wir schreiben das Transportproblem als Standard Minimum Programm (I) - L Xij ~ -Pi, L Xij ~ qj, L aij Xij = min. Das duale Programm (1*) ist yj - Yi ~

j i

aij, L qjyj - L PiYi = max. Angenommen, ein Konkurrenzspediteur bietet dem Planer in der Fabrik Pi den Preis Yi an, transportiert alle Güter, so daß mindestens qj Einheiten in M j ankommen und verkauft alles zurück zum Preis yj mit yj - Yi ~

310 Lösungen

aij. Der Planer hat also L,qjyj - L,PiYi::; L,aijXij = Wert (I) zu zahlen. Er wird also einwilligen, und der Konkurrent wird versuchen, seinen Gewinn zu maximieren. Ist yj - Yi < aij, so zahlt der Planer weniger als seine Kosten und wird diese Route stillegen, Xij = O. Ebenso interpretiert man die anderen Gleichungen.

13.14 Aus CAA)x ::; (!'b)' x 2': 0, cTx = max folgt AT(y' - y") 2': C, y' 2': 0,

y" 2': 0 , bT y' - bT y" = min. Setzen wir y = y' - y", so erhalten wir ein Programm ohne Vorzeichen beschränkung AT y 2': C, bT Y = min.

13.17 Sind x, y konvexe Kombinationen der Xl, ... ,xn , so gilt dies auch für AX + n

(1- A)Y, 0 ::; A ::; 1. Umgekehrt sei x = L, AiXi konvexe Kombination mit 0 < An < i=l

n-1 1. Nach Induktion ist y = 1-\ L, Aixi E K und daher x = (l-An )Y+Anx n E K.

n i=l

13.21 Wir beschreiben (I) wie üblich durch (AIEm )( ~) = b, (~) 2': 0, _cT X = min. Insbesondere gilt a n+j = €j (j = 1, ... , m), wobei €j den Einheitsvektor mit 1 an j-ter Stelle bezeichnet. Es sei Az ~ (AIEm ) jene m x m-Matrix, welche genau die Spalten a k (k E Z) enthält und entsprechend Cz = (Ck : k E Z). In der Simplextafel T für die optimale Lösung x gilt somit a j = L, Tkjak , also €j =

kEZ a n+j = L, Tk,n+jak (j = 1, ... ,m). Sei y = (Yi) wie angegeben. Für n + j cf. Z

kEZ haben wir dn+j ::; 0, cn+j = 0 und somit Yj = -dn+j = L, CkTk,n+j 2': O. Für

kEZ n+ jE Z gilt L, CkTk,n+j = cn+j = O. Insgesamt gilt also yT = C~(Tk,n+j), woraus

kEZ A~y = Cz resultiert. Für i ~ Z (1 ::; i ::; n) haben wir a i = L, Tkiak, somit

kEZ

a iT y = L, Tki(ae y) = L, TkiCk = -Zi = -di + Ci 2': Ci wegen di ::; O. Y ist also kEZ kEZ

eine zulässige Lösung von (1*). Wir wenden nun Satz 13.8 an. Ist aJ x< bj , so muß n + j E Z sein und es gilt Yj = 0 nach Voraussetzung. Gilt Xk > 0, so ist k E Z und wir haben ae y = Ck.

13.25 Sei B die n x q-Inzidenzmatrix des bipartiten Graphen G(S + T, K) und A eine quadratische Untermatrix, entsprechend den Ecken S' +T' und den Kanten K ' . Falls det A "# 0 ist, so muß es eine Diagonale D mit l'en geben. Inzidiert k E K ' nur mit S' aber nicht T' (oder umgekehrt), so muß die entsprechende 1 in D sein. Es folgt det A = ± det A' , wobei die Kanten in A' von S' nach T' führen. Möglicherweise liegen l'en bereits fest (da eine Endecke schon in D erscheint.). Fahren wir so fort, so ergibt sich eine eindeutige Diagonale, also det A = ±1, oder det A = ± det C, wobei die Kanten von C genau zwischen den Ecken von C führen. In diesem Fall ist aber wegen der Bipartitheit die Zeilensumme der Ecken von C aus S gleich derer aus T. Die Zeilen von C sind also linear abhängig, und es folgt det C = O.

Sachwortverzeichnis

Sachwortverzeichnis Abstand, 97, 114 Additionskette, 84 adjazent, 93 Adjazenzmatrix, 94 Äquivalenzrelation, 88 affine Ebene, 235 Algorithmus, 81 Algorithmus von Bellman-Ford, 119 Algorithmus von Dijkstra, 114 Algorithmus von Huffman, 159 Alphabet, 240 Angebot-Nachfrage-Problem, 135 Antikette, 208, 209 arithmetische Summe, 34 asymptotisch gleich, 76 aufspannender Baum, 105 Aus-Grad, 99 Aussagenlogik, 200 Auswahlfunktion, 123 azyklisch, 100

Backtrack, 178 Bandbreite, 95 Bandbreitenproblem, 95 Basis, 111, 201, 271 Basisfolge, 45 Baum, 105

aufspannender, 105 binärer, 167 (n, q)-Baum, 154 vollständiger (n,q)-Baum, 154

Baumdiagramm, 3, 179 Bedeckungszahl, 211 Bellmansche Optimalitätsgleichung, 184 Bellzahlen, 28, 69 benachbart, 93 Bernoulli Zahlen, 72 binäre Relation, 88 binärer Baum, 167 binärer Logarithmus, 77 Binomial-Inversion, 47 Binomial-Konvolution, 67

Binomialkoeffizienten, 6, 13, 27 Binomialsatz, 15 bipartit, 90, 98 bipartiter Graph, 120 Blätter, 153 Block-Code, 240 Blockplan, 227 Boolesche Algebra, 91, 198 Boolesche Funktionen, 199, 214 Boolescher Verband, 199, 207 Branch and bound, 180 Breadth-First Suche, 108 Brücke, 97, 102 Bubble-Sort, 176

Catalan Zahlen, 172, 174 charakteristischer Vektor, 4, 197 Christofides Heuristik, 143 chromatische Zahl, 102, 193 Cliquen problem , 148 Code

dualer, 244 linearer, 244 perfekter, 254 zyklischer, 254

Codewort, 239

Damenproblem, 179 Depth-First Suche, 109 Derangement-Zahlen, 47, 50, 67 Derangements, 38 Diagonale, 123 Differenzenfamilie, 230 Differenzenoperator , 39 Differenzenrechnung, 39 Digraph,99 Dimension, 244 Disjunktion, 200 disjunktive Normalform, 200 diskreter Logarithmus, 248 Distanz, 242 Divide and conquer, 79, 83

311

312

Dominanzsystem, 25 doppelt-stochastische Matrix, 124 Dreiecksungleichung, 143, 199 dualer Code, 244 duales Matroid, 117 duales Programm, 258 Durchmesser, 97 dynamisches Programmieren, 182

Ecke, 268 innere, 153

Ecken, 89 Einfügungsmethode, 163 Einweg-Funktion, 248 elementarer Fluß, 133 Elgamal System, 255 Endecke, 93, 153 entartet, 270 Entropie, 159, 175 Entscheidungsbaum, 152, 162, 186 Entscheidungsproblem, 144 Ereignis, 19 Erwartungswert, 21 Erzeugende Funktion, 1, 57 Euklidischer Algorithmus, 85 Euler Zahlen, 30 Euler-Zug, 137 Eulersche cp-Funktion, 28 Eulersche Graphen, 136 Exponentialfunktion, 74 exponentielle erzeugende Funktion, 66 exponentielle Laufzeit, 81, 145

I-Faktor, 147 I-faktorisierbar,147 Faktorielle

fallende, 7, 14, 40 steigende, 7, 14, 40

Fakultätsfunktion, 75 Fano-Ebene, 226, 243 Fibonacci Zahlen, 1, 28, 59 Filter, 215 Fixpunkt, 10, 23 fixpunktfreie Permutation, 38

Fluß, 130 elementarer, 133

Formellänge, 214 Funktion

Sachwortverzeichnis

exponentielle erzeugende, 66 wahrscheinlichkeitserzeugende, 70

Funktionen Boolesche, 214 monotone, 201 Wachstum von-, 74

Galoisfeld, 219 Gatter, 204 gemeinsame Verteilung, 20 Generatormatrix, 245 geometrisch-arithmetische Ungleichung,

35 geometrische Reihe, 58 geometrische Summe, 36 gerichteter Graph, 99 gerichteter Kreis, 100 gerichteter Multigraph, 99 gerichteter Weg, 100 Gewicht, 244· gewichtete Graphen, 110 Gittergraph, 117 Gitterwege, 30 Gleichverteilung, 19 goldener Schnitt, 61 Größenordnung von Rekursionen, 78 Grad, 93, 210 Gradfolge, 93, 103 Graph, 89

bipartiter, 120 gerichteter, 99 gewichteter, 110 orientierter, 99 vollständiger, 90 vollständiger k-partiter, 91 vollständiger bipartiter, 90

Graphenisomorphieproblem, 146 Gray-Code, 29 Greedy-Algorithmus, 111, 112, 188

Hadamard Matrix, 255

Sachwortverzeichnis

Hamiltonscher Graph, 140 Hamiltonscher Kreis, 140 Hamming-Abstand, 199 Hamming-Code, 245, 254 Hammingschranke, 242, 253 harmonische Zahlen, 6, 17,42 Hasse-Diagramm, 162, 207 Heiratssatz, 121 Horner-Schema, 82 Hypergraph, 207, 210, 214

k-uniform, 210 Hyperwürfel, 91,98

In-Grad,99 In-Order, 168 Indextransformation, 34, 59 Induktion, 35, 54 induzierte Verteilung, 20 induzierter Untergraph, 96 informationstheoretische Schranke, 154 Inklusion-Exklusion, 52 innere Ecke, 153 Inversion, 30, 44 Inversionsformel, 45 Inversionstafel, 30, 177 inzident, 93 Inzidenzmatrix, 4, 94, 99, 116 Inzidenzsystem, 4 Isolieren der Terme, 36, 52 isolierte Ecke, 93 isomorphe Graphen, 92

Jensensche Ungleichung, 170 Job-Zuordnungsproblem, 120, 130 Josephus-Problem, 53

Kanalcodierung, 236 kanonisches

Maximum Programm, 265 Minimum Programm, 265

Kanten, 89 Kapazität, 130 Kapazität des Schnittes, 131 Karnaugh Abbildung, 202, 213

Kette, 208 Kettenzerlegung, 209 Kneser Graph, 103 Komplement, 103 Komplexität, 145 Komplexitätsklasse, 145 Komponenten, 97 Komposition, 39 kongruent, 216, 219 Kongruenzklasse, 217 Konjunktion, 200 konjunktive Normalform, 200 Kontrollmatrix, 246 Kontrollsymbole, 239 konvex, 268 konvexes n-Eck, 182 Konvolution, 57 Kraftsche Ungleichung, 156 Kreis, 92

gerichteter, 100 Kryptogramm, 248 kürzester u, v-Weg, 114 Kürzeste-Wege-Problem, 115 Kugel, 241

Labyrinth-Problem, 101 Lah Zahlen, 52 Lateinisches Quadrat, 222

orthogonal, 222 Laufzeit, 145

exponentielle, 145 polynomiale, 145

Lemma von Farkas, 260 lexikographische Anordnung, 29 lineare Codes, 244 Lösung

optimale, 257, 272 zulässige, 257

Logarithmus, 74 binärer, 77 diskreter, 248

logisches Netz, 203 Lucas Zahlen, 69

M -saturiert, 124

313

314

M-alternierender Weg, 124 magisches Quadrat, 234 Markenproblem, 193 Markovs Ungleichung, 32 Matching, 120,259 Matching Funktion, 205 Matching-Zahl, 120 Matroid, 111, 190

duales, 117 Maximalgrad, 103 Maximum Fluß, 132 Maximum Matching, 120 Mehrfachkanten, 89 Mengen-Partitionen, 6 Mengenfamilie, 123 Mengenverband, 207 metrisches TSP, 143 minimal abhängig, 117 Minimale aufspannende Bäume, 110 minimale Bedeckung, 128 minimale Schnittmengen, 117 Minimalgrad, 103 Minimum Schnitt, 132 Minimum Spanning Tree Heuristik, 142 Minterm Funktion, 200 modulo,216 monotone Funktionen, 201 Münzwechselproblem, 192 Multigraph, 89

gerichteter, 99 Multimenge, 8

Nachfolger, 153 Netto-Fluß, 130 Netzwerk, 130 Newton-Darstellung, 44 nichtentartet, 270 Normalform

disjunktive, 200 konjunktive, 200

NP-vollständig, 145

O-Notation, 75 Öffentliches-Schlüssel-System, 249

Sachwortverzeichnis

offener Euler-Zug, 137 optimale Lösung, 257, 272 Optimierungsproblem, 144 Ordnung, 209, 215 orientierter Graph, 99

Packungszahl, 211 Paritätscode, 240 Partialbruchzerlegung, 60 partielle Summation, 43 k-Partition, 6 Pascalsches Dreieck, 14 perfekter Code, 254 k-Permutation, 7 Permutationen, 7, 10, 29

zyklische, 72 Permutationsmatrix, 123, 127 Petersen Graph, 92 Pivotelement, 274 polyedrische Menge, 270 polynomiale Laufzeit, 145 Potenzsumme, 42, 72 Präfix-Code, 237 primales Programm, 258 Primitivwurzel, 248 Prinzip der Inklusion-Exklusion, 49 Problem des chinesischen Postboten, 139 Problem des Handlungsreisenden, 81 Programm

duales, 258 primales, 258

projektive Ebene, 227

Quadrat Lateinisches, 222 magisches, 234

Quelle, 130 Quellencodierung, 236, 237 QUICKSORT, 164

Radius, 241 Rang, 111 Reed-Muller Codes, 252 Reed-Solomon Codes, 247

Sachwortverzeichnis

reflektiertes Polynom, 60 Regeln von de Morgan, 198 regulär, 93 Rekursion, 13, 37, 59, 80 Rekursionen

Grässenordnung von-, 78 simultane, 64

relativ prim, 28 Restklasse, 217 Restklassenring, 217 Ring-Summen-Normalform, 213 Rucksackproblem, 190

Satz von Dilworth, 209 Satz von Fermat, 218 Satz von Ford-Fulkerson, 132 Satz von Gale-Ryser, 149 Satz von Hoffman-Kruskal, 280 Satz von Menger, 150 Satz von Ramsey, 33 Satz von Shannon, 158 Satz von Sperner, 208 Schlingen, 89 Schlupfvariablen, 266 Schnitt, 131 Schnittecke, 104 Schrittweite, 39 Schubfach prinzip , 24 selbst-komplementär, 103 Senke, 130 Sheffer Stroke, 213 Sieb des Eratosthenes, 85 Simplexalgorithmus, 272 Simpsons Formel, 55 simultane Rekursionen, 64 SOPE-Darstellung, 202 Sortieralgorithmus, 82 Stammfunktion, 41 Standard Maximum Programm, 257 Standard Minimum Programm, 257 Standard Vertretersystem, 220 Standardabweichung, 23 Standardsystem, 217 stark zusammenhängend, 101

Steiner-System, 225, 253 Stern, 103 Stirling Approximation, 77 Stirling Konstante, 77 Stirling-Inversion,47 Stirling-Zahlen erster Art, 11 Stirling-Zahlen zweiter Art, 6 Stirlingsche Formel, 76 Suchproblem, 152 Summationsfaktor, 37 Summe

arithmetische, 34 geometrische, 36 unbestimmte, 41

315

System von verschiedenen Repräsentan­ten, 123

t-Design, 225 t-fehlerentdeckend, 241 t-fehlerkorrigierend,241 t-perfekt, 242 Taillenweite, 104 Träger, 122, 123 Trägerproblem, 148 transitiv, 74 Translationsoperator , 39 Transportproblem, 262 Transversale, 28, 123, 126 Trapdoor Funktion, 250 Traveling Salesman Problem, 81,136,140,

180, 280 trennende Kantenmenge, 150 Triangulierung, 182 Tschebyscheff Inversionsformel, 55 Tschebyscheffs Ungleichung, 32, 54 Turm von Hanoi, 53, 85 Turnier, 104 Typ der Permutation, 11

unabhängig, 102 Unabhängigkeitszahl, 102 unbestimmte Summe, 41 Ungleichung

geometrisch-arithmetische, 35

316

von Jensen, 170 von Markov, 32 von Tschebyscheff, 32

Unterbaum, 153 Untergraph, 96

induzierter, 96 Untermengen, 6 unvergleichbar, 208

Vandermonde Identität, 16, 67 Varianz, 21 vergleichbar, 208 Vergleichbarkeitsgraph, 212 Vergleiche, 162 Verifikation, 145 Versuchsplan, 221 Verteilung, 19

gemeinsame, 20 induzierte, 20

Vertreter, 217 Voll-Addierer, 206 vollständig unimodular, 280 vollständige k-partite Graphen, 91 vollständige bipartite Graphen, 90 vollständige Graphen, 90 Vorgänger, 153

Wägeproblem, 155 Wachstum von Funktionen, 74 Wahr-Falsch-Notation, 34

Sachwortverzeichnis

wahrscheinlichkeitserzeugende Funktion, 70

Wahrscheinlichkeit, 18 Wahrscheinlichkeitsraum, 18 Wald, 105 Weg, 91

gerichteter, 100 Wegesystem, 150 Wert eines Flusses, 131 wesentliche Variable, 204 Wiederholungscode, 239 Wort, 4 Wurzel baum , 153

Zählfunktion, 1 Zahl-Partitionen, 6, 51 Zielfunktion, 257 Zufallsvariable, 20, 71 zulässige Lösung, 257 zulässiger Fluß, 131 zunehmender Weg, 132 Zuordnungsproblem, 90 zusammenhängend, 97 Zusammenhangskoeffizienten, 46 Zusammenlegungsmethode, 83, 164 zyklische Permutationen, 72 Zyklen, 10 Zyklen darstellung , 10 zyklischer Code, 254

Der Analysis-Bestseller in neuer Auflage

Otto Forster

Analysis 1

Differential- und Integralrechnung

einer Veränderlichen '"

Inhalt: Vollständige Induktrqn - Die Körperaxiome - Anordnungsaxiome - Folgen, Grenzwerte - Das Vollstän­digkeitsaxiom - Quadratwurzeln -Konvergenzkriterien für Reihen -Die Exponentialreihe - Punktmen­gen - Funktionen, Stetigkeit - Sätze über stetige Funktionen - Logarith­mus und allgemeine Potenz - Die Exponentialfunktion im Komplexen - Trigonometrische Funktionen -Differentiation - Lokale Extrema. Mittelwertsatz. Konvexität - Nume­rische Lösung von Gleichungen -

·11 vleweg

Abraham-Llncoln-Straße 46 1).65173 Wiesbaden Fax (0611) 76 76-420 www.vleweg.de

Das Riemannsche Integral - Integra­tion und Differentiation - Uneigent­liche Integrale. Die Gamma-Funktion - Gleichmäßige Konvergenz von Funktionenfolgen - Taylor-Reihen -Fourier-Reihen

Eür die Neuauflage wurde nicht nur dle äußere Form geändert, sondern uch der gesamte Text überarbeitet,

qm ihn wo möglich noch verständli­cher zu machen. Es wurde der Tatsache Rechnung getragen, dass heute die meisten Diplom-Mathematiker Informatik als Nebenfach haben (statt wie früher Physik) und es wurden an verschiedenen Stellen Bezüge zur Informatik hergestellt. Verschiedene Übungsaufgaben wurden ergänzt. Die bewährten Charakteristiken des Buches haben sich nicht geändert. Es dringt ohne große Abstraktionen zu den wesentlichen Inhalten (Grenzwerte, Stetigkeit, Differentia­tion, Integration, Reihen-Entwick­lung) vor und illustriert sie mit vielen konkreten Beispielen.

Stand 1.4.99 Änderungen vorbehalten. Erhältlich im Buchhandel oder beim Verlag.

Lineare Algebra nun in 11. Auflage

Gerd Fischer

Lineare Algebra

11., verb. Auf!. 1997. X, 36 (vieweg studium; Grundkurs Br. DM 32,00 ISBN 3-528-77217-4

Inhalt: Lineare Gleichungssysteme - Grundbegriffe - Lineare Abbildun­gen - Determinanten - Eigenwerte -Euklidische und unitäre Vektor­räume - Dualität und Tensor­produkte

~ vleweg

Abraham-Lincoln-Straße 46 0-65173 Wiesbaden Fax (0611) 78 78-420 www.vieweg.de

Dieses seit über 20 Jahren bewährte, einführende Lehrbuch kann in der jetzt vorliegenden, verbesserten und erweiterten Form als Begleittext für eine zweisemestrige Vorlesung für Studenten der Mathematik, Physik und Informatik benutzt werden. Für einen ersten, leichteren Einstieg ist

s Buch ebenfalls zu verwenden, Indern die markierten Abschnitte

eggelassen werden. Zentrale Themen sind: Lineare Gleichungs­systeme, Eigenwerte und Skalar­produkte. Besonderer Wert wird darauf gelegt, Begriffe zu motivie­ren, durch Beispiele und durch Bilder zu illustrieren und konkrete Rechenverfahren für die Praxis abzuleiten. Der Text enthält zahlreiche Übungs­

. aufgaben. Die 11. Auflage enthält zusätzliche Abschnitte über Quotientenvektorräume und Tensorprodukte. Lösungen dazu findet man in dem von H. Stoppel und B. Griese verfaßten "Übungs­buchU (vieweg studium, Bd. 88)

Stand 1.4.99 Änderungen vorbehalten. Erhältlich im Buchhandel oder beim Verlag.