图论学习（三）

途径，迹，路，圈，距离和直径

定义：给定图G = (V, E)，w =v0e1v1e2…ekvk是G中点边交替组成的序列，其中vi∈V，ei∈E，若w满足ei的端点为vi-1与vi，则称w为一条从顶点v0到顶点vk的途径（或通道或通路)，简称(v0, vk)途径。

顶点v0和vk分别称为w的起点和终点，其它点称为内部点，途径中的边数为它的长度。

在简单图中，途径可以简单地由其它顶点序列来表示。
边不重复的途径称为迹，点不重复的迹称为路。
起点和终点相同的途径、迹和路分别称为闭途径、闭迹、圈，闭途径称为环游，闭迹称为回路。

长度为k的圈称为k圈，k为奇数时称为奇圈，k为偶数时称为偶圈。自环是长度为1的圈。3圈常称为三角形。

若图中两个不同点u与v之间必存在途径，则u与v间必存在路。
若过点u存在闭迹，则过点u存在圈。

若过点u存在闭途径，则过点u不一定存在圈。

联结u和v长度最短的路的长度，称为u与v的距离，记为d(u,v)。
图G的直径定义为 d(G) = max{ d(u, v) | u, v∈V }。
在这里插入图片描述

图的连通性

如果图G中u与v间存在途径，则图G中u与v是连通的。否则称u与v不连通。

如果图G中任意两点是连通的，称G是连通图，否则称G是非连通图。在图中，每一个极大的连通部分称为连通分支。G的连通分支的个数，称为G的分支数，记为ω(G)。
在这里插入图片描述
证明：在n阶连通图中，

至少有n-1条边；
如果边数大于n-1，则至少有一个圈。

（1）对G的顶点数作数学归纳。
当n=1,2时，结论显然成立；设结论对n=k时成立。
当n=k+1时，分两种情况讨论。
若G 中没有1度顶点，由握手定理：
在这里插入图片描述
若G中有1度顶点u，考虑G-u，它仍然为连通图，所以G-u至少含有k-1条边。
于是，G至少有k条边。

（2）对于非简单图，结论显然成立。故假设G是简单图。
任取G的一条边W0，必然存在一点u，它不在W0上，但与W0上的某一点相邻，设该点为v。
将边uv添加到W0上，得到一个包含3个点的连通子图W1。
显然，W1也满足“边数等于点数减1”。
如此不断下去，会得到一个连通的生成子图W，其边数正好等于n-1.
但由于G的边数大于n-1，因此存在两个不同的顶点x与y，它们在W中不相邻，但在G中相邻。
边xy以及W中连接x与y的路便构成一个圈。

在这里插入图片描述

若图G是不连通的，则其补图是连通图。
因G是不连通，故G中至少两个分支。
设u，v是G的任意两个顶点。

若u和v在G中不邻接，则在补图中它们邻接。
若u和v在G中邻接，则它们属于G的同一分支，在另一分支中取一定w，则在补图中u和v均与w邻接，从uwv是一条途径，故在补图中u和v连通。

非连通图的补图的直径小于等于2

设图G为n阶简单图，若G中任意两个不相邻顶点u与v满足d(u)+d(v)≥n-1，则G是连通图且d(G)≤2。
证明：我们将证明，对G中任意两点x与y，一定存在一条长度至多为2的连接x与y的路。

若x和y相邻，则上述论断成立。
若x和y不相邻，则一定存在一点w与x和y均相邻。
若不然，在G的剩下的n-2个顶点中，假设有k个与x邻接，但与y不邻接，有l个顶点和y邻接，但不与x邻接，同时假定有m个顶点与x和y均不相邻。
那么d(x)=k,d(y)=l，由于k+l+m=n-2，所以d(x)+d(y)=n-2-m≤n-2，矛盾！

偶图判定定理

定理：一个图是偶图当且仅当它不包含奇圈。
证明：一个图是偶图当且仅当每个连通分支是偶图；一个图不包含奇圈当且仅当每个连通分支不包含奇圈。因此，只需对连通图证明即可。
必要性：设G是具有二分类（X,Y）的偶图，并且C=v1v2…vkv1是G的任意一个圈。
不失一般性，可假定可假定v1∈X。这样v2i-1∈X，且v2i∈Y。又因为v1∈X，所以vk∈Y,所以k为偶数，由此可得C是偶图。
充分性：设G是不包含奇圈的连通图。任选一个顶点u且定义V 的一个分类(X, Y)如下：
X = { x | d (u, x) 是偶数，x∈V(G) }，
Y = { y | d (u, y) 是奇数，y∈V(G) }。
现在证明( X, Y )是G的一个二分类。
断言：对X中任意两点v与w，必不相邻！
在这里插入图片描述