图的三种矩阵表示
邻接矩阵 (Adjacency Matrix)
定义
n阶方阵A = (aᵢⱼ)ₙₓₙ,其中:
aᵢⱼ = 1, 若(vᵢ, vⱼ) ∈ E
aᵢⱼ = 0, 若(vᵢ, vⱼ) ∉ E
aᵢⱼ = 0, 若(vᵢ, vⱼ) ∉ E
性质
- ✓ 反映顶点间直接连接关系
- ✓ 无向图的邻接矩阵是对称矩阵
- ✓ 第i行元素之和 = 顶点vᵢ的出度
- ✓ 第j列元素之和 = 顶点vⱼ的入度
思政应用
组织架构中的直接汇报关系
可达矩阵 (Reachability Matrix)
定义
n阶方阵R = (rᵢⱼ)ₙₓₙ,其中:
rᵢⱼ = 1, 若vᵢ到vⱼ存在路径
rᵢⱼ = 0, 若vᵢ到vⱼ不存在路径
rᵢⱼ = 0, 若vᵢ到vⱼ不存在路径
性质
- ✓ 反映顶点间的间接可达关系
- ✓ 通过邻接矩阵的布尔幂运算得到
- ✓ R = A ∨ A² ∨ A³ ∨ ... ∨ Aⁿ
- ✓ 揭示图的连通性结构
思政应用
信息传递网络的覆盖范围
关联矩阵 (Incidence Matrix)
定义
n×m矩阵B = (bᵢⱼ)ₙₓₘ,其中:
bᵢⱼ = 1, 若顶点vᵢ与边eⱼ关联
bᵢⱼ = 0, 若顶点vᵢ与边eⱼ不关联
bᵢⱼ = 0, 若顶点vᵢ与边eⱼ不关联
性质
- ✓ 反映顶点与边的关联关系
- ✓ n行(顶点数) × m列(边数)的矩阵
- ✓ 每列恰有2个1(无向图)
- ✓ 便于表示超图和二分图
思政应用
任务与责任人的分配关系