离散数学基础 第六章 图论

1、1第六章 图离散数学基础离散数学基础谢胜利谢胜利2 煤气管道的铺设问题。现为城市的各小区之间铺设煤气煤气管道的铺设问题。现为城市的各小区之间铺设煤气管道管道(如下图所示如下图所示)，对，对 n 个小区只需铺设个小区只需铺设 n-1 条管线，由于地条管线，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？本最低？ ABDFE51372364108图论问题3第1节 图的基本概念45 67 81无向图和有向图无向图和有向图9l无向边无向边，例：，例： e3 = （v3,v4） = （v4,v3） l有向边有向边(弧弧)，例：，例：

2、e8 = e3v3v4e8v2v310有向图有向图无向图无向图2、图的基本术语、图的基本术语有向图：有向图：图中各边都是有向边图中各边都是有向边无向图：无向图：图中各边都是无向边图中各边都是无向边混合图：混合图：图中既有有向边又有无向边图中既有有向边又有无向边11 无向图边与边的邻接无向图边与边的邻接：有公共端点的边互为邻接边：有公共端点的边互为邻接边1e2e3e4e5e12有限图：有限图：图中仅有有限个顶点。图中仅有有限个顶点。（无限图：图中有无限个顶点。）（无限图：图中有无限个顶点。）N阶图：阶图：具有具有n个顶点的有限图。个顶点的有限图。零图：零图：只有顶点而没有边的图只有顶点而没有边的

