[图论]哈尔滨工业大学（哈工大 HIT）学习笔记32-39

视频来源：6.1.1 树的定义_哔哩哔哩_bilibili

目录

1. 树的定义

2. 树的性质

3. 极小连通图

4. 树的中心

5. 生成树

6. 最小生成树

7. 割点

8. 割点的性质

---

1. 树的定义

（1）定义：一个连通的无圈的图称为树

（2）平凡树：只有一个顶点的树

（3）推论1：非平凡树至少有两个叶子（？）

（4）推论2：树是双图

2. 树的性质

（1）定理1：若有G（V，E），且G是个（p，q）图，以下命题等价

        ①G是树

        ②G中任意两个顶点间有唯一的路

        ③G连通，p=q+1

        ④G中无圈，p=q+1

        ⑤G中无圈，且G中任意两个不邻接顶点间加一条边得到一个有唯一圈的图

（2）假设对少于p个顶点且满足（1）②的图，p=q+1成立，则G是一个（p，q）图。从G中去掉一条边得到两个支G1=（p1，q1）和G2=（p2，q2）

3. 极小连通图

（1）定义：树的等价定理，去掉一条边就不连通了

（2）定理1：G是树G是极小连通图

4. 树的中心

（1）有树G=（V，E），偏心率 （即距离中最大的为偏心率）

（2）半径有 

（3）中心 

（4）树的中心要么是一个要么是两个（以下为两个中心性的情况）

5. 生成树

（1）定义：图G的一个生成子图如果是树，则称其为生成树

（2）定理：一个图有生成树图是连通图（证明方式：破圈法）

6. 最小生成树

（1）最小的带权生成树，即边的权值最小

（2）算法：普里姆、克鲁斯卡尔等

7. 割点

（1）定义： 有图G=（V，E）,v∈V，若G-v的分支数大于G的分支数，则称v为G的一个割点

（2）有割点的图一定不是哈密顿图

（3）每个非平凡图至少有两个顶点不是割点

8. 割点的性质

（1）v是割点

（2） , u,w间的所有路通过v

（3）存在 的一个划分 ，使得，u,w之间的路均通过v

（4）割点桥： 有图G=（V，E）,x∈E，若G-x的分支数大于G的分支数，则称x为G的一个桥

（5）桥不在任何圈上