[PDF] Hints and Solutions to Exercises

Hints and Solutions to Exercises

the solutions has been given in Latin verses (cf [265, p 74]): [130] Hartsfield, N , Ringel, G , Pearls in Graph Theory, Academic Press, Boston MA, 1990

[PDF] Chapter 1 of Pearls is scanned here

1 mar 2021 · The reader is invited to find a solution Pearls in Graph Theory Graph theory is used in designing printed circuits for use in electronics

[PDF] nora_hartsfield_gerhard_ringel_pearls_in_graphpdf - WordPresscom

Pearls in graph theory: a comprehensive introduction / Nora Hartsfield, Gerhard Ringel -- Rev and augm p cm Includes bibliographical references and index

[PDF] Exercises - Graph Theory SOLUTIONS

Exercises - Graph Theory SOLUTIONS Question 1 Model the following situations as (possibly weighted, possibly directed) graphs Draw each graph, and give 

[PDF] Graph Theory Questions List

The questions below are taken from Pearls in Graph Theory, by Hartsfield and Ringel Most of class will consist of students presenting solutions to these 

[PDF] Graph Theory Problems and Solutions - Tom Davis

11 nov 2005 · Prove that if u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree 8

[PDF] pearson biology chapter 20 test

[PDF] pearson business enterprise and entrepreneurship past papers

[PDF] pearson com us

[PDF] pearson corporate

[PDF] pearson edexcel english language past papers

[PDF] pearson education books free download pdf

[PDF] pearson english grammar books pdf

[PDF] pearson health textbook pdf

[PDF] pearson hoboken

[PDF] pearson login

[PDF] pearson longman books pdf

[PDF] pearson mathematics books pdf

[PDF] pearson media

[PDF] pearson my lab

[PDF] pearson publication

Appendix A

Hints and Solutions to Exercises

Chapter 0

Exercise 0.1The ansatz leads toξn+2=

ξn+1+ξn, such thatξ2=ξ+1, which is solved byτ?= (1+º5)?2>0andσ?= (1-º5)?2=

1?τ<0.

LetFn=aτn+bσnwith0=F0=a+b

and1=F1=aτ+bσ= (a-b)º5?2.

Hencea=1?º5= -band consequently

Fn=τn-σn

⎷5. (This formula is named for

J. P. M. Binet.) Similarly, ifLn=aτn+bσn

with2=L0=a+band1=L

1=1+ (a-

b)º5?2, we getLn=τn+σn.

Forn?N, we have

Fn+1

Fn=τn+1-σn+1

τn-σn=τ-σ?σ

τ?n

1-‰σ

τ?n.

Butσ?τ

= -1?τ2, whence?σ?τ? <1, such thatFn+1?Fn→τ, asn→∞. Similarly for Ln.

Remark A.1.While it is by an easy in-

duction proof that one can show that there is only one mappingF?NN00which ful- lls the recurrence(0.4)and we proved the existence by deducing Binet's formula, the question whether any such recurrence leads to a well-dened mathematical object is rather subtle and usually ignored in theliterature. Because of the latter fact and since theFundamental theorem of recur- sionis of outstanding importance even to dene such elementary things like addition of the natural numbers, we will state and prove it here for the connoisseur (and all those who want to become one). Its rst ap- plication will be the denition of factorials in the next exercise.

Fundamental Theorem of Recursion.Let

Mbe a set,η0?M, and??MN0×M. Then

there exists exactly one mappingη ?MN0 which fulfills the recurrence

η(0) =η0,?k?N0?η(k+1) =?(k,η(k)).

Proof. Uniqueness.Letη,μ?MN0both

fulll the recurrence. Thenη(0) =η0=μ(0) and ifη(k) =μ(k)fork?N0, thenη(k+1) = ?(k,η(k)) =?(k,μ(k)) =μ(k+1). By in- duction we getη=μ.

Existence.The wanted functionη?N0×M

must have the following properties: ?k?N0?ηk?M? (k,ηk) ?η,(A) ?k?N0?m1,m2?M?

ˆk,m1),(k,m2) ?η?m1=m2,(B)

(0,η0) ?η? ?k?N0?m?M?

