Graphe de disques

En théorie des graphes, un graphe de disques (ou disk graph en anglais) est le graphe d'intersection d'une collection de disques. C'est une extension du concept de graphe d'intervalle à la dimension 2.

Un exemple de graphe de disque-unité avec les disques correspondant.

Définition

Formellement, G est un graphe de disques s'il existe une collection de disques dans le plan dont les centres sont en bijection avec les sommets de G et telle que deux disques s'intersectent si et seulement si les sommets correspondants sont reliés par une arête dans G.

Graphe de disque-unité

Quand tous les disques ont le même diamètre, le graphe est qualifié de graphe de disque-unité (Unit-disk graph an anglais). Tout sous-graphe induit d'un graphe de disque-unité est également un graphe de disque-unité.

Applications et modélisations

Les graphes de disque peuvent par exemple représenter des réseaux d'antennes radio : les nœuds modélisent un ensemble d'émetteurs-récepteurs et ils sont reliés si deux nœud peuvent communiquer[1].

Notes et références
  1. Voir par exemple Huson et Sen 1995.

Bibliographie
  • Mark L. Huson et Arunabha Sen, « Broadcast scheduling algorithms for radio networks », dans Military Communications Conference, IEEE MILCOM '95, vol. 2, (ISBN 0-7803-2489-7, DOI 10.1109/MILCOM.1995.483546), p. 647-651.

Liens externes
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.