Graphe d'intervalle

Graphe d'intervalle
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 (en) 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.

Sommaire

Définition formelle

Soient

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

des intervalles. Alors, 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'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

Les graphes d'intervalle sont des graphes cordaux, donc des graphes parfaits. Leurs graphes complémentaires sont des graphes de comparabilité (en) 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.

Algorithmes efficaces de reconnaissance des graphes d'intervalle

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 si il est cordal et son graphe complémentaire est un graphe de comparabilité (en)[5].

Notes et références

  1. ↑ Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch, « A unified approach to approximating resource allocation and scheduling », dans Journal of the ACM, vol. 48, no 5, 2001, p. 1069–1090 [texte intégral, lien DOI] 
  2. ↑ Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E., « An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA », dans Bioinformatics, vol. 10, no 3, 1994, p. 309–317 [lien DOI] 
  3. ↑ Booth, K. S.; Lueker, G. S., « Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms », dans J. Comput. System Sci., vol. 13, 1976, p. 335–379 
  4. ↑ 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 », dans Theor. Comput. Sci., vol. 234, 2000, p. 59–84 [texte intégral, lien DOI] 
  5. ↑ Martin Charles Golumbic (en) (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7
  • Fulkerson, D. R.; Gross, O. A., « Incidence matrices and interval graphs », dans Pacific Journal of Mathematics, vol. 15, 1965, p. 835–855 

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe d'intervalle de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Graphe d'intervalle propre — Un graphe d intervalle qui n est pas un graphe d intervalle propre …   Wikipédia en Français

  • Graphe de disques — Un exemple de graphe de disque unité avec les disques correspondant. En théorie des graphes, un graphe de disques est le graphe d intersection d une collection de disques. C est une extension du concept de graphe d intervalle à la dimension 2.… …   Wikipédia en Français

  • Graphe De Disques — Un graphe de disques est une extension du concept de graphe d intervalles à la dimension 2. La définition est similaire en remplacant intervalle par disque , c est à dire que G est un graphe de disques s il existe une collection de disques dans… …   Wikipédia en Français

  • Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Graphe aléatoire — En mathématiques, un graphe aléatoire est un graphe qui est généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdös et Alfréd Rényi dans une série d articles publiés entre 1959 et 1968[1].… …   Wikipédia en Français

  • Graphe cordal — Un cycle, en noir, avec deux cordes, en vert. Si l on s en tient à cette partie, le graphe est cordal. Supprimer l une des arêtes vertes rendrait le graphe non cordal. En effet, l autre arête verte formerait, avec les trois arêtes noires, un… …   Wikipédia en Français

  • Lexique (graphe) — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Lexique de la théorie des graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Acyclique (grap …   Wikipédia en Français

  • Chordal graph — Graphe cordal Un cycle, en noir, avec deux cordes, en vert. Si l on s en tient à cette partie, le graphe est cordal. Supprimer l une des arêtes vertes rendrait le graphe non cordal. En effet, l autre arête verte formerait, avec les trois arêtes… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”