Td1-solutions theorie du graphe.pdf

7/23/2019 Td1-solutions theorie du graphe.pdf

http://slidepdf.com/reader/full/td1-solutions-theorie-du-graphepdf 1/5

Université Francois Rabelais de Tours

Département de Mathématiques

Solutions Feuille de Travaux Dirigés n◦1

Mimats Semestre 10

Exercice 1 Soit G un graphe acyclique (et donc nécessairement simple). Montrer que G possède au plusn − 1 arêtes.

Solution: On procède par récurrence sur le nombre de sommets n de G.

Initialisation. Si n = 1, alors |E | = 0 et le résultat est vrai.

Hypothèse de récurrence. Tout graphe acyclique contenant n sommets possède au plus n − 1 arêtes.

Hérédité. Soit G = (V, E ) un graphe acyclique tel que |V | = n + 1 ≥ 2. On veut montrer que |E | ≤ n.On peut supposer que |E | ≥ 1. Soit x, y ∈ V tel que [x, y] ∈ E et G = (V, E \[x, y]) le graphe partiel. Legraphe G ne peut pas être connexe, sinon il existerait une chaîne de x à y dans G qui donnerait un cycledans G en rajoutant l’arête [x, y]. Soient G1 = (V 1, E 1), . . . ,Gk = (V k, E k) les composantes connexes de G.Par récurrence, on a

|E | =

ki=1

|E i| + 1 ≤ki=1

|V i| − 1

+ 1 = n + 1 − k + 1 ≤ n.

[En fait, on peut voir que, si le graphe G est connexe, en supprimant une arête dans G, on a créé au plus 2 composantes

connexes. Dans le cas d’un graphe orienté, il est possible de créer plus de 2 composantes fortement connexes en supprimant

un seul arc.]

Exercice 2 Montrer qu’un graphe est biparti si et seulement si il ne contient pas de chaîne fermée delongueur impair.

Solution: Soit G = (V, E ) un graphe biparti. Soit C une chaîne de longueur impaire et soit (v0, . . . , v2n+1)la suite de sommet associé à C . On suppose que v0 ∈ V 1. Puisque G est biparti et (vi, vi+1) ∈ E on voit

facilement que vk ∈ V 2 si k est impair et vk ∈ V 1 si k est pair. Ainsi, v2n+1 ∈ V 2 et C n’est pas fermée.

Soit G = (V, E ) un graphe connexe ne contenant pas de chaîne fermée de longueur impaire et soit u ∈ V .On pose

V 1 = {v ∈ V | ∃ une chaîne de longueur impaire de u à v dans G}

V 2 = {v ∈ V | ∃ une chaîne de longueur paire de u à v dans G}

On a alors

∗ V = V 1 ∪ V 2 puisque G est connexe

∗ V 1 ∩ V 2 = ∅. En effet s’il existe v ∈ V 1 ∩ V 2 alors on peut trouver une chaîne C p de longueur paireet une chaîne C i de longueur impaire allant de u vers v. Mais alors on aurait une chaîne fermée de

longueur impaire u C p−→ v C i−→ u.

∗ Il n’existe pas d’arête entre deux sommets de V 1. En effet, soit v, w ∈ V 1. Il existe C 1 et C 2 deuxchaînes de longueur paire joignant u à v et w respectivement. Si a = [v, w] ∈ E alors

u C 1−→ v

a−→ w

C 2−→ u

est un cycle de longueur impair. C’est une contradiction.

∗ Il n’existe pas d’arête entre deux sommets de V 2. En effet, soit v, w ∈ V 2. Il existe C 1 et C 2 deuxchaînes de longueur impaire joignant u à v et w respectivement. Si a = [v, w] ∈ E alors

u C 1−→ v

a−→ w

C 2−→ u

est une chaîne fermée de longueur impair. C’est une contradiction.On voit donc que G est biparti.[Le résultat est encore vrai si on suppose que G ne contient pas de cycle de longueur impair mais il est un peu plus technique

à montrer puisque un cycle ne passe pas deux fois par la même arête. . . ]

1



Exercice 3

1. Montrer qu’un graphe G est fortement connexe si et seulement si G est connexe et tout arc est dansun circuit.

2. Le résultat est-il encore vrai si on remplace la condition par : G est connexe et tout sommet est dansun circuit ?

