Cours de Recherche Opérationnelle

Programmation Linéaire & Théorie des Graphes

Cours développé et enrichi  Licence 1

Sciences Économiques et de Gestion

Ce cours couvre
Partie I Programmation Linéaire (PL)
 Dénitions, modélisation et hypothèses
 Problème de transport
 Résolution graphique

Partie II Théorie des Graphes

 Graphes non orientés, connexité, bipartis
 Graphes planaires et formule d'Euler
 Nombre cyclomatique et cycles eulériens
 Coloriage des graphes

Partie III Exercices d'application corrigés

Université de Carthage  Faculté des Sciences Économiques et de Gestion

de Nabeul
20242025
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Contents

Partie I  Programmation Linéaire 2

1 Introduction à la Programmation Linéaire 2
1.1 Qu'est-ce que la Programmation Linéaire ? . . . . . . . . . . . . . . . . . . 2
1.2 Les composantes d'un PL . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Solutions admissibles et solution optimale . . . . . . . . . . . . . . . . . . 3

2 Modélisation de Problèmes en PL 4
2.1 Exemple 1 : Problème de Production (Fabrication de Peintures) . . . . . . 4
2.1.1 Étape 1 : Identier les variables de décision . . . . . . . . . . . . . 4
2.1.2 Étape 2 : Formuler la fonction objectif . . . . . . . . . . . . . . . . 5
2.1.3 Étape 3 : Écrire les contraintes . . . . . . . . . . . . . . . . . . . . 5
2.1.4 Le Programme Linéaire complet . . . . . . . . . . . . . . . . . . . . 5
2.2 Exemple 2 : Problème de Régime Alimentaire . . . . . . . . . . . . . . . . 6

3 Hypothèses Restrictives de la PL 6
4 Modélisation d'un Problème de Transport 7
5 Résolution Graphique d'un Programme Linéaire 8
5.1 Principe de la méthode graphique . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 Le Théorème fondamental de la PL . . . . . . . . . . . . . . . . . . . . . . 9
5.3 Exemple prototype : Problème des Ateliers . . . . . . . . . . . . . . . . . . 9
5.3.1 Formulation du PL . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.3.2 Région réalisable et sommets . . . . . . . . . . . . . . . . . . . . . . 10
5.3.3 Calcul des sommets non évidents . . . . . . . . . . . . . . . . . . . 10
5.3.4 Évaluation de la FO aux sommets . . . . . . . . . . . . . . . . . . . 10

Partie II  Théorie des Graphes 12

6 Introduction à la Théorie des Graphes 12
6.1 Aperçu historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.2 Vocabulaire de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

7 Graphes Non Orientés (GNO) 13

7.1 Dénitions fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
7.2 Le Lemme des Poignées de Mains . . . . . . . . . . . . . . . . . . . . . . . 14
7.3 Connexité d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.4 Graphes Bipartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

8 Graphes Planaires 16
8.1 Dénition et intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8.2 Formule d'Euler pour les graphes planaires . . . . . . . . . . . . . . . . . . 17
8.3 Le graphe K3,3 n'est pas planaire . . . . . . . . . . . . . . . . . . . . . . . 17

9 Nombre Cyclomatique et Théorème d'Euler 17

9.1 Nombre cyclomatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.2 Cycles et circuits Eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

10 Coloriage des Graphes 19

10.1 Ensembles stables (indépendants) . . . . . . . . . . . . . . . . . . . . . . . 19
10.2 Coloriage propre et nombre chromatique . . . . . . . . . . . . . . . . . . . 20
10.3 Algorithme de Welsh-Powell . . . . . . . . . . . . . . . . . . . . . . . . . . 20
10.4 Bornes du nombre chromatique . . . . . . . . . . . . . . . . . . . . . . . . 21
10.5 Application : Coloriage et Fréquences Radio . . . . . . . . . . . . . . . . . 22
10.6 Coloriage des Arêtes et Graphe Adjoint . . . . . . . . . . . . . . . . . . . . 22

Partie III  Exercices d'application 24

11 Exercices de Programmation Linéaire 24
12 Exercices de Théorie des Graphes 25
Récapitulatif des formules essentielles 29

2
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

PARTIE I

Programmation Linéaire

1. Introduction à la Programmation Linéaire

1.1. Qu'est-ce que la Programmation Linéaire ?

La Recherche Opérationnelle (RO) est la discipline qui utilise des outils mathéma-
tiques pour aider à prendre de meilleures décisions dans des situations où les ressources
sont limitées. On peut imaginer une usine qui veut produire le plus possible sans dépasser
ses stocks de matières premières, ou un transporteur qui cherche la route la moins coû-
teuse. La Programmation Linéaire (PL) est l'outil phare de la RO pour ce type de
problèmes.

Dénition  Programmation Linéaire (PL)

Un Programme Linéaire est un modèle mathématique dans lequel :
ˆ on cherche à optimiser (maximiser un prot ou minimiser un coût) une fonc-
tion objectif qui est une combinaison linéaire de variables ;

ˆ les contraintes (limitations du problème réel) sont des inégalités ou égalités

linéaires ;

ˆ les variables de décision (les quantités à déterminer) sont soumises à des

contraintes de non-négativité.

Remarque
Le mot linéaire est fondamental. Une expression est linéaire si chaque variable
apparaît seule, élevée à la puissance 1, et sans multiplication entre deux variables.

ˆ 3x 1 + 5x2 est linéaire. (✓)

ˆx 2
1 ou x1 · x2 ne sont pas linéaires. (×)
Pourquoi cette restriction ? Parce que les fonctions linéaires ont des propriétés
géométriques très agréables (elles forment des droites, des plans) qui permettent
de trouver la solution optimale ecacement.

Forme générale d'un Programme Linéaire

max (ou min) Z = c1 x 1 + c2 x 2 + · · · + cn x n
| {z }
sens d'optimisation

3
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Sous les contraintes :



 a11 x1 + a12 x2 + · · · + a1n xn ≤ b1

a21 x1 + a22 x2 + · · · + a2n xn ≤ b2



.
.
.

am1 x1 + am2 x2 + · · · + amn xn ≤ bm





x1 , x2 , . . . , xn ≥ 0


où les cj sont les coecients de la fonction objectif, les aij sont les coecients des
contraintes, et les bi sont les membres droits (les limites disponibles).

1.2. Les composantes d'un PL

Avant toute modélisation, on identie trois éléments essentiels :

