树和生成结构
树是连通无环图，而生成结构则从更大的图中提取出这种最小连通骨架。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
树是无环的连通图；连通图的生成树是其一个子图，该子图是一棵树并包含图中的每个顶点。
Scope
本主题涵盖了树的等价特性、有根树和带标号树、生成树和生成森林，以及通过凯莱公式和矩阵树定理进行的枚举。它还介绍了最小生成树作为优化问题，将图论与算法设计和组合枚举联系起来。
Core questions
- 哪些等价条件可以将图表征为一棵树？
- 给定数量的顶点，有多少种带标号树？
- 给定图包含多少棵生成树？
- 如何有效地找到总权重最小的生成树？
Key concepts
- 无环连通图
- 有根树和带标号树
- 生成树和生成森林
- 普吕弗序列
- 凯莱公式
- 最小生成树
Key theories
- 凯莱公式
- 在n个顶点上恰好有n^(n-2)个不同的带标号树，这是一个经典的枚举结果，可以通过普吕弗序列、矩阵树定理或几种优雅的双射来证明。
- 矩阵树定理
- 图的生成树数量等于其拉普拉斯矩阵的任意一个余子式，将生成树的组合计数与线性代数和行列式联系起来。
Clinical relevance
生成树是网络设计和广播路由的基础，最小生成树解决了成本最低的连接问题，而树结构则在整个计算机科学中组织数据和层次结构。
History
基尔霍夫在19世纪对电路网络的研究产生了矩阵树定理，而凯莱在1889年对带标号树的计数则成为枚举图论中最著名的公式之一。
Key figures
- Arthur Cayley
- Gustav Kirchhoff
- Heinz Prufer
Related topics
Seminal works
- diestel2017
- stanley2011
Frequently asked questions
- 为什么n个顶点的树恰好有n-1条边？
- 树是连通的，这至少需要n-1条边，并且是无环的，这排除了更多的边；这两个条件共同将边的数量精确地限定在n-1条。
- 生成树有什么用？
- 生成树提供了一组最小的连接，以保持网络连通，这是高效广播和最低成本网络设计的基础。