3. Est-il vrai que si dans un graphe G on a x → y et y → x alors il existe un circuit élémentaire passant

par x et y ?Solution: 1. On supposera que G est fortement connexe. Par définition, G est connexe. Soit (x, y) un arcde G. Comme G est fortement connexe, il existe un chemin de y vers x. Si on ajoute à la fin de ce cheminl’arc (x, y) on obtient un circuit contenant x et y .

Réciproquement, supposons que G est connexe et que tout arc est dans un circuit. Soient x, y ∈ V . Ilexiste un chemin non orienté de x vers y. Supposons qu’il existe dans ce chemin un arc (a, b) "dans lemauvais sens". Comme (a, b) appartient à un circuit, il existe un chemin C de b vers a. On remplace alors

(a, b) dans le chemin non-orienté de x vers y par le chemin b C −→ a. On applique cette transformation à

tous les arcs qui sont dans le mauvais sens. On obtient un chemin de x vers y. G est donc fortement connexe.

2. Non :

3. Non :

Exercice 4 Soit G = (V, E ) un graphe orienté avec V = {1, 2, . . . , n}. On considère la matrice A = (ai,j)définie par

ai,j =

1 si i → j

0 sinon

On considère l’algorithme suivant

pour i = 1 à n faireai,i = 1pour j = 1 à n faire

pour k = 1 à n faireaj,k = max{aj,k, aj,iai,k}fin

fin

fin

1. Appliquer l’algorithme au graphe suivant

2. Vérifier que, après avoir appliquer l’algorithme, on a ai,j = 1 si et seulement si i → j .

3. Comment trouver les composantes fortement connexes avec cet algorithme.

2



Solution: 1. Notons AN la matrice obtenue après avoir parcouru la première boucle en i N -fois.

A0 =

0 1 0 1

0 0 1 0

0 0 0 0

1 1 0 0

A1 =

1 1 0 1

0 0 1 0

0 0 0 0

1 1 0 1

A2 =

1 1 1 1

0 1 1 0

0 0 0 0

1 1 1 1

A3 =

1 1 1 1

0 1 1 0

0 0 0 0

1 1 1 1

A4 =

1 1 1 1

0 1 1 0

0 0 1 0

1 1 1 1

2. On notera a(N )i,j les coefficients de AN . Montrons par récurrence sur N que a

(N )i,j = 1 si et seulement il

existe un chemin allant de i vers j et ne passant que par des sommets de valeur inférieure ou égale à N (hormis bien sur les extremités).

Si k = 0, c’est clair puisque A0 est la matrice d’adjacence du graphe.

Montrons que a(N +1)i,j = 1 si et seulement si il existe un chemin de i vers j ne passant que par des sommets

de valeur inférieure ou égale N + 1. Remarquons tout d’abord que

a(N +1)i,j = 1 ⇐⇒ a

(N )i,j = 1 ou a

(N )i,N +1a

(N )N +1,j = 1.

On suppose que a(N +1)i,j = 1. Si a

(N )i,j = 1, alors par récurrence, il existe un chemin de i vers j ne passant

que par des sommets de valeur inférieure ou égale à N et donc aussi à inférieure ou égale N + 1.

Si a(N )i,N +1a

(N )N +1,j = 1 alors a

(N )i,N +1 = 1 et a

(N )N +1,j = 1. Par récurrence, il existe un chemin de i → N + 1 ne

passant que par des sommets ≤ N et un chemin N + 1 → j ne passant que par des sommets ≤ N . Ainsiil existe bien un chemin de i vers j ne passant que par des sommets ≤ N + 1.

Réciproquement supposons qu’il existe un chemin de i vers j ne passant que par des sommets ≤ N + 1.Soit i = i0 → i1 . . . → in = j un chemin de longueur minimale allant de i vers j tel que ir ≤ N + 1

pour tout r. On remarque que, par minimalité, tous les ir sont distincts. Soit im le sommet de valeurmaximale dans ce chemin. Si im < N alors par récurrence on a a

(N )i,j = 1 et on obtient a

(N +1)i,j = 1

dans ce cas. Supposons donc que im = N + 1. On a alors un chemin de i vers N + 1 ne passant quepar des sommets < N + 1 et un chemin de N + 1 vers j ne passant que par des sommets < N + 1. On

en déduit par récurrence que a(N )i,N +1 = 1 et a

(N )N +1,j = 1 et donc a

