La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Fribourg (Switzerland)Exercises FS2009 M´ethodesmathe´matiquesdelinformatique/DiskreteMathematik S e r i e1 Hand in before Monday, 28.09.2009
o ExerciseN1 Give a list of all the (nonlabeled) graphs with 5 edges.(Do not repeat isomorphic graphs.)
o ExerciseN2 Prove that in any graph there is an even number of vertices of odd degree.
o ExerciseN3 Thendimensionalcube graphQnhas as vertices the lists of numbers{a1, a2, . . . , an}withak= 0 or ak= 1, 1kn. Twovertices in this graph are adjacent when the two corresponding lists differ in exactly one place. a) Draw the graphsQ1toQ4. b) How many edges and vertices doesQnhave? c) What are the degrees of vertices inQn? d) Show thatQnis connected. n e) For which values ofndo the complete graphKand the cube graphQnhave an Euler cycle?
o ExerciseN4 (math) Prove by induction the theorem from class: IfAis the adjacency matrix of a graphG= (V, E) k withV={v1, . . . , vn}, then the (i, j) entry ofA,k1, is the number of different walks of lengthk betweenviandvj.