Cours de graphes

30 mars 2007

Cours de graphesQuelques applications.

30 mars 2007

• Définitions de base• Connexité• Les plus courts chemins : Floyd-

Warshall, Dijkstra et Bellmann-Ford• Arbres, graphes particuliers • Arbres de recouvrement ( minimaux ) • Problèmes de flots• Coloriage de graphes, graphes

planaires• Couplages, chemins d’Euler et de

Hamilton• Problèmes NP-complets, réductions• Applications

Les grandes lignes du cours-----------------------------------------------------------------

30 mars 2007

Applications-----------------------------------------------------------------

L E

C O L O R I A G E

D E S A R E T E S

30 mars 2007

Le coloriage des arêtes-----------------------------------------------------------------

• Minimiser les couleurs est un problème NP–complet !

• Nous connaissons une solution polynômiale qui est optimale à une couleur près !

• L’algorithme de Vizing est donc fondamental ! ! !

• Identifier une problématique comme étant un problème de coloriage des arêtes d’un graphe fournit donc tout de suite une solution !

30 mars 2007


• Dans les problèmes de coloriage des arêtes :

– les sommets sont typiquement des ressources,– les arêtes des contraintes de disponibilité !

• Le coloriage ordonnance les contraintes pour qu’elles soient compatibles au niveau des ressources !

• Ce sont souvent des problèmes d’emploi du temps :

– Horaires d’oraux entre profs et élèves.– Horaires d’affectation d’une salle de TP à des

cours.

30 mars 2007


• Souvent, nous avons des variantes plus compliquées du problème, comme par exemple :

• Ceci veut dire que toutes les ressources ne sont pas toujours disponibles !

• Exemple :– des années d’études,– des salles,– des enseignants, avec leurs contraintes d’edt.

30 mars 2007

Applications-----------------------------------------------------------------

L E

C O L O R I A G E

D E S S O M M E T S

30 mars 2007

Le coloriage des sommets-----------------------------------------------------------------

• Nous devons colorier les sommets de façon à ce que deux voisins quelconques n’aient pas la même couleur.

• Nous essayons de minimiser le nombre de couleurs !

• C’est un problème NP–complet et le nombre minimal de couleurs ne peut pas en général être encadré de manière précise !

• Le coloriage des sommets est plus difficile que celui des arêtes . . . et a aussi plus d’applications ! ! !

• Souvent, on utilise des algorithmes polynômiaux qui donnent des solutions que l’on espère « pas trop mauvaises » ! ! !

30 mars 2007


• Dans les problèmes de coloriage des sommets :

– les sommets sont typiquement des entités,– les arêtes des incompatibilités entre entités !

• Le coloriage minimise une ressource critique, comme des nombres de salles, de fréquences, . . . !

• Ce sont souvent des problèmes de :

– Distribution d’une ressource en pénurie.– Minimisation d’une ressource chère.

30 mars 2007


• Attribution de fréquences :

– les émetteurs sont les sommets,– les arêtes représentent le fait que deux

émetteurs ont une intersection non vide de couverture !

• Le coloriage des sommets minimise le nombre de fréquences nécessaires pour couvrir tout le territoire !

• Dans la pratique :

– Les fréquences réelles sont partitionnées en paquets de fréquences.

– Chaque paquet correspond à une couleur.

30 mars 2007


• Emploi du temps :

– les cours sont les sommets,– les arêtes représentent l’incompatibilité entre

cours du fait qu’il sont par exemple donnés par le même enseignant, se font dans la même salle . . .

• Le coloriage des sommets minimise le nombre de créneaux horaires nécessaires pour donner les cours !

• Les questions d’emplois du temps peuvent être traduits en différents problèmes de coloriage !

• Nous pouvons d’ailleurs envisager de colorier aussi bien les sommets que les arêtes !

30 mars 2007