(N )i,N +1a

(N )N +1,j = 1 et on voit que a

(N +1)i,j = 1.

3. Il suffit de vérifier que la matrice A ne contient que des 1 à la fin de l’algorithme.

Exercice 5 Soit G = (V, E ) un graphe simple. Le sommet v est appelé point d’articulation de G, siG\{v} contient plus de composantes connexes que G.

1. Trouver les points d’articulation du graphe suivant.

2. Montrer que le graphe K n n’a pas de point d’articulation.

On supposera le graphe G connexe. Un sous-ensemble V de V est appelé ensemble d’articulation si legraphe G privé de V et de toutes les arêtes incidentes à V n’est plus connexe.

3. Montrer que {b,c,e} est un ensemble d’articulation du graphe suivant

3



4. Montrer que tout graphe connexe non complet possède un ensemble d’articulation.

Soit G un graphe. On définit κ(G) comme étant le nombre minimal de sommet que l’on doit enlever à Gpour obtenir soit un graphe non connexe soit un graphe à un seul sommet.

5. Montrer que κ(G) = n − 1 si et seulement si G = K n.

6. Si κ(G) = 0, que peut-on dire sur G ?

De la même manière, une arête est appelée arête d’articulation si le graphe obtenue en enlevant cette arrête

n’est plus connexe. Un ensemble de coupure est un sous-ensemble E de E tel que le graphe G = (V, E )n’est pas connexe. On définit alors λ(G) comme étant le nombre minimal d’arêtes à enlever pour obtenirsoit un graphe non connexe soit un graphe à un seul sommet.

7. Calculer λ(G) pour les graphes suivants :

8. On suppose que G a n sommets et que G est simple. Montrer que λ(G) = n − 1 si et seulementG = K n.

9. Montrer que κ(G) ≤ λ(G).

10. Montrer que κ(G) ≤ λ(G) ≤ minv∈V deg(v).

Solution: 1. On trouve facilement que les points d’articulation sont b, c et e.

2. Si on supprime un sommet de K n on obtient K n−1, qui est connexe. Il s’ensuit que K n ne possède pasde point d’articulation.

3. C’est une simple vérification.

4. Supposons que G n’est pas complet et que G contient n sommets. Alors il existe un sommet v qui n’estpas connecté à tous les autres sommets. Par exemple, on a (v, w) /∈ E . Si on supprime tous les sommetsdifférents de u et w on obtient un graphe avec deux sommets et sans arêtes, donc non-connexe. Et on abien trouvé un ensemble d’articulation V − {v, w}.

5. Soit G un graphe a n sommets. Si G = K n alors κ(G) = n − 1. En effet si on supprime n’importe quelsous-ensemble de sommets de cardinal k ≤ n − 2, on obtient le graphe K n−k qui est connexe. De plusd’après 4., si G n’est pas complet il possède un ensemble d’articulation de cardinal n−2 et donc κ(G) ≤ n−2.

6. Si κ(G) = 0 alors G n’est pas connexe.

7. On vérifie facilement que λ(G1) = 1 et λ(G2) = 2.

8. Montrons que λ(K n) = n − 1. Soient a, b deux sommets de K n. Notons a = v0, v1, . . . , vn = b lessommets de K n. Alors il existe n − 1 chemins disjoints n’ayant aucune arêtes en commun) allant de a versb : le chemin (v0, vn) et tous les chemins de la forme (v0, vi, vn) pour 1 ≤ i ≤ n − 1. Ainsi, pour que a et bne soit plus joignable par un chemin il faut supprimer au moins n−1 arêtes. Ceci montre que λ(K n) = n−1.

Si G satisfait λ(G) = n − 1. Alors G est nécessairement complet, en effet si G possède un sommet dedegré inférieur ou égale à n − 2 alors l’ensemble des arêtes adjacentes à v serait un ensemble de coupurede cardinal n − 2. On en déduit que G est complet puisque G est simple.

9. Soit G = (V, E ) avec |V | = n. On sait que κ(G) ≤ n − 1. Soit C un ensemble de coupure minimale.Si on supprime C on obtient un graphe non connexe, en particulier il existe un sous-ensemble non-vide S de V qui n’est plus connecté à son complémentaire S = V − S . Si (x, y) ∈ E pour tout (x, y) ∈ S × S

alors C ≥ |S | · |S

| et comme |S |, |S

