Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe d'intervalles
Résumé
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.
Etant donnés des intervalles , le graphe d'intervalle correspondant est où
et
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.
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.
L'étude des graphes d'intervalles a d'ailleurs été motivé en partie par les études biologiques de Seymour Benzer.
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é. La relation de comparabilité est précisément l'.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.