• Variantes de coloriage :– Il y a le coloriage des sommets !– Il y a le coloriage des arêtes !– Il y a le coloriage conjoint des sommets et

arêtes !– Comme le coloriage des sommets attribue une

paire de couleurs à chaque arête, nous pouvons exiger que :• ce coloriage soit « harmonieux » au sens où

il attribue à chaque arête une paire de couleurs différente,

• ce coloriage soit « complet » au sens où chaque paire de couleurs est utilisée au moins une fois.

30 mars 2007


• Allocation de registres :

– les variables d’un programme sont les sommets,

– les arêtes représentent l’incompatibilité entre variables au sens où elles ne peuvent pas utiliser un même registre.

• Le coloriage des sommets minimise le nombre de registres nécessaires pour gérer toutes les variables !

• La gestion d’une valeur dans un registre est beaucoup plus rapide que la gestion en mémoire centrale !

• Si nous n’avons pas assez de registres il faut faire un choix entre les variables ! C’est un autre problème . . .

30 mars 2007


• Deux variables sont compatibles si l’une cesse de servir avant que l’autre ne commence !

• Deux variables sont incompatibles si l’une a des usages avant et après un usage de l’autre variable !

• Des variables peuvent utiliser un même registre si et seulement si elles sont compatibles !

• Exemple :{ x := 5 ; y := 7 ; u := 2 * x ; t := 3 ; t := t + u + y ; }

x et y sont incompatibles !x est compatible avec u et t !y est incompatible avec u et t !u et t sont incompatibles !

30 mars 2007


• Deux variables sont compatibles si l’une cesse de servir avant que l’autre ne commence !

• Deux variables sont incompatibles si l’une a des usages avant et après un usage de l’autre variable !

• Des variables peuvent utiliser un même registre si et seulement si elles sont compatibles !

• Exemple :{ x := 5 ; y := 7 ; u := 2 * x ; t := 3 ; t := t + u + y ; }

x y

u t

Il nous faut3 registres ! Le registre

bleu sert àx et à t !

30 mars 2007


• Coloriage de chemins dans un graphe :

• Nous recevons un graphe et devons colorier un certain nombre de chemins qui sont donnés.

• Deux chemins doivent avoir une couleur différente dès qu’ils partagent une arête.

• Nous devons minimiser le nombre de couleurs !• C’est un problème de coloriage des sommets du

graphe suivant :– Chaque chemin est représenté par un

sommet !– Deux sommets sont reliés par une arête si les

chemins qu’ils représentent partagent des arêtes !

30 mars 2007

Applications-----------------------------------------------------------------

C O U P L A G E S

V E R T E X C O V E R

E T A U T R E S

30 mars 2007

Couplages, vertex cover et autres-----------------------------------------------------------------

• Le couplage consiste à :

– former le plus grand nombre de couples de sommets,

– les arêtes représentant des adéquations entre les sommets.

• Les applications sont bien-sûr nombreuses !

• Quelques exemples :

– Couples de personne–tâche , candidat–poste , . . .

– Couples de binômes en respectant les affinités.

30 mars 2007


• Le Vertex Cover consiste

– à savoir si nous pouvons trouver un sous-ensemble de k sommets au plus tel que chaque arête touche un de ces sommets ?

– ou à trouver le plus petit entier k pour lequel un tel ensemble existe !

• Y a–t–il des applications réelles pour ce tel problème ?

• Pour un graphe de n sommets, le Vertex Cover avec la constante k est équivalent à savoir si Clique admet une solution de taille n–k ?

30 mars 2007


• Le problème Independent Set ( STABLE en français ) :

– Pouvons-nous trouver dans un graphe au moins k sommets qui ne sont pas voisins deux à deux ? ? ?

– Quelle est la plus grande valeur k pour laquelle nous pouvons trouver un stable ? ? ?

• Un graphe avec n sommets admet un stable de taille k si et seulement si son graphe complémentaire admet une clique de taille n–k ! ! !

