chapter单击此处编辑母版标题

1、图论图论简介简介图论图论是数学的一个分支是数学的一个分支, ,以图为研究对象以图为研究对象. .这种图这种图由若干给定的由若干给定的点点和连接两点的和连接两点的线线构成构成, ,借以描借以描述某些事物之间的关系述某些事物之间的关系. .用点代表事物用点代表事物, ,用连接用连接两点的线表示两个事物之间具有特定关系两点的线表示两个事物之间具有特定关系. .图论起源于图论起源于1818世纪世纪, ,追朔到追朔到17361736年瑞士数学家年瑞士数学家L.EulerL.Euler出版第一本图论著作出版第一本图论著作, ,提出和解决著名提出和解决著名KonigsbergKonigsberg七桥问题七桥

2、问题. .从那时以来从那时以来, ,图论不仅在图论不仅在许多领域许多领域, ,如计算机科学如计算机科学, ,运筹学运筹学, ,心理学等方心理学等方面得到了广泛的应用面得到了广泛的应用, ,而且学科本身也获得长而且学科本身也获得长足发展足发展, ,形成了拟阵理论形成了拟阵理论, ,超图理论超图理论, ,代数图论代数图论, ,拓扑图论等新分支拓扑图论等新分支.(.(8.5,8.88.5,8.8二节不讲二节不讲) )图图的定义与记号的定义与记号 图图G G是一个二重组是一个二重组:G=:G= V V, ,E E , ,其中其中V V是非空是非空有限有限集集合合, ,它的元素称为它的元素称为结点结点,

3、 E, E 也是也是( (可空可空) )有限有限集合集合, ,它的元素称为它的元素称为边边. . 图图G G的边的边e e是一个结点二重组是一个结点二重组: : a,ba,b ,a,b,a,b V,eV,e可可以是有序的以是有序的, ,称为称为有向边有向边, ,简称为弧简称为弧,a,a称为弧称为弧e e的的始点始点,b,b称为称为e e的的终点终点; e; e也可以是无序的也可以是无序的, ,称称为为无向边无向边.e=.e= a,ba,b 时时, ,称称e e与与a,ba,b关联关联, ,或或a,ba,b与与e e关联关联, ,或或a a与与b b相相邻接邻接; ;关联于同一结点的一条边关联于

4、同一结点的一条边称为称为自回路自回路. . 每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图; ;每条边都每条边都是有向边的图称为是有向边的图称为有向图有向图; ;我们我们仅仅讨论无向图讨论无向图和有向图和有向图. (. (看看图图8.1-18.1-1和和图图8.1-28.1-2) )图图的定义与记号的定义与记号续续 不与任何结点邻接的结点称为不与任何结点邻接的结点称为孤立结点孤立结点, ,全为全为孤立结点组成的图孤立结点组成的图( (视为无向图有向图均可视为无向图有向图均可) )称称为为零图零图. . 在无向图中两结点间在无向图中两结点间( (包括结点自身包括结点自身) )若多于

5、一若多于一条边，则称这几条边为条边，则称这几条边为平行边平行边. .在有向图中若在有向图中若同始点和同终点的边多于一条同始点和同终点的边多于一条, ,则称这几条边则称这几条边为为平行边平行边, ,平行边的条数称为该边的平行边的条数称为该边的重数重数. .含平含平行边的图称为行边的图称为多重图多重图, ,非多重图称为非多重图称为线图线图. .无自无自回路的线图称为回路的线图称为简单图简单图. .例子见图例子见图8.1-38.1-3. . 有向图去掉方向所得无向图称为该图的有向图去掉方向所得无向图称为该图的底图底图. .常用一个图形来表示常用一个图形来表示图图称为称为图图的的图示图示degdeg+

6、 +(1)=2,deg(1)=2,deg- -(1)=0, deg(1)=deg(2)=(1)=0, deg(1)=deg(2)=degdeg+ +(2)=deg(2)=deg- -(2)=1,(2)=1, =deg(6)=3. =deg(6)=3.deg(1)=deg(1)=deg(4)=2.=deg(4)=2.1234abcd123456abcdef结点的结点的度度( (次数次数) ) 有向图中有向图中, ,以结点以结点v v为始点的边数称为为始点的边数称为v v的的出度出度, ,记为记为degdeg+ +(v);(v);以结点以结点v v为终点的边数称为为终点的边数称为v v的的入入度度

