第七章 图论 7.1 图的基本概念
完全图:任意两个不同的结点都是邻接的简单图称为
完全图。n个结点的无向完全图记为Kn。
图7.1.5给出了K3和K4。从图中可以看出K3有3条边,
K4有6条边。容易证明Kn有条边。
n(n 1) 2
图7.1.5K3与K4示意图
图7.1.6
第七章 图论 7.1 图的基本概念
一个图G可用一个图形来表示且表示是不唯一的。
第七章 图论 7.1 图的基本概念
【例7.1.2】设G=〈V(G),E(G)〉,其中
V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6,e7},e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b) 。
1)若e1,e2,…,ek都不相同, 则称路μ为迹;
2)若v0,v1,…,vk都不相同, 则称路μ为通路;
3)长度大于2的闭的通路(即 除v0=vk外,其余结点均不相同的 路)μ称作圈。
图7.1.1
第七章 图论
7.2 路与回路
例如在图7.2.1中,有连接v5 到v3的路v5e8v4e5v2e6v5e7v3,这 也是一条迹;路v1e1v2e3v3是一 条通路;路v1e1v2e3v3e4v2e1v1是 一条回路,但不是圈;路 v1e1v2e3v3e2v1是一条回路,也是 圈。
定 义 7.2.1 给 定 图 G = 〈V,E〉, 设 v0,v1,…,vk∈V , e1 , e2,…,ek∈E,其中ei是关联于结点vi-1和vi的边,称 交替序列v0e1v1e2…ekvk为连接v0到vk的路,v0和vk分别 称为路的起点与终点。路中边的数目k称作路的长度。 当v0=vk时,这条路称为回路。