• Comme il n’existe aucune arête entre deux sommets du stable, dans le graphe complémentaire toutes les arêtes vont exister, et donc former une clique !

30 mars 2007


• Vertex Cover , Clique et Independent Set sont en fait le même problème, vu sous des facettes différentes !

• Une application pour Independent Set :

– Soient des sommets qui représentent tous les emplacements potentiels de succursales dans une ville.

– Soient les arêtes qui représentent une concurrence trop forte ( et donc un mauvais investissement ) due à une trop grande proximité entre deux sites.

• Maximiser le stable revient à trouver la meilleure saturation de la ville avec des succursales, sans risquer une trop grande concurrence entre elles.

30 mars 2007


• Un exemple ayant 24 sommets :

30 mars 2007

Applications-----------------------------------------------------------------

D I G R E S S I O N :

A L G O R I T H M E S

D ‘ A P P R O X I M A T I O N

30 mars 2007

Algorithmes d’approximation-----------------------------------------------------------------

• Pour des raison pratiques,

– nous renonçons à la solution optimale,– pour avoir une solution en temps polynômial !

30 mars 2007


• Pour des raison pratiques,

– nous renonçons à la solution optimale,– pour avoir une solution en temps polynômial !

• Ceci peut se faire à l’aide d’heuristiques quelconques, qui n’offrent aucune garantie de qualité !

30 mars 2007


• Une heuristique quelconque est un programme qui

– utilise un temps polynômial plus ou moins grand,

– pour appliquer des arguments plus ou moins sophistiqués,

– qui donnent une solution plus ou moins bonne,

– sur une partie plus ou moins grande des instances du problème !

30 mars 2007


• Un algorithme d’approximation à un facteur r près est un programme qui

– utilise un temps polynômial connu,

– pour donner une solution optimale au facteur r près

– et ce quelle que soit l’instance donnée du problème !

• Si la meilleure solution ( inconnue ) vaut opt , alors nous sommes assurés d’obtenir une solution sol telle que opt <= sol <= r * opt

30 mars 2007


• Un algorithme d’approximation à un facteur r près est un programme qui

– utilise un temps polynômial connu,

– pour donner une solution optimale au facteur r près

– et ce quelle que soit l’instance donnée du problème !

• Si la meilleure solution ( inconnue ) vaut opt , alors nous sommes assurés d’obtenir une solution sol telle que sol = r * opt

30 mars 2007


• Pour le « Voyageur de Commerce euclidien » ( inégalité triangulaire ) nous avons construit une solution à un facteur 2 près !

• Il s’agissait de

– trouver un arbre de recouvrement minimal,

– en doubler les arêtes pour en faire un circuit

– et d’éviter de passer plusieurs fois par un sommet ( ce qui ne rallonge pas les distances ) .

• La complexité est en O ( | E | * log ( | E | ) ) .

30 mars 2007


• Théorème :

– Pour le problème « Independent Set » il n’existe pas d’algorithme polynômial qui donne une solution optimale à un facteur r près, quel que soit r , à moins que P ne soit égale à NP !

• Il y a des instances de Independent Set , tout comme de Vertex Cover et Clique , qui ne peuvent pas être approchées en temps polynômial à un facteur 2 ou 5 ou 1000 près ! ! !

30 mars 2007


• Pour Independent Set , la complexité dépend du degré D ( G ) du graphe. Et, nous avons les résultats :

– Pour D ( G ) = 3 , nous ne pouvons pas approximer en temps polynômial à un facteur r = 1,0005 près.



– Pour e petit, nous ne pouvons pas approximer en temps polynômial à un facteur r = D ( G ) ^e près.

30 mars 2007


• Pour Independent Set , la complexité dépend du degré

• D ( G ) du graphe. Et nous avons les résultats :

– Nous pouvons approximer en temps polynômial à un facteur r = ( D ( G ) + 3 ) / 5 près.