1. Les variables de décision : Ce sont les quantités inconnues sur lesquelles on

a le contrôle. Elles représentent ce qu'on cherche à déterminer. On les note
x1 , x2 , . . . , xn .
Exemple : combien de tonnes de produit A et de produit B faut-il fabriquer ?
2. La fonction objectif (FO) : C'est la grandeur à optimiser, exprimée comme une
combinaison linéaire des variables.
Exemple : maximiser le prot total Z = 5x1 + 4x2 .
3. Les contraintes : Ce sont les limitations imposées par la réalité (ressources disponibles,
capacités, demandes, etc.).
Exemple : on ne peut pas utiliser plus de 24 tonnes de matière première M1.

1.3. Solutions admissibles et solution optimale

Dénition  Solution admissible
Une solution admissible (ou réalisable ) est un vecteur de valeurs (x1 , x2 , . . . , xn )
qui satisfait toutes les contraintes du problème, y compris les contraintes de non-
négativité.
L'ensemble de toutes les solutions admissibles forme la région réalisable (ou do-
maine admissible ).

Dénition  Solution optimale

Une solution optimale est une solution admissible qui donne la meilleure valeur
possible à la fonction objectif (la valeur maximale pour un problème de maximisation,
la valeur minimale pour un problème de minimisation).

Exemple  Comparaison de solutions admissibles

Considérons la région réalisable {(x1 , x2 ) : x1 ≥ 0, x2 ≥ 0, x1 +x2 ≤ 5} et la fonction
objectif max Z = 3x1 + 2x2 .

4
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Point x1 x2 Z = 3x1 + 2x2

(1, 2) 1 2 3+4=7
(3, 2) 9 + 4 = 13

3 2
(5, 0) 5 0 15 + 0 = 15 optimal

Les trois points sont admissibles (ils respectent toutes les contraintes), mais le point
(5, 0) est optimal car il maximise Z.

2. Modélisation de Problèmes en PL

La modélisation est l'art de traduire un problème réel en langage mathématique.

C'est souvent l'étape la plus délicate. La démarche se fait toujours en trois étapes :
variables → fonction objectif → contraintes.

2.1. Exemple 1 : Problème de Production (Fabrication de Pein-

tures)
Énoncé
Une société produit de la peinture d' intérieur et de la peinture d' extérieur à
partir de deux matières premières M1 et M2.

Extérieure Intérieure Qté dispo. (t/jour)

M1 6 4 24
M2 1 2 6

Prot (1000 Dt/t) 5 4

Contraintes supplémentaires :

ˆ La demande maximale en peinture intérieure est de 2 t/jour.

ˆ La production en peinture intérieure ne dépasse pas d'une tonne celle de

l'extérieure.

Maximiser le prot total.

2.1.1. Étape 1 : Identier les variables de décision

On se demande : Sur quoi décide-t-on ? Ici, on décide des quantités à produire.

x1 = quantité (t/jour) de peinture extérieure, x2 = quantité (t/jour) de peinture intérieure

5
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

2.1.2. Étape 2 : Formuler la fonction objectif

Chaque tonne d'extérieure rapporte 5 000 Dt et chaque tonne d'intérieure rapporte 4 000 Dt.
Le prot total journalier est :
max Z = 5x1 + 4x2

2.1.3. Étape 3 : Écrire les contraintes

Contrainte sur M1 : Pour x1 t d'extérieure, il faut 6x1 t de M1 ; pour x2 t d'intérieure,
il faut 4x2 t de M1. Le total ne peut pas dépasser 24 t :

6x1 + 4x2 ≤ 24

Contrainte sur M2 :
x1 + 2x2 ≤ 6
Demande maximale en intérieure :
x2 ≤ 2

Contrainte de liaison : La production intérieure ne dépasse pas d'une tonne celle
de l'extérieure signie x2 ≤ x1 + 1 , soit :

−x1 + x2 ≤ 1

Non-négativité (CNN) :
x1 ≥ 0, x2 ≥ 0

2.1.4. Le Programme Linéaire complet

max Z = 5x1 + 4x2



 6x1 + 4x2 ≤ 24 (contrainte M1)

x1 + 2x2 ≤ 6

(contrainte M2)


sous x2 ≤ 2 (demande max intérieure)

−x1 + x2 ≤ 1 (liaison)





x ≥ 0, x ≥ 0 (CNN)
1 2

Remarque
Les contraintes de non-négativité (CNN) sont systématiquement présentes en PL
classique car les quantités physiques (production, transport, stocks. . . ) ne peuvent
pas être négatives. Il ne faut jamais les oublier.

6
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

2.2. Exemple 2 : Problème de Régime Alimentaire

Énoncé
Une personne mélange du maïs et des fruits pour un repas de 400 g minimum.
Son régime exige au moins 30 unités de protéines et au moins 5 unités de bres.

Aliment Protéines (u/g) Fibres (u/g) Coût ($/kg)

Maïs 0,04 0,02 1,5

Fruit 0,60 0,06 4,5

Minimiser le coût du repas.

Variables : x1 = quantité de maïs (en g) ; x2 = quantité de fruit (en g).

Coût : Le coût est en $/kg, donc en $/g on divise par 1000 :
min Z = 0,0015 x1 + 0,0045 x2

min Z = 0,0015 x1 + 0,0045 x2



 x1 + x2 ≥ 400 (quantité totale)

0,04 x + 0,6 x ≥ 30 (protéines)
1 2
sous


 0,02 x1 + 0,06 x2 ≥ 5 (bres)
x1 ≥ 0, x2 ≥ 0

(CNN)

Remarque
Ce problème est de minimisation avec des contraintes de type ≥ (on doit au moins
satisfaire les besoins nutritionnels). C'est le contraire du problème de production
où les contraintes étaient de type ≤ (on ne peut pas utiliser plus que les ressources
disponibles).

3. Hypothèses Restrictives de la PL

La PL est un modèle puissant, mais il repose sur quatre hypothèses implicites. Il est
crucial de les comprendre pour savoir quand la PL est applicable.

Dénition  Hypothèse de Continuité

Les variables de décision xj peuvent prendre n'importe quelle valeur réelle, y
compris des valeurs non entières (fractions).

Pourquoi ? Cette hypothèse permet des calculs continus (dérivées, intersections de

droites, etc.). En pratique, elle est raisonnable quand les variables sont des quantités
continues comme des litres, des tonnes ou des heures.

