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

Informations

• Publié par: magellan
• Nombre de lectures: 102
• Langue: Français

Extrait

Fribourg (Switzerland)Exercises FS2009 M´ethodesmathe´matiquesdel’informatique/DiskreteMathematik S e r i e1 Hand in before Monday, 28.09.2009

o Exercise N 1 Give a list of all the (nonlabeled) graphs with 5 edges.(Do not repeat isomorphic graphs.)

o Exercise N 2 Prove that in any graph there is an even number of vertices of odd degree.

o Exercise N 3 Thendimensionalcube graphQ n has as vertices the lists of numbers{a 1 , a 2 , . . . , a n }witha k = 0 or a k = 1, 1≤k≤n. Twovertices in this graph are adjacent when the two corresponding lists differ in exactly one place. a) Draw the graphsQ 1 toQ 4 . b) How many edges and vertices doesQ n have? c) What are the degrees of vertices inQ n ? d) Show thatQ n is connected. n e) For which values ofndo the complete graphKand the cube graphQ n have an Euler cycle?

o Exercise N 4 (math) Prove by induction the theorem from class: IfAis the adjacency matrix of a graphG= (V, E) k withV={v 1 , . . . , v n }, then the (i, j) entry ofA,k≥1, is the number of different walks of lengthk betweenv i andv j .