ˆk,m) ?η?(k+1,?(k,m)) ?η.(C)

Condition (C) is satisfied, e.g., by

N0×M. Therefore we choose

η=⋂{μ?N0×M?μfulfills(C)}.

A. M. Hinz et al.,The Tower of Hanoi - Myths and Maths, DOI: 10.1007/978-3-0348-0237-6,?Springer Basel 2013

266Appendix A. Hints and Solutions to Exercises

We now prove (A) and (B) simultaneously

by induction onk. By definition,(0,η0) ?η.

Assume that(0,μ0) ?ηfor someM?μ0≠

η0. Letμ?=η∖ {(0,μ0)}. Then(0,η0) ?μ and if(κ,m) ?μ, then(κ+1,?(κ,m)) ?μ as well, since no element of the form(κ+

1,?)has been taken away fromη. There-

fore,μhas property (C); but thenη?μ, in contradiction to the denition of the latter set.

For the induction step, putηk+1?=

?(k,ηk). If(k+1,m) ?ηfor someM? m≠ηk+1, defineμ?=η∖{(k+1,m)}. Again (C) is fullled forμ((0,η0)has not been excluded and(k+1,m) ≠ (k+1,?(k,ηk))), and we get the contradictionη?μ.◻

Exercise 0.2 a)Induction on?. There

is exactly one (injective) mapping from [0]= ∅to[k]. An injectionιfrom[?+1] to[k],??[k]0, can havekvalues for ι(?+1), andι↾[?](↾stands for "restricted to) runs through all injections from[?] to[k]∖{ι(?+1)}, such that there are all in allk(k-1)! ((k-1)-?)!=k! (k-(?+1))!injec- tions from[?+1]to[k].

The statement about bijections fol-

lows from the special case?=k, together with the pigeonhole principle which ex- cludes the possibility of an injection from [k]to a smaller set. b)Again by the pigeonhole principle, there is no subset of[k]with?>kelements. For k≥?, we have from (a)k! (k-?)!injective mappings from[?]to[k]. Each element of ?k] ??occurs?!times as a permuted image set of one of these injections. c)ForkIfk>?, thenk+1≥?+1,k≥?, andk≥?+1, such that from (b) we get ?k `? + ?k `+1?=k! ?!(k-?)!+k! (?+1)!(k-?-1)! =(k+1)! (?+1)!(k-?)!=?k+1 ?+1?.

Exercise 0.3 a)The casek=0is just

for deniteness: of course, the empty set [0]can neither be permuted nor deranged in the ordinary sense of these words, but there is precisely one mapping from[0]to [0], and this mapping does not have a fixed point, such thatf0=1. On the other hand, the only mapping from[1]to[1]clearly has a xed point, whencef1=0.

Letk?Nand??[k]. Any derange-

mentσon[k]can be modified to yield a derangement̃σon[k+1], namely by defin- ing̃σ=σon[k]∖{?},̃σ(?)=k+1, and

̃σ(k+1)=σ(?), i.e. by mapping?onk+1

and the latter to the former image of?. This makes up fork?fkderangements on[k+1].

A derangementσon[k-1]can be

manipulated as follows. Deneτ?[k-1]→ [k]∖{?}byτ(i)=iforiAppendix A. Hints and Solutions to Exercises267

As Euler admits himself, "however, it

is not as easy to derive (0.15) from (0.14).

Therefore, we rst prove formula (0.16) as-

suming (0.14) by induction, where the in- duction step fork?Nreads xk+1=k(xk+xk-1) =(k+1)!? k-1 ?=0 (-1)? ?!+(-1)kk (k+1)!? =(k+1)! k+1 ?=0 (-1)?

Finally, the implication "(0.16)?

(0.15)" is trivial.

Exercise 0.4103910=100000011112and

1110=10112, such that every bit of11is

smaller than or equal to the corresponding one of1039and therefore?1039

11?is odd ac-

cording to (0.8).

Exercise 0.5Employ Fleury"s algorithm:

start in a vertex of odd degree, A say, avoid using a bridge (edge) that separates the re- maining graph into two components, and delete used edges. For example:

