Cours sur les graphes

ble est un problème NP-complet pour toute valeur fixée de k (si k vaut au moins 3) [REF: Garey & Johnson].

De nombreux problèmes ouverts sur la coloration sont présentés dans le livre de Jensen et Toft.

 Le nombre chromatique de G, noté Chi(G), est le plus petit entier k tel que G est k-colorable.

Sur le thème de la coloration, on visitera avec intérêt la page de Joseph Culberson à l'Université de l'Alberta (Canada).

 Un graphe G est parfait si, pour tout sous-graphe H induit de G, le nombre chromatique de H est égal à la taille d'une clique maximum de H, c'est-à-dire, Chi(H)=omega(H). Pour les graphes parfaits voir Golumbic ou Berge & Chvátal.

Flot

 Dans un graphe orienté G un flot est l'affectation d'une valeur réelle à chaque arc de G, représentant une quantité de matière transportée sur cet arc, de telle sorte qu'en chaque sommet la somme des flots entrants soit égale à la somme des flots sortants (loi de Kirchhoff).

On se donne habituellement une capacité maximale sur chaque arc, qui sera une borne supérieure sur le flot autorisé sur cet arc; le problème du flot maximum est alors de trouver un flot dont la valeur sur un certain arc donné (source et puits) est maximum.

On peut de plus se donner un coût de transport d'une unité de flot sur chaque arc, et chercher un flot (maximum) de coût minimum.

Ces problèmes sont bien résolus algorithmiquement, depuis le travail pionnier de Ford et Fulkerson conduisant à des algorithmes polynomiaux, et ont de nombreuses applications et généralisations - voir par exemple le livre récent de Ahuja, Magnanti, Orlin.

Connectivité

 Un graphe G est k-sommet-connexe (resp. k-arête-connexe) s'il faut ôter au moins k sommets (resp. k arêtes) pour le rendre non-connexe. La connectivité (par sommets ou bien par arêtes) du graphe est le plus grand k tel que G est k-connexe. Ces nombres peuvent être calculés en temps polynomial; en fait on réduit habituellement la résolution des problèmes de connectivité à des problèmes de flots.

Récemment, de nouveaux résultats (Karger; Nagamochi et Ibaraki; Frank) permettent de calculer la connectivité d'un graphe sans avoir recours aux méthodes de flots.

Produits de graphes

 Le produit carré de G et H, est le graphe dont l'ensemble des sommets est le produit cartésien de V(G) par V(H), et le couple (ax, by) est une arête du produit si et seulement si soit x=y et ab est une arête de G, soit a=b et xy est une arête de H.

Par exemple, la grille est le produit carré de deux chaînes.

 Le produit croisé de G et H, est le graphe dont l'ensemble des sommets est le produit cartésien de V(G) par V(H), et le couple (ax, by) est une arête du produit si et seulement si ab est une arête de G et xy est une arête de H.

Hamiltonicité

 Un cycle hamiltonien d'un graphe G est un cycle élémentaire passant par tous les sommets de G. Un graphe est hamiltonien s'il possède un cycle hamiltonien comme sous-graphe. Déterminer si un graphe est hamiltonien est un problème NP-complet. Voir l'article de Gould pour un survey récent sur les questions d'hamiltonicité.

 Le problème du voyageur de commerce est de parcourir un réseau en passant au moins une fois en chaque sommet et en minimisant la distance totale, étant donné que chaque arête a une certaine longueur. Voir le livre de Lawler, Lenstra, Rinnooy Kan & Schmoys.

