|
Édition du: 09/02/2026 |
|
INDEX |
GRAPHES |
||
Faites
un double-clic pour un retour en haut de
page
|
Diamètre d'un graphe On connaît les |
||
|
|
Sommaire de cette page >>> Opti |
Débutants Glossaire |
Anglais: Diameter
(graph theory) or width
|
Définitions |
||
|
Graphe (graph) |
Exemple
|
|
|
Longueur du graphe |
Quantité d'arêtes L = 8 |
|
|
Taille du graphe (graph size) – Q |
Quantité de sommets Q = 7 |
|
|
Matrice des distances |
Tableau en i et j donnant toutes les distances
entres les nœuds. La matrice est évidemment symétrique autour de la
diagonale descendante.
|
|
|
Excentricité (eccentricity) |
La plus grande distance entre ce sommet et
n’importe quel autre sommet du graphe.
|
|
|
Rayon (radius) – R |
La plus petite excentricité (non nulle) parmi
tous les sommets. R = 1 |
|
|
Diamètre (diameter) – D |
La plus grande distance entre deux sommets du
graphe (ou la plus grande excentricité). D = 4 |
|
|
Centre (center) |
L’ensemble des sommets dont l’excentricité est
minimale (ceux qui réalisent le rayon).
|
|
|
Périphérie (periphery) |
L’ensemble des sommets dont l’excentricité est
maximale (ceux qui réalisent le diamètre).
|
|
|
Vecteur d'excentricité
(eccentricity vector) |
La liste des excentricités de tous les sommets du
graphe. |
|
|
Exemples |
||
|
À gauche Sur ce graphe, le chemin le plus long (jaune à
rouge) fait le tour et compte 9 arêtes. À droite Sur ce graphe les chemins de jaune à rouge nécessitent un minimum de quatre arêtes |
|
|
|
À gauche: graphe simple Sur ce graphe (bleu) À droite: graphe pondéré Sur ce graphe (bleu) |
|
|
|
Minimiser le
diamètre |
||
|
Cas du carré Le diamètre minium est D = 1 à condition de
joindre tous les sommets entre eux (cad: former un graphe complet). Dans ce cas la longueur du graphe est maximale: Généralisation Pour un nombre quelconque de sommets k, seul le
graphe complet minimise le diamètre (D = 1). En revanche, il maximise la longueur
du graphe: |
|
|
|
Point intermédiaire Si l'on admet la construction de points
intermédiaires, diamètre et longueur sont nettement à la baisse:
|
|
|
Voir suite en Minimiser les réseaux
|
Types de
problèmes |
||
|
|
|
|
|
|
||
|
An On |
||
|
Problème |
Objectif |
|
Minimisation du diamètre |
Réduire la plus longue distance entre deux sommets |
|
Minimisation du rayon |
Réduire la distance maximale depuis un sommet central |
|
Spanner de stretch (t) |
Construire un sous-graphe où toutes les distances sont
≤ (t \cdot d(u,v)) |
|
Arbre couvrant de faible diamètre |
Trouver un arbre couvrant avec diamètre minimal |
|
Centre du graphe |
Trouver le sommet minimisant la distance maximale aux
autres |
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
