Précédent / Suivant / Table des matières

 

 

Exercice I :

Peut-on aligner toutes les pièces d’un jeu de domino selon la règle habituelle du jeu de domino ?

 

Exercice II :

Un graphe G simple d’ordre n≥2 est dit parfait si on ne peut trouver deux sommets de même degré.
1) Montrer qu’aucun graphe simple n’est parfait
2) Montrer que dans une soirée mondaine on trouve toujours deux personnes ayant le même nombre d’amis présents.

 

Exercice III :

Les deux graphes suivants modélisent-ils la même situation ?

Exercice IV :

1) Soit G=(S,A) un graphe simple d’ordre n et soit  son graphe complémentaire. Montrer que si G est k-régulier alors  est (n-k-1)-régulier.
2) Montrer que si deux graphes simples sont isomorphes alors leurs complémentaires aussi.

 

Exercice V :

1) Soit S₁={s₁, s₂ … , s_n} et S₂={s_n+1, s_n+2 … , s_2×n} et  S= S₁S₂. On considère le graphe simple G=(S,A) définie par s_is_jA si et seulement si s_iS₁ et s_jS₂. (G est un graphe biparti complet) Donner la matrice d’adjacence M de G et, sans calcul, déterminer M² et M³. Retrouver ce résultat par le calcul.

 

Exercice VI :

Montrer que si dans un graphe simple il y a exactement deux sommets impairs alors il existe une chaîne joignant ces deux sommets.

 

Exercice VII :

Soit G=(S,A) un graphe simple d’ordre n et de taille p et M sa matrice d’adjacence. On appelle triangle tout sous-graphe complet d’ordre 3 de G.

1) Montrer que p=tr(M²).
2) Montrer que le nombre de triangles de G est égal à 1/6tr(M³).
3) Donner un contre-exemple montrant que M⁴ ne permet pas toujours de connaître le nombre de rectangles de G. (un rectangle est un sous-graphe d’ordre 4 de G qui est un cycle).