ABCDABDAC.

Exercise 0.6We can employ Fleury"s al-

gorithm for the graph in Figure A.1, whose vertices are all even. Starting with edge a, we follow Fleury to get the trail abcdef, here denoted by the labels of the edges. f a b c d e

Figure A.1: Muhammad"s sign manual as a graph

Exercise 0.7We will describe the algo-

rithm informally. To check an edgeabfor being a bridge inG, we search for a path frombtoainG-ab. Starting inb, we screen all neighbors ofb, then neighbors of neighbors and so on, but skipping those al- ready encountered. (Since we stay as close to therootbas possible, this is called a breadth-first search (BFS)). The result is a tree rooted inbandspanningits connected component inG-ab. Ifais not on that tree, thenabis a bridge.

For a practical realization, we may

construct a queue of vertices to be checked for their neighbors. Initially we deneqv= n?=?G?for allv?V(G). The length?of the queue is put to1andqb=1, such that ver- texbis now first in the line. Then we search successively for its neighborsuinG-ab which have not yet been visited, i.e. with qu=n. If we encountera, we stop:abis not a bridge. Otherwise we increase?by1 and putqu=?. After all neighbors ofbhave been scanned, we decrease?by1and also allqu?[n-1]and restart the search for neighbors of the rst vertexvin the queue, that is withqv=1, as long as there is any, i.e.?=?{u?V(G)?qu?[n-1]}?≠0.

Exercise 0.8 a)Coming from L T, the next

three moves areμλμ, which can be found

268Appendix A. Hints and Solutions to Exercises

twice in both equations (0.9) and (0.10), such that there are the four solutions

L T S R Q Z B G H X W V J K F D C P N M,

L T S R Q Z X W V J H G B C P N M D F K,

L T S R Q Z B C P N M D F G H X W V J K,

L T S R Q P N M D C B Z X W V J H G F K.

b)Here the triple isμλ2, occurring only in one kind in each equation, such that we have the two solutions

J V T S R W X Z Q P N M L K F D C B G H,

J V T S R W X H G F D C B Z Q P N M L K.

Exercise 0.9Let us assume thatK3,3is

planar. Since it is 2-colorable, it does not

2?K3,3?, such that with (0.11), we arrive at

tion.

Exercise 0.10Hint: Reduce problem CB

to themissionaries and cannibals problem (MC): three missionaries and three can- nibals want to cross the river with the same boat as before; the cannibals must never outnumber the missionaries on a river bank.

Identifying women with cannibals

and men with missionaries, it is clear that every solution of CB leads to a solution of MC, because individuals do not play a role in the latter and women can never outnumber men on a bank since otherwise a woman would be without her brother.

So if we solve MC, we only have to ver-

ify that the solution will also satisfy CB.

We will stay with the women/men nota-

tion and denote bymwa constellation of m?{0,1,2,3}men andw?{0,1,2,3} women on the bank where the boat is present. By the jealousy condition, only

10of the16combinations are admissi-

ble:00,01,02,03,11,22,30,31,32,33. Of these00(no transfer possible),01(can only be reached from33and leads back there) and30(more women than men on the other bank after transit) can be excluded imme- diately. The remaining7constellations lead to the graph in Figure A.2, whose edges are boat transfers labelled with the passen- ger(s). 33
02 11

32 03 3122

ww mw w m ww wmmmw Figure A.2: The graph of the missionaries and cannibals problem

Note that this graph contains aloopat ver-

tex22. Quite obviously, there are precisely four optimal solutions of length 11. One of the solutions has been given in Latin verses (cf. [265, p. 74]):

Binae, sola, duae, mulier, duo, vir mulierque,

Bini, sola, duae, solus, vir cum mulier.

In fact, all solutions lead to solutions

of (CB), where now individual identities increase the number of dierent solutions.

For instance the transfer33→02can be

performed with any of the three pairs of women, whereas the reverse transfer has to be done with the only pair present. A combinatorial analysis of all cases based 269
on Figure A.3 leads to486solutions alto- gether. It seems that this number has never been given in the abundant literature of the problem.

Variations include higher numbers of

land in the middle of the river; cf. [265].

