离散数学 7-3 图的矩阵表示

1、Discrete Mathematics 山东科技大学山东科技大学 信息科学与工程学院信息科学与工程学院 图的定义图的定义 点的度数点的度数 特殊的图特殊的图 图同构图同构 7-1 图的基本概念图的基本概念 三、特殊的图三、特殊的图 1、多重图、多重图 定义定义7-1.4：含有平行边的图称为多重图。：含有平行边的图称为多重图。 2、简单图：不含平行边和环的图称为简单图。、简单图：不含平行边和环的图称为简单图。 3、完全图、完全图 定义定义7-1.5：简单图：简单图G=中，若每一对结点中，若每一对结点 间均有边相连，则称该图为完全图。间均有边相连，则称该图为完全图。 有有n个结点的无向完全图记为

2、个结点的无向完全图记为Kn。 无向完全图：每一条边都是无向边无向完全图：每一条边都是无向边 不含有平行边和环不含有平行边和环 每一对结点间都有边相连每一对结点间都有边相连 如果在如果在Kn中，对每一条边任意确定一个方向，则称中，对每一条边任意确定一个方向，则称 该图为该图为n个结点的有向完全图。个结点的有向完全图。 显然它的边数为显然它的边数为n(n-1)/2。 定理定理7-1.4图中图中, n个结点的无向完全图个结点的无向完全图Kn 的边数为的边数为n(n-1)/2。 证明：证明： n个结点中任取两个结点的组合数为个结点中任取两个结点的组合数为 Cn2 = = n(n-1)/2 故的边数为故

3、的边数为 |E| = n(n-1)/2 5、相对于完全图的补图、相对于完全图的补图 定义定义7-1.6：给定一个简单图：给定一个简单图G，由，由G中所有结点和所有能使中所有结点和所有能使 G成为完全图的添加边组成的图，称为成为完全图的添加边组成的图，称为G的相对于完全图的的相对于完全图的 补图，或简称为补图，或简称为G的补图，记为的补图，记为 G。即。即G=， G=，其中，其中E2=(u，v)u，v V， ，(u，v) E1 。 。 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 (a)完全图完全图K5 (b)图图G (c)图图G的补图的补图G 6、子

4、图、子图 定义定义7-1.7：设图：设图G=，如果有图，如果有图G=，且，且E E， V V，则称，则称G为为G的子图。的子图。 当当V=V时，则称时，则称G为 为G的生成子图。的生成子图。 例如，下图，例如，下图， 图图(b)的的G和图和图(c)的的G 都是图都是图(a)的的K5的子图。的子图。 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 (a)完全图完全图K5 (b)图图G (c)图图G的补图的补图G 7、相对于图相对于图G的补图 的补图 定义定义7-1.8：设设G=是是G=的子图，若的子图，若给定另一给定另一 个图个图G”=使得使得E”=E-

5、E，且，且V”中仅包含中仅包含E”的边所关联的边所关联 的结点，则称的结点，则称G”是子图是子图G相对于图相对于图G的补图。的补图。 例如，上图例如，上图(b)的的G是图是图(c)的的G 相对于图相对于图(a)的的K5的补图。的补图。 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 (a)完全图完全图K5 (b)图图G (c)图图G的补图的补图G 图的定义图的定义 点的度数点的度数 特殊的图特殊的图 图同构图同构 7-1 图的基本概念图的基本概念 四、同构四、同构 定义定义7-1.9：设图：设图G=及图及图G=， 如果存在一一对应的映射如果存在一一对应

