« Graphe (mathématiques discrètes) » : différence entre les versions
Contenu supprimé Contenu ajouté
bot : révocation de Pamela.Alam (erreur : -50), retour à la version 159110325 de Nyancat90 |
Propriétés de Centralités d'un graphe |
||
Ligne 154 :
Un graphe est ''étiqueté aux sommets'' si chaque sommet porte une étiquette. Un graphe est ''étiqueté aux arêtes'' si chaque arête porte une étiquette. On peut considérer, dans les problèmes d'énumération ou de bijection, des graphes étiquetés ou non étiquetés. Un graphe dont les sommets (ou les arêtes) sont étiquetés par des couleurs est un graphe coloré.
== Propriétés de Centralités d'un graphe[modifier | modifier le code] ==
La centralité est une mesure importante dans l'analyse de graphe. Elle mesure la pertinence et l'importance d'un sommet (ou nœud) dans un réseau.
La centralité de degrés est simplement définie comme le nombre d'arêtes incidentes à un sommet.
La centralité de proximité est définie par la somme inverse des distances les plus courtes par rapport à tous les autres sommets accessibles depuis ce sommet i.
La centralité d'intermédiarité évalue le degré auquel un sommet i se situe sur les chemins les plus courts entre deux autres paires de sommets j et k. La centralité d'intermédiarité du sommet i est définie par le nombre total de chemins les plus courts passant par ce sommet i.[[Utilisateur:Pamela.Alam/Brouillon#cite%20note-1|1]]
L'excentricité e(v), d'un sommet v dans un graphe connexe est la distance maximale d(v, u) pour tout sommet u. [[Utilisateur:Pamela.Alam/Brouillon#cite%20note-2|2]]
Le diamètre d’un graphe est l’excentricité maximale des sommets (c’est-à-dire la distance maximale entre deux sommets).
Le rayon d'un graphe est l'excentricité minimale des sommets (c’est-à-dire la distance minimale entre deux sommets).
== Opérations sur les graphes ==
| |||