chap7离散数学 图论

1、图论与代数系统 图论第七章第七章 图论图论 图论是有许多现代应用的古老题目。瑞士数学家欧拉在图论是有许多现代应用的古老题目。瑞士数学家欧拉在18世世纪引进了图论的基本思想。利用图解决了纪引进了图论的基本思想。利用图解决了哥尼斯堡七桥问题哥尼斯堡七桥问题。 图可以用来解决许多领域的问题。例如：图可以用来解决许多领域的问题。例如：v 用图来确定能否在平面电路板上实现电路用图来确定能否在平面电路板上实现电路v 用图来区分分子式相同但结构不同的两种化学物用图来区分分子式相同但结构不同的两种化学物v 用边上带权值的图来解决诸如寻找交通网络里用边上带权值的图来解决诸如寻找交通网络里v 两个城市间最短通路的

2、问题两个城市间最短通路的问题v 用图来安排考试用图来安排考试 随着科技的发展，图论在解决运筹学、网络理论、信息论、随着科技的发展，图论在解决运筹学、网络理论、信息论、控制论、博弈论等问题时，发挥了巨大的作用。控制论、博弈论等问题时，发挥了巨大的作用。图论与代数系统 图论1、图、图 图由结点和连接两个结点之间的连线组成。连线的长度和图由结点和连接两个结点之间的连线组成。连线的长度和结点的位置是无关紧要的。结点的位置是无关紧要的。 几乎每一门可以想象的学科里都有问题可以用图模型来解几乎每一门可以想象的学科里都有问题可以用图模型来解决。例如：可以用图来表示生态环境里不同物种的竞争；可以决。例如：可以

3、用图来表示生态环境里不同物种的竞争；可以用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅行商问题；地球着色问题等。行商问题；地球着色问题等。 简单的图例子：简单的图例子：大城市之间的高速公路系统建模大城市之间的高速公路系统建模： 可以把各个城市看成结点，城市之间存在告诉公路，则认可以把各个城市看成结点，城市之间存在告诉公路，则认为这两个城市之间有连线，这样可以构成一个简单的图。为这两个城市之间有连线，这样可以构成一个简单的图。 7-1 图的基本概念图的基本概念图论与代数系统 图论(a)、(b)表示的是同一个图形。表示的是同一个图形。(

4、a)bcade1e4e5e6e2e3(b)bcde1e4e2e3e6e52、图的表示法、图的表示法三元组表示：三元组表示：G=,V(G)：非空的结点集合；非空的结点集合；E(G)：边集合；边集合； G： 边集合边集合E E到结点无序偶（有序偶）集合上的函数。到结点无序偶（有序偶）集合上的函数。 7-1 图的基本概念图的基本概念图论与代数系统 图论上图中，上图中，V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6, G(e1)=(a,b), G(e2)=(a,c), G(e3)=(b,d), G(e4)=(b,c), G(e5)=(d,c), G(e6)=(a,d).一般情

5、况下，边可看作是与两个结点关联，所以图可简记为一般情况下，边可看作是与两个结点关联，所以图可简记为 G=。(a)bcade1e4e5e6e2e3 7-1 图的基本概念图的基本概念图论与代数系统 图论3、图的一些基本概念、图的一些基本概念1）无向边：无向边：与结点无序偶关联的边，用（与结点无序偶关联的边，用（a,b)表示；表示； 有向边：有向边：与结点有序偶关联的边，用与结点有序偶关联的边，用表示；表示； 表明是从表明是从a到到b的有向边。的有向边。 孤立结点：孤立结点：无邻接点的结点；无邻接点的结点；无向边：无向边：(a,b),(b,c),(b,d),(c,d),(i,l),(k,l)有向边：

6、有向边：,efghijklabcd 7-1 图的基本概念图的基本概念图论与代数系统 图论3）邻接点：邻接点：由一条有向边或一条无向边相关联的两结点；由一条有向边或一条无向边相关联的两结点； 邻接边：邻接边：关联于同一结点的两条边；关联于同一结点的两条边；2）无向图：无向图：图中每一边都为无向边；图中每一边都为无向边； 有向图：有向图：图中每一边都为有向边；图中每一边都为有向边； 混合图：混合图：图中既有有向边，也有无向边；图中既有有向边，也有无向边； 平凡图：平凡图：仅由一个孤立结点构成的图。仅由一个孤立结点构成的图。abcdefghijkl 7-1 图的基本概念图的基本概念图论与代数系统 图

7、论4）结点的度数）结点的度数在图在图G=V，E中，与结点中，与结点v关联的边数，记为关联的边数，记为deg(v)，一个环的度数为一个环的度数为2。如上图，。如上图，deg(B)=3,deg(E)=5。在有向图中，定义入度、出度的概念在有向图中，定义入度、出度的概念自回路（环）：自回路（环）：关联于同一结点的一条边关联于同一结点的一条边（既可看作是有向边，也可作无向边）（既可看作是有向边，也可作无向边）ABCDE平行边：平行边：连接于同一对结点的多条边连接于同一对结点的多条边 7-1 图的基本概念图的基本概念图论与代数系统 图论入度：入度： 射入一个结点的边的条数，记为射入一个结点的边的条数，记

