离散数学-第七章--图论课件

第七章第七章图论图论7.1 图的基本概念7.2 路与回路7.3 图的矩阵表示7.4 欧拉图和汉密尔顿图7.5 平面图7.6 对偶图与着色7.7 树与生成树1第七章 图论 教学目的及要求：教学目的及要求：深刻理解和掌握图的有关概念和表示。教学内容：教学内容：图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树。教学重点：教学重点：图、路、图的矩阵表示、平面图、树与生成树。教学难点：教学难点：树与生成树。2图论图论图论是近年来发展迅速而又应用广泛的一门新兴图论是近年来发展迅速而又应用广泛的一门新兴学科。学科。图论最早起源于一些数学游戏的难题研究。如：图论最早起源于一些数学游戏的难题研究。如：哥尼斯堡七桥问题、迷宫问题等。哥尼斯堡七桥问题、迷宫问题等。1847年，克希霍夫用图论分析电路网络，最早将年，克希霍夫用图论分析电路网络，最早将图论应用于工程科学。图论应用于工程科学。图论的内容十分丰富图论的内容十分丰富,它是一门应用性很强的学它是一门应用性很强的学科。计算机科学、网络理论、信息论、运筹学、科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具语言学、物理、化学等都以图作为工具,来解决来解决实际问题和理论问题。实际问题和理论问题。3图论图论现实世界中许多状态是由图形来描述的现实世界中许多状态是由图形来描述的,我们用点表我们用点表示事物示事物,用点之间是否有连线表示事物之间是否有某用点之间是否有连线表示事物之间是否有某种关系种关系,于是点以及点之间的若干条连线就构成了图。于是点以及点之间的若干条连线就构成了图。当我们研究的对象能够被抽象为离散的元素集合和当我们研究的对象能够被抽象为离散的元素集合和集合上的二元关系时集合上的二元关系时,用关系图进行表示和处理是很用关系图进行表示和处理是很方便的。方便的。图可分为图可分为有限图有限图和无限图两类和无限图两类,本书只研究有限图本书只研究有限图,即即顶点和边都是有限顶点和边都是有限集合。集合。47.1 图的基本概念图的基本概念离散数学研究的图是不同于几何图形、机械图形离散数学研究的图是不同于几何图形、机械图形的另一种数学结构的另一种数学结构,不关心不关心图中图中顶点的位置顶点的位置、边的边的长短和形状长短和形状,只关心只关心顶点与边的联结关系。顶点与边的联结关系。如下图（如下图（a）和（）和（b）abcde1e2e6e4e3e5（a）abcde1e6e2e4e3e5（b）abcde1e2e6e4e3e55（1）定义定义:一个图一个图G是一个三元组是一个三元组,其其中中V(G)为顶点集合为顶点集合,E(G)是边的集合是边的集合，G是从边集是从边集E到结点偶对集合上的函数。到结点偶对集合上的函数。讨论定义：讨论定义：(a)V(G)=V1，V2，Vn为有限非空集合为有限非空集合,Vi称为结点称为结点,简称简称V是点集。是点集。(b)E(G)=e1，em为有限的边集合为有限的边集合,ei称为边，称为边，每每个个e ei i是连结是连结V中的某两个顶点的中的某两个顶点的,称称E E为边集。为边集。(c)可用可用e或或e(vi,vj)，来表示图的边，这，来表示图的边，这样可把图简化成：样可把图简化成：。7.1 图的基本概念图的基本概念6（2）每一条边都是无向边的图称无向图。）每一条边都是无向边的图称无向图。每一条边都是有向边的图称有向图。每一条边都是有向边的图称有向图。bcdabcda如果图如果图G中既有无向边中既有无向边,又有有向边又有有向边,则称该图为混合图。本课程不讨论混则称该图为混合图。本课程不讨论混合图。合图。7.1 图的基本概念图的基本概念7例：对有向图可表示为：例：对有向图可表示为：，其中其中a、b、c、d,则：则：，=a，b，c，d，,7.1 图的基本概念图的基本概念8（3）在一个图中，若两个结点有一条有向边或者一）在一个图中，若两个结点有一条有向边或者一条无向边关联条无向边关联,则这两个结点成为则这两个结点成为邻接点邻接点。孤立结点：孤立结点：在一个图中不与任何结点相邻接的结在一个图中不与任何结点相邻接的结点，称为孤立结点。如下图中结点点，称为孤立结点。如下图中结点v5。（4）零图：零图：仅由孤立结点构成的图称为零图。仅由孤立结点构成的图称为零图。v1v2v3v4v57.1 图的基本概念图的基本概念9（5）平凡图：平凡图：仅由一个孤立结点构成的图称为平凡仅由一个孤立结点构成的图称为平凡图。图。邻接边：邻接边：关联于同一结点的两条边称为邻接边。关联于同一结点的两条边称为邻接边。（6）自回路（环）：自回路（环）：关联于同一结点的一条边称为关联于同一结点的一条边称为自回路。自回路。如下图，中（c，c）是环 acba7.1 图的基本概念图的基本概念10（7）度数：度数：在图在图G=中，与结点中，与结点v（v V）关联的边数，称为该结点的度数，记作关联的边数，称为该结点的度数，记作deg（v）。）。约定：约定：每个环在其对应结点上度数增加每个环在其对应结点上度数增加2。ABCED7.1 图的基本概念图的基本概念最大度最大度,记为：记为：（G G）最小度最小度,记为：记为：（G G）11定理定理1：每个图中，结点度数的总和等于边数的两倍。每个图中，结点度数的总和等于边数的两倍。即即证：证：每条边必关联两个结点，而一条边给于关联的每条边必关联两个结点，而一条边给于关联的每个结点的度数为每个结点的度数为1。故上述定理成立。故上述定理成立。7.1 图的基本概念图的基本概念12定理定理2：在任何图中，度数为奇数的结点必定是偶数个。在任何图中，度数为奇数的结点必定是偶数个。证：设证：设V1和和 V2分别是分别是G中奇数度数和偶数度数的结点集，中奇数度数和偶数度数的结点集，则由上述定理有：则由上述定理有：由于由于 是偶数之和，必为偶数，而是偶数之和，必为偶数，而 是偶数。故是偶数。故得是得是 偶数，即偶数，即 是偶数。是偶数。7.1 图的基本概念图的基本概念13（8）入度，出度：）入度，出度：在有向图中，射入一个结点的边数在有向图中，射入一个结点的边数称为该结点的入度。由一个结点射出的边数称为该称为该结点的入度。由一个结点射出的边数称为该结点的出度。结点的出度。结点的出度与入度结点的出度与入度和和是该结点的是该结点的度数度数。定理：定理：在任何有向图中，所有结点的入度和等于所在任何有向图中，所有结点的入度和等于所有结点的出度之和。有结点的出度之和。7.1 图的基本概念图的基本概念14bcda证：证：每一条有向边必对应一个入度和出度，若一个结点具每一条有向边必对应一个入度和出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度和等于边数，各结点出度和也是等于边数，因此，各结点入度和等于边数，各结点出度和也是等于边数，因此，任何有向图中，入度之和等于出度和。任何有向图中，入度之和等于出度和。7.1 图的基本概念图的基本概念15（9）连接于同一对结点间的多条边称为是平行的。连接于同一对结点间的多条边称为是平行的。定义：定义：含有平行边的任何一个图称为多重图。含有平行边的任何一个图称为多重图。不含有平行边和环的图称作简单图。不含有平行边和环的图称作简单图。（10）完全图：）完全图：简单图简单图G=中，若每一对结点间都有边中，若每一对结点间都有边相连，则称该图为完全图。相连，则称该图为完全图。a abc（a）a abc（b）（c）a abcd7.1 图的基本概念图的基本概念16定理定理4：n个结点的无向完全图的边数为：个结点的无向完全图的边数为：证明：在有证明：在有n个结点的无向完全图中，任意两点间都个结点的无向完全图中，任意两点间都有边连接，有边连接，n个结点中任意取两点的组合为：个结点中任意取两点的组合为：故有故有n个结点的无向完全图的边数为个结点的无向完全图的边数为7.1 图的基本概念图的基本概念17（11）补图：）补图：给定一个图给定一个图G，由，由G中所有结点和所有中所有结点和所有能使能使G成为完全图的添加边组成的图，称为成为完全图的添加边组成的图，称为G的相的相对于完全图的补图，或简称为对于完全图的补图，或简称为G的补图。记作。的补图。记作。如下图，（如下图，（a）和（）和（b）互为补图。）互为补图。（a）（b）7.1 图的基本概念图的基本概念18（12）子子图图：设设图图G=，如如果果有有图图G=，且且EE，VV，则则称称 G 为为 G 的的子子图。图。如下图，（如下图，（b）、（）、（c）都是（）都是（a）的子图。）的子图。（a）bcdhgafe（b）bcdhgfe（c）bcdhgaf7.1 图的基本概念图的基本概念19（13）生生成成子子图图：如如果果G的的子子图图包包含含G的的所所有有结结点点，则称该子图为则称该子图为G的生成子图。的生成子图。如下图，（如下图，（b）、（）、（c）都是（）都是（a）的生成子图。）的生成子图。（a）（c）7.1 图的基本概念图的基本概念20（14）定义：）定义：设图设图G=及图及图G=，如果存在一一对应的映射，如果存在一一对应的映射g：viv i且且e=（vi，vj）是是G的一条边，当且仅当的一条边，当且仅当e=（g（vi），），g（vj）是）是 G 的一条边，则称的一条边，则称G与与G 同构，记作同构，记作G G。两个图同构的充要条件是：两个图的结点和边分别存两个图同构的充要条件是：两个图的结点和边分别存在着一一对应的关系，且保持关联关系。在着一一对应的关系，且保持关联关系。7.1 图的基本概念图的基本概念21dbea（a）u3u4u2u1（b）存在着一一对应映射存在着一一对应映射g：g(a)=u3，g(b)=u1，g(c)=u4，g(d)=u2，且有：且有：,分分别与别与,一一对应一一对应7.1 图的基本概念图的基本概念22两图同构的一些两图同构的一些必要条件必要条件：（1）结点数目相同。）结点数目相同。（2）边数相等。）边数相等。（3）度数相同的结点数目相同）度数相同的结点数目相同这几个条件不是两个图同构的充分条件。下两图，满足这几个条件不是两个图同构的充分条件。下两图，满足上述三个条件，但并不同构上述三个条件，但并不同构7.1 图的基本概念图的基本概念237.2 路与回路路与回路定义：在图定义：在图G=中，设中，设v0，v1，vnV,e1,e2 en E，其中其中ei是关联于结点是关联于结点vi-1,vi的边，结点与的边，结点与边的交替序列边的交替序列v0 e1 v1 en vn称为联结称为联结v0到到vn的的路路。v1v4v5v2v3e1e2e3e4e5e6e7e8v1v4v5v2v3e1e2e3e4e5e6e7e8v0v3v4v1v2e1e2e3e4e5e6e7e824路的其它概念路的其它概念（1）V0和和vn分别称作分别称作路的起点与终点路的起点与终点。（2）一条路中所有的边的数目称作）一条路中所有的边的数目称作路的长度路的长度。（3）若）若V0=vn则路称作则路称作回路回路。（4）一条路中所有的边均不相同，则此路称作）一条路中所有的边均不相同，则此路称作迹迹。（5）一条路中所有的结点均不相同，则此路称作）一条路中所有的结点均不相同，则此路称作通路通路。（6）对于回路，除）对于回路，除V0=vn外，其余结点均不相外，其余结点均不相同，则此路称作同，则此路称作圈圈。v0v3v4v1v2e1e2e3e4e5e6e7e87.2 路与回路路与回路25路的表示方法：路的表示方法：(a)结点表示法：结点表示法：(b)边表示法：边表示法：例：给出有向图，求例：给出有向图，求起始于，终止于起始于，终止于的路的路7.2 路与回路路与回路26定理：定理：在一个具有在一个具有n个结点的图中，如果从结点个结点的图中，如果从结点vj到结到结点点vk存在一条路，则从从结点存在一条路，则从从结点vj到结点到结点vk必存在一条必存在一条不大于不大于n-1条边的路。条边的路。推论推论：在一个具有：在一个具有n个结点的图中，如果从结点个结点的图中，如果从结点vj到结到结点点vk存在一条路，则从从结点存在一条路，则从从结点vj到结点到结点vk必存在一条必存在一条条边数小于条边数小于n的通路。的通路。7.2 路与回路路与回路27无向图的结点连通性无向图的结点连通性定义定义设图为无向图，且设图为无向图，且，若从，若从vi到到vj存在任何一条路径的话，则称存在任何一条路径的话，则称vi到到vj是连通的。是连通的。有向图的结点可达性有向图的结点可达性定义定义设图为简单有向图，且设图为简单有向图，且，若从，若从vi到到vj存在任何一条路径的话，则称存在任何一条路径的话，则称vi到到vj是可达的。是可达的。7.2 路与回路路与回路28图的连通性：图的连通性：（1）连通性与非连通性：连通性与非连通性：一个无向图，如果它的任何两结点间均是连通的，则称一个无向图，如果它的任何两结点间均是连通的，则称图图G是连通的，否则是非连通的。是连通的，否则是非连通的。一个有向图，忽略边的方向后得到的无向图，若是连通一个有向图，忽略边的方向后得到的无向图，若是连通的，则称该有向图为连通图，否则称非连通图。的，则称该有向图为连通图，否则称非连通图。（a）（b）abcdabcd7.2 路与回路路与回路29（2）强连通，单向连通，弱连通强连通，单向连通，弱连通 有向图有向图G：（简单有向图）：（简单有向图）如果如果G的任何两结点间均是互相可达的，则称图的任何两结点间均是互相可达的，则称图G是是强连通强连通的。的。如果如果G的任何两结点间至少有一个结点到另一结点是可达的。则的任何两结点间至少有一个结点到另一结点是可达的。则称称G是是单向连通单向连通的。的。如果忽略边的方向，将它看成无向图后，图是连通的，则称该图如果忽略边的方向，将它看成无向图后，图是连通的，则称该图为为弱连通弱连通的。的。7.2 路与回路路与回路30定理定理一个有向图是强连通的充要条件是：它包含一个回路，该回路至少包含每个结点一次。7.2 路与回路路与回路31定义定义设，为一简单有向图，且是的子图。具有强连通性质的最大子图称为强分图；具有单侧连通性质的最大子图称为单侧图；具有弱连通性质的最大子图称为弱分图。例：7.2 路与回路路与回路32定理定理在任一简单有向图，中，有向图的每一个结点位于且只位于一个强分图之中。7.2 路与回路路与回路33定义定义设无向图设无向图G=是连通图是连通图,若存在若存在V1 V,使图使图G删删除了除了V1中所有的结点后中所有的结点后,所得的子图是不连通的，所得的子图是不连通的，而对于任而对于任意的意的V2 V1，图图G删除了删除了V2中所有的结点后中所有的结点后,所得的子图是所得的子图是连通的，则称连通的，则称V1是是G的点割集。的点割集。若某一个结点构成一个点割集，则称该结点为割点。若某一个结点构成一个点割集，则称该结点为割点。在下图中在下图中,v2,v4,v3和和v5都是点割集都是点割集,v3和和v5都都是割点。是割点。注意注意,v1与悬挂顶点与悬挂顶点v6不在任何割集中。不在任何割集中。7.2 路与回路路与回路34定义定义设设G为无向连通图且为非完全图为无向连通图且为非完全图,则称则称(G)=min|V1|V1为为G的点割集的点割集为为G的点连通度的点连通度,简称连通度。简称连通度。(G)简记为简记为。规定规定:完全图完全图Kn(n 1)的点连通度为的点连通度为n-1；非连通图的点连通度为非连通图的点连通度为0；7.2 路与回路路与回路35定义定义设无向图设无向图G=是连通图是连通图,若存在若存在E1 E,使图使图G删除了删除了E1中所有的边后中所有的边后,所得的子图是不连通所得的子图是不连通的，的，而对于任意的而对于任意的E2 E1，图图G删除了删除了E2中所有中所有的边后的边后,所得的子图是连通的，则称所得的子图是连通的，则称E1是是G的边割的边割集。集。若某一条边构成一个边割集，则称该条边为割边或若某一条边构成一个边割集，则称该条边为割边或桥。桥。7.2 路与回路路与回路36在下图中在下图中,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集都是割集,其中其中e6和和e5是桥。是桥。7.2 路与回路路与回路37定义定义设设G为无向连通图且为非平凡图为无向连通图且为非平凡图,则称则称(G)=min|E1|E1为为G的边割集的边割集为为G的边连通度。的边连通度。规定规定:平凡图的边连通度为平凡图的边连通度为(G)=0；非连通；非连通图的边连通度也为图的边连通度也为0；7.2 路与回路路与回路38定理定理对于任何无向图对于任何无向图G,有有:(G)(G)(G)。本定理证明略。本定理证明略。例例(1)给出一些无向简单图给出一些无向简单图,使得使得:=；(2)给出一些无向简单图给出一些无向简单图,使得使得:。解解(1)无向完全图无向完全图Kn和零图和零图Nn都满足要求。都满足要求。7.2 路与回路路与回路39(2)在两个在两个Kn(n 4)之间放置一个顶点之间放置一个顶点v,使使v与两与两个个Kn中任意两个不同的顶点相邻中任意两个不同的顶点相邻,所得简单图满所得简单图满足要求。足要求。因为这样的图中有一个割点因为这样的图中有一个割点v,所以所以,=1(当当n=4时时,=3)；因为有两条边组成的边割集因为有两条边组成的边割集,所以所以,=2(当当n=5时时,=4)。7.2 路与回路路与回路407.3 图的矩阵表示矩阵是研究图的有关性质的最有效的工具，可运用图矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出图的路径、回路和其它一些性质。的矩阵运算求出图的路径、回路和其它一些性质。图的邻接矩阵表示方法图的邻接矩阵表示方法定义定义设，是简单图，其中设，是简单图，其中V=v1,v2,vn定义一个定义一个nxn的矩阵的矩阵A，并把其中并把其中各元素各元素aij表示成：表示成：则称矩阵则称矩阵A为图为图G的邻接矩阵。的邻接矩阵。41（1）零图的邻接矩阵称为零矩阵，即矩阵中的）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为所有元素均为0；（2）在图的邻接矩阵中，）在图的邻接矩阵中，行中行中1的个数就是行中相应结点的出度的个数就是行中相应结点的出度列中列中1的个数就是列中相应结点的入度的个数就是列中相应结点的入度7.3 图的矩阵表示例：设图，如下图所示例：设图，如下图所示讨论定义：讨论定义：42矩阵的计算矩阵的计算：可以用来计算两结点间可以用来计算两结点间路径的长度。路径的长度。定理：设定理：设A(G)是图是图G的邻接矩阵，则的邻接矩阵，则(A(G)l中中i行行j列元素列元素aij(l)等于等于G中联结中联结vi与与vj的长度为的长度为l路的数目。路的数目。7.3 图的矩阵表示43表示表示i和和j之间具有长度为之间具有长度为2的路径数，的路径数，表示表示i和和j之间具有长度为之间具有长度为3的路径数，的路径数，表示表示i和和j之间具有长度为之间具有长度为4的路径数，的路径数，7.3 图的矩阵表示44bij表示从结点表示从结点vi到到vj有长度分别为有长度分别为1，2，3，4的不同路径总数。的不同路径总数。此时，此时，bij 0，表示从表示从vi到到vj是可达的是可达的。7.3 图的矩阵表示45定义定义设，是简单有向图，设，是简单有向图，其中其中|V|=（），定义一个），定义一个矩阵矩阵P，它的元素为：它的元素为：则则P称为图称为图G的可达性矩阵。的可达性矩阵。由由矩阵可计算出可达性矩阵，其方法是：矩阵可计算出可达性矩阵，其方法是：若若中中（i,j）是非是非“0”元素，则对应的元素，则对应的，否则，否则7.3 图的矩阵表示46定义定义设无向图，设无向图，其中其中，。，。令则称则称B为无向图为无向图G的的完全关联矩阵完全关联矩阵7.3 图的矩阵表示47例：7.3 图的矩阵表示487.4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图哥尼斯堡七桥问题：哥尼斯堡七桥问题：18世纪在哥尼斯堡城世纪在哥尼斯堡城(今俄罗斯加里宁格勒今俄罗斯加里宁格勒)的普莱格的普莱格尔河上有尔河上有7座桥，将河中的两个岛和河岸连结，如图座桥，将河中的两个岛和河岸连结，如图1所示。所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍否一次走遍7座桥，而每座桥只许通过一次，最后仍回到座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。起始地点。这就是七桥问题，一个著名的图论问题。49于是于是“七桥问题七桥问题”就等价于图中所画图形的一笔画问题就等价于图中所画图形的一笔画问题了。了。欧拉欧拉注意注意到不存在一次走遍到不存在一次走遍7座桥，而每座桥只许通过座桥，而每座桥只许通过一次的走法。一次的走法。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D，4个点，个点，7座桥表示成座桥表示成7条连接这条连接这4个点的线，如图所示。个点的线，如图所示。50基本概念基本概念1、欧拉图：、欧拉图：给定无孤立结点图给定无孤立结点图G，若存在一条路，经，若存在一条路，经过图中每边一次且仅一次，该条路称为过图中每边一次且仅一次，该条路称为欧拉路欧拉路；若；若存在一条回路，经过图中每边一次且仅一次，该回存在一条回路，经过图中每边一次且仅一次，该回路称为路称为欧拉回路欧拉回路。具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图。v2v3v4v1C（V1、V2、V3、V1、V4、V3）51定理定理定理定理1：给定无向连通图：给定无向连通图G，G是是欧拉图欧拉图，当且仅，当且仅当图中每个结点都是当图中每个结点都是偶数度偶数度结点。结点。定理定理2：无向图：无向图G有一条有一条欧拉路欧拉路，当且仅当，当且仅当G是是连连通的通的，且有，且有零个零个或或两个两个奇数度结点。奇数度结点。v2v3v4v152例：从图中找一条从图中找一条欧拉路欧拉路。解解 奇数度顶点是奇数度顶点是:v1和和v9。v1,v2和和v4,v6是桥。是桥。L=v1,v2,v3,v4,v5,v2,v4,v6,v7,v8,v9,v10,v6,v8,v10,v7,v9 是一是一条欧拉路。条欧拉路。53欧拉图欧拉图定义：定义：给定有向图给定有向图G，通过图中每边一次且仅一次的一条，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。单向路（回路），称作单向欧拉路（回路）。定理定理3：有向图有向图G具有一条单向欧拉回路，当且仅当是连通具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等到于出度。的，且每个结点入度等到于出度。一个有向图一个有向图G中具有中具有单向欧拉路单向欧拉路，当且仅当它是，当且仅当它是连通的连通的，而且除而且除两个结点外两个结点外，每个结点的，每个结点的入度入度等于等于出度出度，但这两个，但这两个结点中，一个结点的入度比出度小结点中，一个结点的入度比出度小1，一个结点的入度比，一个结点的入度比出度大出度大1。54欧拉回路问题既是一个欧拉回路问题既是一个有趣的游戏有趣的游戏问题问题,又是一个有又是一个有实用价实用价值值的问题。的问题。邮递员一般的邮递路线是需要邮递员一般的邮递路线是需要遍历某些特定的街道遍历某些特定的街道,理想地理想地,他应该走一条欧拉路他应该走一条欧拉路,即即不重复地走遍图中的每一条边不重复地走遍图中的每一条边。有的邮递任务是有的邮递任务是联系某些特定的收发点联系某些特定的收发点,不要求走遍每一条不要求走遍每一条边边,只要求不重复地遍历图中的每一个顶点只要求不重复地遍历图中的每一个顶点,此时此时感兴趣的感兴趣的是图中的顶点是图中的顶点,这就是下面研究的汉密尔顿图。这就是下面研究的汉密尔顿图。55汉密尔顿图汉密尔顿图1859年年,爱尔兰数学家汉密尔顿爱尔兰数学家汉密尔顿(Halmiton)提出一个提出一个“周游周游世界世界”的游戏的游戏,它把图它把图(a)所示的正十二面体的二十个顶点所示的正十二面体的二十个顶点当作是地球上的二十个城市当作是地球上的二十个城市,要求旅游者从某个城市出发要求旅游者从某个城市出发,沿棱沿棱走过每个城市一次且仅一次走过每个城市一次且仅一次,最后回到出发点最后回到出发点。(b)图图中粗线所构成的回路就是问题的答案中粗线所构成的回路就是问题的答案ab56二、汉密尔顿图二、汉密尔顿图1、定义：定义：给定图给定图G，若存在一条通路，经过图中的，若存在一条通路，经过图中的每个结点恰好一次，这条通路称作每个结点恰好一次，这条通路称作汉密尔顿路汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，若存在一条回路，经过图中的每个结点恰好一次，这条回路称作这条回路称作汉密尔顿回路汉密尔顿回路。具有汉密尔顿回路。具有汉密尔顿回路的图称作的图称作汉密尔顿图汉密尔顿图。57例：(a)存在汉密尔顿回路存在汉密尔顿回路,(a)是汉密尔顿图。是汉密尔顿图。(b)存在汉密尔顿通路但不存在汉密尔顿回路存在汉密尔顿通路但不存在汉密尔顿回路,(b)不是汉密尔顿不是汉密尔顿图。图。(c)不存在汉密尔顿通路且不存在汉密尔顿回路不存在汉密尔顿通路且不存在汉密尔顿回路,(c)不是汉密尔不是汉密尔顿图。顿图。（a）（b）（c）58欧拉图、欧拉回路和汉密尔顿图、汉密尔顿回路之欧拉图、欧拉回路和汉密尔顿图、汉密尔顿回路之间的间的区别区别。(1)欧拉回路是简单回路欧拉回路是简单回路,而而汉密尔顿图是基本回路汉密尔顿图是基本回路。简单回路：简单回路：各边全不相同的回路。各边全不相同的回路。基本回路：基本回路：除终点与始点外，各结点全不相同的除终点与始点外，各结点全不相同的回路。回路。(2)欧拉图欧拉图遍历边遍历边,而而汉密尔顿汉密尔顿图图遍历顶点遍历顶点。59汉密尔顿图汉密尔顿图2、定理：定理：若图若图G=具有汉密尔顿回路具有汉密尔顿回路(路路)，则，则对于结点集对于结点集V的每个非空子集的每个非空子集S(真子集真子集S)有：有：W（G-S）|S|成立，其中成立，其中W（G-S）是）是G-S中的连中的连通分支数。通分支数。(必要条件必要条件)。v1v2v7v3v5v8v4v6取取S=v1，v4v2v7v3v5v8v660汉密尔顿图汉密尔顿图3、定理：定理：设图设图G是有是有n个结点的简单图，若个结点的简单图，若G中每一对中每一对结点度数之和大于等于结点度数之和大于等于n-1，则，则 G 中存在汉密尔顿中存在汉密尔顿路。（路。（充分条件充分条件不是不是必要条件必要条件）61汉密尔顿图汉密尔顿图4、定理：定理：设图设图G是有是有n个结点的简单图，若个结点的简单图，若G中每一对中每一对结点度数之和大于等于结点度数之和大于等于n，则，则 G 中存在汉密尔顿回中存在汉密尔顿回路。（路。（充分条件充分条件不是不是必要条件必要条件）627.5 平面图先看一个例子：先看一个例子：有六个结点的图如右，有六个结点的图如右，试问：能否转变成与其等价的，试问：能否转变成与其等价的，但没有任何交线的平面上的图？但没有任何交线的平面上的图？定义定义设设G=是一个无向图，如果能够把是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称条边除了端点外没有其它的交点，就称G是一是一个平面图。个平面图。45663讨论定义：讨论定义：（1）原来在平面上的图）原来在平面上的图形似交叉，但经过若干形似交叉，但经过若干次的改画后，变成符合次的改画后，变成符合定义所规定的图；定义所规定的图；7.5 平面图64（3）并非所有的图经过处理之后都可变为平面）并非所有的图经过处理之后都可变为平面图。图。如何判断一个图是否为平面图，介绍以下几种方如何判断一个图是否为平面图，介绍以下几种方法：法：1.观察法：观察法：找出基本循环，将交叉的边分别放置在基本循环找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。内或外而避免交叉。7.5 平面图652欧拉定理：欧拉定理：定义定义设设G是一连通平面图，由图中的边所包围是一连通平面图，由图中的边所包围的区域，且在该区域内既不包含图的结点，也的区域，且在该区域内既不包含图的结点，也不包含图的边，这样的区域称为不包含图的边，这样的区域称为G的的面面。包围一个面的诸边称为此面的边界。包围一个面的诸边称为此面的边界。面的面积为有限者称为有限面，面的面积为无面的面积为有限者称为有限面，面的面积为无限者称为无限面。限者称为无限面。例：例：7.5 平面图66注：一个面的边界的回路长度称作是该面的次数，注：一个面的边界的回路长度称作是该面的次数，记为：记为：deg(r)定理定理1：一个有限平面图，面的次数之和等于其：一个有限平面图，面的次数之和等于其边数的两倍。边数的两倍。证证明明：对对于于G中中的的每每一一条条边边e，e或或是是两两个个面面的的公公共共边边，或或是是在在一一个个面面中中为为悬悬挂挂边边被被作作为为边边界界计计算算两两次，故定理成立。证毕次，故定理成立。证毕7.5 平面图67定理定理2(欧拉定理欧拉定理)设图设图G是一个是一个n个结点个结点,m条边的条边的连通平面图，它的面数为连通平面图，它的面数为r，则有欧拉公式：则有欧拉公式：nmr2。证明证明:用归纳法用归纳法 m=0时，时，G为平凡图，为平凡图，n=1，r=1，公式成立。，公式成立。7.5 平面图68设设m=k-1（k1）时公式成立，现在考虑时公式成立，现在考虑m=k时时的情况。因为在连通图上增加一条边仍为连通的情况。因为在连通图上增加一条边仍为连通图，则有三种情况：图，则有三种情况：（1）所增边为悬挂边，此时）所增边为悬挂边，此时G的面数不变，的面数不变，顶点数增顶点数增1，公式成立。，公式成立。（2）在图的任意两个不相邻点间增加一条）在图的任意两个不相邻点间增加一条边，此时边，此时G的面数增的面数增1，边数增，边数增1，但顶点数不，但顶点数不变，公式成立。变，公式成立。（3）所增边为一个环，此时）所增边为一个环，此时G的面数增的面数增1，边数增，边数增1，但顶点数不变，公式成立。，但顶点数不变，公式成立。7.5 平面图69定理3:设G是连通的（n，m）平面图且每个面的次数至少为l（l3），则 证明证明:由定理由定理1(r为G的面数)再由欧拉公式 n-m+r=27.5 平面图70于是有故 7.5 平面图71定理定理4:设图设图G是一个是一个n个结点个结点,m条边的连通简单条边的连通简单平面图，若平面图，若n33则则m3n-6。上述定理给出了是平面图的必要条件，若不满足上述定理给出了是平面图的必要条件，若不满足这些条件，则一定不是平面图。这些条件，则一定不是平面图。例：例：7.5 平面图72证证明明：由由于于G是是n3的的连连通通简简单单平平面面图图，所所以以G的的每每个个面面至至少少由由3条条边边围围成成，即即l 3，代代入入定理定理3，得，得m3n-6证毕证毕7.5 平面图73推推论论1:若若连连通通简简单单平平面面图图G不不以以K3为为子子图图，则则m2n-4。证证明明:由由于于G中中不不含含K3，所所以以G的的每每个个面面至至少由少由4条边围成，即条边围成，即l4，代入定理代入定理3，得，得m2n-4证毕证毕7.5 平面图74推论推论2K5和和K3，3是非平面图。是非平面图。证证明明:假假设设K5是是平平面面图图，由由定定理理4可可知知应应有有m3n-6，而而当当n=5，m=10时时，这这是是不不可可能的，所以能的，所以K5是非平面图。是非平面图。假假设设K3，3是是平平面面图图，因因其其不不含含子子图图K3，由由推推论论1可可知知，当当n=6，m=9时时，m2n-4是是不可能的，所以不可能的，所以K3，3是非平面图。证毕是非平面图。证毕7.5 平面图753库拉托夫斯基（库拉托夫斯基（Kuratowski波兰数学家）定理：波兰数学家）定理：给定两个图，做以下的工作：给定两个图，做以下的工作：(1)在（在（a）图左边的中间联线上插入一个度数为）图左边的中间联线上插入一个度数为2的结的结点，则把一条边分成了二条边；点，则把一条边分成了二条边；(2)在（在（b）图左边图中去掉一个度数为）图左边图中去掉一个度数为2的结点，则把的结点，则把二条边变成一条边。二条边变成一条边。此二项工作不会影响图的平面性。此二项工作不会影响图的平面性。7.5 平面图76定义定义设设G1、G2是二个图，如果它们是同构的，是二个图，如果它们是同构的，或可以通过反复插入或删除度数为或可以通过反复插入或删除度数为2的结点，的结点，使得使得G1和和G2同构，则称同构，则称G1、G2为为2度结点内度结点内同构。同构。例：下列二对图是度数为例：下列二对图是度数为2的结点同构的结点同构2度结点内同构度结点内同构7.5 平面图77定理定理（Kuratowski定理）即库拉托夫斯基定定理）即库拉托夫斯基定理理设设G是一个图，当且仅当是一个图，当且仅当G不包含任何在度数为不包含任何在度数为2的结点内与的结点内与K3,3和和K5图同构的子图时，则图同构的子图时，则G才才是平面图。是平面图。这一定理给出了一个图是平面图的充要条件。这一定理给出了一个图是平面图的充要条件。7.5 平面图78【例例】证明图中的（证明图中的（a）和（和（d）不是平面图。不是平面图。解解:图图(a）是著名的彼得森（是著名的彼得森（Pertersen）图，去掉图，去掉其中的两条边后得子图（其中的两条边后得子图（b），），该子图同构于该子图同构于K3，3（c）。）。因此彼得森图不是平面图。图（因此彼得森图不是平面图。图（d）图中含图中含有子图（有子图（e），），图（图（e）图同构于图同构于K3，3（f）。）。库库拉拉托托斯斯基基定定理理虽虽然然简简单单漂漂亮亮，但但实实现现起起来来并并不不容容易易，特特别别是是顶顶点点数数较较多多的的时时候候，还还有有许许多多这这方面的研究工作要做。方面的研究工作要做。7.5 平面图797.5 平面图801.对偶图对偶图平平面面图图有有一一个个很很重重要要的的特特性性，任任何何平平面面图图都都有有一一个个与与之之对对应应的的平平面面图图，称称为为它它的的对偶图。对偶图。定定义义1设设平平面面图图G=V,E有有r个个面面R1，R2，Rr，若若有有图图G*=V*,E*满满足足下下述条件：述条件：（1）RiG，内内部部有有且且仅仅有有一一个个结结点点v*iV*，i=1，2，r。7.6 对偶图与着色81（2）若若e是是G中中两两个个不不同同面面Ri和和Rj的的公公共共边边，则则存存在在且且仅仅存存在在一一条条边边e*kG*,使使e*k=（v*i，v*j），且与且与e相交；相交；（3）若若e是是一一个个面面Ri内内的的边边，则则在在G*中中有有一一条条与与e交叉的环（交叉的环（v*i，v*i）。）。则称则称G*为为G的对偶图，的对偶图，G*与与G互为对偶图。互为对偶图。7.6 对偶图与着色827.6 对偶图与着色例例如如，图图（a）和和（b）中中，G*是是G的的对对偶偶图图，G的的边边用用实实线线表表示示，G*的的边边用用虚虚线线表表示示，顶顶点点用用实实心点表示。心点表示。832.着色问题着色问题在在地地图图上上，相相邻邻国国家家涂涂不不同同的的颜颜色色，最最少少需需要要多多少少种种颜颜色色？100多多年年前前，有有人人提提出出了了“四四色色猜猜想想”，即即只只用用四四种种颜颜色色就就能能做做到到，但但一一直直无无法法证证明明，直直到到1976年年美美国国数数学学家家才才用用电电子计算机证明了这一猜想。子计算机证明了这一猜想。地地图图着着色色自自然然是是对对平平面面图图的的面面着着色色，利利用用对对偶偶图图，可可将将其其转转化化为为相相对对简简单单的的顶顶点点着着色问题，即对图中相邻的顶点涂不同的颜色。色问题，即对图中相邻的顶点涂不同的颜色。7.6 对偶图与着色84定定义义2设设G是是一一个个无无自自环环的的图图，给给G的的每每个个顶顶点点指指定定一一种种颜颜色色，使使相相邻邻顶顶点点颜颜色色不不同同，称称为为对对G的的一一个个正正常常着着色色。图图G的的顶顶点点可可用用k种种颜颜色色正正常常着着色，称色，称G是是k可着色的。可着色的。使使G是是k可可着着色色的的数数k的的最最小小值值称称为为G的的色色数数，记作记作(G)。如果。如果(G)=k，则称则称G是是k色的。色的。7.6 对偶图与着色85到到现现在在还还没没有有一一个个简简单单的的方方法法可可以以确确定定任任 一一 图图 G是是 n色色 的的。但但 韦韦 尔尔 奇奇 鲍鲍 威威 尔尔（WelchPowell）给给出出了了一一种种对对图图的的着着色色方方法法，步骤如下：步骤如下：（1）将将图图G中中的的顶顶点点按按度度数数递递减减次次序序排排列。列。（2）用用第第一一种种颜颜色色对对第第一一顶顶点点着着色色，并并将与已着色顶点不邻接的顶点也着第一种颜色。将与已着色顶点不邻接的顶点也着第一种颜色。（3）按排列次序用第二种颜色对未着色）按排列次序用第二种颜色对未着色的顶点重复（的顶点重复（2）。）。用第三种颜色继续以上做用第三种颜色继续以上做法，直到所有的顶点均着上色为止。法，直到所有的顶点均着上色为止。7.6 对偶图与着色86【例例】用韦尔奇用韦尔奇鲍威尔法对下图着色。鲍威尔法对下图着色。（1）各各顶顶点点按按度度数数递递减减次次序序排排列列：c，a，e，f，b，h，g，d。（2）对）对c和与和与c不邻接的不邻接的e，b着第一种颜色。着第一种颜色。（3）对）对a和与和与a不邻接的不邻接的g，d着第二种颜色。着第二种颜色。（4）对）对f和与和与f不邻接的不邻接的h着第三种颜色。着第三种颜色。7.6 对偶图与着色87定义定义1连通无回路的无向图称为无向树，连通无回路的无向图称为无向树，简称树，记作简称树，记作T。树叶树叶(终点终点)：树中度数为：树中度数为1 1的结点。的结点。内点内点(分枝点分枝点)：树中度数大于：树中度数大于1 1的结点。的结点。森林：每个连通分图均为树的图。森林：每个连通分图均为树的图。平凡图称为平凡树。平凡图称为平凡树。7.7树与生成树树与生成树88图 1 7.7树与生成树树与生成树例例:图图1中（中（a）、（）、（b）均是树，图（）均是树，图（c）是森林。）是森林。由于树无环且无平行边（否则有回路），所以树必由于树无环且无平行边（否则有回路），所以树必是简单图。是简单图。89定理定理1无向图无向图T是树，以下关于树的定义是等价是树，以下关于树的定义是等价的。的。（1）无回路的连通图）无回路的连通图（2）无回路且）无回路且m=n-1，其中其中m为边数，为边数，n 为顶为顶点数。点数。（3）T是连通图且是连通图且m=n-1。（4）T中无回路，但增加一条边，则得到一条中无回路，但增加一条边，则得到一条且仅一条回路。且仅一条回路。（5）T连通且每条边均是桥。连通且每条边均是桥。（6）每对顶点间有唯一的一条路。）每对顶点间有唯一的一条路。7.7树与生成树树与生成树90（2）无回路且）无回路且m=n-1，其中，其中m为边数，为边数，n为顶点数。为顶点数。证明证明：由树的定义可得（：由树的定义可得（2）。）。施归纳于顶点数施归纳于顶点数n。当。当n=1时，时，m=0，则，则m=n-1成立。成立。假设当假设当n=k时，时，m=n-1成立。则当成立。则当n=k+1时，因为树是时，因为树是连通的且无回路，所以至少有一个度数为连通的且无回路，所以至少有一个度数为1的顶点的顶点v，从树中删去从树中删去v和与它关联的边，则得到和与它关联的边，则得到k个顶点的树个顶点的树T。根据假设它有根据假设它有k-1条边，现将条边，现将v和与它关联的边加到和与它关联的边加到T上还原成树上还原成树T，则，则T有有k+1个顶点，个顶点，k条边，边数比顶点条边，边数比顶点数少数少1，故，故m=n-1成立。成立。7.7树与生成树树与生成树91（3）T是连通图且是连通图且m=n-1证明：证明：由（由（2）可得（）可得（3）。）。反反证证法法：若若图图T不不连连通通，设设T有有k个个连连通通分分支支T1，T2，Tk（k2），其其顶顶点点数数分分别别为为n1，n2，nk，则有则有边数分别为边数分别为m1，m2，mk，则有则有 7.7树与生成树树与生成树92因此，有即即mn-1，这与这与m=n-1矛盾，故矛盾，故T是连通的是连通的m=n-1图。图。7.7树与生成树树与生成树93（4）T中无回路，但增加一条边，则得到一条且仅一条回路。中无回路，但增加一条边，则得到一条且仅一条回路。证明：证明：由（由（3）可得（）可得（4）。）。若若T是连通图并有是连通图并有n-1条边。施归纳于顶点数条边。施归纳于顶点数n。当当n=2时时，m=n-1=1，所所以以没没有有回回路路，如如果果增增加加一一条条边边，只只能能得得到唯一的一个回路。到唯一的一个回路。假假设设n=k时时，命命题题成成立立。则则当当n=k+1时时，因因为为T是是连连通通的的并并有有n-1条条边边，所所以以每每个个顶顶点点都都有有d（v）1，并并且且至至少少有有一一个个顶顶点点v0，满满足足d（v0）=1。否否则则，如如果果每每个个顶顶点点v都都有有d（v）2，那那么么必必然然会会有有总总度度数数2m2n，即即mn，这这与与条条件件m=n-1矛矛盾盾。因因此此至至少少有有一一个个顶点顶点v0，满足满足d（v0）=1。7.7树与生成树树与生成树94删删去去v0及及其其关关联联的的边边，得得到到图图T，由由假假设设知知T无无回回路路，现现将将v0及及其其关关联联的的边边再再加加到到T，则则还原成还原成T，所以所以T没有回路。没有回路。如如果果在在连连通通图图T中中增增加加一一条条新新边边（vi，vj），则则（vi，vj）与与T中中从从vi到到vj的的一一条条路路构构成成一一个个回回路路，且且该该回回路路必必定定是是唯唯一一的的，否否则则当当删删去去新新边（边（vi，vj）时，时，T中必有回路，产生矛盾。中必有回路，产生矛盾。7.7树与生成树树与生成树95（5）T连通且每条边均是桥。连通且每条边均是桥。证明：证明：由（由（4）可得（）可得（5）。）。若若图图T不不连连通通，则则存存在在两两个个顶顶点点vi和和vj，在在vi，vj之之间间没没有有路路径径，如如果果增增加加边边（vi，vj）不不产产生生回回路路，这这与与（4）矛矛盾盾，因因此此T连连通通。因因为为T中中无无回回路路，所所以以删删去去任任意意一一条条边边，图图必必不不连连通通。故故图图中中每每一一条边均是桥。条边均是桥。7.7树与生成树树与生成树96（6）每对顶点间有唯一的一条路。）每对顶点间有唯一的一条路。证明：证明：由（由（5）可得（）可得（6）。）。由图的连通性可知，任意两个顶点之间都有一由图的连通性可知，任意两个顶点之间都有一条通路。如果这条路不唯一，则条通路。如果这条路不唯一，则T中必有回路，删去中必有回路，删去回路上的任意一条边，图仍连通，与（回路上的任意一条边，图仍连通，与（5）矛盾。故）矛盾。故任意两个顶点之间有唯一一条路。任意两个顶点之间有唯一一条路。7.7树与生成树树与生成树97树：无回路的连通图树：无回路的连通图证明：证明：由（由（6）可得树的定义。）可得树的定义。每每对对顶顶点点之之间间有有唯唯一一一一条条路路，那那么么T必必连连通通，若若有有回回路路，则则回回路路上上任任意意两两个个顶顶点点之之间间有有两两条条路路，与与（6）矛矛盾盾。故故图图连通且无回路，是树。连通且无回路，是树。7.7树与生成树树与生成树98定理定理2任何一棵非平凡树任何一棵非平凡树T至少有两片树叶。至少有两片树叶。证证明明设设T是是（n，m）图图，n2，有有k片片树树叶叶，其其余顶点度数均大于或等于余顶点度数均大于或等于2。则。则而 所以所以2n-22n-k，即，即k2。7.7树与生成树树与生成树99【例例】T是是一一棵棵树树,有有两两个个顶顶点点度度数数为为2，一一个个顶顶点点度度数数为为3，三三个个顶顶点点度度数数为为4，T有有几几片片树树叶？叶？解解设树设树T有有x片树叶，则片树叶，则T的顶点数的顶点数 n=2+1+3+x T的边数的边数m=n-1=5+x又由又由握手定理握手定理得得2(5+x)=22+31+43+x所以所以x=9，即树即树T有有9片树叶。片树叶。7.7树与生成树树与生成树100有有一一些些图图，本本身身不不是是树树，但但它它的的某某些些子子图图却却是是树树，其中很重要的一类是生成树。其中很重要的一类是生成树。定定义义2若若无无向向图图G的的一一个个生生成成子子图图T是是树树，则则称称T是是G的的一一棵生成树。棵生成树。例如图例如图3中，中，T1和和T2是图是图G的两棵生成树。的两棵生成树。图 3 7.7树与生成树树与生成树101定理定理3：任何连通图至少有一棵生成树。任何连通图至少有一棵生成树。如何在连通图如何在连通图G中寻找一棵生成树：中寻找一棵生成树：若若G没有回路，则没有回路，则G本身就是一棵树；本身就是一棵树；若若G仅有一条回路，从此回路中删去一条边，仅有一条回路，从此回路中删去一条边，仍保持图的连通性，得到一棵生成树。仍保持图的连通性，得到一棵生成树。若若G有多条回路，则逐个对每条回路重复有多条回路，则逐个对每条回路重复中中操作，直到打断操作，直到打断G中所有回路，得到一棵生成树中所有回路，得到一棵生成树为止。为止。7.7树与生成树树与生成树102如如果果T是是G的的一一棵棵生生成成树树，则则称称T中中的的边边为为树树枝枝，G不不在在T中中的的边边为为T的的弦弦，T的的所所有有弦弦的的集集合合称称作生成树作生成树T的补。的补。一一般般情情况况，图图G的的生生成成树树不不是是唯唯一一的的，一一个个连连通通的的（n，m）图图，其其任任意意一一棵棵生生成成树树的的树树枝枝数数一一定是定是n-1，从而弦数也是固定不变的从而弦数也是固定不变的m-n+1。由由树树的的性性质质可可知知，对对于于图图G的的一一棵棵生生成成树树T，每增加一条弦，便得到一条回路。每增加一条弦，便得到一条回路。定定理理4：一一条条回回路路和和任任何何一一棵棵生生成成树树的的补补至至少少有有一一条条公共边。公共边。7.7树与生成树树与生成树103例如，在图例如，在图3所示的所示的T1中：中：加弦加弦e5，得回路得回路e2e3e5；加弦加弦e4，得回路得回路e1e3e4；7.7树与生成树树与生成树104另另一一方方面面，从从树树T中中删删去去一一边边，便便将将T分分成成两两棵棵树树，即即两两个个连连通通分分支支，图图G中中连连接接这这两两个个连连通通分分支支的的边边的的集集合合，称称为对应于这条边的基本（边）割集。为对应于这条边的基本（边）割集。例如在图例如在图3中的中的G和和T1：对应树枝对应树枝e1，有基本割集有基本割集e1，e4；对应树枝对应树枝e2，有基本割集有基本割集e2，e5；对应树枝对应树枝e3，有基本割集有基本割集e3，e4，e5；7.7树与生成树树与生成树105这这些些边边割割集集所所具具有有的的共共同同特特点点是是：每每个个割割集集中中均均只只含含生生成成树树的的一一个个树树枝枝，其其余的均是弦。余的均是弦。定定理理5：一一个个边边割割集集和和任任何何生生成成树树至至少少有有一一条公共边。条公共边。7.7树与生成树树与生成树106最小生成树最小生成树带带权权图图的的生生成成树树是是实实际际应应用用较较多多的的树树，所所谓谓权权就就是是附附加加在在图图上上的的信信息息，通通常常是是实实数数，权权加加在在边边上上的的称称边权图。边权图。7.7树与生成树树与生成树定义定义3对图对图G的每条边附加上一个实数的每条边附加上一个实数（e），称），称（e）为边）为边e上的权，上的权，