6、的映射g：ViVi 且 且e=(vi，vj) (或 或)是是G的一条边，当且仅当的一条边，当且仅当e=(g(vi)， ， g(vj)(或或)是是G的一条边，的一条边， 则称则称G与与G同构，记作同构，记作G G。 两图同构的一些必要条件：两图同构的一些必要条件： 1.结点数目相同；结点数目相同； 2.边数相等；边数相等； 3.度数相同的结点数目相等。度数相同的结点数目相等。 以上几个条件不是两个图同构的充分条件。以上几个条件不是两个图同构的充分条件。 见见279页图页图7-1.10 同构必须是结点和边分别存在一一对应。同构必须是结点和边分别存在一一对应。 练习 279页（3） 对应结点度数不同

7、，所以两图不同构。对应结点度数不同，所以两图不同构。 作业 279页:(5)（6） 7-2 路与回路路与回路 在现实世界中，常常要考虑这样的问题：如在现实世界中，常常要考虑这样的问题：如 何从一个图中的给定结点出发，沿着一些边连续何从一个图中的给定结点出发，沿着一些边连续 移动而达到另一指定结点，这种依次由点和边组移动而达到另一指定结点，这种依次由点和边组 成的序列，就形成了路的概念。成的序列，就形成了路的概念。 学习本节要熟悉如下术语(22个)： 路、路的长度、迹、回路、通路、圈、 连通、连通分支、点割集、连通图、割点、 点连通度、边割集、边连通度、割边、可达、 单侧连通、 强连通、强分图、

8、弱连通、弱分图、 单侧分图 掌握5个定理，一个推论。 路路 无向图的连通性无向图的连通性 有向图的连通性有向图的连通性 7-2 路与回路路与回路 一、路一、路 定义定义7-2.1图图G=,设设 v0,v1,vn V， e1,en E, 其中其中ei是关联于结点是关联于结点vi-1,vi的边，交替序列的边，交替序列v0e1v1e2envn称为结点称为结点 v0到到vn的的路路（Pseudo path） 。 v0和和vn分别称为路的分别称为路的起点起点和和终点终点， 边的数目边的数目n称作路的称作路的长度长度。 当当v0=vn时，这条路称作时，这条路称作回路回路（closed walk） 。 若一

9、条路中所有的边若一条路中所有的边e1, , en均不相同均不相同,称作称作迹迹（walk） 。 若一条路中所有的结点若一条路中所有的结点v0, v1, vn均不相同均不相同,称作称作通路通路(Path) 。 闭的通路闭的通路,即除即除v0=vn之外，其余结点均不相同的路，称作之外，其余结点均不相同的路，称作圈圈 （circuit） 。 例如例如 路：路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：迹：v5e8v4e5v2e6v5e7v3e4v2 通路：通路：v4e8v5e6v2e1v1e2v3 圈：圈：v2e1v1e2v3e7v5e6v2 在简单图中一条路在简单图中一条路v0e1

10、v1e2envn，由它的结，由它的结 点序列点序列v0，v1，vn确定，所以简单图的路，确定，所以简单图的路， 可由其结点序列表示。可由其结点序列表示。 在有向图中，结点数大于在有向图中，结点数大于1的一条路亦可由边的一条路亦可由边 序列序列e1e2en表示。表示。 定理定理7-2.1n个结点的图中，如果从结个结点的图中，如果从结 点点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在必存在 一条不多于一条不多于n-1条边的路。条边的路。 证明思路：多于证明思路：多于n-1条边的路中必有重复出现的结条边的路中必有重复出现的结 点，反复删去夹在两个重复结点之间

11、的边之后，剩余点，反复删去夹在两个重复结点之间的边之后，剩余 的边数不会超过的边数不会超过n-1条边。条边。 推论推论 n个结点的图中，如果从结点个结点的图中，如果从结点vj 到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在一必存在一 条边数小于条边数小于n的通路。的通路。 定理定理7-2.1的证明的证明 如果从结点如果从结点vj到到vk存在一条路，该路上的结点存在一条路，该路上的结点 序列是序列是vjvivk，如果在这条中有，如果在这条中有l条边，则序列条边，则序列 中必有中必有 l+1个结点，若个结点，若ln-1，则必有结点，则必有结点vs，它在，它在 序

12、列中不止出现一次，即必有结点序列序列中不止出现一次，即必有结点序列 vjvsvsvk，在路中去掉从，在路中去掉从vs到到vs的这些边，仍的这些边，仍 是是vj到到vk的一条路，但此路比原来的路边数要少，的一条路，但此路比原来的路边数要少， 如此重复进行下去，必可得到一条从如此重复进行下去，必可得到一条从vj到到vk的不多的不多 于于n-1条边的路。条边的路。 如在图如在图7-2.1中有中有5个结点。个结点。 v1到到v3的一条路为：的一条路为： v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有此路中有6条边，去掉条边，去掉e3有路有路 v1e2v3e4v2e6v5e7v3 有有4

13、条边。条边。 v1到到v3最短的路为最短的路为v1e2v3 路路 无向图的连通性无向图的连通性 有向图的连通性有向图的连通性 7-2 路与回路路与回路 二、无向图的连通性：二、无向图的连通性： 1、连通、连通 定义定义7-2.2图图G中，如果从结点中，如果从结点u和结点和结点v 之间若存在一条路，则称结点之间若存在一条路，则称结点u和结点和结点v是是连通的连通的 （connected） 。 结点之间的连通性是结点集结点之间的连通性是结点集V上的等价关系，对上的等价关系，对 应该等价关系，必可将作出一个划分，把应该等价关系，必可将作出一个划分，把V分成非空分成非空 子集子集V1, V2, , V

14、m,使得两个结点使得两个结点vj和和vk是连通的，当是连通的，当 且仅当它们属于同一个且仅当它们属于同一个Vi 。把子图。把子图G(V1) , G(V2) , , G(Vm)称为图称为图G的的连通分支连通分支（connected components）, 图图G的连通分支数记为的连通分支数记为W(G) 。 2、连通图、连通图 定义定义7-2.3：若图：若图G只有一个连通分支，则称只有一个连通分支，则称 G是连通图。是连通图。 显然在连通图中，任意两个结点之间必是连显然在连通图中，任意两个结点之间必是连 通的。通的。 对于连通图，常常由于删除了图中的点或边，而影响了对于连通图，常常由于删除了图中

15、的点或边，而影响了 图的连通性。图的连通性。 结点结点v，即是把即是把v以及与以及与v关关 联的边都删除。联的边都删除。 ：，即是把该边删除。，即是把该边删除。 v3 v2 v1 v6 v4 (a) v5 v5 v1 v2 v3v6 v4 (c) e v3 v2 v6 v4 (b) v5 e 二、无向图的连通性二、无向图的连通性 1、连通、连通 定义定义7-2.2图图G中，如果从结点中，如果从结点u和结点和结点v 之间若存在一条路，则称结点之间若存在一条路，则称结点u和结点和结点v是是连通的连通的。 2、连通图、连通图 若图若图G只有一个连通分支，则称只有一个连通分支，则称G是连通图。 是连通

16、图。 对于连通图，常常由于删除了图中的点或边，而影响了对于连通图，常常由于删除了图中的点或边，而影响了 图的连通性。图的连通性。 结点结点v，即是把即是把v以及与以及与v关关 联的边都删除。联的边都删除。 ：，即是把该边删除。，即是把该边删除。 v3 v2 v1 v6 v4 (a) v5 v5 v1 v2 v3v6 v4 (c) e v3 v2 v6 v4 (b) v5 e 3、割点、割点 定义定义7-2.4 图图G =是是连通图连通图,若有结点集若有结点集 V1 V,使图使图G中中V1 V1 连通图连通图,则称则称V1是是G的一个的一个点割集点割集(cut-set of nodes) 。若某

17、一个点构成一个点割集，则称该点若某一个点构成一个点割集，则称该点 为为割点割点。 s a b c d a b c d ba n点连通度：是为了产生一个不连通图需要删去的 点连通度：是为了产生一个不连通图需要删去的点点的最的最 少数目，也称为连通度，记为少数目，也称为连通度，记为k(G) 。 即即k(G)=min|V1| V1是是G的点割集的点割集 称为图称为图G的的点连通度点连通度 (1)若若G是平凡图，则是平凡图，则V1= ， ，k(G)=0 (2)k(Kn)=n-1 (3)若图存在割点，则若图存在割点，则k(G)=1 (4)规定非连通图的连通度规定非连通图的连通度k(G)=0 v5 v1

18、v2 v3 v4 v5 v1 v3 v4 点割集点割集V1=v2 4、割边、割边 定义定义7-2.5 图图G =是是连通图连通图,若有边若有边 集集E1 E E，使图，使图 G中中E1 E1 连通图，则称连通图，则称E1是是G的一个的一个边割集边割集 (cut-set of edges) 。若某一条边就构成一个边割集，。若某一条边就构成一个边割集， 则称该边为则称该边为割边割边或或桥桥。 割边割边e使图使图G满足满足W(G-e)W(G) 。 连通度连通度(edge-connectivity) (G)定义定义：非平凡图：非平凡图 的边连通度为的边连通度为 (G)=min |E1| | E1是是G

19、 G的边割集的边割集 边连通度边连通度 (G)是为了产生一个不连通图需要删去是为了产生一个不连通图需要删去 的边的最少数目。的边的最少数目。 (1)若若G是平凡图则是平凡图则E1= ，(G)=0 (2)若若G存在割边，则存在割边，则 (G)=1， ， (3)规定非连通图的边连通度为规定非连通图的边连通度为 (G)=0 5、定理定理7-2.2 图图G,有有k(G) (G)(G) 。 在在7-2.2节定义了图的最小度：节定义了图的最小度： (G)=min(deg(v)，v V) 下面的定理给出了下面的定理给出了点连通度点连通度k(G) 、边连通度边连通度 (G)和和图的图的 最小度最小度 (G)之

20、间的关系。之间的关系。 k(G)=?,(G)=?,(G)=? s a b c d 证明：证明： 若若G不连通，则不连通，则k(G)= (G)=0，故上式成立。 ，故上式成立。 若若G连通，连通，可分两步证明上式也成立：可分两步证明上式也成立： 1)先证明先证明 (G) (G)： 如果如果G是平凡图，则是平凡图，则 (G)=0 (G)， ， 若若G是非平凡图，则因每一结点的所有关联边必含一是非平凡图，则因每一结点的所有关联边必含一 个边割集，个边割集，(因因 (G)=mindeg(v)|v V，设，设u V使的使的 deg(u)=(G)，与，与u相关联的相关联的 条边必包含一个边割集，条边必包含

21、一个边割集， 至少这至少这 条边删除使图不连通。条边删除使图不连通。)故故 (G) (G)。 5、定理定理7-2.2 图图G,有有 k(G) (G)(G) 。 2)再证再证k(G) (G)： (a)设设 (G)=1，即，即G有一割边，显然这时 有一割边，显然这时k(G)=1，上式成立。，上式成立。 (b)设设 (G)2，则必可删去某，则必可删去某 (G)条边，使 条边，使G不连通，而删去不连通，而删去 其中其中 (G)-1条边，它仍是连通的，且有一条桥条边，它仍是连通的，且有一条桥e=(u，v)。对。对 (G)-1条边中的每一条边都选取一个不同于条边中的每一条边都选取一个不同于u、v的端点，把

