1.
5em 0pt
Republique Algerienne Democratique et Populaire
Ministere de l’Enseignement Superieur et de la Recherche Scientifique
Universite des Sciences et Technologie de Houari Boumedienne
Coloration de Graphes et Application
Realiser Par:
MEZIANE yasmine
SAIDANI sarah
INTRODUCTION
Ce projet porte sur l’application de la théorie des graphes pour résoudre un
problème pratique de gestion des poissons dans des aquariums. Deux
dentistes souhaitent installer plusieurs poissons exotiques dans leur salle
d’attente, mais certaines espèces sont incompatibles en raison de leurs
comportements ou besoins spécifiques. L’objectif est de déterminer le
nombre minimum d’aquariums nécessaires pour garantir la cohabitation de
ces poissons, ce qui est un problème classique de coloration de graphes.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 2 / 16
Modélisation du Problème
Contexte
- Deux dentistes souhaitent installer 9
poissons exotiques dans des aquariums. -
Certaines espèces sont incompatibles. -
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 3 / 16
Modélisation du Problème
Contexte Modélisation sous forme de
- Deux dentistes souhaitent installer 9 Graphe
poissons exotiques dans des aquariums. -
Chaque poisson est représenté par un
Certaines espèces sont incompatibles. -
sommet F1,F2,...,F9
Deux sommets sont adjacents si les
poissons correspondants ne peuvent pas
être placés dans le même aquarium.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 3 / 16
Modélisation du Problème
Contexte Modélisation sous forme de
- Deux dentistes souhaitent installer 9 Graphe
poissons exotiques dans des aquariums. -
Chaque poisson est représenté par un
Certaines espèces sont incompatibles. -
sommet F1,F2,...,F9
Deux sommets sont adjacents si les
poissons correspondants ne peuvent pas
être placés dans le même aquarium.
Objectif
Le but est de déterminer le nombre minimum d’aquariums nécessaires,
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 3 / 16
Graphe Obtenu
F3 F4 F6
F2 F5
F1
F7
F9 F8
Realiser Par: Figure – Graphe G .
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 4 / 16
Analyse Du graphe Obtenu G
Prenons les arêtes données dans le problème où chaque arête indique
qu’un couple de poissons peut cohabiter dans le même aquarium. (Une
arête entre deux sommets signifie que les deux poissons peuvent partager
le même aquarium)
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 5 / 16
Analyse Du graphe Obtenu G
Prenons les arêtes données dans le problème où chaque arête indique
qu’un couple de poissons peut cohabiter dans le même aquarium. (Une
arête entre deux sommets signifie que les deux poissons peuvent partager
le même aquarium)
F2 F4
F3 F1 F5
F7 F6 F8 F9
Realiser Par:
MEZIANE yasmine, SAIDANI sarah F1
Coloration de Graphes et Application 5 / 16
Analyse Du graphe Obtenu G
Prenons les arêtes données dans le problème où chaque arête indique
qu’un couple de poissons peut cohabiter dans le même aquarium. (Une
arête entre deux sommets signifie que les deux poissons peuvent partager
le même aquarium)
F2 F4
F3 F1 F5
F7 F6 F8 F9
Realiser Par:
MEZIANE yasmine, SAIDANI sarah F1
Coloration de Graphes et Application 5 / 16
Le Graphe obtenu est un graphe d’intervalle.
F1
F6 F4
F3 F8
F2 F5
F7 F9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Le complémentaire de ce graphe est le graphe G, dans lequel les arêtes
représentent les incompatibilités entre poissons.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 6 / 16
Théorème
le complémentaire d’un graphe d’intervalle est toujours un graphe de
comparabilité.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 7 / 16
Théorème
le complémentaire d’un graphe d’intervalle est toujours un graphe de
comparabilité.
Classe de G
G est un Graphe de comparabilité.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 7 / 16
Graphe de Comparabilité :Définition et Propriétés
Définition
Un graphe de comparabilité est un graphe dans lequel les arêtes peuvent
être orientées de manière transitive.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 8 / 16
Graphe de Comparabilité :Définition et Propriétés
Définition
Un graphe de comparabilité est un graphe dans lequel les arêtes peuvent
être orientées de manière transitive.
Propriété 1
Transitivité
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 8 / 16
Graphe de Comparabilité :Définition et Propriétés
Définition
Un graphe de comparabilité est un graphe dans lequel les arêtes peuvent
être orientées de manière transitive.
Propriété 1 Propriété 2
Transitivité Les graphes de
comparabilité sont des
graphes parfaits.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 8 / 16
Graphe de Comparabilité :Définition et Propriétés
Définition
Un graphe de comparabilité est un graphe dans lequel les arêtes peuvent
être orientées de manière transitive.
Propriété 1 Propriété 2 Propriété 3
Transitivité Les graphes de Cohérence avec les
comparabilité sont des Algorithmes de
graphes parfaits. Coloration
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 8 / 16
Résolution du Problème : Algorithme 1
Algorithm 1 Coloration d’un graphe avec une orientation transitive
Un graphe G = (V , E )
Une coloration des sommets de G
Étape 1 : Déterminer une orientation transitive
Trouver un ordre total v1 < v2 < · · · < vn des sommets tel que cette
orientation soit transitive.
Étape 2 : Coloration gloutonne
Colorier le sommet vi avec le plus petit numéro de couleur disponible
qui n’est pas utilisé par ses voisins.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 9 / 16
Déterminer une orientation transitive
Dans le graphe d’intervalle obtenu. les intervalles permettent de définir un
ordre des sommets pour le graphe G.
F1
F6 F4
F3 F8
F2 F5
F7 F9
3:
1:
4:
2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 10 / 16
Déterminer une orientation transitive
Dans le graphe d’intervalle obtenu. les intervalles permettent de définir un
ordre des sommets pour le graphe G.
F1
F6 F4
F3 F8
F2 F5
F7 F9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ordre de G
F7 , < F2 , < F3 , < F6 , <, F1 , < F5 , < F4 < F8 <, F9
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 10 / 16
Résolution du Problème : Algorithme 1
Itération 1
1 = (ROUGE)
F3 F4
F6
F2 F5
F1
F7
F9 F8
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 11 / 16
Résolution du Problème : Algorithme 1
Itération 2
Itération 1
On associe ( !=ROUGE) au
1 = (ROUGE)
sommet F8 = 1
F3 F4
F3 F4
F6
F2 F5 F6
F2 F5
F1
F7 F1
F7
F9 F8
F9 F8
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 11 / 16
Frame Title
Itération 3
(1=ROUGE) au sommet F4
F3 F4
F6
F2 F5
F1
F7
F9 F8
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 12 / 16
Frame Title
Itération 3 Itération 4
(1=ROUGE) au sommet F4 (1=ROUGE) au sommet F5
F3 F4 F3 F4
F6 F6
F2 F5 F2 F5
F1 F1
F7 F7
F9 F8 F9 F8
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 12 / 16
Itération 7
(1=ROUGE) au sommet F4
F3 F4
F6
F2 F5
F1
F7
F9 F8
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 12 / 16
Itération 9
(1=ROUGE) au sommet F9
F3 F4
F6
F2 F5
F1
F7
F9 F8
L’algorithme glouton nous a fourni une solution : 3 couleurs suffisent pour
colorier le graphe G .
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 13 / 16
IMPLEMENTATION DE LA METHODE
WELSH-POWELL
Algorithm 2 Coloration gloutonne d’un graphe
1: Entrée : Un graphe G = (V , E )
2: Sortie : Une coloration des sommets de G
3: Ranger les sommets de G par ordre décroissant de leur degré
4: Soit S, l’ensemble des sommets ordonnés par degré décroissant, et i = 1 (première
couleur)
5: Choisir le premier sommet a de S
6: Colorier a avec la couleur i
7: Retirer a de S
8: Déterminer N, l’ensemble des voisins de a
9: Pour chaque sommet x ∈ S \ N, colorier x avec la couleur i
10: Retirer x de S
11: Ajouter les voisins de x à N
12: Passer à la couleur suivante i = i + 1
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 13 / 16
IMPLEMENTATION DE LA METHODE
WELSH-POWELL
L’algorithme de Welsh-Powell a été implémenté en Python et nous a fourni
le résultat suivant :
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 14 / 16
IMPLEMENTATION DE LA METHODE
WELSH-POWELL
L’algorithme de Welsh-Powell a été implémenté en Python et nous a fourni
le résultat suivant :
Conclusion
l’algorithme de Welsh-Powell a coloré le graphe G avec seulement 3
couleurs
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 14 / 16
CONCLUSION
En conclusion, ce projet a permis de démontrer l’efficacité des graphes de
comparabilité et des algorithmes de coloration pour résoudre des problèmes
pratiques. nous avons pu appliquer l’algorithme de Welsh-Powell, qui a
coloré le graphe avec seulement 3 couleurs. Cela implique qu’un total de 3
aquariums sont nécessaires pour accueillir les poissons.
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 15 / 16
MERCI POUR VOTRE ATTENTION
Realiser Par:
MEZIANE yasmine, SAIDANI sarah Coloration de Graphes et Application 16 / 16