图论ch2树思维导图

参考教材：邦迪《图论及其应用》，包含了树、割边和键、割点、应用等内容，知识全面，干货满满，需要可收藏。

ch2：树

• 1. 树
  • 定义：不包含圈的图称为无圈图，连通的无圈图称为树
  • 定理2.1：在一棵树中，任意两个顶点均有唯一的路连接 证明：反证法
  • 定理2.2：若G是树，则epsilon=v-1（边数=顶点数-1） 证明：归纳法
    • 推论2.2：每棵平凡树至少有两个一度顶点
• 2. 割边和键
  • 割边：去掉这个边就可以把图变成不连通的两部分 定义：割边指的是omega(G-e)>omega(G)的边e
  • 定理2.3：e是G的割边当且仅当e不包含在G的一个圈中
  • 定理2.4：一个连通图是树当且仅当每条边都是割边
    • 推论2.4.1：每个连通图都包含生成树
  • 定理2.5：设T是连通图G的生成树，且e是G的不在T中的一条边，则T+e包含唯一的圈
  • 定义：边割、键
    • 边割（集）：去掉边割集中的边，会增加图的联通分支（分成不联通的多部分），边割集可能有多个
    • 键：极小边割集即为键
  • 定理2.6：设T是联通图G的生成树，e是T的任一边，则：
    • 1、余树$\overline{T}$不包含G的键（余树本身是不联通的，不含边割集）
    • 2、$\overline{T}+e$包含G的唯一的键
• 3. 割点
  • 定义：去掉割点图将分裂为多部分
  • 定理2.7：设v是树G的顶点，则v是G的割点当且仅当d(v)>1
    • 推论2.7：每个非平凡的连通图，至少有两个不是割点的顶点
  • 定理2.8（cayley公式）：若e是G的一条边，则$\tau(G)=\tau(G-e)+tau(G*e)$
  • 定理2.9：$\tau(K_n)=n^{n-2}$
• 4. 应用
  • Kruskal算法（避圈法）
  • 定理2.10：Kruskal算法构造的任何生成树$T*=G[{e_1,e_2,...,e_{v-1}]都是最优树