1、图论简介简介图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。本课程在第七，八，九各章中介绍与计算机科学关系密切的图论的内容。第七章第七章 图的基本概念图的基本概念 第一节第一节 无向图及有向图无向图及有向图 内容：内容：有向图，无向图的基本概念。重点：重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等
2、基本概念，3、各顶点度数与边数的关系1()2niid vm及推论，内容：内容：有向图，无向图的基本概念。5、图的同构的定义。重点：重点：4、简单图，完全图，子图，补图的概念，一、图的概念。一、图的概念。1、定义定义。无序积&(,)ABa b aAbB 无向图,GV E&EVV中元素为无向边，简称边。，E有向图,DV EEVV中元素为有向边，简称边。，E一、图的概念。一、图的概念。1、定义定义。无序积&(,)ABa b aAbB,(),(),(),()GV EVV G EE GDV EVV D EE D无向图记为记为图有向图记为记为2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边无向边
3、(,)a b连接顶点,a b的线段。有向边有向边,a b以a为始点，以b为终点的有向线段。例例1、(1)无向图,GV E12345,Vv v v v v，122223131314(,),(,),(,),(,),(,),(,)Ev vv vv vv vv vv v图形表示如右：6e5e4e3e2e1e5v4v3v2v1v图形表示如右：例例1、(2)有向图,DV E12345,Vv v v v v，12323234,Ev vv vv vv v24455455,v vv vv vv v3、相关概念。(1)有限图有限图都是有限集的图。,V E阶图阶图n的图。Vn零图零图的图。特别，若又有E1V，称平凡
4、图。(2)关联关联(边与点关系边与点关系)设边(,)kijev v(或,ijv v)，则称与(或)关联。keivjv3、相关概念。01122ikikikkvevevee与 不关联无向图关联的次数与 关联 次与 关联 次(为环)(2)101ikikikveveve为 的始点与 不关联为 的终点有向图关联的次数(无环)3、相关概念。(2)点的相邻两点间有边，称此两点相邻边的相邻两边有公共端点，称此两边相邻相相邻邻孤立点孤立点无边关联的点。环环一条边关联的两个顶点重合，称此边为环(即两顶点重合的边)。3、相关概念。(2)悬挂点悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边平行边关联于
5、同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图多重图含有平行边的图。简单图简单图不含平行边和环的图。如例1的(1)中，6e5e4e3e2e1e5v4v3v2v1v与关联的次数均为1，1e12,v v与关联的次数为2，2e2v边1456,e e e e都是相邻的，为孤立点，5v为悬挂点，4v6e为悬挂边，2e为环，45,e e为平行边，重数2，为多重图。G4、完全图设为阶无向简单图，若,GV En中每个G顶点都与其余个顶点相邻，则称 1n为Gn阶阶无向完全图无向完全图，记作nK。若有向图的任一对顶点D,()u v uv，既有有向边,u v又有有向边,v u，则称为有向完全图有向完全
6、图。D例如：4K5K二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与,GV Eiv，()id viv相关联的边的条数。有向图的度数,GV Eiv，()()()iiid vdvdv二、顶点的度数，握手定理。二、顶点的度数，握手定理。1、顶点的度数(简称度)。最大度最大度()max()Gd v vV最小度最小度()min()Gd v vV对有向图相应地还有()D()D()G()G，。如例1的(2)中，222()()()d vdvdv134 111()()()d vdvdv101 555()()()224d vdvdv()4D，()1D。设为图的顶点
7、集，称 11,nVv vvG12(),(),()nd vd vd v为的度数序列度数序列。G2、握手定理。定理定理1：设图为无向图或有向图，,GV E11,nVv vvEm为边数)，m，(则1()2niid vm定理定理2：设为有向图，,DV E11,nVv vvEm，则，11()()nniiiidvdvm。2、握手定理推论：推论：任何图中，度为奇数的顶点个数为偶数。1()2niid vm例例2、(1)(3,3,2,3)(5,2,3,1,4)能成为图的度数，序列吗？为什么？(2)已知图中有10条边，4个3度顶点，其余顶G点的度数均小于3，问中至少有多少个顶点？为什么？G三、子图，补图。三、子图
8、，补图。1、子图定义：子图定义：设是两个图，若,GV E,GVE，VV，且EE，则称G是的子图子图，GG是的母图母图，记作GGG。真子图真子图 且(即或GGGGVVEE)。生成子图生成子图且GGVV。三、子图，补图。三、子图，补图。导出子图导出子图 非空，以为顶点集，VVV以两端均在中的边的全体为边集的VG的子图，称的导出子图。V非空EE，以E为边集，以中边关联的顶点的全体为顶点集的EG的子图，称的导出子图。E例例3、(1)(2)(3)(4)(5)(6)上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。2、补图定义补图定义。设为无向完全图，11,GV E,
9、GV E，22,GV E为无向简单图，其中12EE，12EEE，则称1G2G，相对于G互为补图，记12GG21GG，。(1)(2)(3)(4)(5)(6)如例3中，四、图的同构。四、图的同构。定义定义：设两个无向图111,GV E，222,GV E，若存在双射函数12:VV，使得对于任意的1(,)ijev vE，当且仅当2(),()ijevvE并且与重数相同，则称e e与同构同构，1G2G记作12GG。例例4、(1)(2)(3)(4)(5)(6)(7)1v2v3v4v5v5v1v2v3v4v6vecacaefbddb例例5、(1)画出4个顶点，3条边的所有非同构的无向简单图。解：解：只有如下3
10、个图：(1.1)(1.2)(1.3)例例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：解：只有如下4个图：第二节第二节 通路，回路，图的连通性通路，回路，图的连通性 内容：内容：图的通路，回路，连通性。重点：重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、通路，回路。一、通路，回路。1、通路通路(回路回路)中顶点和边的交替序列G0 1 1 2llv e v eev，其中1(,)iiievv(无向图)，或1,iiievv(有向图)，始点始点，0v终点终点，称为到lv0vlv的通路通路。当0lvv时，为回路回路。一、通路，
11、回路。一、通路，回路。2、简单通路，简单回路。简单通路简单通路(迹迹)简单回路简单回路(闭迹闭迹)复杂通路复杂通路(回路回路)一、通路，回路。一、通路，回路。3、初级通路，初级回路。初级通路初级通路(路径路径)初级回路初级回路(圈圈)初级通路(回路)简单通路(回路)，但反之不真。4、通路，回路 的长度中边的数目。例例1、(1)图(1)中，从的通路有：到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v
12、e v 长度3长度6长度6例例1、(1)图(1)中，从的通路有：到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v e v 初级通路简单通路复杂通路例例1、(2)1244 3 3 22v e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3244 3 3 22 5 5 64 3 3 22v e v e v e v e v e v e v e v 长度3长度4长
13、度7图(2)中过)有：的回路(从2v2v到2v例例1、(2)1244 3 3 22v e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3244 3 3 22 5 5 64 3 3 22v e v e v e v e v e v e v e v 初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路(从2v2v到2v5、图中最短的回路。如图：6、性质。定理：定理：阶图中，若从顶点nivjv到存在通路()ijvv，则从ivjv到存在长度小于等于在一个的通路。1n推论：推论：阶图中，若从顶点nivjv到存在通路()ijvv，则从ivjv到存在长度小于
14、等于在一个的初级通路。1n6、性质。定理：定理：阶图中，若niv到自身存在回路，则从到自身存在长度小于等于ivn的回路。在一个推论：推论：阶图中，若niv到自身存在一个简单回路，则从 到自身存在长度小于等于ivn的初级回路。在一个6、性质。由以上定理可知，在阶图中，n任何一条初级通路的长度任何一条初级回路的长度1nn二、图的连通性。二、图的连通性。1、连通，可达。无向图中，从 到存在通路，称ivjv到ivjv是连通的连通的(双向双向)。有向图中，从 到存在通路，称ivjv可达可达ivjv(注意方向)。2、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记,ijd V V
15、(,)ijd V V无向图有向图2、短程线，距离。若之间无通路(或不可达)，规定,ijv v(,),ijijd v vd v v 距离满足：,ijd v v(1)，时，等号成立。,0ijd v vijvv(2),ijjkikd v vd v vd v v若是无向图，还具有对称性，(,)(,)ijjid v vd v v。3、无向图的连通。为连通图为连通图是平凡图，或都是连通的。GGG中任两点为非连通图为非连通图G中至少有两点不连通。G3、无向图的连通。设是一个无向图，是GRG中顶点之间的连通关系，则是等价关系等价关系。R设将划分成个等价类：R()V G(1)k k 12,kV VV，由它们导出
16、的子图 12,G VG V,kG V称为的连通分支连通分支，其个数记为G()p G4、有向图的连通。中任一对顶点都互相可达D(双向)中任一对顶点至少一向可达D略去 中有向边的方向后得到的无向图连通D连通强连通单向连通弱连通强连通单向连通弱连通例例2、强连通单向连通例例2、单向连通弱连通非连通图第三节第三节 图的矩阵表示图的矩阵表示内容：内容：关联矩阵，邻接矩阵，可达矩阵。重点：重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：了解：有向图的可达矩阵。一、无向图的关联矩阵。一、无向图的关联矩阵。1、设无向图,GV E12,nVv vv，12,mEe ee，的关联矩阵G()()ijn
17、 mM Gm，01122()ijijijijjivemveveev与 不关联其中与 关联 次与 关联 次 即 是以 为端点的环例例1、无向图(下图所示)，求G()M G。1v2v3v4v1e2e3e4e5e1110001110()1001200000M G解：2、性质性质。12nijim(1)1()mijijmd v(2)(3)111112()mnnmnijijijiijimmmd v握手定理(4)10mijjm，当且仅当为孤立点。iv2、性质性质。(5)若第 列与第列相同，则说明jk与jeke为平行边。二、有向图的关联矩阵。二、有向图的关联矩阵。1、设无环有向图,DV E12,nVv vv，
18、12,mEe ee，的关联矩阵D()()ijn mM Dm，101ijijijijvemveve为 的始点与 不关联为 的终点其中例例2、有向图(下图所示)，求D()M D。1100010111()0000101110M D解：解：2、性质性质。(1)10nijim(2)1()mijijmd v(3)110mnijjim三、有向图的邻接矩阵。三、有向图的邻接矩阵。1、设有向图,DV E12,nVv vv，EmD的邻接矩阵(1)()ijn nA Da，其中指邻接到的边的条数(非负整数)。(1)ijaivjv例例3、有向图(下图所示)，求D()A D。解：解：12100010()00010010A
19、 D2、性质性质。(1)(1)1()nijijadv(2)(1)1()nijjiadv(3)(1)111()nnnijiijiadvm(4)(1)1niiia为中环的个数。D3、求中长度为 的通路数和回路数。Dl(1)令2()()()ADA D A D矩阵乘法(2)()ijn na其中(2)1nijikkjkaa a10ikjikkjikjvvva avvv有通路无通路表示从到长度为2的通路数(2)ijaivjv()ij或回路数()ij。3、求中长度为 的通路数和回路数。Dl考虑，简记为()lA DlA。1llAAA()()lijn na其中()(1)(1)1nllijikkjkaaa表示从到
20、长度为()lijaivjv()ij或回路数()ij。的通路数l(),liji ja中长度为为D的通路总数，其中()liiial为 中长度为 的回路总数。Dl3、求中长度为 的通路数和回路数。Dl(2)设2(1)rrBAAAr则中元素为中到rB()rijbDivjv长度小于等于r的通路总数，(),riji jb为中长度小于等于Dr的通路总数，其中为D中长度小于等于r()riiib的回路总数。例例4、在例3的有向图中求，。D2A3A4A解：解：21231000100100001A，41264000100100001A31243001000010010A，四、有向图的可达性矩阵。四、有向图的可达性矩
21、阵。(了解了解)设为有向图，,DV E12,nVv vv令1iip，1,2,in1()0ijijvvpij可达否则四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)可达性矩阵()ijn nPp其中元素可由求得：()ijp ij(1)1nnijn nBb(1)100nijijbp否则第七章第七章 小结与例题小结与例题一、无向图与有向图。一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。一、无向图与有向图。一、无向图与有向图。2、运用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构
22、，(3)画出满足某些条件的子图，补图等。二、通路，回路，图的连通性。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。二、通路，回路，图的连通性。二、通路，回路，图的连通性。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。三、图的矩阵表示。三、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点k到另一顶点的长度为k的通路数。例例1、设图，其中,GV E,
23、Va b c d e，分别由下面给出。判断哪些是简单图，哪些E是多重图？(,),(,),(,),(,)Ea bb cc da e(1)(,),(,),(,),(,),(,)Ea bb ee ba ed e(2)(,),(,),(,),(,)Ea bb ee dc c(3)简单图多重图不是例例1、设图，其中,GV E,Va b c d e，分别由下面给出。判断哪些是简单图，哪些E是多重图？,Ea bb cc aa dd ad e(4),Ea ba bb cc dd e(5),Ea aa bb ce ce d(6)简单图多重图不是例例2、下列各序列中，可以构成无向简单图的度数序列的有哪些？(1)(
24、2,2,2,2,2)可以(2)(1,1,2,2,3)不可以(3)(1,1,2,2,2)可以(4)(0,1,3,3,3)不可以(5)(1,3,4,4,5)不可以abcde例例3、右图所示的无向图中，分别求：不同的初级通路(路径)。(1),a d之间所有解：解：有7条，分别为aed aecd aebcd abcdabedabcedabecd，和，。(2),a d之间的短程线。(3)(,)d a d。解：解：aed。解：解：(,)2d a d。例例4、(1)画出完全图的所有非同构的生成子图。4K解：解：例例4、(1)画出完全图的所有非同构的生成子图。4K解：解：例例4、(1)画出完全图的所有非同构的
25、生成子图。4K(2)的生成子图有几个是连通图？4K解：解：有6个：例例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通例例5、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强连通强连通例例6、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，3()_dv(1)1()_dv2()_d v2422()()2dvdv例例6、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()
26、51234123A D，(2)从到长度为2的通路数。1v4v解：解：因，所以从 到 长度为2的通路数为2。(2)142a1v4v例例6、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，(3)从到长度为3的通路数。3v1v解：解：因，所以从 到 长度为3的通路数为5。(3)315a3v1v例例6、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，(4)过长度为3的回路数。4v解：解：因，所以过 长
27、度为3的回路数为3。(3)443a4v例例7、下列各图中各有多少个顶点。(1)16条边，每个顶点的度数均为2。解：解：设顶点数为，x由握手定理，有22 16x，解得16x。解：解：设顶点数为x，解得13x。(2)21条边，3个度数为4的顶点，其余顶点的度数均为3。有4 33(3)2 21x，由握手定理，例例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。解：解：设顶点数为，由握手定理，x设每个顶点的度数均为，y其正整数解(,)x y有：(2,24)(24,2)(3,16)(16,3)(4,12)(12,4)(6,8)(8,6)，。2 24x y，则有例例7、下列各图中各有多少个顶点。(3)24条边，每个顶点的度数均相同。解：解：所以答案有以下八种：2个24度顶点，()a24个2度顶点，()b3个16度顶点，()c16个3度顶点，()d4个12度顶点，()e12个4度顶点，()f6个8度顶点，()g8个6度顶点。()h例例8、设为9个顶点的无向图，每个顶点的度数G不是5就是6。证明 中至少有5个6度顶点或者至G少有6个5度顶点。证明：证明：由握手定理的推论知，中5度顶点的个数G只能是0，2，4，6，8这五种情形。此时6度顶点的个数分别为9，7，5，3，1这五种情形，不论何种情形，均满足结论要求。
