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

这篇具有很好参考价值的文章主要介绍了[图论]哈尔滨工业大学（哈工大 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）

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

3. 极小连通图

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

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

4. 树的中心

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

（2）半径有

（3）中心

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

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

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）桥不在任何圈上文章来源地址https://www.toymoban.com/news/detail-720741.html

到了这里，关于[图论]哈尔滨工业大学（哈工大 HIT）学习笔记32-39的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

1. 树的定义

2. 树的性质

3. 极小连通图

4. 树的中心

5. 生成树

6. 最小生成树

7. 割点

8. 割点的性质

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2