Distance (théorie des graphes) - Distance (graph theory)

Dans le domaine mathématique de la théorie des graphes , la distance entre deux sommets d'un graphe est le nombre d'arêtes d'un chemin le plus court (également appelé graphe géodésique ) les reliant. Ceci est également connu sous le nom de distance géodésique ou distance du chemin le plus court . Notez qu'il peut y avoir plus d'un chemin le plus court entre deux sommets. S'il n'y a pas de chemin reliant les deux sommets, c'est-à-dire s'ils appartiennent à des composantes connexes différentes , alors conventionnellement la distance est définie comme infinie.

Dans le cas d'un graphe orienté, la distance entre deux sommets et est définie comme la longueur d'un chemin dirigé le plus court de à constitué d'arcs, à condition qu'au moins un tel chemin existe. Notez que, contrairement au cas des graphes non orientés, ne coïncide pas nécessairement avec — il s'agit donc simplement d'une quasi-métrique , et il se peut que l'un soit défini alors que l'autre ne l'est pas. ${\style d'affichage d(u,v)}$${\mode d'affichage u}$${\style d'affichage v}$${\mode d'affichage u}$${\style d'affichage v}$${\style d'affichage d(u,v)}$${\style d'affichage d(v,u)}$

Concepts associés

Un espace métrique défini sur un ensemble de points en termes de distances dans un graphe défini sur l'ensemble est appelé métrique de graphe . L'ensemble de sommets (d'un graphe non orienté) et la fonction de distance forment un espace métrique, si et seulement si le graphe est connexe .

L' excentricité d'un sommet est la plus grande distance entre et tout autre sommet ; en symboles c'est . Cela peut être considéré comme la distance entre un nœud et le nœud le plus éloigné de lui dans le graphe. ${\style d'affichage \epsilon (v)}$${\style d'affichage v}$${\style d'affichage v}$${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u)}$

Le rayon d'un graphique est l'excentricité minimale de tout sommet ou, en symboles, . ${\style d'affichage r}$${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)}$

Le diamètre d'un graphique est l'excentricité maximale de n'importe quel sommet du graphique. C'est-à-dire, est la plus grande distance entre n'importe quelle paire de sommets ou, alternativement, . Pour trouver le diamètre d'un graphe, trouvez d'abord le chemin le plus court entre chaque paire de sommets . La plus grande longueur de n'importe lequel de ces chemins est le diamètre du graphique. ${\style d'affichage d}$${\style d'affichage d}$${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u)}$

Un sommet central dans un graphe de rayon est celui dont l'excentricité est — c'est-à-dire un sommet qui atteint le rayon ou, de manière équivalente, un sommet tel que . ${\style d'affichage r}$${\style d'affichage r}$${\style d'affichage v}$${\displaystyle \epsilon (v)=r}$

Un sommet périphérique dans un graphique de diamètre est celui qui est éloigné d'un autre sommet, c'est-à-dire un sommet qui atteint le diamètre. Formellement, est périphérique si . ${\style d'affichage d}$${\style d'affichage d}$${\style d'affichage v}$${\displaystyle \epsilon (v)=d}$

Un sommet pseudo-périphérique a la propriété que pour tout sommet , si est aussi éloigné que possible, alors est aussi éloigné que possible. Formellement, un sommet u est pseudo-périphérique, si pour chaque sommet v avec détient . ${\style d'affichage v}$${\mode d'affichage u}$${\style d'affichage v}$${\mode d'affichage u}$${\mode d'affichage u}$${\style d'affichage v}$${\displaystyle d(u,v)=\epsilon (u)}$${\displaystyle \epsilon (u)=\epsilon (v)}$

La partition des sommets d'un graphe en sous-ensembles par leurs distances à partir d'un sommet de départ donné est appelée une structure de niveau du graphe.

Un graphe tel que pour chaque paire de sommets il y a un chemin le plus court qui les relie est appelé un graphe géodésique . Par exemple, tous les arbres sont géodésiques.

La distance pondérée du plus court chemin généralise la distance géodésique aux graphes pondérés . Dans ce cas, on suppose que le poids d'une arête représente sa longueur ou, pour les réseaux complexes, le coût de l'interaction, et la distance pondérée du plus court chemin est la somme minimale des poids sur tous les chemins reliant et . Voir le problème du plus court chemin pour plus de détails et d'algorithmes. ${\displaystyle d^{W}(u,v)}$${\mode d'affichage u}$${\style d'affichage v}$

Algorithme pour trouver des sommets pseudo-périphériques

Souvent, les algorithmes matriciels clairsemés périphériques ont besoin d'un sommet de départ avec une excentricité élevée. Un sommet périphérique serait parfait, mais est souvent difficile à calculer. Dans la plupart des cas, un sommet pseudo-périphérique peut être utilisé. Un sommet pseudo-périphérique peut être facilement trouvé avec l'algorithme suivant :

1. Choisissez un sommet .${\mode d'affichage u}$
2. Parmi tous les sommets les plus éloignés possible, soit un de degré minimal .${\mode d'affichage u}$${\style d'affichage v}$
3. Si ensuite défini et répétez avec l'étape 2, sinon est un sommet pseudo-périphérique.${\displaystyle \epsilon (v)>\epsilon (u)}$${\style d'affichage u=v}$${\mode d'affichage u}$

Voir également

Remarques