博客

离散数学·欧拉图、哈密顿图、无向树和生成树

  • Post author:
  • Post category:其他




欧拉图

在这里插入图片描述

简而言之——欧拉图就是边不能重复（点可以），还要有回路的图（可以类比成能否用一条线画完这个图，且线经过的路是不重复的）

半欧拉图就是非欧拉图（有欧拉通路，但没有欧拉回路：能经过所有的边，但最后回不到起点）

在这里插入图片描述

有向图的话就要注意一下，方向



定理

在这里插入图片描述


欧拉图要求所有顶点都是偶数度

，也比较容易明白：当出现奇数度顶点时，没办法抵消掉，所以一定会出现一条边走过2次

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述



哈密顿图

在这里插入图片描述

经过所有点，并且点不重的回路



定理

在这里插入图片描述

p(G-V’)指连通分支数


这个定理相对来说比较重要一些：用来判定非哈密顿图



看看，理解一下


在这里插入图片描述

这里是半哈密顿图，所以+1


注意以上2个定理都是无向



以上都为必要条件


在这里插入图片描述


充分条件


在这里插入图片描述



例

在这里插入图片描述



无向树

在这里插入图片描述


连通无回路——树



性质

在这里插入图片描述


m=n-1



例

在这里插入图片描述

在这里插入图片描述

证明较简单，看看就行了

在这里插入图片描述

握手定理

∑d(v)=2m=2(n-1)（仅限于树有2(n-1)）



生成树

在这里插入图片描述

生成子图——点集与原来的图点集一样

图G，T是G的生成子图，并且T是树。那么T是生成树

2023.2.12复习



定理

在这里插入图片描述

印象中这个定理用得好像还挺多的

无向图G连通当且仅当有生成树

在这里插入图片描述

在这里插入图片描述

这个证明可以浅看一下

在这里插入图片描述



基本回路

在这里插入图片描述

简而言之——生成树+一条弦得到的图中有一个圈（

小圈就行

不一定需要生成树所有的边

2023.2.12复习

），就称为基本回路


基本回路系统数量m-n+1



求基本回路系统时，枚举每条边来求



每条弦对应唯一



基本割集系统

在这里插入图片描述

割集是对G来说的

简而言之——只能有一条树枝，其余全是弦（但不是所有的弦）


基本割集系统数量n-1



每条树枝对应唯一



例

在这里插入图片描述

C表示圈（一部分或者全部树枝+1条弦）

S表示割集（一部分或者全部弦+1条树枝）



G的生成树的个数

在这里插入图片描述


这个符号是生成树个数的意思


2023.2.12复习


G\e表示在G中收缩e

G-e就是删掉e这条边

在这里插入图片描述

不连通——生成树个数为0


收缩的意思就是将这条边变为透明的，但是其仍然存在。或者说，理解为字面意思“收缩”，将这条边收缩至无法可视，并且边关联的点也因为边的收缩而产生移位、重合


收缩完之后，

平行边要保留



练习（作业）



3

在这里插入图片描述

在这里插入图片描述

比较经典的题目，难度不大，但充分利用了握手定理，值得看看



5

在这里插入图片描述


标准答案：


在这里插入图片描述


我的答案：


在这里插入图片描述

没什么好说的，比较正常的一道证明题，难度不大



12

在这里插入图片描述


标准答案


在这里插入图片描述


我的答案


在这里插入图片描述

在这里插入图片描述

题目意思也表示很难，但是证明过程值得一看


版权声明：本文为qq_61786525原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。