Problèmes eulériens

 Un parcours est eulérien s'il passe exactement une fois par chaque arête. Un graphe est dit eulérien s'il admet un tel parcours fermé, ce qui revient à être connexe et avoir tous ses degrés pairs (ceci est un théorème d'Euler, souvent considéré comme le 1er théorème de la théorie des graphes). Le livre de Fleischner aborde de nombreuses questions et généralisations sur ce sujet.

 La ville de Königsberg (maintenant Kaliningrad) avait sept ponts sur la rivière Pregel. Les amateurs de questions mathématiques et de promenades digestives se demandaient s'il était possible de faire un tour dans la ville en passant une fois exactement sur chaque pont. Euler, en construisant le graphe représentatif, constata qu'il avait des sommets de degré impair et démontra que cela rendait impossible une telle promenade.

 Le problème dit du postier chinois est de parcourir les rues d'une ville en passant au moins une fois dans chaque rue, le réseau n'étant pas nécessairement eulérien; on cherche bien sur à minimiser le parcours total. Voir Lovász & Plummer, ou Ahuja, Magnanti & Orlin.

Planarité

 On dit qu'un graphe G est planaire si l'on peut le représenter sur un dessin de sorte que les arêtes forment des lignes qui ne se croisent pas. Kuratowski a donné une caractérisation des graphes planaires par "mineurs" exclus. Il existe plusieurs algorithmes polynomiaux pour déterminer si un graphe est planaire, et , lorsqu'il l'est, pour trouver une représentation planaire. Voir par exemple le livre récent de Nishizeki et Chiba.

 Une carte de géographie peut être modélisée par un graphe planaire dont les sommets sont les régions et dont les arêtes sont les paires de régions voisines. On désire colorer les régions d'une telle carte de sorte que des régions voisines aient des couleurs différentes. Empiriquement, il est connu des cartographes depuis longtemps que quatre couleurs suffisent pour une telle tâche. Cependant, malgré diverses tentatives ratées, la 1ère preuve mathématique de ce problème des quatre couleurs n'est apparue qu'en 1976, par Appel et Haken, et elle utilise un ordinateur pour la vérification de nombreux cas. Une preuve plus récente et plus compacte, mais dans le même esprit, a été donnée par Robertson, Seymour, Thomas et Sanders.

Couplage

 Un couplage est un ensemble d'arêtes deux à deux non-adjacentes. On sait trouver en temps polynomial un couplage de taille (ou même de poids) maximum. Depuis les travaux de König, Hall, Tutte, Edmonds, Gallai, Lovász, et bien d'autres, la théorie du couplage est très riche, voir par exemple le livre de Lovász & Plummer.

Programmation Linéaire en Nombres Entiers

(PLNE)

* Toutes les variables sont obligées de prendre des valeurs entières

* En général les coefficients ai,j sont aussi entiers

* Et, donc, on peut se limiter à des constantes bj entières

* Si, les variables sont aussi contraintes d'être entre 0 et 1, elles n'ont que les deux valeurs possibles 0 et 1 et on parle de PL en 01

Maintenant on peut exprimer des contraintes telles x1 > = 1 ou x2 > = 1

par la contrainte x1+x2 > = 1 parce que des ``solutions'' comme x1=x2=0.5 sont interdites.

Le PL ordinaire avec les mêmes variables, contraintes et fonction objective s'appelle le PL relaxé du PLNE.

Sa solution optimale donne une borne (supérieure pour un problème de maximisation) sur la solution optimale du PLNE.

(Mais la solution optimale du PLNE peut être très différente ou même ne pas exister.)

Aspects Théoriques

* Chercher une solution réalisable du PLNE équivaut à chercher un point dans le polytope de solutions réalisables avec tous ses coordonnés entiers

* Si le polytope est long et étroit il n'est pas évident qu'il contient de tels points

* Décider si un PLNE possède des solutions réalisables est un exemple d'un problème NP-complet une classe de problèmes pour lesquels personne ne sait s'il existe ou non un algorithme efficace (opérant en temps polynomial)

* Les meilleurs algorithmes connus sont capables de traiter des programmes avec quelques dizaines de variables

(par comparaison, on peut traiter des PL de plusieurs milliers de variables)

* Méthodes heuristiques

Des cas où les deux programmes sont équivalents

* Pour quelques types de PL, on sait que (s'il existe une solution optimale,) il existe une solution optimale entière

* Donc, le PLNE et le PL ont la même valeur optimale

et c'est beaucoup plus vite de résoudre le PL