8、为deg-(v)；出度：出度： 由一个结点射出的边的条数由一个结点射出的边的条数，记为，记为deg+(v)；入度与出度之和即为该结点的入度与出度之和即为该结点的度数度数。 deg(v)= deg+(v)+ deg-(v)右图中，右图中，deg+(e)=2,deg-(e)=1,deg(e)=3 deg+(f)=1,deg-(f)=2,deg(f)=3 deg+(g)=deg-(g)=1,deg(g)=2 deg+(h)=deg-(h)=1,deg(h)=2efgh 7-1 图的基本概念图的基本概念图论与代数系统 图论定理定理: 图图G=中中,结点度数总和等于边数的两倍结点度数总和等于边数的两倍,

9、即即:deg( )2v VvE最大度：最大度：( )maxdeg( )Gv vV G最小度：最小度：( )mindeg( )Gv vV G5）结点度数的有关性质）结点度数的有关性质ABCDE2)(, 5)(GG右图中，证明：每条边关联两个结点证明：每条边关联两个结点 一条边给相关的每个结点的度数为一条边给相关的每个结点的度数为1 因此，在图中，结点度数总和等于边数的两倍。因此，在图中，结点度数总和等于边数的两倍。deg( )147v VvE例如：上图中， 7-1 图的基本概念图的基本概念图论与代数系统 图论定理定理: 度数为奇数的结点必定是偶数个。度数为奇数的结点必定是偶数个。证明：证明： 设

10、设V1、V2分别为分别为G中奇数度数点集和偶数度数点集，则：中奇数度数点集和偶数度数点集，则：EvvvVvVvVv2)deg()deg()deg(21为偶数。为偶数。2)deg(Vvv为偶数为偶数,2|E|亦为偶数，亦为偶数，1)deg(Vvv为偶数。1V 7-1 图的基本概念图的基本概念图论与代数系统 图论定理：定理： 有向图中，所有结点的入度之和等于有向图中，所有结点的入度之和等于 所有结点的出度之和。所有结点的出度之和。证明：证明： 一条边对应一个入度和一个出度，一条边对应一个入度和一个出度， 一个结点若具有一个出度或入度，则必关联边，一个结点若具有一个出度或入度，则必关联边， 所以入度

11、之和等于边数，出度之和也等于边数。所以入度之和等于边数，出度之和也等于边数。 下面联系前面介绍的平行边和环的概念给出多重图、简单下面联系前面介绍的平行边和环的概念给出多重图、简单图、完全图的概念。图、完全图的概念。 请大家先区分有向图、无向图、混合图的概念。请大家先区分有向图、无向图、混合图的概念。 7-1 图的基本概念图的基本概念图论与代数系统 图论6）多重图：）多重图： 含有平行边的图；含有平行边的图； 简单图：简单图： 不含有平行边和环的图；不含有平行边和环的图； 完全图：完全图： 简单图中，每一对结点间都有边关联。简单图中，每一对结点间都有边关联。 如果对每条边任意确定一个方向，就称该

12、图为如果对每条边任意确定一个方向，就称该图为有向完全图。有向完全图。定理：定理： n个结点的无向（有向）完全图个结点的无向（有向）完全图Kn的边数为的边数为n(n-1)/2。证明：在完全图中，每个结点的度数应为证明：在完全图中，每个结点的度数应为n1，则，则n个结点的个结点的 度数之和为度数之和为n(n-1)，因此，因此|E|n(n-1)/2。abcdefgh 7-1 图的基本概念图的基本概念图论与代数系统 图论7）子图：）子图： G=,有有G=，且，且 G为为G的的 子图。子图。,VVEEefghefgh生成子图：生成子图：包含包含G中所有结点的子图。中所有结点的子图。 7-1 图的基本概念

13、图的基本概念图论与代数系统 图论8）补图：）补图： 设设G是是G的子图，若的子图，若G=,使得使得EEE， 且且V中无孤立结点，则称中无孤立结点，则称G是是G相对于相对于G的补图。的补图。ghabfgchdebfgcdeabfchd(a) (b) (c) 上例中，图上例中，图(c)是图是图(b)相对于图相对于图(a)的补图的补图思考：思考：若若G是是G相对于相对于G的补图，是否一定有的补图，是否一定有G是是G相对于相对于G的的 补图？即补图？即G和和G互为补图？互为补图？ 如上例，是否图如上例，是否图(b)也是图也是图(c)相对于图相对于图(a)的补图呢？的补图呢？不是不是，补图中不包含孤立结

14、点。那何时出现互为补图的情况呢？，补图中不包含孤立结点。那何时出现互为补图的情况呢？ 7-1 图的基本概念图的基本概念图论与代数系统 图论 在图在图G中，由中，由G中所有结点和所有能使中所有结点和所有能使G成为完全图的添加边成为完全图的添加边组成的图是组成的图是G相对于完全图的补图相对于完全图的补图，简称为，简称为G的补图的补图，记为，记为G(a) (b)和和G一定互为补图一定互为补图G 7-1 图的基本概念图的基本概念图论与代数系统 图论在表示图时，图的结点位置和连线长度可以任意选择，故一个图在表示图时，图的结点位置和连线长度可以任意选择，故一个图的图形表示不唯一，因而需讨论图的同构的概念。

15、的图形表示不唯一，因而需讨论图的同构的概念。9）图的同构：）图的同构： G，G=,存在一一对应的映射存在一一对应的映射G：vivi，且，且e(vi,vj)(或或)是是G的一条边当且仅当的一条边当且仅当e=(g(vi),g(vj)(或或)也是也是G的一条边，称的一条边，称G与与G同构同构，记，记为为GG。(a) (b) (c) (d)在上图中，在上图中，(a)和和(b)是同构的，是同构的，(c)和和(d)也是同构的。也是同构的。 7-1 图的基本概念图的基本概念图论与代数系统 图论再如：再如：映射映射(a)=1, (b)=3, (c)=5, (d)=2, (a)=1, (b)=3, (c)=5,

16、 (d)=2, (e e)=4,(f)=6, )=4,(f)=6, 在无向简单图在无向简单图G G1 1和和G G2 2之间建立了之间建立了一个同构一个同构. . 7-1 图的基本概念图的基本概念图论与代数系统 图论由同构的定义，易见两图同构必定满足以下条件：（必要条件）由同构的定义，易见两图同构必定满足以下条件：（必要条件）a、结点数目相等；、结点数目相等；b、边数相等；、边数相等；c、度数相同的结点数目相同。、度数相同的结点数目相同。可知可知G与与G同构的充要条件是：同构的充要条件是：（1）结点一一对应结点一一对应；（2）边一一对应边一一对应；（3）保持关联关系保持关联关系。 7-1 图的

17、基本概念图的基本概念图论与代数系统 图论以上三个条件并不是两图同构的充分条件，如下图：以上三个条件并不是两图同构的充分条件，如下图：acbdeabced(a) (b) 7-1 图的基本概念图的基本概念图论与代数系统 图论1. 基本概念基本概念0112, ,nnv vvV e eeE1） 路：路： 图图G=，设，设 其中其中ei是关联于结点是关联于结点vi-1,vi的边，交替序列的边，交替序列nnveevev2110称为联结称为联结v0到到vn的路；的路；v0，vn分别称为路的起点和终点；分别称为路的起点和终点；回路：回路： 起点和终点相等的路；起点和终点相等的路； 迹：迹： 所有的边都不相同的

18、路；所有的边都不相同的路；通路：通路： 所有的结点都不相同的路；所有的结点都不相同的路；圈：圈： 除除v0=vn外，其余结点都不相同的路。外，其余结点都不相同的路。7-2 路与回路路与回路图论与代数系统 图论v1v2v4v5v3e1e5e8e7e6e4e3e2如右图中，有：如右图中，有： 路：路： v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：迹： v5e8v4e5v2e6v5e7v3e4v2 通路：通路：v4e8v5e6v2e1v1e2v3 图：图： v2e1v1e2v3e7v5e6v2定理：定理： G=具有具有n个结点，如果从结点个结点，如果从结点vj到结点到结点vk存在一存在

19、一 条路，则此两结点间必存在一条边不多于条路，则此两结点间必存在一条边不多于n-1的路。的路。证明：证明： 设结点设结点vj到到vk的路上的结点序列为的路上的结点序列为 ，结点序，结点序列中结点的个数为列中结点的个数为L+1，则这条路中有，则这条路中有L条边，若条边，若Ln-1，则结点，则结点序列中必出现重复结点，因而可以去除重复结点之间的边，得到序列中必出现重复结点，因而可以去除重复结点之间的边，得到的仍是联结的仍是联结vi到到vk的路，依此类推，必可得到边不多于的路，依此类推，必可得到边不多于n-1的路。的路。kijvvv7-2 路与回路路与回路图论与代数系统 图论推论：推论： G=具有具

20、有n个结点，如果从结点个结点，如果从结点vj到结点到结点vk存在一存在一 条路，则此两结点间必存在一条边不多于条路，则此两结点间必存在一条边不多于n-1的通路。的通路。2）连通性：）连通性： 在无向图在无向图G中，若结点中，若结点u和和v之间存在一条路，则之间存在一条路，则 称称u和和v是连通的；是连通的；性质：性质：结点之间的连通性是结点集上的等价关系。结点之间的连通性是结点集上的等价关系。证明：自反性：证明：自反性：v和和v是连通的是连通的 对称性：若对称性：若u和和v连通，则连通，则v和和u必定也是连通的必定也是连通的 传递性：传递性：u和和v连通，连通，v和和w连通，则连通，则u和和w

21、中也存在路，连通中也存在路，连通 对应等价关系给出一个划分，把结点集对应等价关系给出一个划分，把结点集V划分为划分为V1,V2,Vm，使得两个结点使得两个结点vi和和vj是连通的，当且仅当他们同属于同一个是连通的，当且仅当他们同属于同一个Vi。称子图称子图G(V1),G(V2),G(Vm)为图为图G的的连通分支连通分支； 连通分支数：连通分支数：W(G) 无向图无向图G的一个连通分支为的一个连通分支为G的一个的一个极大连通子图极大连通子图 7-2 路与回路路与回路图论与代数系统 图论连通图：连通图： 只有一个连通分支的图；只有一个连通分支的图； 即任意两个结点都连通的无向图。即任意两个结点都连

22、通的无向图。 图图(a)是连通图，是连通图， 图图(b)有三个连通分支的非连通图。有三个连通分支的非连通图。 在图中在图中删除结点删除结点v，即把结点，即把结点v和所有与其和所有与其相关联的边都删掉；相关联的边都删掉； 在图中在图中删除边删除边，仅需把该边删去。，仅需把该边删去。 可知对一个图删结点或边，会影响其连通性。可知对一个图删结点或边，会影响其连通性。 考虑：考虑：至少要删除多少条边或结点，连通图至少要删除多少条边或结点，连通图会变为非连通图呢？（即如何描述连通程度）会变为非连通图呢？（即如何描述连通程度） 引入点割集和边割集的概念引入点割集和边割集的概念(a)（b）7-2 路与回路路

23、与回路图论与代数系统 图论3）点割集：点割集： G=为无向连通图，为无向连通图， ，图，图G删除了删除了V1所有所有 的结点后，所得的子图是非连通图，但删除的结点后，所得的子图是非连通图，但删除V1的任何真子集的任何真子集 后，得到的子图仍是连通图，称后，得到的子图仍是连通图，称V1是是G的一个点割集；的一个点割集；VV 1 割点：割点： 若点割集中只有一个结点，此结点称为割点；若点割集中只有一个结点，此结点称为割点； 点割集或者割点是否唯一？点割集或者割点是否唯一？abcdefabcdfabcef不唯一不唯一e和和d都为图的割点都为图的割点7-2 路与回路路与回路图论与代数系统 图论点连通度

24、：点连通度： 产生一个非连通图需要删去的点的产生一个非连通图需要删去的点的最少数目。记为最少数目。记为。的点割集是|min|)(11GVVGk非连通图的点连通度为非连通图的点连通度为0；存在割点的连通图的点连通度为存在割点的连通图的点连通度为1；完全图完全图Kp的点连通度为的点连通度为p-1；不同点割集中的结点数目是否一定相同？不同点割集中的结点数目是否一定相同？ 右图中，右图中，e和和f都是割点都是割点 c,d为一个点割集。为一个点割集。可知不同点割集中的结点数目也可知不同点割集中的结点数目也未必未必相同相同 因而引入因而引入点连通度点连通度的概念的概念abcdeghf上例中，上例中，k(G

25、)1。7-2 路与回路路与回路图论与代数系统 图论边割集：边割集： G=为无向连通图，为无向连通图， 图图G删除了删除了E1所有所有的边后，所得的子图是非连通图，但删除的边后，所得的子图是非连通图，但删除E的任何真子集，的任何真子集，得到的子图仍是连通图，称得到的子图仍是连通图，称E是是G的一个边割集；的一个边割集；EE 1割边（桥）：割边（桥）： 若边割集中只有一条边，此边称为割边；若边割集中只有一条边，此边称为割边；边连通度：边连通度： 产生一个不连通图需要删去的边的最少数目，记为产生一个不连通图需要删去的边的最少数目，记为。的边割集是|min|)(11GEEG 不连通图的边连通度为不连通

26、图的边连通度为0；存在割边的连通图的边连通度为存在割边的连通图的边连通度为1；完全图完全图Kp的边连通度为的边连通度为p-1；7-2 路与回路路与回路图论与代数系统 图论上式成立。不连通，则证明：, 0)()(GGkG1( )( )( )( )2( )( )( )1( )1GGGGGGGk GGaGGk G 若 连通）是平凡图（只有一个孤立结点），显然；是非平凡图，对于任意结点，删除其关联的边，必定能得到不连通子图，所以每个结点的关联的边必定包含一个边割集，故。）（ ）设， 有一割边，则定理：定理： 对于任何一个图对于任何一个图G，有，有( )( )( )k GGG ( )( )( )k GG

27、G：点连通度；：边连通度；：最小度。abcdef7-2 路与回路路与回路图论与代数系统 图论定理（割点存在定理）：定理（割点存在定理）： 连通无向图连通无向图G中的结点中的结点v是割点的充要是割点的充要条件是存在两个结点条件是存在两个结点u和和w，使得结点，使得结点u和和w的每一条路都通过的每一条路都通过v。)()()()()()(1)()(1)(1)(,1)(,1)(2)(GGGkGGkvuGGGkGGvuGvuGnGGGb因此，。，得到不连通图，有或者，若仍为连通图，删去连通，边。若此时产生的图不条个顶点，至少删去了的端点，可知删去此取一个不同于条边中的每一条边都选），对条桥（仍是连通的，

28、且存在一边，条中的不连通。可知若删去其条边，使得，可删去）设（。过中的任意一条路都得通，也即经过必必不连通，因此中通分支，故在分别属于两个不同的连，但在路之间必定存连通，由于取，设包含两个连通分支，得到子图的割点，则删去是”证明：“vwuvCwuGwuCwuGVwVuEVGEVGGGGGvEVGv,21222111217-2 路与回路路与回路图论与代数系统 图论的割点。是图必定不连通，故中这两个结点，在得到子图，则删去中某两个结点都通过”若连通图“GvGGvvG有向图的连通性和无向图的连通性有很大区别有向图的连通性和无向图的连通性有很大区别efgh可达性：可达性：在有向图中，从结点在有向图中，

29、从结点u到到v有一条路，称为有一条路，称为u可达可达v。可达性是否为等价关系？可达性是否为等价关系？（1）自反性，满足；）自反性，满足；（2）传递性，满足；）传递性，满足；（3）对称性，不满足。）对称性，不满足。如右图，如右图，e可达可达g，g不可达不可达e。所以其不是等价关系。所以其不是等价关系。距离：距离：u可达可达v，u和和v间的最短路的长度，记为间的最短路的长度，记为d若若u到到v是不可达，通常记是不可达，通常记d=图的直径：图的直径：D=max d7-2 路与回路路与回路图论与代数系统 图论路径的性质：路径的性质：（1）d0（2）d=0（3）d+dd（4）u，v彼此可达，彼此可达，d

30、不一定等于不一定等于d 图中图中d=1,d=2距离的概念对无向图同样适用，在无向图中，距离的概念对无向图同样适用，在无向图中，d=defgh7-2 路与回路路与回路图论与代数系统 图论强连通强连通 单侧连通单侧连通 弱连通弱连通下面介绍有向图的连通性的概念，若下面介绍有向图的连通性的概念，若G为简单有向图：为简单有向图： 4）单侧连通：单侧连通： 任何一对结点间，至少有一个任何一对结点间，至少有一个 结点到另一个结点是可达的；结点到另一个结点是可达的； 强连通：强连通： 任何一对结点互相可达；任何一对结点互相可达； 弱连通：弱连通： 略去边的方向，得到的无向图是连通的。略去边的方向，得到的无向

31、图是连通的。7-2 路与回路路与回路图论与代数系统 图论定理：定理： 一个有向图是强连通的，当且仅当一个有向图是强连通的，当且仅当G中一个回路，它中一个回路，它至少包含每个结点一次。至少包含每个结点一次。证明：证明：“” 如果如果G中有一个回路，至少包含每个结点一次，则中有一个回路，至少包含每个结点一次，则G中任意两个结点都是可达的，所以中任意两个结点都是可达的，所以G是强连通图。是强连通图。“=” 若不存在回路经过若不存在回路经过G中的所有结点，则必有一回路不包含某个中的所有结点，则必有一回路不包含某个结点结点v，且，且v与回路上的各个结点不是相互可达，矛盾！与回路上的各个结点不是相互可达，

32、矛盾！得证。得证。5）强分图：）强分图： 具有强连通性质的极大子图；具有强连通性质的极大子图； 单侧分图：单侧分图： 具有单侧连通性质的极大子图；具有单侧连通性质的极大子图； 弱分图：弱分图： 具有弱连通性质的极大子图。具有弱连通性质的极大子图。7-2 路与回路路与回路图论与代数系统 图论1 10 02 23 34 41 10 02 23 34 41 10 02 23 34 41 10 02 23 34 41 10 02 23 34 47-2 路与回路路与回路图论与代数系统 图论定理：定理： 在有向图在有向图G=中，它的每一个结点位于且只位中，它的每一个结点位于且只位 于一个强分图中。于一个强

33、分图中。 证明证明：（：（1）对于结点）对于结点v，设，设S是是G中所有与中所有与v相互可达的结点的相互可达的结点的集合，可知集合，可知S是是G的一个强分图，因此的一个强分图，因此G的每一个结点都位于一的每一个结点都位于一个强分图中；个强分图中；（2）若）若v位于两个不同的强分图位于两个不同的强分图S1，S2中，中，v与与S1，S2中的每个中的每个结点都相互可达，可知结点都相互可达，可知S1，S2中的所有结点通过中的所有结点通过v都相互可达。都相互可达。与强分图的定义矛盾，所以假设不成立。与强分图的定义矛盾，所以假设不成立。所以，有向图的每个结点都位于且仅位于一个强分图中。所以，有向图的每个结

34、点都位于且仅位于一个强分图中。7-2 路与回路路与回路图论与代数系统 图论设设G=是一个简单图，是一个简单图， 是是G的的n个结点，个结点，则则n阶方阵阶方阵A(G)=(aij)称为称为G的邻接矩阵。其中：的邻接矩阵。其中：,21nvvvV对于给定结合对于给定结合A上的关系上的关系R，可以用有向图来表示，而对于关，可以用有向图来表示，而对于关系图，又可以用一个矩阵表示，所以对于一般形式的图，也系图，又可以用一个矩阵表示，所以对于一般形式的图，也给出其矩阵表示。给出其矩阵表示。1、邻接矩阵、邻接矩阵jinadjvvadjvvajijiij或01adj表是邻接，表是邻接，nadj表示不邻接。表示不

35、邻接。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论简单图是无向图，邻接矩阵是对称的；简单图是无向图，邻接矩阵是对称的；简单图是有向图时，邻接矩阵不一定对称。简单图是有向图时，邻接矩阵不一定对称。例：例：v1v4v3v2v1v2v3v4v5v2v4v3v1G1 G2 G30010100100011100)(0001101011000010)(0100110101010110010111110)(321GAGAGA7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论2、置换等价：、置换等价： 把把n阶方阵阶方阵A的列和行分别作置换，得到新的的列和行分别作置换，得到新的 方阵方阵A，称，称A

36、与与A置换等价置换等价。置换等价是。置换等价是n阶布尔矩阵集合阶布尔矩阵集合 上的等价关系。上的等价关系。 对于有向图，按照结点的不同次序写出的邻接矩阵是置换等价对于有向图，按照结点的不同次序写出的邻接矩阵是置换等价的，因此可选取任意一个邻接矩阵作为该图的矩阵表示，通过的，因此可选取任意一个邻接矩阵作为该图的矩阵表示，通过此邻接矩阵来考虑图的一些特性。此邻接矩阵来考虑图的一些特性。在邻接矩阵在邻接矩阵A中，第中，第i行中值为行中值为1的元素个数等于的元素个数等于vi的出度；的出度； 第第j列中值为列中值为1的元素个数等于的元素个数等于vj的入度。的入度。零矩阵对应零图。零矩阵对应零图。7-3

37、图的矩阵表示图的矩阵表示图论与代数系统 图论思考：思考：如何计算图中长度为如何计算图中长度为k的路的数目？的路的数目？的回路的数目。的长度为到表示从的路的数目。的长度为到表示从。列的元素，记行，第中第正好等于的路的数目为：的长度为到。所以从结点即，反之若不存在路，即存在，则，如果路个结点的路，中间必定经过一的长度为到可知，对于每条从的路的数目？的长度为到问：如何计算从结点，邻接矩阵为，设其结点集合为对于简单图22)()()(2001122,)()(,)2()2()2(221221121iiiijiijnnijnkkjiknjinjijijikjikkjikjkikjikkjikjkikjiji

38、nnijnvvavvaaGAjiGAaaaaaaaavvaaaavvvaaaavvvvvvvvaGAvvvVG7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论定理。由归纳假设法可得下面列元素。行，第的第，即为的路的数目为：的长度为到的路，则类似可知从的长度为到联结的路，再的长度为到是由的路的数目，可以看作的长度为到考虑从jiGAaaavvvvvvvvnkkjikijjijkkiji31)2()3()(3213定理：定理： A(G)是图是图G的邻接矩阵，则的邻接矩阵，则(A(G)l中的中的i行，行，j列元素列元素aij(l)等于等于G中联结中联结vi与与vj的长度为的长度为l的路的数目。的路

39、的数目。在实际问题中，常需要考虑到结点之间是否存在路的问题。在实际问题中，常需要考虑到结点之间是否存在路的问题。可以通过计算可以通过计算A,A2,.,An,.，当发现某个，当发现某个Al的第的第i行行,第第j列不为列不为0，就表明就表明vi到到vj可达。可达。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论3、可达性矩阵：、可达性矩阵： G=是简单有向图，是简单有向图，|V|=n，定义，定义nxn矩阵矩阵不存在路到从存在路到从jijiijvvvvp01P=(pij)为可达性矩阵，其中为可达性矩阵，其中推论：推论： G有有n个结点，个结点， A是邻接矩阵，是邻接矩阵， ，bij为为Bn的的i

40、行，行，j列元素，若列元素，若bij0，则表明，则表明vi，vj中存在路。中存在路。nnAAAB2思考：思考：是否是否Al的寻找需要无穷继续下去呢？的寻找需要无穷继续下去呢？ 由前面的定理的推论可知，如果在由前面的定理的推论可知，如果在vi到到vj之间存在路，必定存在之间存在路，必定存在通路，所以通路，所以l只需计算到只需计算到n就可以了，因此有以下推论：就可以了，因此有以下推论：对于简单有向图的任意两个结点之间的可达性，也可以用矩阵对于简单有向图的任意两个结点之间的可达性，也可以用矩阵表示出来，即可达性矩阵表示出来，即可达性矩阵7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论将将Bn中不

41、为零的元素值改为中不为零的元素值改为1，就可得到可达性矩阵，就可得到可达性矩阵P。例例1： 设图设图G的邻接矩阵为的邻接矩阵为 ，求，求G的可达性矩阵。的可达性矩阵。0001101111000010A解：解：00101111101211002A11002122112110123A10123233322211214A212374776455324343214AAAAAB1111111111111111P可见，此图为连通图，且任一结点都有回路。可见，此图为连通图，且任一结点都有回路。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论在计算可达性矩阵时，由于不需要考虑两个结点间的路的数目，在计算可

42、达性矩阵时，由于不需要考虑两个结点间的路的数目，我们可只计算布尔矩阵我们可只计算布尔矩阵其中其中A(i)表示布尔运算下表示布尔运算下A的的i次方。次方。,)()2()1()()2()1(nnAAAPAAA故例例2： 图图G如图所示，求可达性矩阵如图所示，求可达性矩阵P。P1P3P2P4P5解：解：0001010000000010100000010A010000001000010100000100000010100000000101000000100001010000000010100000010)2(A7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论10000010000100000010

43、1000000010100000000101000000100100000010000101000001000)3(A0001010000100000100000010)4(A0100000010000101000001000)5(A1101011010110111101011010)5()4()3()2()1(AAAAAAP对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称的。对于无向图，邻接矩阵是一个对称矩阵，其可达性矩阵也是对称的。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论 上面我们介绍了图的邻接矩阵表示和可达性矩阵表示，可知上面我们介绍了图的邻接矩阵表示和可达性矩阵表示

44、，可知这两种表示方法都是跟结点相关的。这两种表示方法都是跟结点相关的。 还可以给出结点和边的关联矩阵，在给出点和边的关联关系还可以给出结点和边的关联矩阵，在给出点和边的关联关系时，时，假定图中无自回路假定图中无自回路。下面给出完全关联矩阵的概念。下面给出完全关联矩阵的概念。（a）G为无向图为无向图 设设 为为G的结点集，的结点集， 为为G的边集，称矩阵的边集，称矩阵M(G)=(mij)为为 完全关联矩阵完全关联矩阵，其中：，其中：,21pvvvV,21qeeeEjijiijevevm不关联若关联若014、完全关联矩阵：、完全关联矩阵：7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论v4v1

45、v2v3e1e2e3e4e5e6v5完全关联矩阵为：完全关联矩阵为：e1 e2 e3 e4 e5 e61 1 0 0 1 11 1 1 0 0 00 0 1 1 0 10 0 0 1 1 00 0 0 0 0 0v1v2v3v4v5例：例：从关联矩阵研究图形的性质：从关联矩阵研究图形的性质：（1）M（G）中每一列中有且仅有两个）中每一列中有且仅有两个1，对应图中每一边关联两，对应图中每一边关联两个结点。个结点。（2）每一行中元素的和为对应结点的度数。）每一行中元素的和为对应结点的度数。（3）一行中若元素全为）一行中若元素全为0，则其对应的结点为孤立结点。，则其对应的结点为孤立结点。7-3 图的

46、矩阵表示图的矩阵表示图论与代数系统 图论e1 e2 e3 e4 e5 e61 1 0 0 1 11 1 1 0 0 00 0 1 1 0 10 0 0 1 1 00 0 0 0 0 0v1v2v3v4v5（4）平行边对应的列相同。）平行边对应的列相同。（5）结点或边编序不同，对应）结点或边编序不同，对应完全关联矩阵只有行序、列序的完全关联矩阵只有行序、列序的差别。差别。类似，给出有向图的完全关联矩阵的定义：类似，给出有向图的完全关联矩阵的定义： （b）G为有向图为有向图 G=， ， pXq阶矩阵阶矩阵M(G)=(mij)为为G的完全关联矩阵，其中：的完全关联矩阵，其中：,21pvvvV,21q

47、eeeEjijijiijevevevm不关联若的终点是的起点是0117-3 图的矩阵表示图的矩阵表示图论与代数系统 图论v2v5v1v3v4e1e2e3e4e5e7e6e1 e2 e3 e4 e5 e6 e71 0 0 0 1 1 1-1 1 0 0 0 0 00 -1 1 0 0 -1 00 0 -1 1 0 0 -10 0 0 -1 -1 0 0v1v2v3v4v5例：例：关联矩阵：关联矩阵：有向图的完全关联矩阵的一些性质：有向图的完全关联矩阵的一些性质：（1）每一列中一个值为）每一列中一个值为1，一个为，一个为-1，对应图中的一条有向边。，对应图中的一条有向边。（2）把一行中的值为）把一

48、行中的值为1的元素相加，得到顶点的出度，把值为的元素相加，得到顶点的出度，把值为-1的元素相加，得到顶点的入度。的元素相加，得到顶点的入度。（3）一行中元素全为）一行中元素全为0，对应孤立结点。，对应孤立结点。（4）平行边对应的列相同。）平行边对应的列相同。（5）结点或边编序不同，对应完全关联矩阵只有行序、列序的）结点或边编序不同，对应完全关联矩阵只有行序、列序的差别。差别。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论行相加运算：行相加运算： 有向图：对应分量普通加法运算；有向图：对应分量普通加法运算； 无向图：对应分量模无向图：对应分量模2加法运算。加法运算。行相加相当于行相加相当于

49、G中对应结点的合并。中对应结点的合并。1jriraa，说明，说明vi和和vj中只有一个结点是边中只有一个结点是边er的端点，合并的端点，合并 后仍是后仍是er的端点。的端点。0jriraa，有两种情况：，有两种情况：a、vi，vj都不是都不是er的端点；的端点； b、vi，vj都是都是er的端点，合并后删去自回路。的端点，合并后删去自回路。若合并后完全关联矩阵中出现元素全为若合并后完全关联矩阵中出现元素全为0的列，表明对应的的列，表明对应的边消失。边消失。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论v1v2v3v4v5e1e2e3e5e4e6e7v4,5v1v2v3e7e6e5e4e3

50、e2(a)(b)图图(a)合并合并v4，v5后得到图后得到图(b)，对应关联矩阵如下：，对应关联矩阵如下：e1 e2 e3 e4 e5 e6 e70 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 01 1 0 0 0 0 01 0 1 0 1 0 1v1v2v3v4v5e1 e2 e3 e4 e5 e6 e70 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 00 1 1 0 1 0 1v1v2v3v4,5M(G)：M(G)：例：例：7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论图图(a)合并合并v2，v3且删去自回路后得到图且删去自回路

51、后得到图(b)，对应，对应关联矩阵如下：关联矩阵如下：例：例：v2v3e3v1v6v5v4e1e4e5e6e2e7e8e9v1v4v5v6v2,3e1e2e7e8e9e4e15e6(a)(b)e1 e2 e3 e4 e5 e6 e7 e8 e91 1 0 0 0 0 0 0 0-1 0 1 0 0 0 1 0 00 0 -1 1 0 0 0 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 10 0 0 -1 -1 0 0 0 0v1v2v3v4v5v6e1 e2 e3 e4 e5 e6 e7 e8 e9v1v2,3v4v5v6M(G)：M(G)：e1 e2 e3

52、 e4 e5 e6 e7 e8 e91 1 0 0 0 0 0 0 0-1 0 1 0 0 0 1 0 00 0 -1 1 0 0 0 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 -10 0 0 -1 -1 0 0 0 0v1v2v3v4v5v61 1 0 0 0 0 0 0 0-1 0 0 1 0 0 1 -1 10 -1 0 0 0 1 -1 1 00 0 0 0 1 -1 0 0 -10 0 0 -1 -1 0 0 0 07-3 图的矩阵表示图的矩阵表示图论与代数系统 图论例：例：计算右图对应的完全关联矩阵的秩。计算右图对应的完全关联矩阵的秩。v1v2

53、v3v4v5e1e2e3e5e4e6e7e1 e2 e3 e4 e5 e6 e70 0 0 0 0 1 10 0 0 1 1 1 00 1 1 1 0 0 01 1 0 0 0 0 01 0 1 0 1 0 1v1v2v3v4v51010110110000000011100111000000001110101011100000000111001110000000011)()5()1()1)(4(行对调GM7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论1100000110000001101000001110000001110101001100000011010000011100000011

54、1011000110000001110000001110000001110101101100000011100000011100000011)5()3()4)(3()5()2()3)(2(列对凋行对调7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论415)(0000000100100000111000100110000001110010001001000001110001001100000011)5()4()6)(4(GMrank列对凋7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论有以下定理：有以下定理：定理：定理： G为连通图，有为连通图，有r个结点，则其完全关联矩阵个结点，则其完

55、全关联矩阵M(G)的秩为的秩为r-1，即，即rank M(G)=r-1。行，得，将第一行加到第行为）首列仅第一行和第（第一行，则行成为，调整行使得第和的端点为，）的第一列对应边（设时成立）证明结点数为（个结点，则有时成立。即连通图）假设（，显然；，）（学归纳法证明：对无向图，用数jjGMivveeGMrrGMrankrGrrji132)(1122117-3 图的矩阵表示图的矩阵表示图论与代数系统 图论1)(1)()(2)()(0)(011111111rGMrankGMrankGMrankrGMrankGGvvGGGGMGMGMji也是连通图，所以是连通图，则得到的，和合并是的完全关联矩阵，而是

56、，）（ 推论：推论： G有有r个结点，个结点，w个极大连通子图，则图个极大连通子图，则图G的完全关联的完全关联矩阵的秩为矩阵的秩为r-w。 可用之求图的最大连通子图数目。可用之求图的最大连通子图数目。7-3 图的矩阵表示图的矩阵表示图论与代数系统 图论7-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图欧拉提出著名的哥尼斯堡七桥问题：环城欧拉提出著名的哥尼斯堡七桥问题：环城“遍游遍游”，即从某地出发，每座桥都仅走一遍，即从某地出发，每座桥都仅走一遍，最后回到起点。最后回到起点。欧拉给出一个简单的准则，说明欧拉给出一个简单的准则，说明哥尼斯堡七桥问题是不能解的。哥尼斯堡七桥问题是不能解的。下面给出欧拉路

57、，欧拉回路，下面给出欧拉路，欧拉回路，欧拉图，半欧拉图的概念。欧拉图，半欧拉图的概念。ADBC图论与代数系统 图论给定无孤立结点图给定无孤立结点图G， 欧拉路：欧拉路： 通过图中每边一次且仅一次的路；通过图中每边一次且仅一次的路；欧拉回路：欧拉回路： 通过图中每边一次且仅一次的回路；通过图中每边一次且仅一次的回路；半欧拉图：半欧拉图：存在欧拉路的图；存在欧拉路的图；欧拉图：欧拉图： 具有欧拉回路的图。具有欧拉回路的图。 对于半欧拉图或者欧拉图，由于其经过每条边，必定会经过对于半欧拉图或者欧拉图，由于其经过每条边，必定会经过所有的点，因此必定是一个连通图。所有的点，因此必定是一个连通图。 除了是

58、连通图之外，对于图中的结点的度数，也可以得到较除了是连通图之外，对于图中的结点的度数，也可以得到较好的结论。好的结论。 有下面定理及推论。有下面定理及推论。7-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图图论与代数系统 图论 定理：定理： 无向图无向图G具有一条欧拉路，当且仅当具有一条欧拉路，当且仅当G是连通的，且是连通的，且有零个或两个奇数度结点。有零个或两个奇数度结点。度结点。中有零个或者两个奇数所以为奇数。都，则为偶数，若，则对于端点若必定为偶数。，度数出现一次，关联两条边，不是端点，在欧拉路中假设但是边不重复。结点可以重复出现，具有欧拉路，设为证明：必要性：Gvdvdvvvdvvvvvee

59、vevevevGkkkiikkiii)()()(,00001221107-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图图论与代数系统 图论。点停下，得到一条迹一个奇数度结连通，必定可以到达另。由于此下去，每边仅取一次，如到再经关联边为偶数，可由，若进入经过关联边出发造一条迹，从从其中一个结点开始构）有两个奇数度结点，（：数度结点，构造欧拉路连通，有零个或两个奇若充分性：LGvevvvevG2211110)deg(17-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图图论与代数系统 图论继续。，则得到欧拉路，否则合起来为图和如果。前面方法，得到闭迹中某个结点重合，重复少有一个结点与中至偶数，且中每个结点的度

60、数仍为，则得到子图否则，去掉就是欧拉路。中的所有边，则包含了若。闭迹回到此结点，得到一条述方法必定可以从任一结点出发，用上中没有奇数度结点，则）若（GLLLLGGGLLGLLG2121111127-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图图论与代数系统 图论推论：无向图推论：无向图G具有一条欧拉回路，当且仅当具有一条欧拉回路，当且仅当G是连通的，且是连通的，且所有结点的度数全为偶数。所有结点的度数全为偶数。半欧拉图半欧拉图 欧拉图欧拉图7-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图图论与代数系统 图论ADBC可见可见deg(A)=5，deg(B)=deg(C)=deg(D)=3，故在图中不存在欧