– Nous pouvons approximer en temps polynômial à r = ( D ( G ) * log log D ( G ) ) / log D ( G ) près.

– Pour D ( G ) grand, la seconde formule est meilleure.

30 mars 2007

Applications-----------------------------------------------------------------

V A R I A N T E S

D E P R O B L E M E S

D E F L O T

30 mars 2007

Variantes de problèmes de flot-----------------------------------------------------------------

• Le problème de flot tel que nous l’avons regardé est en fait la variante la plus simple de toute une famille de problèmes de flot !

• L’extension la plus simple consiste à introduire plusieurs sources et plusieurs puits !

• Elle ne change rien à la problématique, car il suffit de rajouter une « super-source » et un « super-puits » pour se ramaner à la situation de départ.

• C’est différent lorsque chaque source produit une couleur différente, destinée au puits correspondant.

30 mars 2007


• Multi-commodity Flow Problem !– Nous avons n sources et n puits. Chaque

source produit une couleur différente, destinée au puits qui lui correspond. La demande est d .

– Respect des capacités :

– Conservation, pas de mélange :

– Respect des demandes :

i

S f ( u , v ) <= c ( u , v )i i

S f ( u , v ) = 0 si u = s , pi i i/v

S f ( s , v ) = S f ( v , p ) = di i ii iv v

30 mars 2007


• Complexité du Multi-commodity Flow Problem :– Si les flots sont des entiers, le problème de

décision sous-jacent est NP–complet déjà pour deux sources et puits.

– Le problème est par contre polynômial si les flots sont des réels ! ! !

• Analogie :– La programmation linéaire en nombres

entiers est NP–complète !

– La programmation linéaire dans un univers continu est polynômiale !

30 mars 2007


• Minimum Cost Flow Problem !– C’est un problème de flot mono-source et

puits.

– A chaque arc ( u , v ) nous associons un coût a ( u , v ) !

• L’objectif est de minimiser le coût total d’un flot de valeur d donné :

S f ( s , v ) = dv

Minimiser : S a ( u , v ) * f ( u , v )u , v

30 mars 2007


• Minimum Cost Max Flow Problem !– C’est un problème de flot mono-source et

puits.

– A chaque arc ( u , v ) nous associons un coût a ( u , v ) !

• L’objectif est de minimiser le coût total du meilleur flot qui peut être atteint :

Maximiser : S f ( s , v )v

tout en minimisant : S a ( u , v ) * f ( u , v )u , v

30 mars 2007


• Résolution du Minimum Cost Max Flow Problem :

• Le problème est simple, car il suffit d’adapter le principe de Ford & Fulkerson.

• Nous allons chercher le chemin augmentant dont le coût total est le plus faible. Le poids de ce chemin correspond au coût unitaire du flot !

• C’est l’algorithme de Dijkstra !

• La complexité est la même que pour la version sans les coûts, car nous avons la même complexité pour la vague et Dijkstra ! ! !

30 mars 2007


• Circulation Problem, le problème le plus général ! ! !

• Le puits est relié à la source et ils doivent aussi conserver le flot, d’où le nom de circulation !

• En plus de la capacité maximale c ( u , v ) , nous associons à l’arc ( u , v ) une capacité minimale notée l ( u , v ) !

• Pour un flot d donné, il s’agit de trouver une circulation :

l ( u , v ) <= f ( u , v ) <= c ( u , v )

S f ( u , v ) = 0v

f ( p , s ) = d

30 mars 2007


• Tout est polynômial sauf le multi-commodity en nombres entiers !

• Nous pouvons limiter le nombre de sources à unité.

• En supprimant les bornes inférieures l ( u , v ) , nous revenons à un classique problème de flot !

• En annulant les coûts, nous obtenons un simple problème de flot sans coûts !

• En portant la capacité de l’arc ( p , s ) à infini, nous obtenons un problème de maximisation !

