Graphe de disques

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.

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.

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


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • 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

  • Coloration De Graphe — En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu aucun nœud du… …   Wikipédia en Français

  • Coloration de graphe — En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l utilisation d un nombre minimal de… …   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

  • Nombre chromatique — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Theoreme quatre couleurs — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Tours de Hanoï — Un modèle d une Tour d Hanoï (avec 8 disques) Étapes de la résolution du problème avec 4 disques. Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien françai …   Wikipédia en Français

  • TOPOLOGIQUES (ESPACES VECTORIELS) — La théorie des espaces normés, développée par S. Banach et ses élèves, s’est vite révélée insuffisante pour les besoins de l’analyse fonctionnelle où interviennent de nombreux espaces vectoriels munis d’une topologie qui n’est pas déduite d’une… …   Encyclopédie Universelle

  • SYSTÈMES DYNAMIQUES DIFFÉRENTIABLES — Sans doute née avec le mémoire que Poincaré écrivit en 1881 «sur les courbes définies par des équations différentielles», où l’étude quantitative (analytique) locale des équations différentielles dans le champ complexe est remplacée par leur… …   Encyclopédie Universelle

  • phonographe — [ fɔnɔgraf ] n. m. • 1877; de phono et graphe 1 ♦ Anciennt Appareil constitué d un récepteur, d un enregistreur et d un reproducteur des sons ou de la voix. Phonographes à cylindre, à pavillon. 2 ♦ (déb. XXe) Appareil acoustique reproduisant les… …   Encyclopédie Universelle

Share the article and excerpts

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