1、图论简介简介图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。第八章第八章 图论图论 第一节第一节 图的基本概念图的基本概念 内容：内容：有向图，无向图的基本概念。重点：重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系1()2niid vm及推论，内容：内容：有向图
2、，无向图的基本概念。5、图的同构的定义。重点：重点：4、简单图，完全图，子图，补图的概念，2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边无向边(,)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 v24
3、455455,v vv vv vv v3、相关概念。(1)有限图有限图都是有限集的图。,V E阶图阶图n的图。Vn零图零图的图。特别，若又有E1V，称平凡图。(2)关联关联(边与点关系边与点关系)设边(,)kijev v(或,ijv v)，则称与(或)关联。keivjv3、相关概念。01122ikikikkvevevee与 不关联无向图关联的次数与 关联 次与 关联 次(为环)(2)101ikikikveveve为 的始点与 不关联为 的终点有向图关联的次数(无环)3、相关概念。(2)点的相邻两点间有边，称此两点相邻边的相邻两边有公共端点，称此两边相邻相相邻邻孤立点孤立点无边关联的点。环环一条
4、边关联的两个顶点重合，称此边为环(即两顶点重合的边)。3、相关概念。(2)悬挂点悬挂点只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边平行边关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图多重图含有平行边的图。简单图简单图不含平行边和环的图。如例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顶点都与其余个顶点相邻，则
5、称 1n为Gn阶阶无向完全图无向完全图，记作nK。若有向图的任一对顶点D,()u v uv，既有有向边,u v又有有向边,v u，则称为有向完全图有向完全图。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)
6、中，222()()()d vdvdv134 111()()()d vdvdv101 555()()()224d vdvdv()4D，()1D。设为图的顶点集，称 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三、子图，补图。三、子图，补图。1、子图定义：子图定义
7、：设是两个图，若,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,GV E，22,GV E为无向
8、简单图，其中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个图：(1.1)(1.2)(1
9、.3)例例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：解：只有如下4个图：第二节第二节 路径和回路（路径和回路（1）内容：内容：图的通路，回路，连通性。重点：重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、路径，回路。一、路径，回路。1、路径路径(回路回路)中顶点和边的交替序列G0 1 1 2llv e v eev，其中1(,)iiievv(无向图)，或1,iiievv(有向图)，始点始点，0v终点终点，称为到lv0vlv的通路通路。当0lvv时，为回路回路。一、路径，回路。一、路径，回路。2、简单路径，简单回路。简
10、单路径简单路径(迹迹)：同一条边不出现两次：同一条边不出现两次基本路径（链）：同一顶点不出现两次基本路径（链）：同一顶点不出现两次简单回路简单回路(闭迹闭迹)：没有相同边的回路：没有相同边的回路基本回路：通过各顶点不超过一次的回路基本回路：通过各顶点不超过一次的回路一、路径，回路。一、路径，回路。基本路径(回路)简单路径(回路)，但反之不真。3、路径，回路 的长度中边的数目。例例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 6
11、442 5 5 76v e v e v e v e v e v 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
12、 e v e v e v e v e v e v 长度3长度4长度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到2v4、性质。定理定理1：阶图中，若从顶点nivjv到存在路径()ijvv，则从ivjv到存在长度小于等于在一个的基本路径。（定理8.2-1）1n4、性质。定理定理2：阶图中
13、，若niv到自身存在一个简单回路，则从 到自身存在长度小于等于ivn的基本回路。（定理8.2-2）在一个二、图的连通度。二、图的连通度。1、连通，可达。无向图中，从 到存在通路，称ivjv到ivjv是连通的连通的(双向双向)。有向图中，从 到存在通路，称ivjv可达可达ivjv(注意方向)。2、短程线，距离。短程线连通或可达的两点间长度最短的通路。距离短程线的长度，记,ijd V V(,)ijd V V无向图有向图3、无向图的连通。为连通图为连通图是平凡图，或都是连通的。GGG中任两点为非连通图为非连通图G中至少有两点不连通。G3、无向图的连通。设是一个无向图，是GRG中顶点之间的连通关系，则
14、是等价关系等价关系。R设将划分成个等价类：R()V G(1)k k 12,kV VV，由它们导出的子图 12,G VG V,kG V称为的连通分支连通分支，其个数记为G()p G4、有向图的连通。中任一对顶点都互相可达D(双向)中任一对顶点至少一向可达D略去 中有向边的方向后得到的无向图连通D连通强连通单向连通弱连通强连通单向连通弱连通例例2、强连通单向连通例例2、单向连通弱连通非连通图8.2 路径与回路（路径与回路（2）内容：内容：欧拉、哈密尔顿路径、赋权图中的最短路径。重点：重点：1、欧拉图的定义，无向图是否具有 欧拉回路的判定2、迪克斯特拉算法计算赋权图的最短路径了解：了解：无向图是否具
15、有哈密尔顿回路的判定。一、欧拉回路问题的提出。一、欧拉回路问题的提出。1736年，瑞士数学家欧拉，哥尼斯堡七桥问题(2)BACD二、定义。欧拉通路欧拉通路(欧拉迹欧拉迹)通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路欧拉回路(欧拉闭迹欧拉闭迹)通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图欧拉图 存在欧拉回路的图。注意：注意：(1)欧拉通路与欧拉回路不同。(2)欧拉图指具有欧拉回路(并非通路)的图。(3)欧拉通路(回路)必是简单通路(回路)。(4)连通是具有欧拉通路(回路)的必要条件。(5)欧拉通路(回路)是经过图中所有边的通路(回路)中最短的通路(回路)。三、无向图是否
16、具有欧拉通路或回路的判定。三、无向图是否具有欧拉通路或回路的判定。有欧拉通路连通，G GG中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)GG连通，G中均G为偶度顶点。例例1、以下图形能否一笔画成？(1)(2)例例1、以下图形能否一笔画成？(3)(4)例例2、两只蚂蚁比赛问题。G图abc(甲)(乙)两只蚂蚁甲、乙分别处在图中的顶点处，并设图,a bG中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点处。如果它们速度相同，问谁最先到达目的地？c四、有向图是否具有欧拉通路或回路的判定。四、有向图是否具有欧拉通路或回路的判定。有欧拉通路连通，除两
17、个顶点外，其D D余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(DD为欧拉图)连通，DD中所有顶点的入度等于出度。例例3、判断以下有向图是否欧拉图。二、哈密尔顿图二、哈密尔顿图一、问题的提出。一、问题的提出。1859年，英国数学家哈密尔顿，周游世界游戏。(1)(2)二、哈密尔顿图。二、哈密尔顿图。哈密尔顿通路 通过图中每个顶点一次且仅一次的通路。哈密尔顿回路 通过图中每个顶点一次且仅一次的回路。哈密尔顿图存在哈密尔顿回路的图。注意：注意：(1)哈密尔顿通路与哈密尔顿回路不同。(2)哈密尔顿图是指具有哈密尔顿回路(并非通路)的图。(
18、3)哈密尔顿通路(回路)必是初级通路(回路)。(4)连通是具有哈密尔顿通路(回路)的必要条件。注意：注意：(5)若图通路。G具有哈密尔顿回路，则必有哈密尔顿(6)阶图的哈密尔顿通路长为n1n，回路长为n。三、判定。三、判定。采用尝试的办法。例例1、判断下图是否具有哈密尔顿回路，通路。(1)解：解：存在哈密尔顿通路，但不存在哈密尔顿回路。例例1、判断下图是否具有哈密尔顿回路，通路。解：解：是哈密尔顿图，存在哈密尔顿回路和通路。(2)例例1、判断下图是否具有哈密尔顿回路，通路。解：解：不存在哈密尔顿回路，也不存在哈密尔顿通路。(3)哈密尔顿回路存在的两件个充分条件 定理8.2-13 设 是具有 个
19、顶点的简单无向图，若在G中每一对顶点的次数之和大于n,则在G中存在一条哈密尔顿回路。EVG,3n推论8.2-13 在简单无向图中，若每一顶点的次数则在G中存在一条哈密尔顿回路。n2170三、最短路径三、最短路径定义定义 设设G=(V，E)是无向简单图，如果对是无向简单图，如果对E中每条边中每条边e都有一个实数都有一个实数w(e)附着其上，则称附着其上，则称G为为权图权图，称，称w(e)为为边边e的的权权。设。设P是是G的一条路，的一条路，P上所带权的总和称为路上所带权的总和称为路P的的权权。有时记为。有时记为G=(V，E，W)725351433abcdef71设权图设权图G中每条边的权均大于等
20、于中每条边的权均大于等于0，u,v为为G中任意中任意的两个顶点，从的两个顶点，从u到到v的所有路中权最小的路称为的所有路中权最小的路称为u到到v的的最短路径最短路径，求给定的两顶点之间的最短路径问题，求给定的两顶点之间的最短路径问题称为称为最短路径问题最短路径问题。最短路径最短路径算法算法：由由E.W.Dijkstra（迪克斯特拉）于（迪克斯特拉）于1959年给出的标号法（年给出的标号法（Dijkstra算法）。算法）。三、最短路径三、最短路径72问题问题：图：图G=(V,E,W),1V,求求1到到V其它点的最短距离。其它点的最短距离。设设S为最短距离已经确定的集合，为最短距离已经确定的集合，
21、T为最短距离未确定的集合。为最短距离未确定的集合。算法描述如下：算法描述如下：(1)初始话：初始话：S=1，T=V-S。(2)求求1经过经过S中的点。到中的点。到T中点的最短距离。记为中点的最短距离。记为D(i)。D(i)=w(1,i)(3)选选T中中D(i)值最小的点值最小的点i，记为，记为k。把。把k加入加入S，T=V-S。(4)对对T中的点中的点i更新更新D(i)：若若D(k)+W(i,k)D(i)，D(i)=D(k)+W(i,k)(5)T为空集，算法结束。为空集，算法结束。三、最短路径三、最短路径73651227411abcdef例例 用用Dijkstra求下图中求下图中a到到d的最短
22、路径。的最短路径。abcdefa62 2f37 93b595ce9d67 7674四、最短路径四、最短路径例例 求下图中求下图中a到到f的最短路径。的最短路径。254171411abdfec13A,b,d,c,e,f 68.3 图的矩阵表示图的矩阵表示内容：内容：邻接矩阵，关联矩阵，可达矩阵。重点：重点：1、有向图的邻接矩阵。2、有向图，无向图的关联矩阵。了解：了解：有向图的可达矩阵。一、有向图的邻接矩阵。一、有向图的邻接矩阵。1、设有向图,DV E12,nVv vv，EmD的邻接矩阵(1)()ijn nA Da，其中指邻接到的边的条数(非负整数)。(1)ijaivjv例例1、有向图(下图所示
23、)，求D()A D。解：解：12100010()00010010A D2、性质性质。(1)(1)1()nijijadv(2)(1)1()nijjiadv(3)(1)111()nnnijiijiadvm(4)(1)1niiia为中环的个数。D3.的元素的意义 设 ，则 。表示：从结点 和 两者引出的边，如果能共同终止于一些结点，则 就是这些终止结点的数目。TAATijAAbBjknkikijaab1jvivijb特别地：时，对角线上的元素 就是结点 的引出次数。ji iibiv4.的元素的意义 设 ，则 。表示：从一些结点引出的边，如果能同时终止于 和 ，则 就是这样的结点数目。AAT,AAbB
24、Tijkjnkkiijaab1ivijbjv特别地：时，对角线上的元素 就是结点 的引出次数。ji iibiv5、求中长度为 的通路数和回路数。Dl(1)令矩阵乘法(2)()ijn na其中(2)1nijikkjkaa a10ikjikkjikjvvva avvv有通路无通路表示从到长度为2的通路数(2)ijaivjv()ij或回路数()ij。)()()(2DADADA5、求中长度为 的通路数和回路数。Dl考虑，简记为()lA DlA。()()lijn na其中()(1)(1)1nllijikkjkaaa表示从到长度为()lijaivjv()ij或回路数()ij。的通路数l(),liji ja
25、中长度为为D的通路总数，其中()liiial为 中长度为 的回路总数。DlAAAll15、求中长度为 的通路数和回路数。Dl(2)设2(1)rrBAAAr则中元素为中到rB()rijbDivjv长度小于等于r的通路总数，(),riji jb为中长度小于等于Dr的通路总数，其中为D中长度小于等于r()riiib的回路总数。例例4、在例1的有向图中求，。D2A3A4A解：解：21231000100100001A，41264000100100001A31243001000010010A，二、无向图的关联矩阵。二、无向图的关联矩阵。1、设无向图,GV E12,nVv vv，12,mEe ee，的关联矩
26、阵G()()ijn mM Gm，01122()ijijijijjivemveveev与 不关联其中与 关联 次与 关联 次 即 是以 为端点的环例例2、无向图(下图所示)，求G()M G。1v2v3v4v1e2e3e4e5e1110001110()1001200000M G解：2、性质性质。12nijim(1)1()mijijmd v(2)(3)111112()mnnmnijijijiijimmmd v握手定理（m为边数）（每列之和为2表示每条边只有两个顶点）（每行之和表示对应点的度数）(4)10mijjm，当且仅当为孤立点。iv2、性质性质。(5)若第 列与第列相同，则说明jk与jeke为平
27、行边。三、有向简单图（无环）的关联矩阵。三、有向简单图（无环）的关联矩阵。1、设无环有向图,DV E12,nVv vv，12,mEe ee，的关联矩阵D()()ijn mM Dm，101ijijijijvemveve为 的始点与 不关联为 的终点其中例例2、有向图(下图所示)，求D()M D。1100010111()0000101110M D解：解：2、性质性质。(1)10nijim(2)1()mijijmd v(3)110mnijjim四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)设为有向图，,DV E12,nVv vv令1iip，1,2,in1()0ijijvvpij可达否则
28、四、有向图的可达性矩阵。四、有向图的可达性矩阵。(了解了解)可达性矩阵()ijn nPp其中元素可由求得：()ijp ij(1)1nnijn nBb(1)100nijijbp否则8.7 树树一一.无向树及生成树无向树及生成树 内容：内容：无向树，生成树。重点：重点：1、无向树的定义(包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或基本回路。一、无向树。一、无向树。1、无向树无向树 连通且不含回路的无向图。无向树简称树，常用表示。T平凡树平凡树 平凡图（仅有一个结点的简单图）。森林森林 连通分支数大于等于2，且每个连通分支都是树的无向
29、图。T树叶度数为1的顶点树 的顶点分支点度数大于1的顶点例例1、(1)fceadb(2)(3)例例1、(4)2、树的六个等价定义。(1)连通且不含回路。G(2)的每对顶点间具有唯一的路径。G(3)连通且G1nm。(4)无回路且G1nm。定理：定理：设,GV EVnEm，则以下命题等价。2、树的六个等价定义。(5)无回路，但在G中任两个不相邻的顶点G之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不G连通了。3、性质性质。(1)树中顶点数与边数的关系：1nm。(2)定理定理：非平凡树至少2片树叶。证明：证明：设为阶非平凡树，,TV En设有 片树叶，则有Tk个顶点
30、度数大于等()nk于2，12()2()niimd vknk由握手定理，又由(1)1mn，代入上式，解得2k，即至少2片叶。T例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)1 1 1 1 151T例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)1 1 1 1242T例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3
31、)1 1 1 1333T例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)1 1 12234T5T例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)1 122226T二、生成树。二、生成树。1、定义：定义：设是无向连通图，,GV ET是G的生成子图，若T是树，称T是G的生成树。树枝树枝弦弦余树余树GT在中的边，GT不在中的边，T的所有的弦的集合的导出子图。例例4、(3)(2)(1)上图中，(2)是(1)的生成
32、树，(3)是(2)的余树。注意：注意：(1)生成树不唯一，(2)余树不一定是树。2、连通图的性质连通图的性质。设,GV E为连通图，Vn，Em，(1)至少有一棵生成树，G(2)1mn，(3)设是TG的生成树，T是T的余树，则T中有1mn条边。已知连通图，求其生成树步骤。G3、最小生成树。对于有向图或无向图的每条边附加一个实数G()w e，则称()w e为边e上的权权，G连同附加在各边上的实数称为带权图带权图，记为,GV E W。最小生成树最小生成树 各边权和最小的生成树。定义：定义：设无向连通带权图,GV E W，T是G的一棵生成树，T各边带权之和称为T的权，记作()W T。求最小生成树的方法
33、Kruskal（克鲁斯克尔（克鲁斯克尔)避圈法避圈法。设阶无向连通带权图n,GV E W中有m条边12,me ee，它们带的权分别为12,ma aa，不妨设12maaa，(1)取1e在T中(非环，若1e为环，则弃1e)。(2)若不与2e1e构成回路，取2e在T中，否则弃2e，再查3e，继续这一过程，直到形成树为止。cdefba解：解：1T例例5、求以下连通图的最小生成树及T()W T。(1)6643215555fabcde123541()15W T54321bcdefa解：解：1T例例5、求以下连通图的最小生成树及T()W T。(1)6643215555fabcde1()15()W TW Tf
34、edcba解：解：2T例例6、求以下连通图的最小生成树及T()W T。(2)987764321105abcdef123572()18W T75321fedcba解：解：2T例例6、求以下连通图的最小生成树及T()W T。(2)987764321105abcdef2()18()W TW T注意：注意：的最小生成树可能不唯一，G但G的不同最小生成树权的值一样。第八章第八章 小结与例题小结与例题一、无向图与有向图。一、无向图与有向图。1、基本概念。有向图与无向图的定义；关联与邻接(相邻)；顶点的度数；零图与平凡图；简单图与多重图；完全图；子图，补图；图的同构。一、无向图与有向图。一、无向图与有向图。
35、2、运用。(1)灵活运用握手定理及其推论，(2)判断两个图是否同构，(3)画出满足某些条件的子图，补图等。二、通路，回路，图的连通性。二、通路，回路，图的连通性。1、基本概念。通路和回路；无向图和有向图中顶点之间的可达关系；短程线，距离；有向图连通的分类。二、通路，回路，图的连通性。二、通路，回路，图的连通性。2、运用。(1)判断有向图或无向图中通路(回路)的类型。(2)求短程线和距离。(3)判断有向图连通的类型。三、欧拉图。三、欧拉图。1、基本概念。欧拉通路，欧拉回路，欧拉图。2、运用。判定无向图是否具有欧拉通路或回路。四、哈密尔顿图。四、哈密尔顿图。1、基本概念。哈密尔顿通路，哈密尔顿回路
36、，哈密尔顿图。2、运用。判断无向图是否具有哈密尔顿通路或回路。五、图的矩阵表示。五、图的矩阵表示。1、基本概念。无向图的关联矩阵，有向图的关联矩阵和邻接矩阵。2、运用。(1)关联矩阵的行和、顶点度数间的关系。(2)由有向图的邻接矩阵的次幂求从一顶点k到另一顶点的长度为k的通路数。六、无向树及生成树。六、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3)根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4)求生成树，最小生成树。七、应用七、应用1、赋权图的最短路径迪克斯特拉算法2、最小生成树克鲁斯克尔算法例例1、设图，其中,GV E,Va
37、 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)(2,
38、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、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？强连通单向连通弱连通例例4、下图所示的六个图中，强连通，单向连通，弱连通的分别有哪些？单向连通强
39、连通强连通例例5、画一个欧拉图，使它具有：(1)偶数个顶点，偶数条边。(2)奇数个顶点，奇数条边。解：解：解：解：例例5、画一个欧拉图，使它具有：(3)偶数个顶点，奇数条边。(4)奇数个顶点，偶数条边。解：解：解：解：例例6、今有,a b c d e f g七个人，已知下列事实：会讲英语；会讲英语和汉语；ab会讲英语、意大利语和俄语；c会讲日语和汉语；d会讲德语和意大利语；e会讲法语、日语和俄语；f会讲法语和德语。g试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？解：解：语言就连一条边，这样得到无向图G，再求G的哈密尔顿回路。用七个顶点表示七个人，若两人之间有共同abcdefg
40、图GabcdefgG的哈回路例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?(1)解：解：不是欧拉图，不是哈密尔顿图，例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：解：是欧拉图，是哈密尔顿图.(2)例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不解：不是欧拉图，是哈密尔顿图，(3)例例7、下图中哪些是欧拉图，哪些是哈密尔顿图?解：不解：不是欧拉图，是哈密尔顿图.(4)例例8、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，3()_dv(1)1()_dv2()_d v2422()()2dv
41、dv例例8、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，(2)从到长度为2的通路数。1v4v解：解：因，所以从 到 长度为2的通路数为2。(2)142a1v4v例例8、已知图的邻接矩阵，D10111000()10011100A D231121011()21112011AD372343112()51234123A D，(3)从到长度为3的通路数。3v1v解：解：因，所以从 到 长度为3的通路数为5。(3)315a3v1v例例9、下列各图中各有多少个顶点。(1)16条边，每个顶点的度数均为2。解：解：设顶点数为，x解得16x。解：解：设顶点数为x，(2)21条边，3个度数为4的顶点，其余顶点的度数均为3。，由握手定理，由握手定理，有，1622x解得13x。有212)3(334x147651227411abcdef例例 10 用用Dijkstra求下图中求下图中a到到d的最短路径。的最短路径。abcdefa62 2f37 93b595ce9d67 7654321bcdefa解：解：1T例例11.求以下连通图的最小生成树及T()W T。(1)6643215555fabcde1()15()W TW T
