图论 第1章 图的基本概念

1、杨 帆 江苏科技大学数理学院 第一章：图的基本概念 第一章：图的基本概念 图的定义与基本术语 同构 途径(way)和道路(path) 图的连通性 图的运算 图的概念 图论中的图是由若干给定的顶点顶点及连接两顶 点的边边所构成的图形。 这种图形通常用来描述某些事物之间的某种 特定关系，用顶点顶点代表事物，用边边表示相应 两个事物间的某种关系。 哥尼斯堡七桥问题 图论起源于著名的哥尼斯堡七桥问题: 哥尼斯堡市跨越河的两岸，河中心有两个小岛。 小岛与河的两岸有七条桥连接。在所有桥都只所有桥都只 走一遍走一遍的前提下，如何才能把这个地方所有的 桥都走遍？ 哥尼斯堡七桥问题 在任何顶点出发，必须从一条边

2、进，从另一条边出 一进一出，每个顶点相关联的边必须为偶数。 莱昂哈德莱昂哈德欧拉欧拉 在1735年圆满地解决了这个问题， 证明七桥问题无解，同时，欧拉还给出了任意一种 河-桥图能否全部走一次的判定法则，以及怎样快速 找到所要求的路线。这些解析，最后发展成为了数 学中的图论。 图的定义 二元组定义： V 是顶点集，E 是边集 E 的元素是一个二元组数对，用表示， ),(EVG = ),(yx Vyx, )( ),(),( ),(),( ),(),( 517 546415 424433 322211 7654321 54321 1 , vve , vve, vve , vve, vve , vve

3、, vve , e, e, e, e, e, eeE , v, v, v, vvV (V, E)G = = = = = = = 图的基本术语(1) 阶：阶：图G的顶点集合V的大小称为图G的阶 没有任何边的图称为空图，记作。 只有一个顶点的图称为平凡图(trivial graph)。 关联与邻接：关联与邻接： 点与点的邻接(adjacent) 点与边的关联(incident) 两个顶点之间有边相连，则两个顶点邻接，并 且通过这条边关联。 重边：重边：连接同一对顶点的边数大于1 环：环：顶点通过同一条边与自己关联 图的基本术语(2) 多重图：多重图：允许重边，又允许有环的图 简单图：简单图：没有环

4、及多重边的图 有向图有向图/ /无向图：无向图： 每条边都规定了方向的图称为有向图，而边没 有方向的图为无向图。 有限图有限图/ /无限图：无限图： 顶点集合和边集合都是有限集合称为有限图， 否则称为无限图。 例题 证明：在任意六人中必存在三人，要么都相 识，要么都不相识。 证明 构造图。六个人=a, b, c, d, e, f 边集：两人认识，则代表两人的顶点之间连 一条红边，否则连一条绿边。 考虑某点，不妨设为f，至少有3条边同色 （不妨设为红色）。设这三条同色边为fa， fb，fc。考虑三角形abc。1.abc中含红边 （设为bc），则fbc为一同色三角形；2.abc 不含红边，则abc

5、为一同色三角形（绿色）。 同构 G1和G2的顶点和边都一一对应，且连接关 系完全相同，只是顶点和边的标号不同，则 G1和G2是同构同构的。 同构关系实际是一种等价关系。 完全图 完全图：完全图：每对不同的顶点都有边相连 阶完全图记作 共有条边 补图：补图：设G为简单图，而H是一个以V(G)为顶点 集，且顶点在H中邻接当且仅当它们在G中不 邻接，则称H为G的补图，记作 ) 1( 2 1 2 =nnCn n K n GH = GH 竞赛图 定义：完全图的定向图称为竞赛图。 举例：n=1，n=2， n=3 二部图(bipartite graph) 定义定义：设和 是G的顶点子集， 其中，且G中每一条

6、边 的一个端点在 中，另一个端点在 中，则 称G为二部图二部图，记作 分划称为图G的二分划二分划。 1 V 2 V = 2121 ),(VVGVVV 1 V 2 V );,( 21 EVVG = ),( 21 VV 完全二部图 对于二部图G，如果 中的顶点与 中的每 个顶点都邻接，则称为完全二部图完全二部图。 若，则完全二部图记作。 1 V 2 V nVmV= 21 , nm K , Petersen 图 图 习题 1.2.3 pp. 13 证明：下列三个无向图都与Pertersen图同构。 图的基本术语(3) 顶点的度：顶点的度：与该顶点相关联的边的数目 记作，或简记作； 度为零的顶点称为孤

7、点；孤点； 度为1的顶点称为悬挂点；悬挂点； 对于有向图，有出度出度和入度入度之分； 奇顶点和偶顶点； 计算有环的顶点，环边计两次. 图G的最大度最大度: 图G的最小度最小度： )deg(v)(vd )(| )(max)(GVvvdG= )(| )(min)(GVvvdG= 图的基本术语(4) 正则图：正则图：图的每个顶点的度都相同 每个点的度均为k的正则图，称为k-正则图 0-正则图1-正则图2-正则图3-正则图 握手定理 顶点的度与边的关系： 在任意图G中，度为奇数的顶点个数是偶数 = Vv Ev2)deg( 4)(, 3)( , 3)(, 4)(, 2)( 54 321 = = vdvd

8、 vdvdvd 16)43342()(=+= v i vd 8=E =+ 12 2)()( VvVv Evdvd 子图 若，且H中边的重 数不超过G，则H称为G的子图子图，记作 若以下条件有一项成立，则H称为G的真子图真子图。 (1) (2) (3)H中至少有一条边的重数小于G中对应边重数 )()(),()(GEHEGVHV GH );()(GVHV );()(GEHE 子图 生成子图生成子图(Spanning graph)，又称支撑子图。 满足的真子图)()(),()(GEHEGVHV= 点导出子图 点导出子图点导出子图(induced graph): 设，以 为顶点集，且两端点都在 中 的

9、边的全体为边集所组成的子图，称为由 导出 的G的子图，记作。 导出子图表示从G中去掉 及其关联边的 子图，记作。 若，则把简记作，称为主子图。 )(GVV V VG VG VVG V V V vV =VG vG G, 321 vvvG 2 vG 边导出子图 边导出子图边导出子图: 设，以 为边集，以 中所有边的端点 为顶点集，组成的子图称为G的边导出子图，记 作。 从中删去 的所有边得到的子图，记作 在上增加一个边集 所得到的图，记作 )(GEE E EG E )(GE E EG EG+)(GE E G, 6541 eeeeG, 75 eeG 8 eG+ 图G1，G2的关系 设. 若,则称G1

10、和G2是点不交 （vertex-disjoint） 若,则称G1和G2是边不交的 （edge-disjoint） G1和G2的并, 其中 GGGG 21 , =)()( 21 GVGV =)()( 21 GEGE 21 GG )()()( 2121 GVGVGGV= )()()( 2121 GEGEGGE= 设G1和G2是两个图，若G1和G2无公共顶点， 则称它们是不相交的不相交的(disjoint)；若G1和G2无 公共边，则称它们是边不重的边不重的(edge disjoint)。 图的运算 设G1和G2是两个无孤立点的图 (1) 由G1和G2中所有边组成的图，称为G1和G2 的并并(uni

11、on)，记作 并运算 21 GG 相同的顶点 在并中只能 出现一次 21 GG 2 G 1 G 由G1和G2的公共边组成的图称为G1和G2的 交交(cap)，记作 交运算 21 GG 2 G 1 G 21 GG 由G1中去掉G2中的边组成的图称为G1和G2 的差差(difference)，记作 差运算 21 GG 2 G 1 G 21 GG 例题 1.3.2 设G是简单无向图且。 证明：G中含奇数个度点。 证明由推论1.3.2知，为 偶数。因为，所以n为奇数个。 因此，为奇数个。 ，为偶数。 设。若，则且 为偶数。由，存在y，使得 为偶数。即且。中度不为 的点是成对的出现的。 )4(mod1,

12、nGG c ) 1( 2 1 n eo VVGV=)( | o V )4(mod1n | e V )4(mod1n ) 1( 2 1 n e Vx ) 1( 2 1 )(nxdG c GG ) 1( 2 1 )(1)(=nxdnxd G Gc )()(xdyd c G G = e Vy ) 1( 2 1 )(nydG e V ) 1( 2 1 n 链链: : 从顶点u到顶点v的一条链是指一个序 列，其中 的起点终点 为及 ； 称作途径的长度；称为链的 起点；称为链的终点。 链 (walk，chain) kkk vevvevev 122110 . = i e 1i v i v k uv = 0

13、vvk= 45341 vvvvv 简便起见，只用顶点表示为： 475634431 vevevevev链链： 如果，称该途径是闭的闭的，反之则称为开开 的的； 链 逆转后得到的链记 为，称为 的逆链逆链。 链 中一段子序列称为 的 节节。 链 (chain) vu = 011221. vevevvev kkk = 1 jjjiii vevvev 111 . + ),( ji vv 若链 的边均不相同，则称该链为 迹迹(trail)。 若所有顶点顶点均不相同均不相同(所有边必然不 相同)，则称该途径为道路道路(path) 。 闭的迹称为回（circuit）；闭的道路称作圈圈(cycle) 道路 (

14、path) k vvvv. 210 k eee. 21 45341 vvvvv链链： 若链 的边均不相同，则称该链为 迹迹(trail)。 若所有顶点顶点均不相同均不相同(所有边必然不 相同)，则称该途径为道路道路(path) 。 闭的迹称为回（circuit）；闭的道路称作圈圈(cycle) 道路 (path) k vvvv. 210 k eee. 21 道路道路： 6321 vvvv 若链 的边均不相同，则称该链为 迹迹(trail)。 若所有顶点顶点均不相同均不相同(所有边必然不 相同)，则称该途径为道路道路(path) 。 闭的迹称为回（circuit）；闭的道路称作圈圈(cycle)

15、 道路 (path) k vvvv. 210 k eee. 21 圈圈： 14321 vvvvv Hamilton路 定义：包含图中每个顶点的路称为Hamilton 图。 Th1.4.1 每个竞赛图都含有Hamilton有向路。 证明 反证，设P= 是图的最长路。 且l2)阶简单图，w是有最 小度的顶点，如果， 则G是哈密顿图。 证明：由定理1.7.2可直接推出。 哈密顿图的充分条件 2/)deg(nw 设G是n阶图，若任一对顶点满足 而且若边，则将边加于图G， 如此反复加边直到无边可加为止，得到的图 叫G的闭包闭包，记作 。 闭包 vu, nvu+)deg()deg( )(),(GEvu),