22、的端点，把 这些端点删去则必至少删去这些端点删去则必至少删去 (G)-1条边。条边。 若这样产生的图是不连通的，则若这样产生的图是不连通的，则k(G) (G)-1 (G)； 若这样产生的图是连通的，则若这样产生的图是连通的，则e仍是桥，此时再删去仍是桥，此时再删去u或或v就必就必 产生一个不连通图，故产生一个不连通图，故k(G) (G)。 由由1)和和2)得得k(G) (G) (G)。 u v 6.定理定理7-2.3 无向图无向图G的结点的结点v是割点的充分必要条是割点的充分必要条 件是存在两个结点件是存在两个结点u和和w,使得结点使得结点u和和w的每一条路都通过的每一条路都通过v 。 证明思

23、路：证明思路： 1) 先证先证:v是割点是割点存在结点存在结点u和和w的每条路都通过的每条路都通过v 若若v是连通图是连通图G=割点，设删去割点，设删去v得到的子图得到的子图G, 则则G至少包至少包 含两个连通分支含两个连通分支G1=和和G2= 。任取。任取u V1，w V2， 因为因为G是连通的，故在是连通的，故在G中必有一条连结中必有一条连结u和和w的路的路C，但，但u和和w在在G 中属于两个不同的连通分支，故中属于两个不同的连通分支，故u和和w必不连通，因此必不连通，因此C必须通过必须通过v， 故故u和和w之间的任意一条路都通过之间的任意一条路都通过v 。 2)再证再证:存在结点存在结点

