랜덤 그래프의 지름이 중요한 이유는 무엇입니까?
가장 긴 최단 경로의 길이로 정의 되는 그래프 의 지름 이 임의의 그래프 (예 : 임의의 그래프) 에서 중요하지 않은 양임을 알 수 있습니다.$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라는 것은 매우 우연입니다!