Méthodes mathématiques de l'informatique diskrete mathematik

Publié par

Publié le : jeudi 21 juillet 2011
Lecture(s) : 101
Nombre de pages : 1
Voir plus Voir moins
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.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.