Graphe d'intervalles

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

Définition formelle

Etant donnés des intervalles $I_{1},I_{2},\ldots ,I_{n}\subseteq \mathbb {R}$ , le graphe d'intervalle correspondant est $G=(V,E)~$ où

V=\{I_{1},I_{2},\ldots ,I_{n}\}

et

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

Applications

Les graphes d'intervalles sont utilisés pour modéliser les problèmes d'allocation de ressources en recherche opérationnelle et en théorie de la planification. Chaque intervalle représente une demande pour une ressource (telle qu'une unité de traitement d'un système informatique distribué ou une salle d'une classe) pour une période de temps spécifique. La recherche du stable maximum du graphe correspond à la meilleure allocation de ressources pouvant être réalisée sans conflits^[1]. Une coloration optimale des sommets du graphe d'intervalles représente une affectation de ressources qui couvre toutes les demandes avec le moins de ressources possible.

La recherche d'un ensemble d'intervalles qui représente un graphe d'intervalle permet d'assembler des séquences contigües d'ADN^[2]. L'étude des graphes d'intervalles a d'ailleurs été motivé en partie par les études biologiques de Seymour Benzer^[3]^,^[4].

Propriétés

Le théorème de Gilmore et Hoffman montre qu'un graphe d'intervalles est un graphe cordal (donc un graphe parfait) dont le graphe complémentaire est un graphe de comparabilité^[5]^,^[6]. La relation de comparabilité est précisément l'ordre d'intervalle (en).

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

Les graphes d'intervalles connexes sans triangle sont exactement les graphes chenilles^[7].

Du fait qu'un graphe est un graphe d'intervalles si et seulement s'il est cordal et que son graphe complémentaire est un graphe de comparabilité, il s'ensuit que le graphe et son complément sont tous deux des graphes d'intervalles si et seulement si le graphe est à la fois un graphe scindé et un graphe de permutation.

Aspects algorithmiques

Algorithmes efficaces de reconnaissance

Déterminer si un graphe $G=(V,E)$ donné est un graphe d'intervalles peut être décidé avec une complexité en temps $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'intervalles 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\leq j\leq k.$

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

Problèmes restreints à la classe

De nombreux problèmes NP-complets sur les graphes quelconques admettent 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^[11] et le problème du chemin hamiltonien^[12]^,^[13].

Notes et références

↑ (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, n^o 5,‎ 2001, p. 1069-1090 (DOI 10.1145/502102.502107, lire en ligne)
↑ (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, n^o 3,‎ 1994, p. 309-317 (DOI 10.1093/bioinformatics/10.3.309)
↑ Seymour Benzer, « On the Topology of the Genetic Fine Structure », Proceedings of the National Academy of Sciences of the USA, vol. 11, n^o 45,‎ 1959, p. 1607-1620.
↑ Mark Muldoon, « Discrete Maths, Coursework », sur Université de Manchester, 2016
↑ Paul C. Gilmore et Alan J. Hoffman, « A characterization of comparability graphs and of interval graphs », Canad. J. Math, vol. 16, n^os 539-548,‎ 1964, p. 4
↑ Martin Aigner, Graphs and Partial orderings, Université de Caroline du Nord, octobre 1968 (lire en ligne)
↑ Jürgen Eckhoff, « Extremal interval graphs », Journal of Graph Theory, vol. 17, n^o 1,‎ 1993, p. 117–127 (DOI 10.1002/jgt.3190170112).
↑ (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
↑ (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)
↑ Martin Charles Golumbic (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, (ISBN 0-12-289260-7)
↑ Kellogg S. Booth et George S. Lueker, « A linear time algorithm for deciding interval graph isomorphism », Journal of the ACM, vol. 26, n^o 2,‎ 1979, p. 183-195 (DOI 10.1145/322123.322125).
↑ J Mark Keil, « Finding Hamiltonian circuits in interval graphs », Information Processing Letters, vol. 20, n^o 4,‎ 1985, p. 201-206
↑ Voir (en) « Information System on Graph Class Inclusions » pour plus d'exemples.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Interval graph » (voir la liste des auteurs).

Bibliographie

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

Liens externes

(en) « Information System on Graph Class Inclusions »
(en) Eric W. Weisstein, « Interval graph », sur MathWorld

[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, n^o 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, n^o 3,‎ 1994, p. 309-317 (DOI 10.1093/bioinformatics/10.3.309)

[3] Seymour Benzer, « On the Topology of the Genetic Fine Structure », Proceedings of the National Academy of Sciences of the USA, vol. 11, n^o 45,‎ 1959, p. 1607-1620.

[4] Mark Muldoon, « Discrete Maths, Coursework », sur Université de Manchester, 2016

[5] Paul C. Gilmore et Alan J. Hoffman, « A characterization of comparability graphs and of interval graphs », Canad. J. Math, vol. 16, n^os 539-548,‎ 1964, p. 4

[6] Martin Aigner, Graphs and Partial orderings, Université de Caroline du Nord, octobre 1968 (lire en ligne)

[Eckhoff1993-7] Jürgen Eckhoff, « Extremal interval graphs », Journal of Graph Theory, vol. 17, n^o 1,‎ 1993, p. 117–127 (DOI 10.1002/jgt.3190170112).

[8] (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

[9] (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)

[10] Martin Charles Golumbic (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, (ISBN 0-12-289260-7)

[11] Kellogg S. Booth et George S. Lueker, « A linear time algorithm for deciding interval graph isomorphism », Journal of the ACM, vol. 26, n^o 2,‎ 1979, p. 183-195 (DOI 10.1145/322123.322125).

[12] J Mark Keil, « Finding Hamiltonian circuits in interval graphs », Information Processing Letters, vol. 20, n^o 4,‎ 1985, p. 201-206

[13] Voir (en) « Information System on Graph Class Inclusions » pour plus d'exemples.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]