Diamètre (théorie des graphes)

En théorie des graphes , le diamètre d'un graphe non orienté connexe est la distance la plus éloignée entre deux de ses sommets. C'est-à-dire qu'il s'agit du diamètre d'un ensemble pour l'ensemble des sommets du graphe et pour la distance du plus court chemin dans le graphe. Le diamètre peut être considéré soit pour les graphes pondérés, soit pour les graphes non pondérés. Les chercheurs ont étudié le problème du calcul du diamètre, à la fois dans des graphes arbitraires et dans des classes spéciales de graphes.

Le diamètre d'un graphe déconnecté peut être défini comme infini ou indéfini.

Le problème du diamètre en degrés cherche des relations étroites entre le diamètre, le nombre de sommets et le degré d'un graphe. Une façon de le formuler est de demander le plus grand graphe avec des limites données sur son degré et son diamètre. Pour tout degré fixé, cette taille maximale est exponentielle dans le diamètre, la base de l'exposant dépendant du degré.

La circonférence d'un graphe, la longueur de son cycle le plus court, peut être au plus pour un graphe de diamètre . Les graphes réguliers pour lesquels la circonférence est exactement sont les graphes de Moore . Il n'existe qu'un nombre fini de graphes de Moore, mais leur nombre exact est inconnu. Ils fournissent les solutions au problème du diamètre en degrés pour leur degré et leur diamètre.

Les réseaux de petit monde sont une classe de graphes de faible diamètre, modélisant le phénomène réel de six degrés de séparation dans les réseaux sociaux .

Le diamètre d'un graphe peut être calculé en utilisant un algorithme de chemin le plus court pour calculer les chemins les plus courts entre toutes les paires de sommets, puis en prenant le maximum des distances qu'il calcule. Par exemple, dans un graphe avec des poids d'arêtes positifs, cela peut être fait en utilisant à plusieurs reprises l'algorithme de Dijkstra , une fois pour chaque sommet de départ possible. Dans un graphe avec des sommets et des arêtes, cela prend du temps . Le calcul des chemins les plus courts de toutes les paires est la méthode la plus rapide connue pour calculer exactement le diamètre d'un graphe pondéré.

Dans un graphe non pondéré, l'algorithme de Dijkstra peut être remplacé par une recherche en largeur , ce qui donne un temps . Alternativement, le diamètre peut être calculé en utilisant un algorithme basé sur une multiplication matricielle rapide , en temps proportionnel au temps de multiplication des matrices, en utilisant approximativement des algorithmes de multiplication matricielle connus. Pour les graphes clairsemés, avec peu d'arêtes, la recherche en largeur répétée est plus rapide que la multiplication matricielle. En supposant l' hypothèse de temps exponentiel , la recherche en largeur répétée est presque optimale : cette hypothèse implique qu'aucun algorithme ne peut atteindre le temps pour n'importe quel . $0\epsilon >0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12">

Il est possible d'approximer le diamètre d'un graphe pondéré avec un rapport d'approximation de 3/2, en temps , où la notation cache les facteurs logarithmiques dans la limite temporelle. Sous l'hypothèse du temps exponentiel, aucune approximation sensiblement plus précise, sensiblement plus rapide que toutes les paires de chemins les plus courts, n'est possible.

Le diamètre peut être calculé en temps linéaire pour les graphes d'intervalles , et en temps quasi-linéaire pour les graphes de largeur arborescente bornée . Dans les graphes médians , le diamètre peut être trouvé dans la borne de temps sous-quadratique . Dans toute classe de graphes fermés sous des mineurs de graphes , tels que les graphes planaires , il est possible de calculer le diamètre en temps sous-quadratique, avec un exposant dépendant de la famille de graphes.