24、u和和w的每条路都通过的每条路都通过v v是割点是割点 若连通图若连通图G中的某两个结点中的某两个结点u和和w的每一条路都通过的每一条路都通过v，则删去，则删去v 得到子图得到子图G，在，在G中这两个结点中这两个结点u和和w必然不连通，故必然不连通，故v是图是图G的的 割点。割点。 三、有向图的连通性：三、有向图的连通性： 1、可达：、可达： n在无向图 在无向图G中，从结点中，从结点u到到v若存在一条路，则称结若存在一条路，则称结 点点u到结点到结点v是可达的。是可达的。 有向图的可达性：有向图的可达性：图图G=, 从结点从结点u u和到结点和到结点v v有一条路有一条路,称为从称为从u u

25、可达可达v v。 有向图上的有向图上的可达性可达性(accesible),是结点集上的二元关是结点集上的二元关 系，它是自反的和传递的，但是一般来说不是对称系，它是自反的和传递的，但是一般来说不是对称 的。故可达性不是等价关系。的。故可达性不是等价关系。 如果如果u可达可达v，它们之间可能不止一条路，在所有这，它们之间可能不止一条路，在所有这 些路中，最短路的长度称为些路中，最短路的长度称为u和和v之间的距离（或短程之间的距离（或短程 线），记作线），记作d，它满足下列性质：，它满足下列性质： nd0 nd =0 nd + d d 把把D=max d, u,vV称作图的直径。称作图的直径。 n

26、 如果从如果从u到到v是不可达的，则通常写成是不可达的，则通常写成 d = n 注意：当注意：当u可达可达v，且，且v也可达也可达u时，时， d 不一定等不一定等 于于d 2、定义定义7-2.6 图图G中，中，任何一对结点任何一对结点间，至少有一个间，至少有一个 结点到另一个结点是可达的，则称这个图是结点到另一个结点是可达的，则称这个图是单侧连通单侧连通 的的 。 n 如果对于图 如果对于图G中的中的任何一对结点两者之间任何一对结点两者之间是相互可是相互可 达的，则称这个图是达的，则称这个图是强连通强连通的。的。 n 如果在图 如果在图G中略去边的方向，将它看成无向图后，中略去边的方向，将它看

27、成无向图后， 图是连通的，则称该图为图是连通的，则称该图为弱连通弱连通的。的。 显然，强连通图显然，强连通图单侧连通图单侧连通图弱连通图。而逆推均弱连通图。而逆推均 不成立。不成立。 v2 v3 v4 v1 (a)强连通强连通 v2 v3 v4 v1 (b)单侧连通单侧连通 v2 v3 v4 v1 (c)弱连通弱连通 证明：充分性：如证明：充分性：如G中有一条有向回路，经过每一点至中有一条有向回路，经过每一点至 少一次，则少一次，则G中任意两点中任意两点u、vV，u和和v都是相互可达都是相互可达 的，则的，则G是强连通图。是强连通图。 3、定理、定理7-2.4：一个有向图是强连通的充分必要条：

28、一个有向图是强连通的充分必要条 件是件是G有一个回路，它至少包含每个结点一次。有一个回路，它至少包含每个结点一次。 必要性：任取必要性：任取u，vV，图，图G是强连通图，则是强连通图，则uv有有有有 向路，向路，vu也有有向路，则也有有向路，则uvu构成了一个有向回构成了一个有向回 路，如果该有向回路没有包含路，如果该有向回路没有包含w，而，而uw，wu均有均有 有向路，则有向路，则uvuwu又是一个有向回路，一直下又是一个有向回路，一直下 去可以将图中所有的点均包含进去。去可以将图中所有的点均包含进去。 4、定义、定义7-2.7：在简单有向图中，：在简单有向图中， n具有 具有强连通强连通性

29、质的性质的最大最大子图子图，称为强分图；，称为强分图； n具有单侧连通性质的最大子图，称为单侧分图； 具有单侧连通性质的最大子图，称为单侧分图； n具有弱连通性质的最大子图，称为弱分图。 具有弱连通性质的最大子图，称为弱分图。 v4 v2 v3 v1 v5 定理定理7-2.5 G= 证明思路：证明思路： 1) 1)先证先证: : 2)2)再证再证: : 作业 n286287： (2)(5)(8) 7-3 图的矩阵表示图的矩阵表示 n图 图G=的图形表示方法：的图形表示方法： n 使用图形表示法很容易把图的结构展现出来，而且这使用图形表示法很容易把图的结构展现出来，而且这 种表示直观明了。种表示

30、直观明了。 n 但这只在结点和边但这只在结点和边(或弧或弧)的数目相当小的情况下才是的数目相当小的情况下才是 可行的。显然这限制了图的利用。可行的。显然这限制了图的利用。 n图的另一种表示法 图的另一种表示法图的矩阵表示法：图的矩阵表示法： n 克服了图形表示法的不足克服了图形表示法的不足 n 可以充分利用现代工具电子计算机，以达到研究图的可以充分利用现代工具电子计算机，以达到研究图的 目的。目的。 一、邻接矩阵一、邻接矩阵 定义定义7-3.1 G= V=v1,v2,vn (adjacency matrix) vi adj vj vi nadj vj 或或 i=j adjnadj 0 1 0

