图论相关概念
- 一、基本概念
- 二、图与子图
- 三、度的相关定理
- 四、一个常用的证明方法
- 五、途径、迹、路
- 六、圈
一、基本概念
- 区别于集合：边集可以重复
- G = （V，E），教材中的另一个对应关系的参数不重要
- V(G) 顶点集
- E(G) 边集合
- 关联：指顶点与边相连
- 相邻：点与点 边与边
- 重边：
- 有限图：边数顶点数都是有限的图
- 平凡图：顶点只有一个的图：不一定没有边，环也有可能
- 简单图：不含重边和环的图
- 平面图：可以用画在纸上的图，且各条边只在顶点处相交
- 同构：边与点数目相同，对应关系相对而言相同，即不做标记的图可以是同构，只是记号改变的图
- 完全图：每个顶点都与其他顶点相连
- 二部图：顶点集合分成两部分
- 完全二部图：顶点集合分成两部分，每一部分中的顶点都与另一部分中的任何一个顶点相连
二、图与子图
关联矩阵与邻接矩阵
M ( G ) = [ m i j ] M(G)=[m_{ij}] M(G)=[mij] v i 与 e j 关 联 次 数 v_i与e_j关联次数 vi与ej关联次数 环为2
A ( G ) = [ G i j ] A(G)=[G_{ij}] A(G)=[Gij] a i j 表 示 v i 与 v j 相 关 联 的 次 数 a_{ij}表示v_i与v_j相关联的次数 aij表示vi与vj相关联的次数
三、度的相关定理
∑ v ∈ V d G ( v ) = 2 ϵ \sum_{v\in V}d_G(v)=2\epsilon ∑v∈VdG(v)=2ϵ
环算两条边
δ ( G ) 最 小 度 \delta(G)最小度 δ(G)最小度
Δ ( G ) 最 大 度 \Delta(G)最大度 Δ(G)最大度
δ ( G ) = Δ ( G ) = k \delta(G)=\Delta(G)=k δ(G)=Δ(G)=k 称为k正则图
四、一个常用的证明方法
介绍一个常用的证明方法：贡献法
左边变化等于右边变化则证明相等，有点类似与归纳法
证明： ∑ v ∈ V d G ( v ) = 2 ϵ \sum_{v\in V}d_G(v)=2\epsilon ∑v∈VdG(v)=2ϵ
可以一开始取 ϵ = 1 \epsilon=1 ϵ=1 显然等式成立，然后变化的时候两个等式相同即证明等式成立
推论：在任何图中，奇度点个数总等于偶数
这个比较容易证明，考虑以下等式即可证明
V 1 → 奇 度 V_1\rightarrow 奇度 V1→奇度
V 2 → 偶 度 V_2\rightarrow 偶度 V2→偶度
∑ v ∈ V 1 d ( v ) + ∑ v ∈ V 2 d ( v ) = ∑ v ∈ V d ( v ) \sum_{v\in V_1}d(v)+\sum_{v\in V_2}d(v)=\sum_{v\in V}d(v) ∑v∈V1d(v)+∑v∈V2d(v)=∑v∈Vd(v)
五、途径、迹、路
途径：点边交替出现的序列，点边都是可以重复的
w = v 0 e 1 v 1 e 2 . . . e k v k w=v_0 e_1 v_1 e_2 ...e_k v_k w=v0e1v1e2...ekvk
简单图中 w w w 的顶点序列可以唯一确定一条途径，所以可以省略边不写
迹： w w w 中边互不相同
路： w w w 中的点互不相同当然边肯定也互不相同
途径一定会包括路和迹
迹和路一定是途径而途径不一定是路和迹
六、圈
一条起点和内部顶点互不相同的闭迹
定理：
一个圈是二部图当且仅当它不包含奇圈
本文链接：https://my.lmcjl.com/post/13871.html
4 评论