Théorie des graphes : Td1 theorie des graphes m2 iup miage f12 fe2
Télécharger PDFIUP Miage FI2-FE2 – Th ́eorie des graphesle 21 septembre 2004
TD no 1
1.Un grapheGd’ordre 7, `a 10 arˆetes a six sommets de degr ́eaet un sommet de degr ́eb. Que valentaetb?
De plus, si l’on consid`ere queGest simple que vautb?
2.SoitGun graphe d’ordre 12, `a 14 arˆetes dont les sommets sont de degr ́e 2 ou 3. CombienGa-t-il de sommets
de degr ́e 2 ?
3.Vous invitez 5 personnes. A chacune vous demandez combien d’invit ́es elle connait. Vous obtenez 5 r ́eponses
diff ́erentes. Est-ce possible ?
4.Montrer que parmi 6 personnes, il y en a au moins 3 qui se connaissent mutuellement ou au moins 3 qui ne
se connaissent pas mutuellement. (par mutuellement on entend deux `a deux)
5.Montrer que tout graphe non orient ́e simple d’ordren,n≥2 a au moins deux sommets de mˆeme degr ́e.
6.Un graphe non orient ́e simple d’ordre 4 peut-il avoir trois sommets de degr ́e 3 et un sommet de degr ́e 1 ?
7.On dit qu’une suite d’entiers naturelsk1 ,···, kn est graphique s’il existe un graphe non orient ́e simple
d’ordrentel que ses sommetsx1 ,···, xn ont respectivement les degr ́esk1 ,···, kn . Les suites ci-dessous sont-elles
graphiques ?
•5,5,4,4,3,3,3,1,0,0
•7,6,2,2,2,1,0,0
•5,3,3,3,2,2,1,1
•3,3,2,2,2,2,1
Montrer que pour toutx∈{0,1,2,3,4,5}la suitex,1,2,3,5,5 n’est pas graphique.
Th ́eor`eme 1
(Havel-Hakimi) : une suited ́ecroissanted’entiers naturelsk1 ≥ ··· ≥kn avecn≥2etk1 ≥1
est graphique ssi la suitek2 −1, k3 −1,···, kk 1+1 −1, kk 1+2 ,···kn est graphique. (on a supprim ́ek1 puis on a
retranch ́e1auxk1 premiers termes)
Ce th ́eor`eme fournit un algorihtme pour d ́eterminer si une suite est graphique ou non. (cherchez les cas de base)
8.Dessiner un graphe non orient ́e simple dont l’ensemble des degr ́es des sommets est{0,4,5}.
9.Le compl ́ement d’un graphe non orient ́e simpleG= (X, E, φ) est le grapheGc = (X, Ec , φc ) tel que deux
sommets sont adjacents dansGc ssi ils ne sont pas adjacents dansG.
9.1Comment formuler le probl`eme de l’exercice 4 en terme de graphe utilisant la notion de graphes compl ́ementaires.
9.2Un grapheGnon orient ́e simple est dit autocompl ́ementaire siGest isomorphe `aGc . Montrer que siG,
d’ordren, est autocompl ́ementaire alorsn≡0ou1modulo4.1 10.SoitA={0,1,2,3,4}. Le graphe de Petersen est le graphe non orient ́e d ́efini comme suit : les sommets
sont les paires d ́el ́ements deAetxyest une arˆete ssix∩y=∅. Par exemple{01}et{23}sont adjacents et{01}
et{13}ne sont pas adjacents.
D ́eterminer l’ordre de ce graphe, le degr ́e de chaque sommet, le nombre d’arˆetes et le diam`etre de ce graphe.
Dessiner ce graphe. Est-il planaire ? Quel est son nombre chromatique ?
11.Un chimiste veut transporter des produits chimiquesA,B,C,D,E,F,Xdans des caisses. Mais certains
produits ne peuvent se cˆotoyer sous peine de r ́eaction dangereuse :A,B,Cr ́eagissent entre eux,AetEr ́eagissent
chacun avecFetDetXr ́eagit avecC,E,F. Trouver le nombre minimal de caisses n ́ecessaires au transport.
12.Un commissariat doit effectuer 8 surveillances selon des horaires fix ́es par le tableau suivant
surveillanceno 12345678
d ́ebut515873131119
fin1018181214212023
Quel sera le nombre minimal de policiers n ́ecessaires ? (remarque : dans les horaires de d ́ebut et de fin sont
comptabilis ́ees les d ́eplacements depuis ou bien jusqu’au commissariat).
13.SoitGun graphe non orient ́e simple d’ordren. Montrer que siGest biparti alorsm≤n 24 .
14.Trouver une repr ́esentation planaire du grapheK5 −eo`ueest une arˆete quelconque deK5 .
15.Soitχ(G) le nombre chromatique d’un graphe simple. L’algorithme glouton de coloration des sommets
consiste `a suivre une liste des sommets et `a les colorier dans l’ordre avec le plus petit entier disponible. Appliquer
le sur les graphes suivants :GHΓ Cet algorithme donne-t-il toujours le nombre chromatique ?