31、0 A(G1)= 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 A(G)= 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 无向图的邻接矩阵是对 称矩阵，有向图的邻接 矩阵不一定是对称的。 0 0 1 1 1 0 0 0 A(G1)= 1 1 0 1 0 1 0 0 图G2的邻接矩阵是将 图G1的邻接矩阵第一、 二行对调，第一、二列 对调得到的。 0 1 0 0 A(G1)= 0 0 1 1 1 1 0 1 1 0 0 0 n对于给定图 对于给定图G，显然不会因结点编序不同而使其，显然不会因结点编序不同而使其 结构发生任何变化，即图的结点所

32、有不同的编序结构发生任何变化，即图的结点所有不同的编序 实际上仍表示同一个图。实际上仍表示同一个图。 n换句话说，这些结点的不同编序的图都是同构的， 换句话说，这些结点的不同编序的图都是同构的， 并且它们的邻接矩阵都是相似的。并且它们的邻接矩阵都是相似的。 n于是图 于是图G与与H同构同构存在置换矩阵存在置换矩阵P，使，使 A(H)=P-1A(G)P n今后将略去这种由于 今后将略去这种由于V中结点编序而引起邻接矩中结点编序而引起邻接矩 阵的任意性，而取该图的任一个邻接矩阵作为该阵的任意性，而取该图的任一个邻接矩阵作为该 图的矩阵表示。图的矩阵表示。 n若邻接矩阵的元素全为零，则其对应的图是

33、若邻接矩阵的元素全为零，则其对应的图是 零图；零图； n若 若(无向图无向图)邻接矩阵的元素除主对角线元素邻接矩阵的元素除主对角线元素 外全为外全为1，则其对应的图是简单完全图。，则其对应的图是简单完全图。 n(有向图 有向图)邻接矩阵的元素除主对角线元素外邻接矩阵的元素除主对角线元素外 全为全为1，则其对应的图是强连通图。，则其对应的图是强连通图。 邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质： n当给定的简单图是无向图时，邻接矩阵是 当给定的简单图是无向图时，邻接矩阵是 对称矩阵；对称矩阵； n若给定任何对称矩阵 若给定任何对称矩阵A，显然可以唯一地作，显然可以唯一地作

34、出以出以A为其邻接矩阵的简单图为其邻接矩阵的简单图G。 n所有 所有n个结点的不同编序的简单图的集合与个结点的不同编序的简单图的集合与 所有所有n阶对称矩阵的集合可建立一一对应。阶对称矩阵的集合可建立一一对应。 邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质： n当给定的图是简单有向图时，其邻接矩阵并非 当给定的图是简单有向图时，其邻接矩阵并非 一定是对称矩阵，但所有一定是对称矩阵，但所有n个结点的不同编序的个结点的不同编序的 简单图的集合，与所有简单图的集合，与所有n阶邻接矩阵的集合亦可阶邻接矩阵的集合亦可 建立一一对应。建立一一对应。 n不仅如此，通过对矩阵元素的一些计算还

35、可以 不仅如此，通过对矩阵元素的一些计算还可以 得到对应图的某些数量的特征。得到对应图的某些数量的特征。 邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质： 在给定简单有向图的邻接矩阵中，在给定简单有向图的邻接矩阵中，第第i行元素行元素 是由结点是由结点vi出发的弧所确定，故第出发的弧所确定，故第i行中值为行中值为1的的 元素数目等于结点元素数目等于结点vi的出度。同理，第的出度。同理，第j列中值为列中值为 1的元素数目等于结点的元素数目等于结点vj的入度的入度。即。即d+(vi)= 和和d-(vj)= 。 1 n ik k a 1 n kj k a 利用邻接矩阵计算结点的入度和

36、出度利用邻接矩阵计算结点的入度和出度 利用邻接矩阵计算长度为利用邻接矩阵计算长度为k的路径条数的路径条数: l l 共共l个个 n 其中其中 k=1k=1 . . 例 290页例1 定理定理7-3.1 G= 证明思路：对证明思路：对 用数学归纳法证明。用数学归纳法证明。 1) 1) 当当时时: : 2) 2)设命题对设命题对 成立，即：成立，即： 3) 3)现证现证时也成立。即时也成立。即 n k=1 k=1 对对k k求和即得结论。求和即得结论。 vkvivj 长度长度=1 长度长度=l P300 (1)求出图7-3.9中有向图的邻接矩阵A，找出从v1到v4 长度为2和4的路，用计算A2，A

37、3，A4来验证这结论。 解 A= 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 2 0 1 0 2 1 1 0 0 1 1 A2= 0 2 1 2 0 2 2 2 0 2 1 2 0 2 0 1 A3= 0 4 2 3 0 4 1 3 0 4 2 3 0 2 2 2 A4= 从v1到v4长度为2的路为v1 v2 v4 从v1到v4长度为4的路有：v1 v2 v4 v2 v4 v1 v2 v3 v2 v4 v1 v4 v2 4 v3 v4 v2 v3 v1 v4 在一些实际问题中，有时要判定图中结点在一些实际问题中，有时要判定图中结点vi到结到结 点点vj是

38、否可达，或者说是否可达，或者说vi到到vj是否存在路。如果利用是否存在路。如果利用 图图G的邻接矩阵的邻接矩阵A，则可计算，则可计算A2，A3，An，。 当发现其中某个当发现其中某个Al的的aij(l)1，就表明，就表明vi可达可达vj或或vi到到vj 存在一条路。但这种计算繁琐量大，又不知计算存在一条路。但这种计算繁琐量大，又不知计算Al 到何时为止。到何时为止。 根据定理根据定理7-2.1的推论可知，如果有向图的推论可知，如果有向图G有 有n 个结点，个结点， vi到到vj有一条路，则必然有一条长度不大有一条路，则必然有一条长度不大 于于n的通路，因此，只需考虑的通路，因此，只需考虑aij