| ≥ 1 et |S | + |S

| = n on a |C | ≥ n − 1. Supposons donc qu’il existe(x, y) ∈ S × S tel que (x, y) /∈ E . On consière alors l’ensemble T défini par

T := (N (x) ∩ S ) ∪ {u ∈ S − {x} | ∃(u, w) ∈ E avec w ∈ S }.

4



On voit tout d’abord que y /∈ T puisque y /∈ N (x) et y /∈ S . Ensuite, x et y sont connectés dans G mais pasincident, ainsi il existe une chaîne C S (respectivement de C S ) de S (respectivement de S ) et v ∈ S, w ∈ S

tel que

x C S−→ v

[v,w]−→ w

C S

−→ y

Et donc T est un ensemble d’articulation de G puisque x et y ne peuvent pas être connectés dans le grapheinduit par V \T . Finalement, pour que C déconnecte S et S il faut enlever au moins |T | arêtes. En effet

chaque sommet de T correspond à une arête de S vers S

. On a donc |T | ≤ |C

| d’ou le résultat.

10. C’est clair : si on enlève toutes les arêtes incidentes à v , et il en y a d(v), on déconnecte le graphe.

Exercice 6 Le but de cet exercice est de prouver le Théorème suivant :

Théorème de Ore. Tout graphe simple G = (V, E ) ayant n ≥ 3 sommets et tel que le deg(u)+deg(v) ≥ npour toute paire de sommets non adjacents possède un cycle hamiltonien.

1. Montrer que si G ne possède pas de cycle hamiltonien alors il existe un graphe H avec les mêmessommets que G tel que si on ajoute une arête à H alors H a un cycle hamiltonien.

2. Montrer que H possède un chaîne hamiltonienne.

3. Soient v1, . . . , vn les sommets de la chaîne hamiltonienne ci-dessus. Montrer qu’il existe 1 < i < n tel

que (v1, vi) ∈ E et (vi−1, vn) ∈ E .4. En déduire que H possède un cycle hamiltonien dans G. Conclure.

Solution: 1. On ajoute une arête à G de telle manière que le graphe G1 obtenu soit simple et ne possèdepas de circuit hamiltonien. Si ce n’est pas possible alors G a la propriété souhaitée. Sinon on ajoute unearête à G1 de telle manière que le graphe G2 obtenu soit simple et ne possède pas de circuit hamiltonien. Sice n’est pas possible alors G1 a la propriété souhaitée. Sinon on continue. . . Le processus doit s’arrêter (onarrive au bout d’un moment à K n qui est hamiltonien !) et le dernier graphe obtenu a la propriété souhaitée.

2. Soit [x, y] une arête que l’on peut ajouter à H de telle manière que le nouveau graphe H soit simple. Pardéfinition de H , H est hamiltonien, il existe donc un cycle hamiltonien de la forme (x = v1, . . . , vn = y, x).L’arête [x, y] n’est pas une arête de H mais toutes les autres le sont, ainsi (v1, . . . , vn) est un chemin ha-

miltonien.

3. On procède comme dans la preuve du théorème de Dirac. On sait que deg(v1) + deg(vn) ≥ n et doncv1 et vn ont, à eux deux, au moins n voisins dans {v2, . . . , vn−1} (v1 et vn ne sont pas voisins dans H etdonc pas dans G). Soit

I := {i | (v1, vi) ∈ E } et J := { j | (vj−1, vn) ∈ E }.

Montrons que I et J ne sont pas disjoints. Si I ∩ J = ∅ alors

|I ∪ J | = |I | + |J | = |N (v1)| + |N (vn)| ≥ n

par hypothèse. Mais I ∪ J ⊂ {2, . . . , n} et donc |I ∪ J | ≤ n − 1. C’est une contradiction, l’intersection de

I et J est non vide. Soit i ∈ I ∩ J . On a donci ∈ I =⇒ [v1, vi] ∈ E et i ∈ J =⇒ [vi−1, vn] ∈ E

4. On a, en utilisant 3, le cycle suivant :

v1, . . . , vi−1, vn, . . . , vi, v1

qui est bien hamiltonien. Ceci contredit le fait que H n’est pas hamiltonien, ainsi notre hypothèse dedépart, le fait que G n’était pas hamiltonien, est fausse et G doit être hamiltonien.

5

Documents

Td1-solutions theorie du graphe.pdf