Pourquoi le diamètre d'un graphe aléatoire est-il important ?

Aug 17 2020

Je peux voir que le diamètre d'un graphe, défini comme la longueur du plus long chemin le plus court, est une quantité non triviale dans un graphe aléatoire , par exemple le graphe aléatoire$G(n,p)$formé en ajoutant des bords entre$n$points indépendamment avec probabilité$p$.

Mais qu'est-ce qui le rend si mathématiquement significatif? Quelles relations a-t-il avec les autres idées fondamentales de graphe ? De plus, si j'ajoute une contrainte sur le graphique, telle que la distribution des degrés ou des contraintes spatiales sur les sommets (c'est-à-dire un graphique géométrique aléatoire), qu'est-ce que cela fait à la signification du diamètre du graphique?

Réponses

5 BrandonduPreez Aug 17 2020 at 23:01

Le diamètre du graphe est important en soi, de la même manière que le nombre chromatique ou le degré maximum. Si vous voulez que votre graphique modélise un réseau, il vous indique le nombre maximum de "sauts" qu'il faut effectuer pour passer d'un nœud à un autre. Si votre graphique est intégré géométriquement comme, par exemple, un graphique où chaque arête est une ligne droite de longueur 1, alors le diamètre du graphique (abstrait) est une limite supérieure sur le diamètre du graphique intégré, considéré comme un sous-ensemble de$\mathbb{R}^n$.

Laisser$D$être le diamètre d'un graphe,$n$sa commande,$\Delta$son degré maximum et$\kappa$sa connectivité. Quelques heuristiques générales sur le comportement du diamètre (ce sont des tendances, pas des théorèmes):

  • Si un graphe a un faible diamètre et de nombreux sommets, alors il doit avoir de nombreuses arêtes, et ces arêtes doivent être distribuées de manière quelque peu «uniforme» afin de ne pas permettre à deux sommets d'être éloignés.
  • Si le diamètre du graphe est très grand par rapport au nombre de sommets, alors le graphe a moins d'arêtes.
  • Dans la même veine que les points ci-dessus, le diamètre et le degré maximum limitent ensemble le nombre total de sommets qu'un graphe peut avoir. Heuristiquement, vous ne pouvez pas obtenir plus de sommets d'un graphe que si vous créez un arbre de profondeur$D$qui se ramifie à peu près$\Delta-1$fois à chaque couche, avec quelques bords supplémentaires pour fermer les choses. L'étude de cette borne est le sujet du problème du degré de diamètre .
  • Alors que le diamètre et le degré maximum sont liés$n$d'en haut, le diamètre et la connectivité l'ont lié d'en bas. La limite ressemble à peu près à$n \geq \kappa \cdot (D-1)$.
  • Le diamètre contraint également la circonférence du graphique. En bref, si le diamètre est faible et que le graphe contient un cycle quelconque, il doit contenir un cycle de courte longueur.

Enfin, le diamètre agit comme une belle contrainte de complexité. Si vous essayez d'étudier une structure ou une caractéristique dans des graphes généraux et que vous vous perdez désespérément, il est souvent utile de considérer ce qui se passe dans les graphes de diamètre 2 (en particulier compte tenu d'une autre contrainte ou d'une classe de graphe restreinte qui va avec). Ce qui rend assez fortuit le fait que presque tous les graphes ont un diamètre de 2 !