39、(l)就可以了，其中就可以了，其中 1ln。即只要计算。即只要计算Bn=A+A2+A3+An。 如果关心的是结点间可达性或结点间是否有路，如果关心的是结点间可达性或结点间是否有路， 至于结点间的路存在多少条及长度是多少无关紧要，至于结点间的路存在多少条及长度是多少无关紧要， 那么便可用可达矩阵来表示结点间可达性。那么便可用可达矩阵来表示结点间可达性。 定理定理7-2.1n个结点的图中，如果从结个结点的图中，如果从结 点点vj到结点到结点vk存在一条路，则从结点存在一条路，则从结点vj到结点到结点vk必存在必存在 一条不多于一条不多于n-1条边的路。条边的路。 二、可达矩阵二、可达矩阵 定义定义

40、7-3.2 G= V=v1,v2,vn vi vj vi vj P124:Warshall算法求取关系算法求取关系R的传递闭包的传递闭包R I = 1，2，3， ，n 第第i步：如果步：如果 A j，i=1，则将第，则将第i行加到第行加到第j行。行。 Warshall算法求取可达矩阵算法求取可达矩阵P 三、关联矩阵三、关联矩阵 1、无向图的关联矩阵、无向图的关联矩阵 定义定义7-3.3图图G=,设设 v1, v2, vp V, e1, eq E, 称称pq阶矩阵阶矩阵M (G)=(mij)p q 为图 为图G的的 （incidence matrix）。其中）。其中: vi ej vi ej m

41、ij= 举例举例 v1v2 v3v4 e1 e2 e3 e4 e5 e6 e1e2e3e4e5e6 v1110011 v2111000 v3001101 v4000110 v5000000 v5 无向图的关联矩阵无向图的关联矩阵 e1e2e3e4e5e6 v1110011 v2111000 v3001101 v4000110 v5000000 关联矩阵的运算关联矩阵的运算 无向图无向图G的两行相加定义为：第的两行相加定义为：第i行第行第j行的行的 对应元素对应元素模模2相加相加；相当于删除结点；相当于删除结点vi与结与结 点点vj之间的关联边，合并结点之间的关联边，合并结点vi和和vj 。合。

42、合 并后得到的新结点记为并后得到的新结点记为vi,j 。 2、有向图的关联矩阵、有向图的关联矩阵 定义定义7-3.4图图G=,设设 v1, v2, vp V, e1, eq E, 称称pq阶矩阵阶矩阵M (G)=(mij)p q 为图 为图 G的的(incidence matrix)。其中。其中: vi ej vi ej vi ej mij= 举例举例 v1v2 v3v4 e1 e2 e3 e4 e5 e6 e1e2e3e4e5e6 v11100-1 1 v2-1 -1 1000 v300-1 10-1 v4000-1 10 v5000000 v5 有向图的关联矩阵的特点：有向图的关联矩阵的特

43、点： (1)每一列中有一个每一列中有一个1和一个和一个-1，对应一边一个始，对应一边一个始 点、一个终点，元素和为零。点、一个终点，元素和为零。 (2)每一行元素的绝对值之和为对应点的度数。每一行元素的绝对值之和为对应点的度数。-1 的个数等于入度，的个数等于入度，1的个数等于出度。的个数等于出度。 e1e2e3e4e5e6 v11100-1-1 v2-1-11000 v300-1101 v4000-110 v5000000 关联矩阵的运算关联矩阵的运算 有向图有向图G的两行相加定义为：第的两行相加定义为：第i行第行第j行行的对应元的对应元 素素算术相加算术相加；相当于删除结点；相当于删除结点

44、vi与结点与结点vj之间的关联边，之间的关联边， 合并结点合并结点vi和和vj 。合并后得到的新结点记为。合并后得到的新结点记为vi,j 。 3、关联矩阵的秩、关联矩阵的秩 定理定理7-3.2图图G=,有有r个结点个结点,则其则其 完全关联矩阵完全关联矩阵M(G)的秩为的秩为r-1,即即rank M (G)=r-1 。 证明思路：证明思路： 定理定理7-3.2的推论的推论图图G=,有有r 个结点个结点,w个最大连通子图个最大连通子图,则图则图G的完全关联矩阵的完全关联矩阵 M(G)的秩为的秩为r- w,即即rank M (G)=r-w 。 小结 n图的矩阵 n邻接矩阵：点与点之间的邻接关系矩阵

45、 n可达矩阵：点与点之间的可达关系矩阵 n关联矩阵：点与边之间的关联关系矩阵 作业作业 nP300： n(2) n(3) n(4)的关联矩阵 7-4 欧拉图和汉密尔顿图欧拉图和汉密尔顿图 要求：要求： 1、理解欧拉图、汉密尔顿图的定义。、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。、会判断一些图不是汉密尔顿图。 4、熟悉一些欧拉图和汉密尔顿图。、熟悉一些欧拉图和汉密尔顿图。 一、欧拉图一、欧拉图 1、哥尼斯堡七桥问题、哥尼斯堡七桥问题 A B C D n近代图论的历史可追溯到近代图论的历史可追溯到18世纪的世纪的七桥问题七

