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

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

1 page
Publié par :

magellan

Ajouté le : 21 juillet 2011
Lecture(s) : 102
Signaler un abus

Vous aimerez aussi

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 diﬀer 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 diﬀerent walks of lengthk betweenviandvj.