16、(vu G 闭包的构造过程就是把度的和至少为图的顶 点个数的非邻接顶点对递推地连接起来，直 到不再有这样的顶点对存在 图G的闭包是唯一唯一的。 闭包 当且仅当一个简单图的闭包是哈密顿图时， 这个简单图才是哈密顿图。 证明： 闭包与哈密顿图 例题 有n个人，任意两个人合起来认识其余n-2个人。 证明：当n大于等于4时，这n个人能站成一个 圈，使每个人两旁站着自己认识的人。 证明 构造G=（V, E）uv相邻，当且仅当u与v认 识。任取不相邻两点u，v，则其余n-2个人必 与u或v相邻。即 若，则存在点a使得au相邻，但 av不相邻。则对于a，u而言，合起来至多认识 n-3个人，矛盾！ 若，同理，

17、可以找到上述a。故 ，由定理1.7.2，存在H-圈。 2)()(+nvdud 2)()(=+nvdud 1)()(=+nvdud nvdud+)()( 距离：距离：从 出发到 的最短道路若存在，则此 道路的长度称作从 到 的距离，记作 若此道路不存在，则 连通图G的最长距离成为图G的直径直径，记作。 距离 uv uv),(vud =),(vud )(Gd 2),(=vud 5)(=Gd表示什么？ )(ud 线图（line graph） G=（V,E）， 其线图L(G) 其中V(L(G)=E=e1，e2，en 其中任意ei，ej在线图中相邻当且仅当在G中 相应的边有公共端点。 图的矩阵表示 邻接矩阵A(G)=(aij)，阶矩阵 其中是G中连接点xi和xj的边的数目。A(G) 对称矩阵。 关联矩阵M（G）=( ) ，阶矩阵 nn ij a