30 mars 2007


• Le problème d’affectation !

• Il s’agit de trouver un couplage maximal, de poids minimal dans un graphe bi-parti valué !

• Nous avons, par exemple, des personnes et des tâches, ainsi que des coûts de personne–tâche !

• Il s’agit de trouver une bijection entre les personnes et les tâches qui minimise la somme des coûts !

• Si le couplage maximal et de poids minimal est NP–complet sur un graphe pondéré quelconque, il est cependant polynômial sur un graphe bi-parti !

30 mars 2007


• Le problème d’affectation est un cas particulier du « problème de transport » !

• Dans le problème de transport, nous avons un nombre m de mines et un nombre u d’usines, ainsi que des coûts de transport connus d’une mine vers une usine !

• Chaque mine ne livre qu’une seule usine et chaque usine ne se fournit qu’auprès d’une mine.

• Il s’agit de trouver la correspondance qui minimise la somme des coûts !

30 mars 2007


• Le « problème de transport » est un cas particulier du « problème de flot avec coûts » !

• En effet, il suffit de rajouter une « super-mine » en amont des mines et une « super-usine » en aval des usines et de bien choisir les capacités et coûts !

• Nous pouvons en fait trouver un petit nombre de problèmes qui englobe une bonne partie des problèmes que l’on peut rencontrer usuellement !

30 mars 2007

Applications-----------------------------------------------------------------

C H E M I N S

D ‘ E U L E R E T

D E H A M I L T O N

30 mars 2007

• Il peut y avoir des applications surprenantes pour les chemins d’Euler !

• Ainsi, des problèmes d’alignements locaux de séquences de DNA ont pu être ramenées à des problèmes de chemins d’Euler, en utilisant des graphes de De Bruijn !

• Le fait de savoir si un anneau peut être plongé dans un graphe est un problème de cycle de Hamilton !

• Tous problèmes de circuits de type « Voyageur de Commerce » sont des questions de cycles de Hamilton !

Chemins d’Euler et de Hamilton-----------------------------------------------------------------

30 mars 2007

• Pour un graphe G donné, nous définissons le graphe de représentation R ( G ) suivant :

– Chaque arête de G devient un sommet de R ( G ).

– Deux sommets de R ( G ) sont reliés s’ils correspondent à des arêtes adjacentes dans G .


G Les sommetsde R ( G ) ! ! !

Les arrêtesde R ( G ) ! ! !

30 mars 2007

• Si le graphe G admet un chemin d’Euler, alors le graphe R ( G ) aussi !

• Si le graphe G admet un chemin d’Euler, alors le graphe R ( G ) admet un chemin de Hamilton !

• Si le graphe G admet un chemin de Hamilton, alors le graphe R ( G ) aussi !

• Les réciproques ne sont pas vraies !


G

30 mars 2007

• Les cycles de Hamilton servent souvent à démontrer que d’autres problèmes sont NP–complets !

• Savoir si un graphe possède un arbre de recouvrement de degré 2 au plus est NP–complet ! En effet, cet arbre est égal au chemin de Hamilton !

• Savoir si un graphe possède un arbre de recouvrement de degré 3 au plus est NP–complet ! En effet, un graphe G admet un chemin de Hamilton si et seulement si le graphe G’ suivant admet un arbre de recouvrement de degré 3 au plus.Nous gardons les

arêtes et dupliquonsles sommets !

u

v

G : u

v

G’ : u’

v’

Ensuite,nous

rajoutons lesarêtes ( u , u’ ). . .


30 mars 2007

Applications-----------------------------------------------------------------

A R B R E S

D E R E C O U V R E M E N T

( M I N I M A U X )

30 mars 2007

Arbres de recouvrements (minimaux)-----------------------------------------------------------------

• L’arbre de recouvrement est important parce que

– il fournit la plus petite solution connexe en termes d’arêtes,

– il fournit la plus grande solution sans cycles en termes d’arêtes,