7、, ,记为记为degdeg- -(v);(v);它们的和它们的和: : deg(v)=deg deg(v)=deg+ +(v)+deg(v)+deg- -(v) (v) 称为称为v v的的度度. . 无向图中无向图中, ,与结点与结点v v相关联的边数称为相关联的边数称为v v的的度度, ,记记为为deg(v).deg(v). 各结点的度都相等的图称为各结点的度都相等的图称为正则图正则图, ,或或k-k-正则正则图图, ,其中其中k k为结点度的公共值为结点度的公共值.(.(注注: :可以只考虑可以只考虑正则的无向图正则的无向图, ,然后再定义其底图的无向图是然后再定义其底图的无向图是正则图的

8、有向图为正则有向图正则图的有向图为正则有向图.).) 例子见上一张幻灯片和例子见上一张幻灯片和图图8.1-58.1-5. .关于有关于有 n n 结点结点 m m 边的边的(n,m)(n,m)图图度的定理度的定理 定理定理8.1-18.1-1 令令 v v1 1, , ,v vn n为图的所有结点为图的所有结点, ,则则 i=1i=1n n deg(vdeg(vi i)=2m. (1)=2m. (1)证证: :对于公式对于公式(1)(1)左边的和式左边的和式, ,图的每条边贡献的图的每条边贡献的度数恰为度数恰为2,2,从而结论成立从而结论成立. .注注: :对有向图对有向图(1)(1)可写成可

9、写成 i=1i=1n n degdeg+ +(v)+(v)+ i=1i=1n n degdeg- -(v)=2m.(v)=2m.定理定理8.1-28.1-2 任何图中度为奇数的结点必为偶数个任何图中度为奇数的结点必为偶数个. .证证: : 因偶度点度的和为偶数因偶度点度的和为偶数, ,若奇度点为奇数个若奇度点为奇数个, ,则奇度点度的和必为奇数则奇度点度的和必为奇数. .但偶数加奇数得奇但偶数加奇数得奇数数, ,便与便与(1)(1)式右边为偶数相式右边为偶数相矛盾矛盾. .8.1#4(c)8.1#4(c)简单无向图简单无向图 G G 必有必有2 2结点同度结点同度证证: :令令 G=vG=v1

10、 1, ,v,vn n.若若 G G 中中没有孤立点没有孤立点, ,则则 G G 中中 n n个结点的度只取个结点的度只取 n-1n-1 个可能值个可能值: : 1,2,1,2,n-1,n-1,从而从而 G G 中至少有两个结点的度相同中至少有两个结点的度相同. .否则否则,G,G中有孤立点中有孤立点, ,不妨设不妨设v vk k,v,vk+1k+1, ,v,vn n为全部为全部孤立点孤立点, ,则则 v v1 1, ,v,vk-1k-1的度只取的度只取 k-2k-2个可能值个可能值: : 1,2,1,2,k-2,k-2,从而此从而此 k-1k-1个结点中至少有两个个结点中至少有两个同度点同度

11、点. .图的图的同构同构定义定义: :对给定两个图对给定两个图 G=G= V,EV,E ,G,G = = V V ,E,E , ,若存在若存在双射双射 f:Vf:VV V 使对任意使对任意a,ba,b V, V, (a,b) (a,b) E E (f(a),f(b)(f(a),f(b) E E , ,并且并且(a,b)(a,b)与与(f(a),f(b)(f(a),f(b)有相同重数有相同重数, ,则称则称 G G 与与 G G 同构同构, ,记记为为 G G G G . .注注: : 两图同构是相互的两图同构是相互的: G: G G G G G G.G. 两图同构时不仅结点之间要有一一对应关系

12、两图同构时不仅结点之间要有一一对应关系, ,而且要求这种对应关系而且要求这种对应关系保持保持结点间的结点间的邻接关邻接关系系. .对有向图同构还要求对有向图同构还要求保持边的方向保持边的方向. . 寻求判断图同构的简单有效方法仍是图论待寻求判断图同构的简单有效方法仍是图论待解决的重要问题解决的重要问题. .同构图同构图举例举例 G G G G H H H H1 1a,2a,2b,3b,3c, c, 1 1a,2a,2b,3b,3c,c, 4 4d 4d 4d,5d,5e,6e,6f f1234abcd123456abcdefGGHH非同构图非同构图举例举例存在结点数及每个结点对应度都相等的两个

13、图存在结点数及每个结点对应度都相等的两个图仍然不同构的情况仍然不同构的情况. .一个例子是一个例子是图图8.1-88.1-8; ;另一另一例如下例如下:(:(注意注意: :两个两个4 4度点或邻接或不相邻接度点或邻接或不相邻接) )GG子图的概念子图的概念定义定义: :给定两个无给定两个无( (有有) )向图向图 G=G= V,EV,E ,G,G = = V V ,E,E . .若若 V VV V 和和 E EE E, ,则称则称 G G 是是G G的的子图子图; ;若若 V VV,EV,EE,E,且且 G G G G, ,则称则称 G G 是是 G G 的的真子图真子图; ;若若 V V =

14、V=V 和和 E EE E, ,则称则称 G G 是是 G G 的的生成子图生成子图; ;若子图若子图 G G 无孤立结点且无孤立结点且G G 由由E E 唯一确定唯一确定, ,则称则称G G 是是由由边集边集E E 导出的子图导出的子图; ;若对子图若对子图 G G = = V V ,E,E 中任二结点中任二结点 u,v,(u,v)u,v,(u,v) E E (u,v)(u,v) E E , ,则称则称 G G 是由是由结点集结点集V V 导出的子图导出的子图( (易见易见:V:V 导出的子图导出的子图G G 是以是以V V 为其结点集为其结点集, ,所有所有在在G G中同时关联于中同时关联

15、于V V 中两点的边为其边集中两点的边为其边集).).有向图子图举例有向图子图举例( (图图8.1-108.1-10) ): :由由(1,2),(1,4),(5,1)(1,2),(1,4),(5,1)导出的子图导出的子图; ; : :由由(1,2),(3,2),(3,4),(1,4)(1,2),(3,2),(3,4),(1,4)导出的子图导出的子图( (也是此也是此4 4点导出的子图点导出的子图); ); : :由由1,2,4,51,2,4,5导出的子图导出的子图. . 11112222555334444完全图完全图与与补图补图 E=VE=V V V的有向图的有向图G=G= V,EV,E 称为

16、称为有向完全图有向完全图.n.n个结个结点的点的无向简单图无向简单图如果任二不同结点都相邻时如果任二不同结点都相邻时, ,称为称为n n结点结点无向完全图无向完全图, ,记为记为 K Kn n. .完全图的例子完全图的例子见图见图8.1-118.1-11. . n n 结点线图结点线图G=G= V,EV,E 与与H=H= V,EV,E 称称互为补图互为补图( (记为记为G=HG=H或或H=GH=G),),如果如果E E是是n n结点完全图的边集与结点完全图的边集与E E的差集的差集. .下列二无向图下列二无向图G G与与H H互为补图互为补图. .GHK4 48.1#138.1#13的用红的用

17、红, ,兰色给兰色给 K K6 6边着色边着色命题命题: :对任意一种着色方案的着色结果对任意一种着色方案的着色结果, ,或者有一或者有一个红个红 K K3 3, ,或者有一个兰或者有一个兰 K K3 3. .证证: :令令a,b,c,d,e,fa,b,c,d,e,f为为K K6 6的的6 6结点结点. .因过因过f f的的5 5条边必条边必有三边着为同色有三边着为同色, ,不失一般性不失一般性, ,设设(a,f),(b,f), (a,f),(b,f), (c,f)(c,f)已着红色已着红色. .若若(a,b),(a,c),(b,c)(a,b),(a,c),(b,c)已着兰已着兰色色, ,则则

18、a,b,ca,b,c导出的子图是一个兰导出的子图是一个兰K K3 3, ,从而结从而结论成立论成立. . 否则否则此三边必有一边此三边必有一边, ,例如例如(a,b)(a,b)已着已着红色红色, ,则则a,b,fa,b,f导出的的子图是红导出的的子图是红 K K3 3. .证毕证毕. .推论推论: :任何任何6 6人的人群中人的人群中, ,或者有或者有3 3人互相认识人互相认识, ,或或者有者有3 3人彼此陌生人彼此陌生.(.(当二人当二人x,yx,y互相认识互相认识, ,边边(x,y)(x,y)着红色着红色, ,否则着兰色否则着兰色. .则则6 6人认识情况对应人认识情况对应于于K K6 6

19、边的一个二着色边的一个二着色. .由上述命题知或者有红由上述命题知或者有红K K3 3或者有兰或者有兰K K3 3.).)fabcabc6改改5 5结论不成立结论不成立路径与回路路径与回路 图图 G=G= V,EV,E 的的点边交替序列点边交替序列 P=vP=v0 0e e1 1v v1 1e e2 2v v2 2 e en nv vn n称为称为 G G 的一条从的一条从v v0 0 到到v vn n的的长长为为 n n 的的路径路径, ,其其中中,e,ei i=(v=(vi-1i-1,v,vi i) ) E,i=1,E,i=1,n(,n(对有向图要求对有向图要求 v vi-1i-1,v,v

20、i i为为e ei i的的始始, ,终点终点).). P P 称为称为简单路径简单路径, ,如果如果 e e1 1, , ,e,en n 两两不同两两不同; ; P P 称为称为基本路径基本路径( (链链),),如果如果 v v0 0,v,v1 1, , ,v,vn n 两两不两两不同同( (易见易见链必为简单路径链必为简单路径); P); P 称为称为回路回路, ,如果如果 v v0 0= = v vn n; ; 回路回路 P P 称为称为简单简单( (基本基本) )回路回路, ,如果如果e e1 1, , ,e,en n(v(v1 1, , ,v,vn n) )两两不同两两不同. . 路径

21、路径 P P 可只用边序列可只用边序列 e e1 1e e2 2 e en n表示表示. .若若 G G 为为线图线图, ,则路径则路径 P P 也可只用结点序列也可只用结点序列 v v0 0v v1 1 v vn n 表示表示. . 例见例见图图8.2-18.2-1. . 任何图任何图 G G 中中有有从从 u u 到到 w w 的的路径路径( (回路回路) )必必有有从从 u u 到到 w w 的的基本路径基本路径( (回路回路) )由于由于G G有从有从u u到到w w的路径的路径,G,G必有一条长度最小的从必有一条长度最小的从u u到到w w的路径的路径:P.:P.如果如果P P不是基

22、本路径不是基本路径, ,则则 P=ueP=ue1 1v v1 1e e2 2 v vi ie ei+1i+1 v vj je ej+1 j+1 e en nw w 中中 v vi i=v=vj j, ,于是于是 P-eP-ei+1i+1, , ,e,ej j 仍是仍是G G的一条从的一条从u u到到w w的路径的路径, ,但长但长度比度比P P长度还要长度还要小小, ,得出得出矛盾矛盾. .v vi iv vj+1j+1v vj-1j-1v vi+1i+1v vn-1n-1uwv v1 1P在在 n n 结点的图中任何结点的图中任何链链的长度都的长度都不大于不大于 n-1n-1; ;任何任何基

23、本回路基本回路的长度都的长度都不大于不大于 n n证证: :设任一链设任一链 P P 的长度为的长度为k,k,则则 P P穿程于穿程于 k+1k+1个结点个结点: :P P = = v v0 0e e1 1v v1 1e e2 2v v2 2 e ek kv vk kv vk k. . 因因 v v0 0,v,v1 1, , ,v,vk k 两两不同两两不同, ,故故 k+1k+1 n,n,从而从而 k k n-1.n-1.同理同理, ,长度为长度为k k的基本回路有的基本回路有 k k 个不同结点，从而个不同结点，从而 k k n. n. 距离距离的概念的概念 图图 G=G= V,EV,E

24、中中, ,从结点从结点 u u 到到 w w 的的最短路径最短路径( (必为必为链链) )的的长度长度称为称为 G G 的从的从 u u 到到 w w 的的距离距离, ,记为记为 d(u,w)d(u,w). . 如果从如果从 u u 到到 w w没有路径没有路径, ,则令则令 d(u,w)=+d(u,w)=+ .(.(注意注意: :在无向图中恒有在无向图中恒有 d(u,w)=d(w,u),d(u,w)=d(w,u),而在有向图中而在有向图中可能出现可能出现d(u,w)d(u,w) d(w,u).)d(w,u).) 对任意对任意 u,v,wu,v,w V,d(u,v)V,d(u,v)是非负整数或

25、是非负整数或+ + ; ; d(u,v) d(u,v) 0;d(u,v)=00;d(u,v)=0 当且仅当当且仅当 u=w;u=w; d(u,v)+d(v,w) d(u,v)+d(v,w) d(u,w)(d(u,w)(三角不等式三角不等式, ,距离特性距离特性) ) 三角不等式的证明三角不等式的证明: :若若 d(u,v)=+d(u,v)=+ 或或 d(v,w)=+d(v,w)=+ , ,结论显然成立结论显然成立. .否则否则, ,有从有从 u u 到到 v v 长长度为度为 d(u,v)d(u,v)的路径和从的路径和从v v到到w w长度为长度为d(v,w)d(v,w)的路的路径径, ,从而

26、有从从而有从u u到到w w长度为长度为d(u,v)+d(v,w)d(u,v)+d(v,w)的路径的路径. .无向图无向图的的连通性连通性 在无向图在无向图G G中中, ,若有从结点若有从结点u u到到w w的路径的路径( (或从或从u u到到w w的的链链, ,因有因有u-wu-w路必有路必有u-wu-w链链),),则称从则称从u u到到w w可达可达. .约定约定每个结点到自身可达每个结点到自身可达.(.(图图8.2-2(b)8.2-2(b) ) 无向图称为是无向图称为是连通连通的的, ,如果任二结点都可达如果任二结点都可达. .易易见见: : G G 连通当且仅当连通当且仅当 G G 有

27、一个生成子图连通有一个生成子图连通. . 无向图结点间的无向图结点间的可达关系是等价关系可达关系是等价关系( (满足自满足自反反, ,对称和传递律对称和传递律),),因此其因此其商集商集给出给出 G G 的结点集的结点集的一个的一个划分划分, ,属于一个等价类的结点导出属于一个等价类的结点导出 G G 的一的一个连通子图个连通子图, ,且不存在以此子图为真子图的连且不存在以此子图为真子图的连通子图通子图. .故把这些连通子图称为故把这些连通子图称为G G的的连通分支连通分支.G.G的任何二结点相互可达的任何二结点相互可达当且仅当当且仅当它们属于同一它们属于同一个连通分支个连通分支.G.G为连通

28、当且仅当它为连通当且仅当它恰有一个恰有一个连通连通分支分支. G. G的连通分支数记为的连通分支数记为 (G)(G). .有向图有向图的的连通性连通性 已知有向图已知有向图 G,G,若它的若它的底图底图是连通无向图是连通无向图, ,则则 G G 称为是称为是弱连通弱连通的的; ;若若 G G 的任二结点都相互可达的任二结点都相互可达, ,则则G G称为是称为是强连通强连通的的; ;若若 G G 的任二结点至少从一的任二结点至少从一个到另一个可达个到另一个可达, ,则则 G G 称为是称为是单向连通单向连通的的. . 易见易见: :强连通性强连通性 单向连通性单向连通性 弱连通性弱连通性; ;

29、但反之不真但反之不真. .反例如下反例如下: : 强连通强连通 单向连通非强连通单向连通非强连通 弱连通非单向连通弱连通非单向连通 从从a a到到b b不可达不可达 从从a a到到b b不可达且不可达且 从从b b到到a a不可达不可达aabbcd有向图有向图的强的强( (单向单向, ,弱弱) )连通分支连通分支 已知有向图已知有向图 G G 及其子图及其子图 G G . .若若 G G 是强是强( (单向单向, ,弱弱) )连通的连通的, ,并且并且 G G 中没有以中没有以 G G 为真子图的强为真子图的强( (单向单向, ,弱弱) )连通子图连通子图, ,则称则称 G G 为为 G G

30、的的强强( (单向单向, ,弱弱) )连通分连通分支支. . 注注 一个有向图的上述三种连通分支可能是一个有向图的上述三种连通分支可能是互不相同的互不相同的, ,图图8.2-48.2-4中的图就是这样中的图就是这样. . 在有向图中可用在有向图中可用属于同一强属于同一强( (弱弱) )连通分连通分支支引入结点间的引入结点间的等价关系等价关系. .但对但对单向连通分单向连通分支支引入的关系不满足引入的关系不满足传递性传递性, ,从而不是等价关从而不是等价关系系( (图图8.2-58.2-5).).8.2#48.2#4无向图无向图 G G恰有的恰有的2 2个奇度结点个奇度结点可达可达解解1 1:

31、:令令u,wu,w为为G G恰有的恰有的2 2个奇度结点个奇度结点. .考察考察u u所在的所在的连通分支连通分支G G. .因任何图的因任何图的奇度点为偶数奇度点为偶数, ,故故G G至至少还有另一奇度点少还有另一奇度点. .但但G G的每个点的每个点在在G G和和G G中有中有相同的度相同的度, ,所以所以G G恰有恰有2 2个奇度点而且就是个奇度点而且就是u u和和w.w.再由再由G G的的连通性连通性推出推出u u到到w w可达可达. .解解2 2: :可一般地证明在可一般地证明在无向图无向图G G中从任一奇度点中从任一奇度点u u出出发的一条最长简单路的另一端点必为一个奇度发的一条最

32、长简单路的另一端点必为一个奇度点点, ,原因是从原因是从u u出发的出发的最长最长简单路不会终止在简单路不会终止在u u处处( (否则否则d(u)d(u)为偶数为偶数););也不会终止在任一偶度也不会终止在任一偶度点点v v处处( (否则否则d(v)d(v)为奇数为奇数).).赋权图赋权图中的中的距离距离应用广泛的应用广泛的赋权图赋权图是三重组是三重组:G=:G= V,E,WV,E,W ,V,E,V,E 分别分别为为 G G 的结点集和边集的结点集和边集, ,W W是从是从 E E 到到 R R+ +的函数的函数, ,边边e=(i,j)e=(i,j)的函数值的函数值 W(e)=W(i,j)W(

33、e)=W(i,j)称为称为 e e 的的权权. . 赋权图赋权图 G G的一条路径的一条路径 P=(eP=(e1 1, ,e,ek k) )的的长度长度定义为定义为: : W(P)=W(eW(P)=W(e1 1)+)+W(e+W(ek k).).从结点从结点u u到到w w的的距离距离定义定义为为d(u,w)=d(u,w)=minminW(P)|PW(P)|P为为G G中从中从u u到到w w的路径的路径,约约定定:d(u,u)=0;d(u,w):d(u,u)=0;d(u,w) = = , ,当从当从u u到到w w不可达不可达. .例如例如, ,对右边的图有对右边的图有d(a,c)=5;d(

34、a,c)=5; d(a,d)=9;d(a,d)=9;d(a,e)=7.d(a,e)=7.21073245abcde求已知求已知简单连通赋权图简单连通赋权图G G中从源点中从源点a a到到其它各点其它各点x x的最短距离的的最短距离的DijkstraDijkstra算法算法 步骤步骤 把结点集把结点集V V分割为二子集分割为二子集 S,T.S,T.开始时开始时S=a,T=S=a,T=V-SV-S. . 步骤步骤 对每结点对每结点 t t T,T,求出求出 D(t)D(t)之后再定出之后再定出x x T T 使得使得 D(x)=D(x)= minD(x)|tminD(x)|t T.T. 步骤步骤

35、置置 S S 为为 S Sxx置置 T T为为T-x.T-x.若若 T=T=则则停止停止, ,否则转步骤否则转步骤作作下一次循环下一次循环. .将证将证: :第第步求得的每一点步求得的每一点x x对应有对应有 D(x)=d(a,x)D(x)=d(a,x). . 开始时开始时 令令 D(t)=W(a,t),D(t)=W(a,t),结论显然成立结论显然成立: D(x)= : D(x)= minW(a,t)|tminW(a,t)|t T=d(a,x).T=d(a,x). 下一步对下一步对S S =S=Sx,Tx,T =T-x=T-x令令D D (t)(t)为为T T 中结中结点的点的D(t)D(t)

36、值值, ,则则 D D (t)(t)= = minD(t),D(x)+W(x,t)minD(t),D(x)+W(x,t). .DijkstraDijkstra算法的标号法算法的标号法举例举例21073645210736452210736452107364510 2 95225599990000用用DijkstraDijkstra算法的标号法算法的标号法解解8.2#11(b)8.2#11(b)11010141 05 326101555462233881063 EulerEuler路径路径与与EulerEuler图图 KonigsbergKonigsberg七桥问题七桥问题(1736(1736年年

37、).). 穿程于穿程于( (有向或无向有向或无向) )图图 G G 的每条边一次且仅一的每条边一次且仅一次的路径次的路径( (回路回路) )称为称为 EulerEuler 路径路径( (回路回路).). 具有具有 EulerEuler 回路的回路的连通连通图称为图称为EulerEuler图图. . EulerEuler定理定理 无向无向连通图连通图G G有一条有一条EulerEuler路径当且路径当且仅当仅当 G G 有零个或两个奇数度结点有零个或两个奇数度结点( (证明见教本证明见教本255255页页););有向有向连通图连通图G G有一条有一条EulerEuler路径当且仅路径当且仅当当

38、G G的每点出的每点出, ,入度相等入度相等, ,只有两点例外只有两点例外, ,并且它并且它们出们出, ,入度之差一为入度之差一为1,1,一为一为-1.-1. 推论推论 无向连通图无向连通图 G G 是是EulerEuler图当且仅当图当且仅当 G G 的的结结点度数都是偶数点度数都是偶数. . 应用应用: Konigsberg: Konigsberg七桥问题不可解七桥问题不可解, ,因对应图因对应图( (见见图图8.2-8(b)8.2-8(b) )都是都是 3 3 度结点度结点. .用定理用定理8.2-48.2-4的证明方法的证明方法构造构造EulerEuler回路回路11555222334

39、441112341 1351 5245=12341 1352451=12341352451无向图无向图 G G 能否能否一笔画一笔画的问题等价于的问题等价于 G G 是是否有一条否有一条EulerEuler路径路径( (回路回路) )的问题的问题 若图只有若图只有两个两个奇结点奇结点, ,则任何则任何EulerEuler路径必路径必从其中一点开始到另一点结束从其中一点开始到另一点结束. .利用这条规律利用这条规律, ,先在此先在此2 2奇点之间加条边使之变成奇点之间加条边使之变成EulerEuler图并画图并画出一条出一条EulerEuler回路回路, ,然后再去掉所加的边即得一然后再去掉所加

40、的边即得一条条EulerEuler路径路径. .ab123456789HamiltonHamilton路径路径与与HamiltonHamilton图图 无向连通图无向连通图G G穿程于穿程于G G 的每一结点的每一结点一次且仅一一次且仅一次次的路径的路径( (回路回路) )称为称为G G 的一条的一条HamiltonHamilton 路径路径( (回路回路););具有具有HamiltonHamilton回路的无向连通图称为回路的无向连通图称为HamiltonHamilton图图. .由定义知由定义知HamiltonHamilton 路径路径( (回路回路) )必必为为基本基本路径路径( (回路

41、回路).). 18591859年年IrelandIreland数学家数学家HamiltonHamilton提出环游世界提出环游世界游戏给出游戏给出HamiltonHamilton图的一个经典例子图的一个经典例子( (图图8.2-8.2-1111).). 可以证明可以证明: :对任意正整数对任意正整数 n n 3 3 完全图完全图 K Kn n 恒有恒有HamiltonHamilton回路回路( (不难从任一点开始作出一条不难从任一点开始作出一条HamiltonHamilton回路回路, ,每一步都通到一个新结点每一步都通到一个新结点, ,最后最后回到起点回到起点).().(推广到赋权图的情形推

42、广到赋权图的情形, ,求有最小权求有最小权的的HamiltonHamilton回路问题就是有名的回路问题就是有名的货郎问题货郎问题) )HamiltonHamilton图图的一个必要条件的一个必要条件 定理定理 若若G=G= V,EV,E 为为HamiltonHamilton图图, ,则对每个则对每个S S V V有有 (G-S)(G-S) |S|S|, ,其中其中 (G-S)(G-S)表示子图表示子图G-SG-S的连通分支数的连通分支数. .证证: :设设C C是是G G的一条的一条HamiltonHamilton回路回路( (必为必为基本基本回路回路),),则对则对V V的任意真子集的任意

43、真子集S S都有都有 (C-S)(C-S) |S|, (1)|S|, (1)( (S=aS=a1 1 时时,(1),(1)式成立等式式成立等式; ; S=aS=a1 1,a,a2 2 时时,C,C1 1=C-=C-aa1 1 是链是链; ; 而而 C-S=CC-S=C1 1-a-a2 2 是链是链, ,当且仅当当且仅当a a2 2为为C C1 1端点端点, ,否则否则 (C-S)=2.(C-S)=2.总之总之, , (C-S)(C-S) 2=|S|. 2=|S|. S=aS=a1 1, ,a,ak k,a,ak+1k+1 时时, ,由归纳法得由归纳法得 (C-S)(C-S) (C-a(C-a1

44、 1, ,a,ak k)+1 )+1 |a|a1 1, ,a,ak k|+1=k+1=|a|+1=k+1=|a1 1, ,a,ak+1k+1|.|.) )因生成子图的连通分支数不比母图的多因生成子图的连通分支数不比母图的多和和C-SC-S是是G-SG-S的生成子图的生成子图, ,故得证故得证 (G-S)(G-S)(C-S)(C-S) |S|.|S|.a a1 1a a2 2Ca a1 1Ca a2 28.2#158.2#15求简单无向图求简单无向图G:(G:(b b)G)G有有E-E-回路但回路但无无H-H-回路回路;(;(d d)G)G无无E-E-回路也无回路也无H-H-回路回路 左图左图G

45、 G无奇度点故有无奇度点故有EulerEuler回路回路; ;易见易见G G无无HamiltonHamilton回路回路( (取取S=a,bS=a,b时时, ,有有 (G-S)=32=|S|).(G-S)=32=|S|). 右图右图H H有奇度点故无有奇度点故无EulerEuler回路回路; ;易见易见H H无无HamiltonHamilton回路回路( (证明同上或用证明同上或用穷举法穷举法验证验证).).GHabab非非HamiltonHamilton图图举例举例例例 图图8.2-128.2-12不是不是HamiltonHamilton图图, ,原因是原因是: :取取S S为为3 3个黑点

46、时有个黑点时有 (G-S)=4(G-S)=4 3=|S|.3=|S|.例例 图图8.1-58.1-5的的PetersonPeterson图图不是不是HamiltonHamilton图图, ,但它满足但它满足对一切非空子集对一切非空子集S S V V有有 (G-S)(G-S) |S|,|S|,所以所以, ,定理定理8.2-68.2-6的条件的条件不是充分的不是充分的. .例例 图图8.2-138.2-13不是不是HamiltonHamilton图图( (用一种符号标用一种符号标记法证明记法证明).).结点符号标记法结点符号标记法补充补充图标记结束后图标记结束后, ,可能出现可能出现相邻结点标记符

47、号相同相邻结点标记符号相同的情况的情况, ,此时应先在该对结点之间增加一个新此时应先在该对结点之间增加一个新结点结点( (此点必为此点必为2 2度点度点),),同时将它标以不同的符同时将它标以不同的符号号. .设所有有相同标记的邻点都做上述处理之设所有有相同标记的邻点都做上述处理之后得到的图记为后得到的图记为G G . .则则 G G 有有HamiltonHamilton路当且仅当路当且仅当G G 有有HamiltonHamilton路路. .故若故若 G G 的不同标记结点数不的不同标记结点数不同时同时( (如下图如下图) )即可断定即可断定 G G 不是不是HamiltonHamilton

48、图图. .AAABBBAAABBBBGG n(n( 3)3)结点无向简单图结点无向简单图G G为为HamiltonHamilton图图的一个充分条件的一个充分条件: :n/2,n/2, 记记最小度数最小度数证证: :用用反证法反证法. .若结论不成立若结论不成立, ,则必有则必有n n结点的结点的最大最大( (边数边数最多最多) )非非HamiltonHamilton图图G=G= V,EV,E . .因因G G K Kn n, ,故故G G有结点有结点u,v, u,v, (u,v)(u,v) E,E,且且G+(u,v)G+(u,v)为为HamiltonHamilton图图, ,同时同时G+(u

49、,v)G+(u,v)中任中任一一HamiltonHamilton回路都含边回路都含边(u,v).(u,v).于是于是G G有从有从u u到到v v的的HamiltonHamilton路径路径(u=v(u=v1 1,v,v2 2, ,v,vn n=v)(=v)(见下图见下图).).令令S S=v=vi i|(u,v|(u,vi+1i+1) ) E,E,T T=v=vi i|(v|(vi i,v),v) E,E,则则 v vn n S ST, T, |S|ST|n.T|n.又又 S ST=T=( (否则设某否则设某v vi i S ST,T,则如下图所则如下图所示示G G有有HamiltonHam

50、ilton回路矛盾回路矛盾).).因此因此d(u)+d(v)=|S|+|T|=|Sd(u)+d(v)=|S|+|T|=|ST|+|ST|+|ST|n,T|n,与假设矛与假设矛盾盾. .u=v v1 1v v2 2v vi-1i-1v vi+1i+1v vi iv vn n=v=v注注与与例例 注注 由上面的证明可得更一般结论由上面的证明可得更一般结论:n:n结点无向结点无向简单图简单图G G为为HamiltonHamilton 图图, ,如果如果G G的的任任2 2结点度数结点度数之和都不小于之和都不小于 n/2n/2. . 例例 n n结点无向结点无向k-k-正则图正则图必为必为Hamilt

51、onHamilton图只要图只要 k k n/2. (n/2. (因因 =k=k n/2)n/2)HamiltonHamilton图图的一个应用的一个应用( (习题习题8.2#68.2#6) )BCDEFG7 7位客人入席位客人入席,A,A只会讲英语只会讲英语,B,B会讲英会讲英, ,汉语汉语,C,C会讲会讲英英, ,意大利意大利, ,俄语俄语,D,D会讲日会讲日, ,汉语汉语,E,E会讲德会讲德, ,意大意大利语利语,F,F会讲法会讲法, ,日日, ,俄语俄语,G,G会讲法会讲法, ,德语德语. .能否安能否安排圆桌席位使每位客人与其左右邻不用翻译便排圆桌席位使每位客人与其左右邻不用翻译便可

52、交谈可交谈? ?建立无向图模型建立无向图模型: :结点为结点为客人客人; ;会共同语言的会共同语言的2 2结结点相邻接点相邻接. .则问题则问题归结为归结为求此图的一条求此图的一条HamiltonHamilton回路回路. .不难验证不难验证, ,此图有此图有一条一条HamiltonHamilton回路是回路是: :(A,B,D,F,G,E,C,A).(A,B,D,F,G,E,C,A).按此按此回路安排席位可满足要求回路安排席位可满足要求. .A英英法德俄意日汉HamiltonHamilton图图对编码的一个应用对编码的一个应用把圆周等分成把圆周等分成2 2n n个扇形个扇形, ,每一扇形代表

53、一个每一扇形代表一个n n位二进制串位二进制串用以表示旋转指针的位置用以表示旋转指针的位置( (不难设计指针上的不难设计指针上的n n个触点个触点来实现这个数来实现这个数).).当当n=3n=3时右下图是一例时右下图是一例. .由于交界附近由于交界附近会出现误差会出现误差, ,自然要求自然要求相邻二数尽可能接近相邻二数尽可能接近, ,即要求即要求ijkijk与与uvwuvw相邻必须满足相邻必须满足|i,j,k|i,j,ku,v,w|=2 (1) u,v,w|=2 (1) 此问题可归结为求此问题可归结为求立方图立方图G=G= V,EV,E ,V=000,001,V=000,001, , 111,

54、111, ijk,uvwijk,uvwE E当且仅当条件当且仅当条件(1)(1)成立成立, ,的一条的一条HamiltonHamilton路路.(.(解存在但不唯一解存在但不唯一) )111110101100000010011 001000001011111110100101010有向线图有向线图的的邻接矩阵邻接矩阵 定义定义 将有向线图将有向线图G=G= V,EV,E 的结点集的结点集强行命名强行命名( (标标定次序定次序) )为为 V=1,2,V=1,2,n,n,则则n n阶阶(0,1)(0,1)方阵方阵A=(aA=(aijij) )称为的称为的G G邻接矩阵邻接矩阵, ,其中其中当当(i

55、,j)(i,j) E,aE,aijij=1;=1;否则否则,a,aijij=0.=0. 注注 邻接矩阵与结点的邻接矩阵与结点的标定次序有关标定次序有关, ,不同的不同的标定次序对应的邻接矩阵不同标定次序对应的邻接矩阵不同, ,但这两个矩阵但这两个矩阵置换相似置换相似, ,即适当地交换行和列的次序能从一即适当地交换行和列的次序能从一个邻接矩阵变到另一个个邻接矩阵变到另一个. .或者说或者说, ,它们对应的有它们对应的有向线图同构向线图同构. . 有向线图在标定次序后得到唯一邻接矩阵有向线图在标定次序后得到唯一邻接矩阵; ;一个一个n n阶阶(0,1)(0,1)方阵对应唯一标定次序的有向线方阵对应

56、唯一标定次序的有向线图图. .换句话说换句话说, ,不计图的同构和矩阵的置换相似不计图的同构和矩阵的置换相似有向线图与一个有向线图与一个n n阶阶(0,1)(0,1)方阵一一对应方阵一一对应. .有限集有限集V V上的关系上的关系R R的的图示图示是以为是以为V V结结点集的一个点集的一个有向线图有向线图 易见易见: :关系关系R R的的关系矩阵关系矩阵正是正是R R的图示作为有向的图示作为有向线图的线图的邻接矩阵邻接矩阵. . 一个有向线图一个有向线图G=G= V,EV,E 对应的关系对应的关系R R的逆关系的逆关系R R 对应的有向线图对应的有向线图G G = = V,EV,E 称为称为G

57、 G的的逆图逆图.G.G与与G G 有有相同相同( (的强行命名的强行命名) )的结点集的结点集, ,并且并且(i,j)(i,j) E E (j,i)(j,i) E E . . 逆图逆图G G 的邻接矩阵的邻接矩阵A A 与原图的邻接矩阵与原图的邻接矩阵A A之间的之间的关系是关系是: : A A =A=AT T. .无向线图无向线图与与赋权图赋权图的的邻接矩阵邻接矩阵 定义定义 无向线图无向线图G=G= V,EV,E ,V=1,2,V=1,2,n,n的邻接矩的邻接矩阵是阵是n n阶阶(0,1)(0,1)方阵方阵A=(aA=(aijij),),其中其中当当(i,j)(i,j) E,aE,aij

58、ij=a=ajiji=1;=1;否则否则,a,aijij=a=ajiji=0.=0.由此可见由此可见, ,无向线图的邻接矩阵是对称矩阵无向线图的邻接矩阵是对称矩阵: : A=AA=AT T. .例如例如, ,零图的邻接矩阵是零矩阵零图的邻接矩阵是零矩阵; ; 完全图完全图K Kn n的邻接的邻接矩阵是恰有矩阵是恰有n n个个0 0并全在对角线上的并全在对角线上的n n阶阶(0,1)(0,1)方方阵阵. . 定义定义 赋权图赋权图G=G= V,E,WV,E,W ,V=1,2,V=1,2,n,n的邻接矩的邻接矩阵是阵是n n阶阶(0,1)(0,1)方阵方阵A=(aA=(aijij),),其中其中当

59、当(i,j)(i,j) E,aE,aijij=W(i,j);=W(i,j);否则否则,a,aijij=0.=0.邻接矩阵邻接矩阵的图论意义的图论意义设设A A为有向线图为有向线图G G的邻接矩阵的邻接矩阵. . A A的第的第i i行行( (列列) )和和等于第等于第i i结点结点的出的出( (入入) )度度, ,i=1,i=1,n.n. B=AA B=AAT T= =( (b bijij) )的元素的元素 b bijij=a=ai1i1a aj1j1+ +a+ainina ajnjn=k=k表示有表示有k k个点个点, ,它们都是从它们都是从i,ji,j引引出的有向边的公共交点出的有向边的公

60、共交点. .特别特别, ,b biiii是第是第i i结点的出度结点的出度. .对偶地对偶地可讨论可讨论A AT TA A的元素的图论意义的元素的图论意义. . A A2 2=AA=AA=(a(aijij(2)(2) )的元素的元素a aijij(2)(2)=a=ai1i1a a1j1j+ +a+ainina anjnj=k=k表示有表示有k k个点个点, ,它们都是从它们都是从i i到到j j长为长为2 2的有向路的有向路径的中点径的中点, ,即从即从i i到到j j长为长为2 2的路径恰有的路径恰有k k条条. .一般一般地地, ,从从i i到到j j长为长为m m的路径恰有的路径恰有a