The problem has also been employed as an

example for problem representations, i.e. models, in the Articial Intelligence liter- ature; cf. [12]. 3 3 12

213 31 1 1

2 11 1 Figure A.3: Numbers of alternatives in the careful brothersproblem

Chapter 1

Exercise 1.1The two pendant vertices are

the end-vertices of a path. By the Hand- shaking lemma the rest of the vertices form a union of cycles.

Exercise 1.2The path of length2n-1

fromα(n)toω(n)inRncan be dissected into the two paths from0nto1nand from

1n=11n-1toω(n)=10n-1of lengthsβn

andβn-1, respectively.

Exercise 1.3In every move precisely one

bit is switched. This yields the vertex col- oring. It can be proved by induction that moves of type 0 and 1 are alternating along a shortest path fromα(n)toω(n), obviously starting and ending with move type 0.

Exercise 1.4 a)The state graph is con-

structed by adding edges{s 00,s

11}with

s ?Bn-2toRn, just like the red edges in

Figure A.4.

000100001011010101110111

Figure A.4: The graphR3with double moves (red edges) b)We may define the graph̃Rnfrom the previous graph by deleting all vertices of the forms

01, because they subdivide the

new edges. It is a path graph again, whose length is2n-1+2n-2-2?2n-2=3?2n-2-1. c)As in (1.2), we havẽβ1=1,?n?N? ̃βn+1+̃βn=3?2n-1-1. Forγn?=2n-1-̃βn this means thatγ1=0and?n?N?γn+1=

1-γn, whence

̃βn=2n-1-(neven).

Appendix A. Hints and Solutions to Exercises

270Appendix A. Hints and Solutions to Exercises

Exercise 1.5Hint:(2n-1)mod 3=nmod

2. Forn=0,C=Vand?C?=1. For

n?N, either0nor0n-11is a codeword.

Consequently, the codewords are those ver-

ticess?Bnwithd(s)mod 3=0or1, re- spectively. From the hint it follows that for evennnecessarilyα(n)andω(n)are code- words and that?C?=1

3(2n+2); for oddn

there are two perfect codes, containing ei- therα(n)orω(n)and with?C?=1

3(2n+1).

Exercise 1.6We are looking for the state

s?B14which lies on the pathR14between

114and014at a distance9999from the for-

mer. Sinceβ14=d(114,s)+d(s,014), we get d(s,014)=⌈2

3(214-1)⌉ -d(114,s)

=10922-9999=923 =000011100110112.

We can now apply the Gray code au-

tomaton in Figure 1.4 which yieldss=

00001001010110. Therefore, rings2,3,5,

7, and10are on the bar, all others are off.

Exercise 1.7Obviously,W(P1)=0, and

for a pendant vertexeofPk,k>1, we have

W(Pk)=?

v?V(Pk) d(e,v) +W(Pk-1) =Δk-1+W(Pk-1)=?k

2? +W(Pk-1).

Comparing this with Exercise 0.2(c), we re-

alize thatW(Pk-1)fulfills the same recur- rence as?k

3?, such thatW(Pk)=?k+1

3?.

Exercise 1.8Writek=2r(2s+1),r,s≥0.

Then observe that in the binary representa-

tion(bnbn-1...b1b0)2ofkwe haveb0=b1= ⋯=br-1=0andbr=1. Hencẽgk=r. Since by Corollary 1.11,gk=r+1, the conclusion follows.

Exercise 1.9The recursion forqfollows

immediately from the binary representa- tion ofk. But thengk=q(k-1)-q(k)+2, because the right-hand side fullls the re- cursion of the Gros sequence in Proposi- tion 1.10. Summing̃gk=q(k-1)-q(k)+1 from 1 tonyields Legendre"s formula.

Exercise 1.10Hint: Starting at0n, walk

along the edges of the cube by switching bgkin thek-th step fork?[2n-1]. This path will end in0n-11, corresponding to a corner of then-cube which is linked to our starting corner by an extra edge.

Exercise 1.11We will show that Corol-

lary 1.11 remains valid withgreplaced by a. We first claim that for anyr?N0, (i) a2r=r+1, and that (ii)ak