Universit Paris 13 Sup Galile INFO2Institut Galile Anne
2011-2012
Algorithmique de GraphesTD3 : Quelques preuves dans les
graphes
Exercice 1Pour un graphe G = (V,E), montrer que :
1.vV
dv = 2|E|, o dv est le degr du sommet v.
2. Le nombre de sommets de degr impair est pair.
3. Si m = |E| et n = |V | et G est simple, m n(n1)2 .
Exercice 2Existe-t-il
1. un graphe dont la suite des degrs esta) 1, 3, 3, 4, 5, 6, 6,
6, 6, 6, 6, 7 ?b) 2, 3, 4, 5 ? Si (di)1in est une suite dentiers
non dcroissante, dmontrer que
lon peut lui associer un graphe si et seulement si la somme des
di est paire.
2. un graphe simple dont la suite des degrs est 1, 1, 3, 3, 3,
3, 5, 6, 8, 9 ?
Exercice 3Soit G = (V,A) le graphe orient dfini par :V = {a, b,
c, d, e}A = {(a, b), (a, c), (b, d), (c, b), (c, d), (d, a), (d,
e), (e, c)}
1. On note d+(x) le degr sortant de x, cest--dire le nombre
darcs (x, y), x 6= y.On note de faon analogue d(x) le degr
entrant.Calculer d+(x) et d(x) pour chaque sommet x V .
2. Trouver dans G un cycle de longueur 4, un circuit de longueur
3.
3. On appelle chemin (resp. circuit) eulrien un chemin (resp.
circuit) qui passe une fois etune seule sur chaque arc du graphe.On
a les proprits suivantes :Proprit 1 : Un graphe orient connexe
admet un chemin eulrien de a b ssid+(a) d(a) = d(b) d+(b) = 1et x,
x 6= a, x 6= b, d+(x) = d(x).Proprit 2 : Un graphe orient connexe
admet un circuit eulrien ssix, d+(x) = d(x).G admet-il un chemin
eulrien ? Un circuit eulrien ? Si oui, en trouver un.
Exercice 4Peut-il exister un groupe de 15 personnes au sein
duquel chacun a exactement 3 amis ?
Exercice 5Les artes dun graphe complet n 6 sommets ont t colores
en rouge et en vert au hasard.Montrer que le graphe contient au
moins un triangle unicolore.
1
Exercice 6Le professeur Mongraf et sa femme ont organis une
soire avec quatre autres couples. Cer-taines personnes, issues de
couples diffrents, se sont serres la main. A la fin de la
soire,Mongraf demande chacun combien de mains il a serr. Il reoit
neuf rponses diffrentes.Combien sa femme a-t-elle serr de mains
?
Exercice 7G = (V,E) est un graphe simple non orient. Soit (G)
=
PvV
d(v)
2|V | .
1. Quelle interprtation peut-on donner (G) ?
2. On suppose quil existe v1 de V tel que d(v1) (G). Posons{V1 =
V \{v1}E1 = E\{[v1, v]; v V }
Considrons le graphe G1 = (V1, E1). Quelle relation a-t-on entre
(G) et (G1) ?
3. En dduire un algorithme qui permet dextraire un sous-graphe H
dun graphe nonorient simple G, vrifiant : min{dH(v); v H} > (H)
(G).
Exercice 8Le conseil gnral dun dpartement comprend 7
commissions. On sait que :- tout conseiller gnral fait partie de 2
commissions exactement,- 2 commissions quelconques ont exactement
un conseiller gnral en commun.Combien y a-t-il de conseillers
gnraux ? (Justifier clairement la rponse en utilisant
ungraphe.)
2
