Méthodes mathématiques de l'informatique diskrete mathematik
1
page
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
1
page
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Fribourg (Switzerland)Exercises FS2009 M´ethodesmathe´matiquesdel’informatique/DiskreteMathematik S e r i e1 Hand in before Monday, 28.09.2009
o ExerciseN1 Give a list of all the (nonlabeled) 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 Thendimensionalcube graphQnhas as vertices the lists of numbers{a1, a2, . . . , an}withak= 0 or ak= 1, 1≤k≤n. 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,k≥1, is the number of different walks of lengthk betweenviandvj.
