定义:给定图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阶连通图中,
(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的任意两个顶点。
非连通图的补图的直径小于等于2
设图G为n阶简单图,若G中任意两个不相邻顶点u与v满足d(u)+d(v)≥n-1,则G是连通图且d(G)≤2。
证明:我们将证明,对G中任意两点x与y,一定存在一条长度至多为2的连接x与y的路。
定理:一个图是偶图当且仅当它不包含奇圈。
证明:一个图是偶图当且仅当每个连通分支是偶图;一个图不包含奇圈当且仅当每个连通分支不包含奇圈。因此,只需对连通图证明即可。
必要性:设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,必不相邻!
赋权图:若图G的每一条边e都有一个实数w(e),称为e的权,则G连同它边上的权称为赋权图。
若H是一个赋权图,则H的各边权之和称为图H的权,记为W(H)。
设G是赋权图,u与v是G中两点,在连接u与v的所有路中,各边权值之和最小的路,称为u与v间的最短路,最短路的权值称为u与v的距离,记为d(u,v)。
易知,各边的权均为1的赋权图中的路长与非赋权图中的路长是一致的。
最短路问题:给出一个连接各城镇的铁路网络,在这个网络指定的两个城镇之间确定一条最短路线。
数学模型:在一个赋权图中的两个指定顶点a和b之间找出一条最短(a, b)路。
Dantzig算法(顶点标号法)
Dantzig算法不仅找到了最短的(a, b)路,而且给出了a到图G的所有其他顶点的最短路。
上一篇:JavaEE-进程调度
下一篇:5G学习地图