Почему важен диаметр случайного графа?
Я вижу, что диаметр графа, определяемый как длина самого длинного кратчайшего пути, является нетривиальной величиной в случайном графе, например, случайном графе.$G(n,p)$ формируется путем добавления краев между $n$ указывает независимо с вероятностью $p$.
Но что делает его таким математически значимым? Какое отношение это имеет к другим фундаментальным идеям графов? Более того, если я добавлю некоторые ограничения к графу, такие как распределение степеней или пространственные ограничения на вершины (например, случайный геометрический граф), что это повлияет на значение диаметра графа?
Ответы
Диаметр графика важен сам по себе, так же как и хроматическое число или максимальная степень. Если вы хотите, чтобы ваш граф моделировал сеть, он сообщает вам максимальное количество «переходов», которое нужно пройти, чтобы добраться от одного узла к любому другому. Если ваш граф геометрически встроен как, скажем, граф, каждое ребро которого представляет собой прямую линию длины 1, то диаметр (абстрактного) графа является верхней границей диаметра встроенного графа, рассматриваемого как подмножество$\mathbb{R}^n$.
Позволять $D$ диаметр графа, $n$ его порядок, $\Delta$ его максимальная степень и $\kappa$его возможность подключения. Некоторые общие эвристики поведения диаметра (это тенденции, а не теоремы):
- Если граф имеет небольшой диаметр и много вершин, тогда он должен иметь много ребер, и эти ребра должны быть распределены в некоторой степени «равномерно», чтобы никакие две вершины не находились далеко друг от друга.
- Если диаметр графа очень велик по сравнению с количеством вершин, то у графа меньше ребер.
- Аналогично предыдущим пунктам, диаметр и максимальная степень вместе ограничивают общее количество вершин, которые может иметь граф. Эвристически вы не можете получить больше вершин из графа, чем если бы вы создали дерево глубины.$D$ это примерно разветвляется $\Delta-1$раз на каждом слое, с несколькими дополнительными краями, чтобы закрыть объекты. Изучение этой границы составляет тему проблемы диаметра степеней .
- В то время как диаметр и максимальная степень ограничены $n$сверху диаметр и связность ограничивают его снизу. Граница выглядит примерно как$n \geq \kappa \cdot (D-1)$.
- Диаметр также ограничивает обхват графа. Короче говоря, если диаметр небольшой, а график содержит какой-либо цикл, он должен содержать цикл небольшой длины.
Наконец, диаметр действует как хорошее ограничение сложности. Если вы пытаетесь изучить какую-либо структуру или функцию в общих графах и безнадежно теряетесь, часто бывает полезно рассмотреть, что происходит в графах диаметра 2 (особенно с учетом некоторых других ограничений или ограниченного класса графов). Это делает весьма случайным то, что почти все графы имеют диаметр 2!