概念

图与树

有向图/无向图刻画不对称/对称关系；树是边数最少的连通图，森林与生成树是树在一般图上的延伸，广泛用于数据结构。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

已是本主题的起点

图与树图论

01定义

图

G=(V,E)

由顶点与边组成，是最通用的关系模型；有向图刻画不对称关系，无向图刻画对称关系。树是边数最少的连通图（

n

顶点恰

n-1

条边），是数据结构与网络骨架的基本构件。

树与含圈图的对比：边数 = 顶点数 − 1 是树的身份证

邻接矩阵、邻接表、关联矩阵三种表示各擅胜场；图同构判定（GI）是复杂度理论中地位特殊的问题——既非已知 NP 完全，也未知多项式可解。

无圈连通 ⇔ 任意两点恰一条路径 ⇔ 连通且去任一边即断 ⇔ $|E|=|V|-1$ 且连通——四种定义互相等价，应用各异。

凯莱公式： $n$ 个标号顶点共有 $n^{n-2}$ 棵树（普吕弗序列双射证明）；生成树计数由基尔霍夫矩阵树定理统一处理。

\text{标号树个数}=n^{n-2}\quad(\text{凯莱})

\text{树}:\ |E|=|V|-1,\ \text{连通无圈}

欧拉 1736 年解决柯尼斯堡七桥问题开创图论；凯莱 1857 年计数化学异构体时研究树；基尔霍夫 1847 年用图分析电路——图论自诞生即面向应用。

文件系统目录、社交网络、互联网路由表、编译器语法树、数据库查询计划——一切层级与关联结构的数学底座。

生成树：n 个节点的连通无环骨架逐步加边：树的边数恒为 n−1

step 已加边数0