1. 概述
本文将介绍图的密度（Graph Density）概念，包括其定义、计算公式及在不同类型图中的应用。我们会通过具体示例帮助理解，方便在处理大规模网络结构时快速判断图的稠密程度。
2. 什么是图的密度？
图的密度用于衡量图中实际存在的边数与图中可以存在的最大边数之间的比例。它能反映图在结构上的“稠密”程度，常用于图算法优化、网络分析等场景。
2.1 最大边数计算
无向图（Undirected Graph）：不考虑自环和多重边的情况下，一个包含
n个顶点的无向图最多可以有：$$ \text{Max}_{U} = \frac{n(n - 1)}{2} $$
有向图（Directed Graph）：每个顶点可以与其他所有顶点建立两个方向的连接，因此最大边数为：
$$ \text{Max}_{D} = n(n - 1) $$
2.2 图密度公式
无向图密度：
$$ \text{DEN}_{U} = \frac{2|E|}{|V|(|V| - 1)} $$
有向图密度：
$$ \text{DEN}_{D} = \frac{|E|}{|V|(|V| - 1)} $$
其中：
|E|：图中实际存在的边数|V|：图中顶点数量
3. 特性说明
- ✅ 完全图（Complete Graph）的密度为 1，表示图中所有可能的边都已存在。
- ❌ 如果图中所有顶点都是孤立的（Isolated Vertices），即没有边存在，则密度为 0。
- ⚠️ 密度值范围在
[0, 1]之间，越接近 1 表示图越稠密。
4. 示例说明
4.1 有向图示例
如下图所示，有向图 G₂ 包含 5 个顶点、6 条边：
计算步骤：
最大边数：
$$ \text{Max}_{G_2} = 5 \times (5 - 1) = 20 $$
密度计算：
$$ \text{DEN}_{G_2} = \frac{6}{20} = 0.3 $$
4.2 无向图示例
如下图所示，无向图 G₃ 包含 6 个顶点、8 条边：
计算步骤：
最大边数：
$$ \text{Max}_{G_3} = \frac{6 \times (6 - 1)}{2} = 15 $$
密度计算：
$$ \text{DEN}_{G_3} = \frac{8}{15} \approx 0.53 $$
5. 总结
图的密度是衡量图结构稠密程度的重要指标，尤其在处理大规模网络结构时，能帮助我们快速判断是否还有添加边的空间。
- ✅ 密度公式清晰，适用于有向图和无向图。
- ✅ 完全图密度为 1，空图密度为 0。
- ✅ 示例展示了具体计算过程，便于理解与应用。
掌握图密度的计算方法，有助于提升图算法设计与网络优化的效率。