3、图平行边：平行边：两顶点之间有多条边（若为有向图则方向也相同）。两顶点之间有多条边（若为有向图则方向也相同）。边的重数：边的重数：两顶点间平行边的条数。两顶点间平行边的条数。多重图：多重图：含有平行边的多重图。含有平行边的多重图。自环（自回路）：自环（自回路）：两个端点重合的边两个端点重合的边简单图：简单图：不含平行边且不含自环的图。不含平行边且不含自环的图。13141v1v2v2v3v3v4v4v5v5v6v6v7v)(a)(b27253153551711227536415二、二、 图中顶点的度数图中顶点的度数1、无向图中顶点的度数、无向图中顶点的度数【定义【定义】在图（无向图或有向图）中，

4、若顶点在图（无向图或有向图）中，若顶点a和和b是边是边e的两个端点，则称顶点的两个端点，则称顶点a和和b是是邻接邻接的，并的，并称边称边e关联关联于顶点于顶点a和和b。【定义【定义】设图设图G是无向图，是无向图，v是图是图G中的顶点，与中的顶点，与v关联的边的条数称为关联的边的条数称为顶点顶点v的度数的度数，记作，记作deg(v)。 与结点与结点v关联的环对关联的环对v的度数的贡献要计算两次的度数的贡献要计算两次16孤立点：孤立点：度数为零的顶点度数为零的顶点悬挂点：悬挂点：度数为度数为1的顶点的顶点悬挂边：悬挂边：与悬挂点关联的边与悬挂点关联的边K度点：度点：度数为度数为k的顶点的顶点17【

5、定理定理】（握手定理）（握手定理） 任一图中，顶点的度数的任一图中，顶点的度数的总和等于边数的二倍，即总和等于边数的二倍，即【推论推论】 任一图中，奇度数顶点的个数必为偶数。任一图中，奇度数顶点的个数必为偶数。VvEv|2)(degVvVvVvEvvv|2)(deg)(deg)(deg211819【例【例】下列各组数中，哪下列各组数中，哪些些可以构成无向图的度可以构成无向图的度数列数列：（1） 1，1，1，2，2 （2） 2，2，2，2，3（3）2，3，3，3，3（4）2，2，2，2，2202122 23（2）有向图中顶点的度数）有向图中顶点的度数【定义【定义】设图设图G是有向图，是有向图，v

6、是是G的顶点，以的顶点，以v为始点为始点的有向边的条数称为的有向边的条数称为v的的出度出度，称为，称为deg+(v), 以以v为终为终点的有向边的条数称为点的有向边的条数称为v的的入度入度，称为，称为deg-(v)。例：例：deg+(a)=2 deg-(a)=1deg+(b)=0 deg-(b)=2deg+(c)=1 deg-(c)=2deg+(d)=2 deg-(d)=2deg+(e)=2 deg-(e)=024【定理定理】 设图设图G是有向图，是有向图，G中含有中含有n个顶点个顶点和和m条边，则图中各顶点的的出度之和与各顶条边，则图中各顶点的的出度之和与各顶点的入度之和相等，且等于图的边数

7、。点的入度之和相等，且等于图的边数。mvvVvVv)(deg)(deg-25三、特殊图三、特殊图 【定义【定义】设图设图G为无向简单图，如果图为无向简单图，如果图G中各个顶中各个顶点的度数都为点的度数都为k，则称，则称G为为k度度正则图正则图，记为，记为k-正正则图则图26三、特殊图三、特殊图 【定义【定义】在在n阶无向简单图中，如果任意两个不同的顶阶无向简单图中，如果任意两个不同的顶点之间都有一条边关联，则称此无向简单图为点之间都有一条边关联，则称此无向简单图为无向无向完全图完全图，记作，记作Kn。无向完全图无向完全图Kn的边数是多少？的边数是多少？ 【定理【定理】在在n阶无向完全图阶无向完

8、全图Kn中，共有中，共有n(n-1)/2条边。条边。27【定义【定义】在在n阶有向图中，如果任意两个不同的顶点阶有向图中，如果任意两个不同的顶点之间都有两条方向相反的有向边关联，且每一个之间都有两条方向相反的有向边关联，且每一个顶点都有自回路，则称此有向图为顶点都有自回路，则称此有向图为有向完全图有向完全图。有向完全图各顶点的入度与出度是多少？有向完全图各顶点的入度与出度是多少？三、特殊图三、特殊图 28四、四、 子图子图【定义【定义】在图在图G中删去一些边或顶点后所得的中删去一些边或顶点后所得的图称为图图称为图G的子图。的子图。删边：删边：删去图中某一条边，但仍保留这条边的两个删去图中某一条

9、边，但仍保留这条边的两个端点。端点。删点：删点：删去图中某一点以及与这个点关联的所有边。删去图中某一点以及与这个点关联的所有边。29删边删边删点删点30【定义【定义】由图由图G中删去一些边后所得到的子图称为中删去一些边后所得到的子图称为图图G的的生成子图生成子图。【定义】在图【定义】在图G中仅删去一个顶点后所得的子图称中仅删去一个顶点后所得的子图称为图为图G的的主子图主子图。313233设有两个图设有两个图G1=(V1, E1)，G2=(V2, E2)，如果存在着如果存在着双射双射 ：V1V2，使得，使得(u,v)E1当且仅当当且仅当 ( (u), (v)E2 且边的重数相同，则称图且边的重数

10、相同，则称图G1与与G2同构同构，记作记作 G1 G2。3435363738注意：注意：顶点数相同、边数相同、度数列相同顶点数相同、边数相同、度数列相同为二图同构的必要条件而非充分条件为二图同构的必要条件而非充分条件391 12 25 56 63 34 4Ga ab be ef fc cd dG40 41六、补图六、补图 【定义定义】 G为为n阶简单图，由阶简单图，由G的所有顶点和的所有顶点和能使能使G成为完全图的添加边所构成的图称为成为完全图的添加边所构成的图称为G的相的相对于完全图的对于完全图的补图补图，简称，简称G的补图，记作的补图，记作 。 G42【例【例】 下图中下图中 是是G相对于

11、相对于K5的补图。的补图。G43 对于补图对于补图,显然有以下结论显然有以下结论GGGG 互为补图，即互为补图，即与与)1( )()()()()()2(GEGEKEGEGEn(3) n阶完全图与阶完全图与n阶零图互为补图阶零图互为补图44第2节 图的连通性45 成都成都昆明昆明重庆重庆广州广州长沙长沙武汉武汉上海上海兰州兰州西安西安沈阳沈阳北京北京天津天津郑州郑州厦门厦门高雄高雄台北台北46471v1v2v2v3v3v4v1e1e2e2e3e3e4e4e5e5e6e7e4849 5051原岸原岸对岸对岸 原岸原岸对岸对岸 初始初始状态状态结束结束状态状态渡河过程中所有可能的安全状态：渡河过程中

12、所有可能的安全状态：可以使用二元组表示安全状态：第一元素表示留可以使用二元组表示安全状态：第一元素表示留在原岸的子集，第二元素表示留在对岸的子集。在原岸的子集，第二元素表示留在对岸的子集。52531）起点与终点相同的通路）起点与终点相同的通路(长度长度 1)称为称为回路回路(circuit)。2）边不重复的回路称为）边不重复的回路称为简单回路简单回路。3）除起点重复一次外）除起点重复一次外, 别的结点均不重别的结点均不重复的复的简单回路简单回路称为称为基本回路基本回路或或环环(cycle)。540v0v55 56 575859 6061 【定义定义】设图设图G是无向连通图，如果图是无向连通图，

13、如果图G中存在一个顶中存在一个顶点点v，使得删去顶点，使得删去顶点v后，图后，图G成为不连通图，则称成为不连通图，则称v为为割点割点。 【定义定义】设图设图G是无向连通图，如果图是无向连通图，如果图G中存在一条边中存在一条边u，使得删去边，使得删去边u后，图后，图G成为不连通图，则称成为不连通图，则称v为为割割边或桥边或桥。62 【定义定义】在简单有向图在简单有向图G中，若任二顶点间均相互可达，中，若任二顶点间均相互可达，则称则称G为为强连通图强连通图；若任二顶点间至少从一个顶点到；若任二顶点间至少从一个顶点到另一个顶点是可达的，则称另一个顶点是可达的，则称G是是单向连通图单向连通图；若在忽；

14、若在忽略略G中各边的方向时中各边的方向时G是无向连通图，则称是无向连通图，则称G是是弱连弱连通图通图。 63 【例例】下下图中，图图中，图(a)是强连通图，图是强连通图，图(b)是单是单向连通图，图向连通图，图(c)是弱连通图。是弱连通图。abcdabcdabcd64第3节 图的表示65 【定义定义】设无向图设无向图G的点集为的点集为V，边集为，边集为E，且，且V=v1，v2，vn，E=e1,e2,em,令令则称则称(m ij ) nm 为为G的关联矩阵，记作的关联矩阵，记作 M (G) 的的环环是是关关联联关关联联与与不不关关联联与与ijijijijvevevem21066【例例】 求下图求

15、下图G的关联矩阵。的关联矩阵。12342100001110( )0011100001M G12345eeeee67 无向图的关联矩阵的特性：无向图的关联矩阵的特性： （1） ，即，即 M(G)每每列元素之和为列元素之和为2，因为每条边恰有两个端点，因为每条边恰有两个端点（若是简单图则每列恰有两个（若是简单图则每列恰有两个1）。）。 （2） ，因而全为，因而全为0的行所的行所对应的顶点是孤立顶点。对应的顶点是孤立顶点。12(1,2,)nijimjm mjiijvdm1)(68 * 4、有向无环图的关联矩阵、有向无环图的关联矩阵 【定义定义】设设G=V,E是有向无环图，是有向无环图， V=v1，v

16、2，vn，E=e1，e2，em，令，令101ijmvi是是ej的起点的起点 vi与与ej不关联不关联 vi是是ej的终点的终点 则称则称(m ij ) nn 为为G的关联矩阵，记作的关联矩阵，记作 M (G)。 6912345100000111100( )011011000111000000M G123456eeeeee70 M (G) 的特性：的特性： （1） （一条边关联两个点：一个起点，一（一条边关联两个点：一个起点，一个终点），从而有个终点），从而有 。 （2）每一行中）每一行中1的数目是该点的出度，的数目是该点的出度，-1的数目是该的数目是该点的入度。点的入度。 （3）二列相同，当且

17、仅当对应的边是平行边（同向）。）二列相同，当且仅当对应的边是平行边（同向）。 （4）全为）全为0的行对应孤立顶点。的行对应孤立顶点。10nijim110mnijjim 71 注注:无向图也有相应的邻接矩阵，一般只考无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。质基本与有向图邻接矩阵的性质相同。72731v1v2v2v3v3v4v4v1G2G,0110110110020120)(1GA.0100010110000020)(2GA无向图中自环对应主对角线上元素是无向图中自环对应主对角线上元素是1还

18、是还是2？747576nivaaaaiiiiijjiiij,.,2 , 1),deg(n1n177练习现有如下所示图：(1) 写出该图的关联矩阵和邻接矩阵。(2) 求各个顶点的度。(3) 图中是否存在平行边？如果存在，请指出。 78jviv1v2vnv791v2v3v4v5v8081828311121212211212.( ).nnnnnnnrrrrrrR GAAArrr841v2v3v4v5v858687第第4节节 一些特殊的图一些特殊的图881 二部图【定义【定义】无向图无向图G=V，E的顶点集的顶点集V能分成两个能分成两个子集子集V1和和V2，满足，满足（1）V=V1V2，V1V2= ；

19、（2）任给）任给e=（u，v）E，均有，均有uV1，vV2。则称则称G为二部图。为二部图。【定义【定义】设设G = (V, E)是二部图，如果是二部图，如果V1中每个顶点中每个顶点都与都与V2中所有顶点邻接，则称中所有顶点邻接，则称G为完全二部图，并为完全二部图，并记为记为Km,n，其中，其中m=|V1|，n=|V2|。Km,n的边数是多少？的边数是多少？89Km,n的边数是多少？的边数是多少？90一个无向图是二部图当且仅当一个无向图是二部图当且仅当图中无奇数长度的回路。图中无奇数长度的回路。9192（补）二部图的应用（补）二部图的应用某公司招聘了某公司招聘了3名大学毕业生，公司有名大学毕业生

20、，公司有5个部门需要个部门需要人。不考虑单向的意愿，毕业生意愿去这个部门，人。不考虑单向的意愿，毕业生意愿去这个部门，这个部门也同意接收这名毕业生如表所示。这个部门也同意接收这名毕业生如表所示。部门部门1部门部门2部门部门3部门部门4部门部门5毕业生毕业生A*毕业生毕业生B*毕业生毕业生C*有什么分配方案使得在每个部门最多可接收一有什么分配方案使得在每个部门最多可接收一个毕业生的前提下毕业生都满意！个毕业生的前提下毕业生都满意！93 94 95961v2v3v4v5v9798abcde99100v v1 1v v2 2v v3 3v v4 4v v5 5(b)(b)v v1 1v v2 2v

21、v3 3v v4 4(c)(c)v v1 1v v2 2v v3 3v v4 4v v5 5(a)(a)101 A(甲)B(乙)C102 103104)(a)(bbcade1v2v3v4v5v105106107 108上述定理在应用中它本身用处不大，但上述定理在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利它的逆否命题却非常有用。我们经常利用其逆否命题来判断某些图不是汉密尔用其逆否命题来判断某些图不是汉密尔顿图，即：顿图，即： 若存在若存在V的某个非空子集的某个非空子集W使得使得w(G-W)|W|，则，则G不是汉密尔顿图。不是汉密尔顿图。109110v v3 3v v1 1v v2

22、 2v v4 4v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5v v3 3111设设G = (V, E)是是n(n 3)阶阶简单无向图简单无向图, 若对于任意的不相邻结点若对于任意的不相邻结点u, v V, 有有 1121v2v3v4v5v6v113114设设G = (V, E)是是n(n 3)阶简单无向图阶简单无向图, 若对于任意的不相邻结点若对于任意的不相邻结点u, v V, 有有在在 中存在中存在 115116 117第5节 最短路径1181 Dijkstra算法算法1191v2v3v4v5v6v4233321120121122基本思想基本思想：设置

23、一个集合：设置一个集合S（也可以看作红点集）（也可以看作红点集）存存放已经找到最短路径的顶点，放已经找到最短路径的顶点，S的初始状态只包含源的初始状态只包含源点点v，对，对viV- -S （也可以看作蓝点集）（也可以看作蓝点集） ，假设从源，假设从源点点v到到vi的有向边为最短路径。以后每求得一条最短的有向边为最短路径。以后每求得一条最短路径路径v, , vk，就将，就将vk加入集合加入集合S中，并将路径中，并将路径v, , vk , vi与原来的假设相比较，取路径长度较小者为最与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合短路径。重复上述过程，直到集合V中全部顶点加中全部顶点加入到集合入到集合S中。中。1 Dijkstra算法算法123 集集 合合 V- -S集集合合 Svkv