46、桥问题 穿过穿过哥尼斯堡哥尼斯堡城的七座桥，要求每座桥通过一次城的七座桥，要求每座桥通过一次 且仅通过一次。且仅通过一次。 七桥问题等价于在图中求一条回路，此回路经过七桥问题等价于在图中求一条回路，此回路经过 每条边一次且仅有一次。欧拉在每条边一次且仅有一次。欧拉在1736年的论文中年的论文中 提出了一条简单的准则，确定了哥尼斯堡七桥问提出了一条简单的准则，确定了哥尼斯堡七桥问 题是不能解的。题是不能解的。 2、欧拉图、欧拉图(Euler) 如果无孤立结点图如果无孤立结点图G上有一条经过上有一条经过G的的所有边一所有边一 次且仅一次的路径，则称该路径为图次且仅一次的路径，则称该路径为图G的的

47、（Euler walk）。）。 如果图如果图G上有一条经过上有一条经过G边一次且仅一次的的回路，边一次且仅一次的的回路， 则称该回路为图则称该回路为图G的的 （Euler graph）。）。 定理定理7-47-4.1 无向图无向图G具有一条具有一条欧拉路欧拉路，当且仅当，当且仅当G 连通，并且有零个或两个奇数度结点。连通，并且有零个或两个奇数度结点。 证明思路：证明思路：1) 1) 先证必要性先证必要性: : G有欧拉路有欧拉路 G G的欧拉路是点边序列的欧拉路是点边序列v0e1v1e2 ekvk，其中结点可能重复，其中结点可能重复， 但边不重复。因欧拉路经过（所有边但边不重复。因欧拉路经过（

48、所有边）所有结点，所以图）所有结点，所以图G 是连通的。是连通的。 vivi vivi v0=vkv0Gv0vk v0vkG 必要性证完。必要性证完。 2)2)再证充分性再证充分性:(:(证明过程给出了一种构造方法证明过程给出了一种构造方法) ) G G有欧拉路有欧拉路 v0e1v1v1v1 e2v2G v0e1v1e2 ekvkG v0 v0 G GGG GGvi Gvi G 充分性证完充分性证完 由于有了欧拉路和欧拉回路的判别准则，因此哥由于有了欧拉路和欧拉回路的判别准则，因此哥 尼斯堡七桥问题立即有了确切的否定答案，因为从图尼斯堡七桥问题立即有了确切的否定答案，因为从图 中可以看到中可以

49、看到deg(A)5，deg(B)deg(C)deg(D)=3， 故欧拉回路必不存在。故欧拉回路必不存在。 定理定理7-47-4.1的推论的推论 无向图无向图G具有一条具有一条欧拉回路欧拉回路，当且，当且 仅当仅当G连通且所有结点度数皆为偶数。连通且所有结点度数皆为偶数。 4、一笔画问题、一笔画问题 要判定一个图要判定一个图G是否可一笔画出，有两种情况：是否可一笔画出，有两种情况： n一是从图 一是从图G中某一结点出发，经过图中某一结点出发，经过图G的每一边一的每一边一 次仅一次到达另一结点。次仅一次到达另一结点。 n另一种就是从 另一种就是从G的某个结点出发，经过的某个结点出发，经过G的每一边

50、的每一边 一次仅一次再回到该结点。一次仅一次再回到该结点。 v1 v2 v3 v4v5 为欧拉路，有从为欧拉路，有从v2到到v3的一笔画。的一笔画。 为欧拉回路，可以从任一结点出发，一笔画回到原为欧拉回路，可以从任一结点出发，一笔画回到原 出发点。出发点。 5.定义定义7-4.2：给定有向图：给定有向图G，通过图中每边一次，通过图中每边一次 且仅一次的一条单向路（回路），称作单向欧拉路且仅一次的一条单向路（回路），称作单向欧拉路 （回路）。（回路）。 可以将可以将欧拉路和欧拉回路的概念推广到有向图中。欧拉路和欧拉回路的概念推广到有向图中。 6. 6.定理定理7-47-4.2 (1)有向图有向图

51、G为具有一条为具有一条单向欧拉单向欧拉 回路回路，当且仅当，当且仅当G连通连通，并且每个结点的，并且每个结点的入度等于出入度等于出 度度。(2)有向图有向图G有有单向欧拉路单向欧拉路，当且仅当，当且仅当G连通连通，并，并 且恰有两个结点的入度与出度不等，且恰有两个结点的入度与出度不等，它们中一个的它们中一个的 出度比入度多出度比入度多1 1，另一个入度比出度多，另一个入度比出度多1 1。 证明思路与证明思路与定理定理7-47-4.1类似类似 例例1 1有向欧拉图应用示例：有向欧拉图应用示例：计算机鼓轮的设计计算机鼓轮的设计。 鼓轮表面分成鼓轮表面分成24=16等份，其中每一部分分别用绝等份，其

52、中每一部分分别用绝 缘体或导体组成，绝缘体部分给出信号缘体或导体组成，绝缘体部分给出信号0，导体部分给，导体部分给 出信号出信号1，在下图中阴影部分表示导体，空白体部分表，在下图中阴影部分表示导体，空白体部分表 示绝缘体，根据鼓轮的位置，触点将得到信息示绝缘体，根据鼓轮的位置，触点将得到信息4个触点个触点 a,b,c,d读出读出1101(状态图中的边状态图中的边e13),转一角度后将读出转一角度后将读出 1010 (边边e10)。 问鼓轮上问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓个部分怎样安排导体及绝缘体才能使鼓 轮每旋转一个部分，四个触点能得到一组不同的四位二轮每旋转一个部分，四个触点