– il évite les choix arbitraires entre plusieurs chemins !

• Il est compatible avec la minimisation sous la forme du calcul de l’arbre de recouvrement minimal !

30 mars 2007


• Le problème devient difficile dès que nous imposons des contraintes sur la forme de l’arbre, comme une arité bornée, . . .

• De même, il est difficile de trouver, parmi les n sommets d’un graphe pondéré, le sous-ensemble de k sommets qui admet l’arbre de recouvrement le plus léger.

• Le calcul de l’arbre de recouvrement minimal a de nombreuses applications– soit en tant que solution directe d’un

problème,– soit comme étape essentielle d’un calcul

plus complexe comme l’approximation du TSP.

30 mars 2007


• Le problème de « l’arbre de recouvrement euclidien » est une variante intéressante !

• Nous considérons des points dans le plan ( ou un espace de dimension plus grande ) et cherchons l’arbre de recouvrement minimal en termes de distances euclidiennes.

• Un exemple :

• La solution la plus simple consiste à calculer les distances entre toutes les paires de points et de dérouler ensuite un calcul d’ARM !

30 mars 2007

Applications-----------------------------------------------------------------

P L U S

C O U R T S

C H E M I N S

30 mars 2007

Plus courts chemins-----------------------------------------------------------------

• Le calcul des composantes connexes, des chemins les plus courts et des chemins les plus légers est à la base de beaucoup de traitements !

• Une première difficulté peut provenir du fait que l’inégalité triangulaire ne soit pas respectée !

• Une seconde difficulté peut provenir du fait que, en présence d’arêtes de poids négatives, nous puissions tomber sur des cycles de poids négatifs !

• Nous avons en général plusieurs algorithmes à notre disposition, de complexités variables, mais toujours polynômiales !

30 mars 2007

Plus courts chemins-----------------------------------------------------------------

• Il est équivalent de

– minimiser une somme de poids,

– minimiser le poids de l’arête la plus lourde, c’est-à-dire minimiser un maximum,

– maximiser une somme de poids,

– maximiser le poids de l’arête la plus légère, c’est-à-dire maximiser un minimum !

30 mars 2007

Synthèse-----------------------------------------------------------------

• Quelques applications.

30 mars 2007

Synthèse du cours-----------------------------------------------------------------

• Connexité

• Les plus « courts » chemins :

• La vague• La multiplication de matrices• Floyd-Warshall• Dijkstra• Bellmann-Ford

30 mars 2007


• Arbres :

• Définitions équivalentes• Arbres de recouvrement• Arbres de recouvrement

minimaux

30 mars 2007


• Problèmes de flots :

• Théorème du MIN–MAX• Algorithme de Ford et

Fulkerson• Algorithme de Edmonds et Karp

30 mars 2007


• Coloriage de graphes :

• Coloriage des sommets• Coloriage des arêtes• L’algorithme de Vizing

• Graphes planaires

30 mars 2007


• Couplages

• Chemins d’Euler

• Chemins de Hamilton

30 mars 2007


• Problèmes NP-complets :

• La théorie ( rappels )• Les réductions polynômiales• Des exemples de réductions

30 mars 2007


• Quelques graphes particuliers :

• Le graphe en ligne, la grille, . . .• L’anneau, le tore, . . .• L’hypercube• Des graphes plus exotiques . . .

30 mars 2007


• Quelques applications :

• Illustrations directes du cours• Quelques extensions de

résultats

30 mars 2007

L E S P R O B L E M E SD E G R A P H E S

D O I V E N T E T R EA P P R I S C A R

L E S S O L U T I O N SS O N T S O U V E N T

D I F F I C I L E SA T R O U V E R ! ! !

30 mars 2007

L ‘ I N T U I T I O NE S T

S O U V E N TU N

T R E SM A U V A I S

G U I D E ! ! !

Documents

Cours de graphes