7
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Limite : Si les variables doivent être entières (nombre de machines, nombre

d'employés. . . ), on utilise la Programmation en Nombres Entiers (PNE), plus
complexe.

Dénition  Hypothèse de Certitude

Tous les coecients (cj , aij , bi ) sont supposés être des constantes connues avec
précision.

Pourquoi ? Le modèle mathématique doit avoir des données xes pour être résolu.
Si les données sont incertaines (exemple : le prix du marché uctue), on utilise
l' analyse de sensibilité ou la programmation stochastique.

Dénition  Hypothèse de Proportionnalité

La contribution de chaque variable à la FO et aux contraintes est strictement pro-
portionnelle à sa valeur : doubler xj double sa contribution. Il n'y a pas d'économies
d'échelle ni de coûts xes.

Exemple : Si x1 = 3 rapporte Z = 15 (avec c1 = 5), alors x1 = 6 rapporte Z = 30.

Si la réalité présentait des remises pour grande quantité, la PL serait inadaptée.

Dénition  Hypothèse d'Additivité

La valeur totale de la FO est la somme des contributions individuelles de chaque
variable. Il n'y a pas d'interactions entre variables : Z = c1 x1 +c2 x2 +· · · , sans termes
croisés comme c12 x1 x2 .

Exemple : Si produire x1 = 2 et x2 = 3 rapporte exactement autant que produire

x1 = 2 seul plus produire x2 = 3 seul, l'additivité est vériée.

4. Modélisation d'un Problème de Transport

Dénition  Problème de Transport

Un problème de transport consiste à déterminer comment acheminer des marchan-
dises depuis m sources (dépôts, usines) vers n destinations (clients, marchés), de
manière à minimiser le coût total de transport, en respectant les capacités des sources
et les demandes des destinations.

Remarque
Le problème de transport est un cas particulier de PL avec une structure très régulière.
Les variables sont les quantités transportées de chaque source vers chaque desti-
nation. Si on a m sources et n destinations, il y a m×n variables.

8
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Énoncé
Une entreprise dispose de deux dépôts D1 (capacité 8 u.) et D2 (capacité 9 u.)
et de trois points de vente A (besoin 4), B (besoin 5), C (besoin 8). Les coûts de
transport unitaires (Dt/u.) sont :

A B C
D1 5 3 4
D2 6 7 2

Variables de décision : xij = quantité transportée du dépôt i vers le point de vente

j. On a 6 variables : xD1A , xD1B , xD1C , xD2A , xD2B , xD2C .
Fonction objectif :
min Z = 5xD1A + 3xD1B + 4xD1C + 6xD2A + 7xD2B + 2xD2C

Contraintes d'ore (chaque dépôt doit expédier tout son stock) :

xD1A + xD1B + xD1C = 8 (D1)

xD2A + xD2B + xD2C = 9 (D2)

Contraintes de demande (chaque point de vente doit être satisfait) :

xD1A + xD2A = 4, xD1B + xD2B = 5, xD1C + xD2C = 8

CNN : xij ≥ 0 pour tout i, j .

Dénition  Problème équilibré
Un problème de transport est dit
P P équilibré si l'ore totale est égale à la demande
totale : i si = j dj .

Ici : 8 + 9 = 17 = 4 + 5 + 8. Le problème est équilibré.

Si le problème n'est pas équilibré, on ajoute une source ctive (si demande > ore)
ou une destination ctive (si ore > demande) avec des coûts nuls pour équilibrer le
modèle.

5. Résolution Graphique d'un Programme Linéaire

5.1. Principe de la méthode graphique

Lorsqu'un PL ne comporte que deux variables de décision, on peut le résoudre géométrique-
ment. Cette méthode est très pédagogique et permet de visualiser la solution.

9
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Algorithme  Résolution graphique

1. Représenter le repère (x1 , x2 ) avec x1 ≥ 0 et x2 ≥ 0 (1er quadrant).

2. Pour chaque contrainte ax1 + bx2 ≤ c, tracer la droite frontière ax1 + bx2 = c.

3. Identier le demi-plan satisfaisant chaque contrainte (le côté qui contient

l'origine, en général).

4. La région réalisable est l'intersection de tous ces demi-plans.

5. Identier les sommets (points extrêmes) de la région réalisable en résolvant
les intersections deux à deux.

6. Évaluer la FO en chaque sommet. Le sommet optimal est la solution.

5.2. Le Théorème fondamental de la PL

Théorème  Théorème fondamental de la Programmation Linéaire
Si un programme linéaire admet une solution optimale, alors il en existe au moins
une qui se trouve en un sommet (point extrême) de la région réalisable.

Pourquoi ? Intuitivement, la fonction objectif est une droite (en 2D) qu'on déplace
dans la direction de l'optimisation. Cette droite touche la région réalisable en dernier
en un sommet (ou sur un côté entier, mais un sommet appartient toujours à ce côté).
Donc il sut de tester les sommets pour trouver l'optimum.

Remarque
Ce théorème est extraordinairement utile : au lieu d'explorer une innité de points
admissibles, il sut d'évaluer la FO en un nombre ni de sommets.

5.3. Exemple prototype : Problème des Ateliers

Énoncé
Une entreprise fabrique deux types de produits. Les temps de fabrication (heures)
et capacités sont :

Produit 1 Produit 2 Capacité (h/sem.)

Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18

Marge (Dt/u.) 3 5

Maximiser la marge totale.

10
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

5.3.1. Formulation du PL
x1 = quantité de Produit 1 ; x2 = quantité de Produit 2.

max Z = 3x1 + 5x2



 x1 ≤ 4 (Atelier 1)

2x ≤ 12
2 soit x2 ≤ 6 (Atelier 2)
sous


 3x1 + 2x2 ≤ 18 (Atelier 3)
x1 ≥ 0, x2 ≥ 0 (CNN)


5.3.2. Région réalisable et sommets

On trace chaque contrainte comme une droite, puis on identie le demi-plan admissible.

x2
x1 = 4
7

C(2, 6)
D(0, 6)6 x2 = 6

3 B(4, 3)
RR
2

x1
O(0, 0) 0 1 2 3 4
A(4,5 0) 6 3x1 + 2x2 = 18

5.3.3. Calcul des sommets non évidents

Sommet B = intersection de x1 = 4 et 3x1 + 2x2 = 18 :
3(4) + 2x2 = 18 =⇒ 12 + 2x2 = 18 =⇒ x2 = 3 ⇒ B = (4, 3)
Sommet C = intersection de 3x1 + 2x2 = 18 et x2 = 6 :
3x1 + 2(6) = 18 =⇒ 3x1 = 6 =⇒ x1 = 2 ⇒ C = (2, 6)

5.3.4. Évaluation de la FO aux sommets

Sommet x1 x2 Z = 3x1 + 5x2

O 0 0 0
A 4 0 12
B 4 3 27
C 2 6 36 ← MAXIMUM
D 0 6 30

11
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

À retenir
Solution optimale : x∗1 = 2, x∗2 = 6, avec Z ∗ = 36 Dt.
L'entreprise doit produire 2 unités du Produit 1 et 6 unités du Produit 2 pour
maximiser la marge hebdomadaire à 36 Dt.

12
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

PARTIE II

Théorie des Graphes

6. Introduction à la Théorie des Graphes

6.1. Aperçu historique

La théorie des graphes est née en 1736 grâce au mathématicien suisse Leonhard Euler.
Il s'est intéressé au célèbre problème des Sept Ponts de Königsberg : la ville était traversée
est-il possible de
par une rivière avec deux îles reliées par sept ponts. La question était :
se promener en traversant chaque pont exactement une fois et en revenant à son point de
départ ?
Euler a montré que non, en transformant le problème géographique en un problème
de structure abstraite  c'est la naissance des graphes.

p1
p3
B A C
p2
p4

p5 p7 p6

Graphe des ponts de Königsberg

Aujourd'hui, les graphes modélisent les réseaux informatiques, les routes, les réseaux
sociaux, les circuits électroniques, les emplois du temps, etc.

6.2. Vocabulaire de base

Dénition  Graphe
Un graphe G est déni par :
ˆ un ensemble ni V (ou X) de sommets (vertices en anglais) ;

ˆ un ensemble E (ou U) d' arêtes (edges ), chaque arête étant une paire de som-
mets {u, v}.

On note G = (V, E). L' ordre du graphe est |V | (nombre de sommets) et sa taille
est |E| (nombre d'arêtes).

Exemple  Graphe simple

Soit G = (V, E) avec V = {A, B, C, D} et E =
{(A, B), (A, C), (B, C), (B, D), (C, D)}.

13
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

A B

C D

Ce graphe est d'ordre 4 (|V | = 4) et de taille 5 (|E| = 5).

Dénition  Types particuliers de graphes

ˆ Graphe simple : pas de boucle ni d'arête multiple entre deux mêmes sommets.

ˆ Boucle : arête d'un sommet vers lui-même. Elle compte double dans le degré.

ˆ Multigraphe : graphe autorisant plusieurs arêtes entre les mêmes sommets.

ˆ Graphe complet K n : graphe simple où chaque sommet est relié à tous les
n(n − 1)
autres. Il possède arêtes.
2
ˆ Graphe planaire : graphe qui peut être dessiné dans le plan sans croisement
d'arêtes (hors sommets).

Exemple  Graphes complets

K3 (triangle) K4

n(n−1)
K3 : 3 sommets, 3 arêtes. K4 : 4 sommets, 6 arêtes. Kn : n sommets,
2
arêtes,
chaque sommet de degré n − 1.

7. Graphes Non Orientés (GNO)

14
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

7.1. Dénitions fondamentales

Dénition  Degré d'un sommet
Le degré d'un sommet v , noté d(v), est le nombre d'arêtes incidentes à v (c'est-à-dire
qui touchent v ).
Attention : une boucle en v (arête de v vers v) compte pour 2 dans le degré de v .

Exemple  Calcul des degrés

1 2

3 4

d(1) = 2 (relié à 2 et 3), d(2) = 3 (relié à 1, 3, 4), d(3) = 3 (relié à 1, 2, 4),

d(4) = 2 (relié à 2 et 3).
Somme des degrés : 2 + 3 + 3 + 2 = 10 = 2 × 5 = 2|E|. ✓

7.2. Le Lemme des Poignées de Mains

C'est l'un des résultats les plus importants et les plus utilisés de la théorie des graphes.

Lemme  Lemme des Poignées de Mains (Handshaking Lemma)

Pour tout graphe G(V, E) :
X
d(v) = 2|E|
v∈V

La somme des degrés de tous les sommets est égale à deux fois le nombre d'arêtes.

Pourquoi ? Parce que chaque arête {u, v} contribue exactement +1 au degré de u

et +1 au degré de v. Donc chaque arête est comptée exactement deux fois dans la
somme des degrés. L'image des poignées de mains : si n personnes se serrent la
main, le nombre total de mains tendues est 2× (nombre de poignées).

Propriété  Corollaire fondamental

Dans tout graphe, le nombre de sommets de degré impair est toujours pair.

Démonstration :
P
On a v∈V d(v) = 2|E|, qui est pair. On décompose la somme
en deux parties :
X X
d(v) + d(v) = 2|E| (pair)
d(v) pair d(v) impair
| {z } | {z }
somme paire ?

La première somme est paire (somme de nombres pairs). Donc la deuxième somme
est aussi paire. Or une somme de nombres impairs n'est paire que si le nombre de

15
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

termes est pair. Donc il y a un nombre pair de sommets de degré impair. □

Exemple  Application : groupe d'amis

Dans un groupe de 20 enfants, est-il possible que 7 d'entre eux aient exactement 3
amis, 9 en aient 4, et les 4 autres en aient 5 ?
Test :
P
d(v) = 7 × 3 + 9 × 4 + 4 × 5 = 21 + 36 + 20 = 77.
Or 77 est impair. Par le Lemme des Poignées de Mains, cette somme doit être paire
(égale à 2|E|). Contradiction ! Une telle conguration est impossible.

Exemple  Test d'impossibilité

Peut-il exister un graphe à 3 sommets où tous les sommets ont degré 3 ?
Impossible.
P
d(v) = 3 × 3 = 9 (impair). Or 2|E| est toujours pair.

7.3. Connexité d'un graphe

Dénition  Graphe connexe
Un graphe G(V, E) est dit connexe si, pour tout couple de sommets (u, v), il existe
un chemin (suite d'arêtes consécutives) reliant u à v .
En d'autres termes : depuis n'importe quel sommet, on peut atteindre n'importe quel
autre sommet en suivant les arêtes.
Si un graphe n'est pas connexe, il se décompose en plusieurs composantes connexes
(sous-graphes connexes maximaux).

Exemple  Connexe vs non connexe

Connexe Non connexe

1 2 1 2 3 4

C1 C2
3

7.4. Graphes Bipartis

Dénition  Graphe biparti
Un graphe G(V, E) est dit biparti si ses sommets peuvent être divisés en deux
ensembles disjoints X et Y tels que toute arête relie un sommet de X à un sommet
de Y. Il n'existe aucune arête entre deux sommets du même ensemble.
On note G = (X ∪ Y, E).

16
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Dénition  Graphe biparti complet Km,n

Le graphe biparti complet Km,n est le graphe biparti où chaque sommet de X
(|X| = m) est relié à chaque sommet de Y (|Y | = n). Il possède m×n arêtes.

Exemple  Graphe biparti  Aectation

Un graphe biparti est naturel pour modéliser des problèmes d'aectation : X =
ensemble d'employés, Y = ensemble de tâches. Une arête (i, j) signie que l'employé
i peut eectuer la tâche j .

T1
E1

E2 T2

E3
T3
Employés Tâches

8. Graphes Planaires

8.1. Dénition et intuition

Dénition  Graphe planaire
Un graphe G est planaire si on peut le dessiner dans le plan de sorte que ses arêtes
ne se croisent pas (sauf en leurs extrémités, i.e., aux sommets).
Quand un graphe planaire est dessiné dans le plan, les arêtes délimitent des régions
(aussi appelées faces ). On compte toujours une région non bornée (la face extérieure,
qui s'étend à l'inni).

Exemple  Un graphe planaire

Le graphe K4 est planaire. On peut le dessiner sans croisement :

F3
F4
4
F1 F2
1 2

|V | = 4, |E| = 6, R = 4 faces (3 triangles intérieurs + 1 extérieure). Vérication :

4 − 6 + 4 = 2. ✓

17
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

8.2. Formule d'Euler pour les graphes planaires

Théorème  Formule d'Euler
Soit G un graphe planaire connexe avec |V | sommets, |E| arêtes et R régions (faces,
y compris la face extérieure). Alors :

|V | − |E| + R = 2

Intuition : Cette formule est remarquable car elle est vraie pour tout graphe planaire
connexe, quelle que soit sa structure. C'est une propriété topologique fondamentale.
Exemple rapide : Un cube : |V | = 8, |E| = 12, R = 6. Vérions : 8 − 12 + 6 = 2.
✓

8.3. Le graphe K3,3 n'est pas planaire

Théorème  Non-planarité de K3,3
Le graphe biparti complet K3,3 (3 maisons reliées à 3 usines : eau, gaz, électricité)
n'est pas planaire.

Démonstration par l'absurde :

On a |V | = 6 et|E| = 3 × 3 = 9. Supposons par l'absurde que K3,3 est planaire.
Par la formule d'Euler : R = 2 − |V | + |E| = 2 − 6 + 9 = 5 régions.
K3,3 est biparti, donc il ne contient aucun cycle de longueur impaire (triangle, pen-
tagone. . . ). Le plus court cycle possible a longueur 4. Donc chaque région est délim-
itée par au moins 4 arêtes :

X
d(r) ≥ 4R = 4 × 5 = 20
r∈régions

Mais chaque arête borde au plus 2 régions, donc :

X
d(r) ≤ 2|E| = 2 × 9 = 18
r

On obtient 18 ≥ 20 : contradiction ! Donc K3,3 n'est pas planaire. □

9. Nombre Cyclomatique et Théorème d'Euler

18
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

9.1. Nombre cyclomatique

Dénition  Nombre cyclomatique
Soit G(V, E) un graphe avec n = |V | sommets, m = |E| arêtes et p composantes
connexes. Le nombre cyclomatique (ou dimension du cycle ) est :

γ(G) = m − n + p

Il représente le nombre minimal de cycles indépendants qu'on peut trouver dans

le graphe (c'est-à-dire le nombre de cycles qu'on ne peut pas obtenir par combinaison
d'autres cycles).

Remarque
Interprétation intuitive :

ˆ G Si est connexe (p = 1) : γ(G) = m − n + 1.

ˆ γ(G) = 0 : le graphe est un arbre (pas de cycle du tout).

ˆ γ(G) = 1 : le graphe contient exactement un cycle indépendant.

ˆ γ(G) > 0 : le graphe contient des cycles.

Exemple  Calcul du nombre cyclomatique

Soit un graphe connexe avec 5 sommets et 7 arêtes :

γ =7−5+1=3 cycles indépendants

9.2. Cycles et circuits Eulériens

Dénition  Chemin et cycle Eulérien
ˆ Un chemin eulérien est un chemin qui passe par chaque arête exactement une
fois.
ˆ Un cycle eulérien est un chemin eulérien fermé (qui revient à son point de
départ).

ˆ Un graphe admettant un cycle eulérien est dit eulérien.

Théorème  Théorème d'Euler (condition nécessaire et susante)

Un graphe connexe eulérien (admet
G est un cycle eulérien) si et seulement si
tous ses sommets ont un degré pair.

Intuition : Lorsqu'on parcourt un cycle eulérien, chaque fois qu'on entre dans un
sommet par une arête, on doit en repartir par une autre arête diérente. Les arêtes

19
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

incidentes à chaque sommet s'apparient donc deux à deux : il en faut un nombre

pair. Si un sommet a un degré impair, on resterait bloqué à un moment.
Corollaire : chemin eulérien (non fermé) si et seule-
Un graphe connexe admet un
ment s'il possède exactement 0 ou 2 sommets de degré impair. Si exactement
2 sommets ont un degré impair, le chemin eulérien va de l'un à l'autre.

Exemple  Les ponts de Königsberg revisités

Dans le graphe des ponts, les degrés sont : d(A) = 3, d(B) = 3, d(C) = 3, d(D) = 3.
Il y a 4 sommets de degré impair. Donc ni cycle eulérien ni chemin eulérien n'est
possible (il faudrait exactement 0 ou 2 sommets impairs). Impossible de traverser
tous les ponts exactement une fois.

Exemple  Dominos sans doubles

Considérons des dominos avec faces numérotées de 1 à 5 (sans doubles). On modélise
: sommets = valeurs {1, 2, 3, 4, 5}, arête (i, j) = domino(i, j).
Chaque sommet i est relié à chacun des 4 autres sommets ⇒ d(i) = 4 (pair). Le
graphe est connexe. Donc il est eulérien : on peut former une boucle fermée
avec les dominos.
Avec des faces de 1 à n (sans doubles) : d(i) = n − 1. Si n est impair, n − 1 est pair
⇒ boucle possible. Si n est pair, n − 1 est impair ⇒ boucle impossible.

10. Coloriage des Graphes

Le coloriage des graphes répond à la question : comment attribuer des couleurs aux
sommets (ou arêtes) d'un graphe de sorte que deux éléments voisins aient toujours des
couleurs diérentes, en utilisant le moins de couleurs possible ?

10.1. Ensembles stables (indépendants)

Dénition  Ensemble stable
Un ensemble stable (ou indépendant ) S ⊆ V est un ensemble de sommets tels que
deux quelconques d'entre eux ne sont pas adjacents (aucune arête ne les relie).
Le cardinal maximum des ensembles stables est noté α(G) (nombre de stabilité).

Exemple  Stable dans un graphe

Dans un graphe avec arêtes {(1, 2), (2, 3), (3, 4), (1, 3)} :

ˆ S = {2, 4} : stable (✓) car 2 et 4 ne sont pas adjacents.

ˆ S = {1, 2, 3} : pas stable (×) car 1 et 2 sont adjacents.

20
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

10.2. Coloriage propre et nombre chromatique

Dénition  Coloriage propre
Un coloriage propre de G consiste à attribuer à chaque sommet une couleur (un
entier) de sorte que deux sommets adjacents reçoivent des couleurs diérentes.
Un coloriage en k couleurs correspond à une partition des sommets en k ensembles
stables S1 , S2 , . . . , Sk (deux à deux disjoints).

Dénition  Nombre chromatique

Le nombre chromatique χ(G) (aussi noté δ(G)) est le nombre minimum de
couleurs nécessaires pour réaliser un coloriage propre de G.

Exemple  Nombre chromatique simple

1 2

3 4

χ(G) = 3 (rouge, bleu, vert). Il est impossible de colorier proprement avec 2 couleurs
car le graphe contient un triangle (1, 2, 3)  les 3 doivent avoir des couleurs diérentes.

10.3. Algorithme de Welsh-Powell

L'algorithme de Welsh-Powell est une heuristique (méthode approchée ecace en pra-
tique) pour colorier un graphe. Il ne garantit pas toujours le nombre chromatique exact,
mais donne une bonne approximation.

Algorithme  Welsh-Powell
1. Trier les sommets par ordre décroissant de leur degré.
2. Parcourir la liste et, pour chaque sommet non encore colorié :

ˆ lui attribuer la première couleur non encore utilisée par ses voisins déjà
coloriés ;

ˆ parcourir la suite de la liste et attribuer la même couleur à tout sommet

non encore colorié et non adjacent à un sommet ayant déjà cette couleur.

3. Passer à la couleur suivante jusqu'à ce que tous les sommets soient coloriés.

Exemple  Application de Welsh-Powell

Soit un graphe G à 7 sommets avec : d(V1 ) = 5, d(V3 ) = 4, d(V5 ) = 4, d(V7 ) = 4,
d(V4 ) = 3, d(V2 ) = 2, d(V6 ) = 2.
Étape 1  Tri décroissant :

21
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Sommet V1 V3 V5 V7 V4 V2 V6
Degré 5 4 4 4 3 2 2

Étape 2  Attribution des couleurs :

On suppose que les adjacences sont : V1 adj V3 , V5 , V7 , V4 , V2 ; V3 adj V1 , V5 ; V5 adj
V1 , V3 , V2 ; V7 adj V1 , V6 ; V4 adj V1 ; V2 adj V1 , V5 ; V6 adj V7 .

ˆV 1 (pas de voisin colorié) → Couleur C1

ˆV 3 (voisin V1 a C1) → Couleur C2. Est-ce que V4 , V6 sont non adjacents à V3

et peuvent avoir C2 ?
V4 : non adjacent à V3 , mais adjacent à V1 (C1) → V4 peut prendre C2. V6 :
non adjacent à V3 , non adjacent à V4 → V6 peut prendre C2.

ˆV 5 (voisins V1 C1 et V3 C2) → Couleur C3. V7 : non adjacent à V5 , non

adjacent à V6 (C2. . . wait) → V7 adjacent à V6 (C2) et à V1 (C1) → prend C3.

ˆV 2 : adjacent à V1 C1, V5 C3 → Couleur C2 (si non adjacent à V4 C2 et V6 C2

 supposons que oui).

Résultat indicatif :

Sommet V1 V3 V5 V7 V4 V2 V6
Couleur C1 C2 C3 C3 C2 C2 C2

χ(G) ≤ 3 (W-P peut ne pas être optimal).

10.4. Bornes du nombre chromatique

Propriété  Encadrement de χ(G)
SoitG un graphe avec n sommets, degré maximum ∆ = maxv d(v), clique maximum
ω(G) et nombre de stabilité α(G).

ω(G) ≤ χ(G) ≤ ∆ + 1

ˆ Minoration : χ(G) ≥ ω(G) . Tous les sommets d'une clique sont mutuellement
adjacents, donc ils doivent tous avoir des couleurs diérentes. On a besoin d'au
moins ω(G) couleurs.

ˆ Majoration : χ(G) ≤ ∆ + 1 . En coloriant gourmand (on donne à chaque

sommet la plus petite couleur non utilisée par ses voisins), on n'a jamais besoin
de plus de ∆+1 couleurs, car chaque sommet a au plus ∆ voisins.

ˆ Autre minoration : χ(G) ≥ α(G)

n
, car chaque couleur forme un stable de

taille au plus α(G).

ˆ Autre majoration : χ(G) ≤ n + 1 − α(G) .

22
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Exemple  Application des bornes

Graphe à n=6 sommets, ∆ = 3, ω = 2, α = 3.

2 ≤ χ(G) ≤ 4

Le nombre chromatique est 2, 3 ou 4. W-P permettra de trancher.

10.5. Application : Coloriage et Fréquences Radio

Exemple  Attribution de fréquences
Deux émetteurs radio se brouillent s'ils sont dans la même zone de couverture. On
veut attribuer des fréquences de sorte qu'aucune paire d'émetteurs qui se brouillent
n'ait la même fréquence, en minimisant le nombre de fréquences utilisées.
Modélisation : chaque émetteur = un sommet. Une arête entre deux émetteurs
signie qu'ils se brouillent. Colorier le graphe = attribuer des fréquences. χ(G) =
nombre minimal de fréquences nécessaires.

A B

D C
E

Bleu = F1, Rouge = F2, Vert = F3

χ(G) = 3 : trois fréquences susent.

10.6. Coloriage des Arêtes et Graphe Adjoint

Dénition  Coloriage propre des arêtes
Un coloriage propre des arêtes de G consiste à attribuer une couleur à chaque
adjacentes (partageant un sommet commun) reçoivent
arête de sorte que deux arêtes
des couleurs diérentes.
Le nombre chromatique d'arête χ′ (G) est le nombre minimal de couleurs pour
réaliser un tel coloriage.
′
On a toujours : χ (G) ≥ ∆(G).

Dénition  Graphe adjoint (Line Graph)

Soit G = (V, E). Son graphe adjoint G′ = (V ′ , E ′ ) est déni par :
ˆV ′
=E : les sommets de G′ sont les arêtes de G.

23
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

ˆ (e , e ) ∈ E
1 2
′
si et seulement si les arêtes e1 et e2 partagent un sommet dans G.

Lien fondamental : colorier les arêtes de G est équivalent à colorier les sommets
′ ′
de G. Donc χ (G) = χ(G′ ).

Exemple  Construction du graphe adjoint

Soit G avec arêtes a1 = (1, 2), a2 = (1, 3), a3 = (2, 3), a4 = (2, 4), a5 = (3, 4).
Dans G′ : a1 et a2 partagent le sommet 1 → adjacents ; a1 et a3 partagent 2 →
adjacents ; etc.

a1
a1
1 2

a2 a3 a4 a2 a3

3 4
a5
a4 a5
G G (graphe adjoint)
′

24
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

PARTIE III

Exercices d'Application

11. Exercices de Programmation Linéaire

Exercice  Fabrication d'ordinateurs

Une entreprise fabrique deux types d'ordinateurs : l'IM4 et l'IM5. L'IM4 comporte
2 barrettes mémoire et l'IM5 en comporte 6. Le marché impose une limite de 10 000
processeurs et 48 000 barrettes par trimestre. L'assemblage de l'IM4 prend 3 minutes
et celui de l'IM5 prend 1 minute ; la capacité d'assemblage est de 24 000 minutes par
trimestre. Le prot est de 400 Dt sur l'IM4 et 800 Dt sur l'IM5.
Formuler et résoudre graphiquement ce PL.

Solution :
Variables : x1 = nombre d'IM4 ; x2 = nombre d'IM5.
Programme Linéaire :
max Z = 400x1 + 800x2


x1 + x2 ≤ 10 000 (processeurs)

2x + 6x ≤ 48 000 (barrettes)
1 2


3x1 + x2 ≤ 24 000 (assemblage)
x1 , x2 ≥ 0


Sommets de la région réalisable (intersections des droites actives) :

Sommet x1 x2 Z = 400x1 + 800x2

O = (0, 0) 0 0 0
Intersection processeurs/assemblage voir calcul

Méthode : On résout les intersections deux à deux. Par exemple, x1 +x2 = 10000 et
3x1 + x2 = 24000 donnent 2x1 = 14000 ⇒ x1 = 7000, x2 = 3000, et Z = 2 800 000 +
2 400 000 = 5 200 000.
On évalue Z en tous les sommets et on retient le maximum.

Exercice  Alimentation du bétail

On cherche la composition à coût minimal d'un aliment pour bétail en mélangeant
orge (x1 ), arachides (x2 ) et sésame (x3 ). L'aliment doit comporter au moins 22% de
protéines et 3,6% de graisses.

25
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Orge Arachides Sésame Requis

Protéines (%) 12 52 42 ≥ 22
Graisses (%) 2 2 10 ≥ 3,6
Coût (Dt/t) 25 41 39 

Variables : xj = fraction de tonne du produit j dans une tonne d'aliment.

min Z = 25x1 + 41x2 + 39x3



 x1 + x2 + x3 = 1 (mélange total)

12x + 52x + 42x ≥ 22 (protéines)
1 2 3
2x1 + 2x2 + 10x3 ≥ 3,6
 (graisses)

x1 , x2 , x3 ≥ 0


En substituant x3 = 1 − x1 − x2 , on obtient un PL à deux variables résolvable

graphiquement.
Après substitution (contrainte de protéines) :
12x1 + 52x2 + 42(1 − x1 − x2 ) ≥ 22 =⇒ −30x1 + 10x2 ≥ −20 =⇒ 3x1 − x2 ≤ 2

12. Exercices de Théorie des Graphes

Exercice  Segments sur une feuille

Comment tracer 5 segments sur une feuille de telle manière que chaque segment en
coupe exactement 3 autres ?

Solution  Utilisation du Lemme des Poignées de Mains :

Modélisons par un graphe G : chaque sommet est un segment, et on trace une arête
entre deux sommets si les segments correspondants se croisent.
L'hypothèse chaque segment coupe exactement 3 autres signie que tous les som-
mets ont degré 3 : d(v) = 3 pour tout v .
On aurait alors : X
d(v) = 5 × 3 = 15 (impair)
v∈V

pair.
P
Or, par le Lemme des Poignées de Mains, d(v) = 2|E|, qui est toujours
Contradiction !
Conclusion : Une telle conguration est impossible.

Exercice  Graphe k-régulier

Quel est le nombre d'arêtes d'un graphe k -régulier d'ordre n (chaque sommet a ex-
actement le degré k) ? Quelles conditions doit-on avoir sur n et k ?

26
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Solution : P
Si chaque sommet a degré k, alors d(v) = nk .
Par le Lemme des Poignées de Mains :

nk
nk = 2|E| =⇒ |E| =
2
Conditions d'existence :
ˆ nk
2
doit être un entier ⇒ nk doit être pair, donc n ou k est pair.

ˆ k ≤ n−1 (dans un graphe simple, un sommet ne peut être adjacent à lui-même).

Exercice  Conseil Municipal

Le conseil municipal comprend 7 commissions avec les règles :

ˆ Règle 1 : tout conseiller fait partie d'exactement 2 commissions.

ˆ Règle 2 : deux commissions quelconques ont exactement un conseiller en com-

mun.

Combien y a-t-il de membres dans le conseil municipal ?

Solution :
Construisons un graphe G : les sommets sont les 7 commissions. On relie deux
commissions par une arête s'il existe un conseiller leur appartenant toutes deux.
Puisque toute paire de commissions partage exactement un conseiller, toute paire
de sommets est reliée par une arête : le graphe est le graphe complet K7 .
7×6
Nombre d'arêtes de K7 : = 21.
2
Chaque arête représente un conseiller (le conseiller commun aux deux commissions
qu'elle relie). Par la Règle 1, chaque conseiller appartient à exactement 2 commis-
sions, donc correspond à exactement une arête.

Il y a 21 membres dans le conseil.

Vérication : chaque commission (sommet de K7 ) a degré 6 (reliée à 6 autres

commissions). Elle partage donc 6 membres avec les autres commissions. Chaque
commission a 6 membres. Total : 7 × 6/2 = 21 membres (on divise par 2 car chaque
membre appartient à 2 commissions). ✓

Exercice  Non-planarité de K5
Montrer que si G est un graphe simple planaire à n sommets et m arêtes (n ≥ 3),
alors m ≤ 3n − 6. En déduire que K5 n'est pas planaire.

Solution :
Supposons G planaire et connexe (n ≥ 3). Par la formule d'Euler : R = 2 − n + m.
Chaque région est délimitée par au moins 3 arêtes (le plus court cycle dans un graphe

27
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

simple a longueur 3). En comptant les incidences région/arête :

X
d(r) ≥ 3R = 3(2 − n + m)
r

Mais chaque arête borde au plus 2 régions :

X
d(r) ≤ 2m
r

Donc2m ≥ 3(2 − n + m) = 6 − 3n + 3m, ce qui donne −m ≥ 6 − 3n, soit m ≤ 3n − 6.

Pour K5 : n = 5, m = 10. Or 3n − 6 = 9 < 10 = m. La condition est violée.
K5 n'est pas planaire.

Exercice  Graphe d'un parc (matrice d'adjacence)

On donne un graphe de 7 sommets par sa matrice d'adjacence M :

 
0 1 0 0 0 0 1
1 0 0 0 1 1 0
 
0 0 0 1 1 0 0
 
0
M = 0 1 0 1 0 0

0 1 1 1 0 1 1
 
0 1 0 0 1 0 0
1 0 0 0 1 0 0

1. Déterminer le nombre minimal de couleurs pour peindre les bancs (deux bancs
reliés ⇒ couleurs diérentes).

2. Est-il possible de parcourir toutes les allées sans passer deux fois par la même
?

Solution :
Degrés (somme de chaque ligne) : d(1) = 2, d(2) = 3, d(3) = 2, d(4) = 2,
d(5) = 5, d(6) = 2, d(7) = 2.
1. Coloriage  Welsh-Powell :
Tri décroissant : V5 (5), V2 (3), V1 (2), V3 (2), V4 (2), V6 (2), V7 (2).

ˆV 5 : aucun voisin colorié → C1. Qui peut aussi prendre C1 ? Les non-voisins
de V5 : V5 est adjacent à V2 , V3 , V4 , V6 , V7 . Donc V1 est non-voisin de V5 → V1
prend C1.
ˆV 2 : adjacent à V5 (C1) et V1 (C1) → C2. Qui peut aussi prendre C2 parmi les
non coloriés ? V3 : adjacent à V5 (C1), non adjacent à V2 → C2.
ˆV 4 : adjacent à V5 (C1) et V3 (C2) → C3. V6 : adjacent à V5 (C1) et V2 (C2),
non adjacent à V4 → C3. V7 : adjacent à V5 (C1) et V1 (C1), non adjacent à
V4 , V6 → C3.

Résultat :

28
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Sommet V5 V2 V1 V3 V4 V6 V7
Couleur C1 C2 C1 C2 C3 C3 C3

χ(G) ≤ 3. Et puisque V2 , V3 , V5 forment un triangle (vériez dans M ), on a χ(G) ≥ 3.

Donc χ(G) = 3.
2. Chemin eulérien :
Sommets de degré impair : V2 (degré 3) et V5 (degré 5). Il y a exactement 2 sommets
de degré impair.
Le graphe est connexe (vériable dans la matrice). Donc par le théorème d'Euler :
un chemin eulérien existe, partant de V2 et arrivant à V5 (ou vice-versa). On peut
parcourir toutes les allées exactement une fois.

29
Cours de Recherche Opérationnelle Licence 1  FSEG Nabeul

Récapitulatif des Formules Essentielles

Programmation Linéaire
Forme générale : max / min Z = j cj xj sous j aij xj ≤ bi et xj ≥ 0.
P P
Solution admissible : satisfait toutes les contraintes.
Théorème fondamental : la solution optimale se trouve en un sommet du polyè-
dre réalisable.
Problème de transport
P : m sources,
P n destinations, m × n variables xij .
Problème équilibré : ores = demandes.

Théorie des Graphes

Lemme des poignées de mains :

X
d(v) = 2|E|
v∈V
Corollaire : le nombre de sommets de degré impair est toujours pair.
n(n − 1)
Graphe complet Kn : |E| = , degré de chaque sommet = n − 1.
2
Formule d'Euler : |V | − |E| + R = 2 (graphe planaire connexe)
Critère de planarité : m ≤ 3n − 6 (général) ; m ≤ 2n − 4 (biparti).
K5 et K3,3 ne sont pas planaires.
Nombre cyclomatique : γ(G) = m − n + p
Graphe eulérien ⇐⇒ connexe + tous les degrés sont pairs.
Chemin eulérien ⇐⇒ connexe + exactement 0 ou 2 sommets de degré impair.
Nombre chromatique : ω(G) ≤ χ(G) ≤ ∆(G) + 1

Conseils pour l'examen

1. En PL : identier d'abord les variables, puis la FO, puis les contraintes (dans
cet ordre). Ne jamais oublier les CNN.

2. En résolution graphique : calculer les sommets par intersection deux à deux,

puis évaluer la FO en chaque sommet.

3. Pour montrer qu'un graphe n'existe pas : utiliser le Lemme des Poignées de
Mains (vérier la parité).

4. Pour la non-planarité : utiliser m ≤ 3n − 6 ou montrer par absurde avec la

formule d'Euler.

5. Pour un cycle eulérien : vérier connexité + tous les degrés pairs.

6. Welsh-Powell : toujours trier par degré décroissant avant de colorier.

7. Le nombre cyclomatique donne le nombre de cycles de base : si γ=0 c'est

un arbre, si γ>0 le graphe contient des cycles.

30