53、能得到一组不同的四位二 进制数信息。进制数信息。 0 1 11 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 a b c d 设有一个八个结点的有向图，如下图所示。其结点分别记为设有一个八个结点的有向图，如下图所示。其结点分别记为 三位二进制数三位二进制数000，001，111， 设设ai 0,1，从结点，从结点a1 a2 a3可引出两条有向边，其终点分别是可引出两条有向边，其终点分别是a2 a30以及以及a2 a31。该两条边分别记为。该两条边分别记为a1 a2 a30和和a1 a2 a31。 按照上述方法，对于八个结点的有向图共有按照上述方法，对于八个结点的有向图共有16

54、条边，在这种图的条边，在这种图的 任一条路中，其邻接的边必是任一条路中，其邻接的边必是a1 a2 a3a4和和a2 a3a4a5的形式，即是第的形式，即是第 一条边标号的后三位数与第二条边的头三位数相同。一条边标号的后三位数与第二条边的头三位数相同。 由于图中由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所条边被记为不同的二进制数，可见前述鼓轮转动所 得到得到16个不同位置触点上的二进制信息，即对应于图中的一条欧个不同位置触点上的二进制信息，即对应于图中的一条欧 拉回路。拉回路。 010 101 110 100 011 001 111 000 e10=1010 e13=1101 e5=

55、0101e3=0011 e11=1011 e6=0110 e7=0111 e14=1110 e15=1111 e12=1100 e2=0010e4=0100 e1=0001e8=1000 e9=1001 e0=0000 a1 a2 a3 (=000) 0a1 a2 a3 (=000) 1 a1 a2 a3 (=001) 1 a1 a2 a3 (=100) 0 a1 a2 a3 (=111) 0 a1 a2 a3 (=111) 1 a1 a2 a3 (=110) 0 a1 a2 a3 (=011) 1 所求的欧拉回路为：所求的欧拉回路为： e0e1e2e4e9e3e6e13e10e5e11e7e

56、16e14e12e8(e0) （从图示位置开始）（从图示位置开始） e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二进制序列为：所求的二进制序列为： 0000100110101111 (0) 1101011110000100 (1) （从图示位置开始）（从图示位置开始） 上述结论可推广到鼓轮具有上述结论可推广到鼓轮具有n n个触点的情况。构造个触点的情况。构造2 2n-1 n-1 个结点的有向图，每个结点标记为个结点的有向图，每个结点标记为n-1n-1位二进制数位二进制数, ,从结点从结点 a1a2a3.an-1出发出发, ,有一条终点为有一条

57、终点为a2a3.an-10的边的边, ,该边记为该边记为 a1a2a3.an-10；还有一条终点标记为；还有一条终点标记为a2a3.an-11的边的边, ,该边记该边记 为为a1a2a3.an-11 。邻接边的标记规则为：。邻接边的标记规则为：“第一条边后第一条边后n-n- 1 1位与第二条边前位与第二条边前n-1n-1位二进制数相同位二进制数相同”。 哈密尔顿回路问题见图哈密尔顿回路问题见图7-4.67-4.6。 二、汉密尔顿图二、汉密尔顿图 与欧拉回路类似的是与欧拉回路类似的是汉密尔顿回路。汉密尔顿回路。 它是它是1859年汉密尔顿首先提出的一个关于年汉密尔顿首先提出的一个关于12面体面体

58、 的数学游戏：能否在图的数学游戏：能否在图7-4.6中找到一个回路，使它中找到一个回路，使它 含有图中所有结点一次且仅一次？含有图中所有结点一次且仅一次？ 若把每个结点看成一座城市，连接两个结点的边看若把每个结点看成一座城市，连接两个结点的边看 成是交通线，那么这个问题就变成能否找到一条旅成是交通线，那么这个问题就变成能否找到一条旅 行路线，使得沿着该旅行路线经过每座城市恰好一行路线，使得沿着该旅行路线经过每座城市恰好一 次，再回到原来的出发地？他把这个问题称为周游次，再回到原来的出发地？他把这个问题称为周游 世界问题。世界问题。 定义定义7-4.3：给定图：给定图G， n若存在一条路经过图中

59、的每个结点恰好一次， 若存在一条路经过图中的每个结点恰好一次， 这条路称作这条路称作汉密尔顿路汉密尔顿路。 n若存在一条回路，经过图中的每个结点恰好 若存在一条回路，经过图中的每个结点恰好 一次，这条回路称作一次，这条回路称作汉密尔顿回路汉密尔顿回路。 n具有汉密尔顿回路的图称作 具有汉密尔顿回路的图称作汉密尔顿图汉密尔顿图。 二、汉密尔顿图二、汉密尔顿图 图图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图存在一条汉密尔顿回路，它是汉密尔顿图 2、定理、定理7-4.3 若图若图G具有汉密尔顿回路，则对具有汉密尔顿回路，则对 于结点集于结点集V的每个非空子集的每个非空子集S均有均有W(G-S)|

60、S|，其中，其中W(G-S) 是是G-S的连通分支数。的连通分支数。 证明证明 设设C是是G的一条汉密尔顿回路，对于的一条汉密尔顿回路，对于V的任何一个非的任何一个非 空子集空子集S，在，在C中删去中删去S中任一结点中任一结点a1，则，则C-a1是连通的非回是连通的非回 路，路， W(C- a1)=1， |S|1，这时，这时 W(C-S)|S|。 若再删去若再删去S中中 另一结点另一结点a2，则，则W(C-a1-a2)2，而，而 |S|2，这时，这时 W(C-S)|S|。 由归纳法可得：由归纳法可得：W(C-S)|S|。同时同时C-S是是G-S的一个生成子的一个生成子 图，因而图，因而W(G-