资料课堂演示2013dm

1、第九章 图9.1 图的基本概念图的基本概念9.2 图中的通路、图的连通性和图的矩阵表示图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路带权图与带权图中的最短通路9.4 欧拉图欧拉图9.5 哈密尔顿图哈密尔顿图 9.6 二部图二部图 9.7 平面图与平面图的着色平面图与平面图的着色通路通路称顶点序列称顶点序列(vi1，vi2，vis)为图为图G中的一条中的一条通路通路，若，若vij V，1js，且，且(vij, vi(j+1) E，其中，其中 1js-1。例例 (v1, v2, v3)为通路为通路 (v1,v3,v4,v6,v7)为通路为通路通路通路称边序列称边序列 (e

2、i1，ei2，eit) 为图为图G中的一条中的一条通路通路，若，若eij E，1jt，且适当的规定边，且适当的规定边eij(1jt)中的两个端点中的两个端点，让其中一个为起点，一个为终点，可以使，让其中一个为起点，一个为终点，可以使eij的终点的终点与与ei(j+1)的起点是同一顶点，其中的起点是同一顶点，其中1jt-1。例例 (e2, e3)为通路为通路 (e1,e5,e8,e12)为通路为通路通路的长度、顶点间的距离通路的长度、顶点间的距离l 称一条通路经过的边的多少为这条称一条通路经过的边的多少为这条通路的长度通路的长度。l 称两个顶点间的最短通路的长度为该两个称两个顶点间的最短通路的长

3、度为该两个顶点间的顶点间的距离。距离。例例 l (v1,v3,v4,v6,v7)为通路，长度为为通路，长度为4。l (v1,v2,v3,v4,v5,v8,v7)为通路为通路, 长度为长度为6。l v1与与v7之间的距离为之间的距离为4。简单通路、初等通路 称一条通路为称一条通路为简单通路简单通路, 如果它的每一条边都不重复如果它的每一条边都不重复出现。出现。 称一条通路为称一条通路为初等通路初等通路, 如果它的每一个顶点都不重如果它的每一个顶点都不重复出现复出现.例例 l (v1,v2,v5,v6,v4,v5,v8,v7)为简单通路为简单通路,但非初等通路但非初等通路.回路、简单回路、初等回路

4、（圈）设设(vi1，vi2，vis)是图是图G=(V,E)中的一条通路，若中的一条通路，若vi1=vis，则这条通路为，则这条通路为G中的一条回路。中的一条回路。n若一个回路中边不重复出现，则称之为简单回路。若一个回路中边不重复出现，则称之为简单回路。n若一个回路中顶点不重复出现，则称之为初等回若一个回路中顶点不重复出现，则称之为初等回路，又称之为圈。路，又称之为圈。例例 回路、简单回路、初等回路（圈）l (v2,v4,v5,v6,v4,v3,v2)为一个简单回路，但不是圈为一个简单回路，但不是圈例例 回路、简单回路、初等回路（圈）l (v3,v2,v5,v6,v4,v3)为一个圈为一个圈定理

5、1G=(V,E)是一个无向图。是一个无向图。v1，v2 V，若若G中存在一条中存在一条v1 到到v2的通路，的通路，则一定存在一条从则一定存在一条从v1到到v2的初等通路。的初等通路。定理1的证明设设 S=n NG中存在一条长为中存在一条长为n的从的从v1 到到v2的通路的通路 由题知由题知S，又，又SN，由自然数集的非空子集有最小数，由自然数集的非空子集有最小数，可设可设m S，对于任意，对于任意n S，有，有 m n。设设(v1=vi0，vi1，vi(m-1)，v2=vim)是是G中一条从中一条从v1到到v2长度为长度为m的通路，则这条通路即是初等通路。的通路，则这条通路即是初等通路。否则

6、，若它不是初等通路，一定存在两个相同的顶点否则，若它不是初等通路，一定存在两个相同的顶点vij和和vik(0jkm)，使得，使得vij=vik。于是于是 (vi0，vij ，vi(k+1)， ，vim)也是也是 中一条从中一条从v1到到v2的通路，且长度为的通路，且长度为m-k+j (m)，这与，这与m最小矛盾。最小矛盾。推论G=(V,E)是一个无向图，是一个无向图， |V|=n。如果。如果G中存在中存在一条从一条从v1到到v2的通路，那么一定存在一条从的通路，那么一定存在一条从v1到到v2的长度小于等于的长度小于等于n-1的通路。的通路。恰有恰有 n个顶点的图个顶点的图G 中的初等通路最长为

7、中的初等通路最长为n-1。连通图连通图定义定义 G=(V,E)是一个无向图，若是一个无向图，若G中任意两个不同的中任意两个不同的顶点之间在顶点之间在G中都有通路存在，中都有通路存在， 则称则称G是一个连通图，否则称是一个连通图，否则称G为不连通图。为不连通图。有向连通图有向连通图定义定义 称一个有向图是连通的，如果去掉边的方向称一个有向图是连通的，如果去掉边的方向后所得无向图是连通的。后所得无向图是连通的。单侧连通一个有向图任意二点之间都有单向通路，一个有向图任意二点之间都有单向通路，则称为则称为单侧连通单侧连通图。图。例例连通、非单侧连通单侧连通强连通如果一个有向图任意二点之间都有双向的通路

8、，则称如果一个有向图任意二点之间都有双向的通路，则称为为强连通强连通图。图。例例单侧连通非强连通强连通例例 连通分支连通分支连通分支数为连通分支数为1 连通分支数为连通分支数为4连通分支连通分支设设G为一个无向图为一个无向图,R是是G中顶点之间的连通关系中顶点之间的连通关系,按着按着R可将可将V(G)划分成划分成k(k1)个等价类个等价类,记成记成V1,V2,Vk,称由它们导出的子图称由它们导出的子图GV1,GV2,GVk 为为G的的连通分支。连通分支。例例 G=(V,E)是一个简单图，试证明若是一个简单图，试证明若G不连通不连通，则，则 G的补图的补图 G 一定连通。一定连通。证明：因为证明

9、：因为G不连通，则不连通，则G可以分为若干连通子图：可以分为若干连通子图： （V1，E1），），- ，（，（Vn，En） 根据补图构造过程知，在根据补图构造过程知，在G的补图中，的补图中， V1中每中每个顶点与其它顶点集个顶点与其它顶点集V2，- ，Vn中顶点有边相中顶点有边相连。连。 这样，这样， 在在G的补图中，有的补图中，有n 分别属于两个顶点子集分别属于两个顶点子集Vi与与Vj中的任意两个顶中的任意两个顶点之间有边直接相连，点之间有边直接相连，n 属于同一个顶点子集属于同一个顶点子集Vi的任意两个顶点借助顶的任意两个顶点借助顶点子集点子集Vj的任意一个顶点连通。的任意一个顶点连通。所以

10、，根据连通的定义知：所以，根据连通的定义知：G的补图一定连通的补图一定连通 。关联矩阵(incidence matrix) 设设 G=(V,E)是一个无向图，是一个无向图，|V|=n，|E|=m，V=v1,v2, ,vn，E=e1,e2, ,em，则有则有nm 阶矩阵阶矩阵 ， M(G)=(mij)nm其中其中: 称称 M(G)=(mij)nm为图为图G的关联矩阵。的关联矩阵。mij=1 如顶点如顶点vi与边与边ei关联关联0 如顶点如顶点vi与边与边ei关联关联例 关联矩阵 e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 1 0 0 0 v2 1 0 0 1 0 0 0

11、 0 v3 0 0 1 1 0 0 1 1v4 0 0 0 0 1 1 0 1v5 0 1 0 0 0 1 1 0 M(G)=邻接矩阵 (adjacency matrix) 设设 G=(V,E)是一个无向图，是一个无向图，|V|=n， V=v1,v2, ,vn，则有则有nn 阶矩阵，阶矩阵， A(G)=(aij)nn其中其中: 称称 A(G)=(aij)nn为图为图G的邻接矩阵。的邻接矩阵。aij=1 如顶点如顶点vi与与vi关联关联,即即vi,vj E0 如顶点如顶点vi与与vi不关联不关联,即即vi,vj E例 邻接矩阵 v1 v2 v3 v4 v5v1 0 1 1 1 1v2 1 0 1

12、 0 1v3 1 1 0 1 1v4 1 0 1 0 1v5 1 0 1 1 0 A(G)=定理2G=(V,E)是一个无向图，其中是一个无向图，其中V=v1,v2, ,vn。A是是 G的邻接矩阵。的邻接矩阵。对于任意的自然数对于任意的自然数k，设矩阵，设矩阵Ak的第的第i行第行第j列的元素为列的元素为aij(k)，即，即 Ak=(aij(k)nn则则aij(k) 给出了所有的从给出了所有的从vi到到vj的长度为的长度为k的通路的条数。若的通路的条数。若 aij(k)=0，说明没有，说明没有vi到到vj的长度为的长度为k的通路。的通路。定理定理2的证明的证明对于任意的h(1hn)，ahj=1，表

13、示 vh到vj相邻接，即vh,vj E，而若aih(k) 0，则它表示所有的从vi到 vh长度为k的通路的条数，而其中任何一条从vi到vh的长度为k的通路，加上边vh,vj ，得到一条 vi到vj 的长为 k+1的一条通路。若ahj=0，或 aih(k)=0，表示从 vi经 k步到 vh，再走一步到vj 这样的从vi到vj 的长为k+1的通路不存在。综上所述， aij(k+1)给出了所有的从vi到vj长度为k+1的通路的总数。aij(k+1)=aih(k)*ahjh=1n证明：对l用归纳法。当l=1时，由A的定义，结论显然成立。 归纳假设当l=k时，结论成立。当l=k+1时，由矩阵乘法定义有可

14、达矩阵令令 A=A+A2+ +An-1=(aij)nn称之为称之为可达矩阵可达矩阵。性质：对于任意的性质：对于任意的vi与与vj，vivj，若存在从，若存在从vi到到vj的通的通路，则路，则 aij1一个无向图是连通的，一个无向图是连通的，当且仅当可达矩阵除对角线外均不是当且仅当可达矩阵除对角线外均不是0。例例0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 0 0 0 00 1 1 0 1 1 0 00 1 0 1 0 1 0 10 0 0 1 1 0 1 00 0 0 0 0 1 0 10 0 0 0 1 0 1 0 A2 1 1 2 1 0 0 0 1 4 2 2 1 2 0 1 1 2 3 1 2 1 0 02 2 1 4 2 1 1 11 1 2 2 4 1 2 00 2 1 1 1 3 0 20 0 0 1 2 0 2 00 1 0 1 0 2 0 2 A22 6 5 3 3 3 0 1 6 6 7 9 9 3 3 1 5 7 4 8 4 3 1 23