Por que o diâmetro de um gráfico aleatório é importante?
Eu posso ver que o diâmetro de um gráfico, definido como o comprimento do caminho mais longo e mais curto, é uma quantidade não trivial em um gráfico aleatório , por exemplo, o gráfico aleatório$G(n,p)$formado pela adição de arestas entre$n$pontos independentemente com probabilidade$p$.
Mas o que o torna tão matematicamente significativo? Que relações ela tem com as outras ideias fundamentais de grafos? Além disso, se eu adicionar alguma restrição ao gráfico, como a distribuição de graus ou restrições espaciais nos vértices (ou seja, gráfico geométrico aleatório), o que isso faz com a significância do diâmetro do gráfico?
Respostas
O diâmetro do gráfico é significativo por si só, da mesma forma que o número cromático ou grau máximo. Se você deseja que seu gráfico modele uma rede, ele informa o número máximo de 'saltos' necessários para ir de um nó a outro. Se o seu gráfico é incorporado geometricamente como, digamos, um gráfico em que cada aresta é uma linha reta de comprimento 1, então o diâmetro do gráfico (abstrato) é um limite superior no diâmetro do gráfico incorporado, considerado como um subconjunto de$\mathbb{R}^n$.
Deixar$D$ser o diâmetro de um gráfico,$n$sua ordem,$\Delta$seu grau máximo e$\kappa$sua conectividade. Algumas heurísticas gerais de como o diâmetro se comporta (essas são tendências, não teoremas):
- Se um grafo tem diâmetro baixo e muitos vértices, ele deve ter muitas arestas, e essas arestas devem ser distribuídas de maneira um tanto 'uniforme' para não permitir que dois vértices fiquem distantes.
- Se o diâmetro do gráfico for muito grande em comparação com o número de vértices, o gráfico terá menos arestas.
- De maneira semelhante aos pontos acima, o diâmetro e o grau máximo juntos limitam o número total de vértices que um gráfico pode ter. Heuristicamente, você não pode obter mais vértices de um grafo do que se criar uma árvore de profundidade$D$que se ramifica aproximadamente$\Delta-1$vezes em cada camada, com algumas arestas extras para fechar as coisas. Estudar este limite é o tópico do problema de diâmetro de grau .
- Enquanto o diâmetro e o grau máximo são limitados$n$de cima, o diâmetro e a conectividade o limitam de baixo. O limite se parece mais ou menos com$n \geq \kappa \cdot (D-1)$.
- O diâmetro também restringe a circunferência do gráfico. Resumindo, se o diâmetro for baixo e o gráfico contiver algum ciclo, ele deverá conter um ciclo de comprimento curto.
Finalmente, o diâmetro atua como uma boa restrição de complexidade. Se você está tentando estudar alguma estrutura ou recurso em grafos gerais e está se perdendo irremediavelmente, muitas vezes é útil considerar o que acontece em grafos de diâmetro 2 (especialmente devido a alguma outra restrição ou classe de grafo restrita para acompanhá-lo). O que torna bastante fortuito que quase todos os grafos tenham diâmetro 2!