Ê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 GraphSearch.
Concept
Densité d'un graphe
Résumé
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
La densité d'un graphe est définie par le rapport entre le nombre d'arêtes (ou d'arcs) divisé par le nombre d'arêtes (ou d'arcs) possibles.
Dans le cas d'un graphe non orienté simple , la densité est le rapport :
Le numérateur compte le nombre d'arêtes existantes et le multiplie par deux, étant donné que chaque arête est liée à une paire de sommets. Le dénominateur dénombre le total d'arêtes nécessaires pour que chaque sommet soit relié à tous les autres (complétude). On calcule et non , car, dans un graphe simple, les arêtes relient deux sommets différents.
La densité 0 correspond au graphe où tous les sommets sont isolés, et la densité 1 au graphe complet.
Une mesure de la densité d'un graphe est l'arboricité qui compte le nombre minimal de forets nécessaires pour couvrir le graphe. On peut aussi utiliser la dégénérescence.
La notion de densité apparaît en combinatoire, notamment dans le lemme de régularité de Szemerédi.
Les structures de données utilisées pour représenter des graphes peuvent être adaptées à la densité du graphe. En particulier, les graphes denses sont plutôt représentés par des matrices d'adjacence, alors que les graphes creux sont mieux représentés par des listes d'adjacence.
Certains algorithme sont construits pour être efficaces sur les graphes d'une certaine densité, et sont plutôt mauvais si on les utilise sur des graphes quelconques. On parle typiquement d'algorithmes pour les graphes denses ou pour les graphe creux.
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.
Publications associées (1)
Concepts associés (21)
Graphe orienté
thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
Densité d'un graphe
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
Dégénérescence (théorie des graphes)
En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.
Cours associés (10)
CS-455: Topics in theoretical computer science
The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of f
MATH-360: Graph theory
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
Séances de cours associées (57)
Famille ExponentielleCOM-406: Foundations of Data Science
Couvre le concept de la famille exponentielle et discute des cartes en avant et en arrière, des calculs coûteux, des paramètres, des fonctions et de la convexité.
Modèle de bloc stochastique: Détection communautairePHYS-467: Machine learning for physicists
Couvre le modèle de bloc stochastique pour la détection communautaire.
Ergodicity unique pour les foliations génériques
Explore une ergonomie unique pour les foliations génériques sur les surfaces de Kähler.