Graphe d'intervalle

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

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.

Définition formelle

Soient

I_{1}, I_{2}, \dots, I_{n} \subset R

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

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

{I_{α}, I_{β}} \in E ⟺ I_{α} \cap I_{β} \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.

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.

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}, \dots, 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'interval en temps linéaire, dû à Booth et Lueker est basé sur un arbre PQ (en) complexe, mais Habib et al 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 son graphe complémentaire est un graphe de comparabilité.