Graphe d'intervalle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Sept intervalles de la droite réelle et le graphe d'intervalle associé

En théorie des graphes, un graphe d'intervalle est le graphe d'intersection d'un ensemble d'intervalles de la droite réelle. Chaque sommet du graphe d'intervalle représente un intervalle de l'ensemble, et une arête relie deux sommets lorsque les deux intervalles correspondants s'intersectent.

Définition formelle[modifier | modifier le code]

Soient

I_1, I_2, \ldots, I_n \subset\R

des intervalles. Alors, le graphe d'intervalle correspondant est G=(V,E)~

 V = \{I_1, I_2, \ldots, I_n\}

et

 \{I_\alpha, I_\beta\} \in E \iff  I_\alpha \cap I_\beta \neq \emptyset.

Applications[modifier | modifier le code]

Les graphes d'intervalle sont utilisés pour modéliser les problèmes d'allocation de ressources en recherche opérationnelle. Chaque intervalle représente l'allocation d'une ressource pendant un certain temps; la recherche du stable maximum du graphe correspond à la meilleure allocation de ressources pouvant être réalisée sans conflits[1].

La recherche d'un ensemble d'intervalles qui représente un graphe d'intervalle peut aussi être une manière d'assembler des séquences contigües d'ADN[2].

Propriétés[modifier | modifier le code]

Les graphes d'intervalle sont des graphes cordaux, donc des graphes parfaits. Leurs graphes complémentaires sont des graphes de comparabilité et la relation de comparabilité est précisément l'ordre d'intervalle (en).

Un graphe d'intervalle propre est un graphe d'intervalle possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre. Un graphe d'intervalle unitaire est un graphe d'intervalle possédant une représentation d'intervalles dans laquelle chaque intervalle est de longueur 1. On peut démontrer que ces deux classes sont en fait équivalentes.

Aspects algorithmiques[modifier | modifier le code]

Algorithmes efficaces de reconnaissance[modifier | modifier le code]

Déterminer si un graphe G = (V,E) donné est un graphe d'intervalle peut être fait en complexité temporelle O(|V|+|E|) en recherchant un ordonnancement des cliques maximales de G qui est consécutif en respectant les inclusions des nœuds. De manière formelle, un graphe G est un graphe d'intervalle si et seulement si les cliques maximales  M_1, M_2, \ldots, M_k de G peuvent être ordonnées telles que pour tout  v \in M_i \cap M_k , alors v \in M_j pour tout entier j,\ i \le j \le k.

L'algorithme original permettant de savoir si un graphe est un graphe d'intervalle en temps linéaire, dû à Booth et Lueker[3] est basé sur un arbre PQ (en) complexe, mais Habib et al[4] ont montré comment résoudre plus simplement le problème, en utilisant le fait qu'un graphe est un graphe d'intervalle si et seulement s'il est cordal et son graphe complémentaire est un graphe de comparabilité[5].

Problèmes restreints à la classe[modifier | modifier le code]

De nombreux problèmes NP-complets dans le cas général, il existe des algorithmes de complexité polynomiale ou même linéaire si l'on se restreint aux graphes d'intervalles, par exemple le problème de l'isomorphisme de graphes[6] et le problème du voyageur de commerce[7],[8].

Notes et références[modifier | modifier le code]

  1. (en) Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor et Baruch Schieber, « A unified approach to approximating resource allocation and scheduling », Journal of the ACM, vol. 48, no 5,‎ 2001, p. 1069-1090 (DOI 10.1145/502102.502107, lire en ligne)
  2. (en) Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler et Philip E. Bourne, « An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA », Bioinformatics, vol. 10, no 3,‎ 1994, p. 309-317 (DOI 10.1093/bioinformatics/10.3.309)
  3. (en) Booth, K. S.; Lueker, G. S., « Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms », J. Comput. System Sci., vol. 13,‎ 1976, p. 335–379
  4. (en) Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent, « Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing », Theor. Comput. Sci., vol. 234,‎ 2000, p. 59–84 (DOI 10.1016/S0304-3975(97)00241-7, lire en ligne)
  5. Martin Charles Golumbic (en) (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7
  6. Kellogg S. Booth et George S. Lueker, « A linear time algorithm for deciding interval graph isomorphism », Journal of the ACM, vol. 26, no 2,‎ 1979, p. 183-195 (DOI 10.1145/322123.322125).
  7. J Mark Keil, « Finding Hamiltonian circuits in interval graphs », Information Processing Letters, vol. 20, no 4,‎ 1985, p. 201-206
  8. Voir (en) « Information System on Graph Class Inclusions » pour plus d'exemples.

Bibliographie[modifier | modifier le code]

  • (en) Fulkerson, D. R.; Gross, O. A., « Incidence matrices and interval graphs », Pacific Journal of Mathematics, vol. 15,‎ 1965, p. 835–855

Liens externes[modifier | modifier le code]