有n个结点的无向完全图记为K。 无向完全图：每一条边都是无向边，不含有平行边和环，每一对结点 间都有边相连 4、定理7-1.4：n个结点的无向完全图Kn的边数为n(n-1)/2。 如果在K中，对每一条边任意确定一个方向，则称该图为n个结点的 有向完全图。显然它的边数为n(-1)/2。 练习：279页(1) 证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的 出度平方之和。 证明设有向完全图有n个结点。对于任意结点V;均有 deg"(vi)+deg(vi)=n-1 (1) 而有向完全图的边数为n(血-1)/2， 由定理7-1.1有∑deg(v;)+Σdeg(v;）=n(n-1) 由定理7-1.3有∑deg(w)=∑deg(v) 所以∑deg(v;)=∑deg(v)=n(n-1)/2(2) 由(1)有(deg(v)2-(m-1-deg(w)2 因此Σ(degw)2=∑(-l-degw))2 =[-1)2-2a-1)degw)+(degw:)3 Σ(degv)2=Σ(m-1-deg(v:)2 =x[m-)2-2(a-)degv)+(deg(w）)2] =n(n-1)2 -2n(n-1)Edeg (vi)+E deg (vi))2 =n(m-1)2-2(a-1)Σdeg(w)+Σ(deg(w))2 由(2)有∑deg(v)=n(-1)/2 代入上式即得 6
6 有 n 个结点的无向完全图记为 K n 。 无向完全图：每一条边都是无向边，不含有平行边和环，每一对结点 间都有边相连 4、定理 7-1.4：n 个结点的无向完全图 Kn 的边数为 n(n-1)/2。 如果在 Kn 中，对每一条边任意确定一个方向，则称该图为 n 个结点的 有向完全图。显然它的边数为 n(n-1)/2。 练习：279 页(1) 证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的 出度平方之和。 证明 设有向完全图有 n 个结点。对于任意结点 vi 均有 deg+ (vi ) + deg- (vi ) = n-1 （1） 而有向完全图的边数为 n(n-1)/2， 由定理 7-1.1 有∑deg+ (vi ) + ∑ deg- (vi ) = n(n-1) 由定理 7-1.3 有∑deg+ (vi ) = ∑ deg- (vi ) 所以∑deg+ (vi ) = ∑ deg- (vi ) = n(n-1)/2 （2） 由（1）有(deg+ (vi ))2 = (n-1 - deg- (vi ) )2 因此∑(deg+ (vi ))2 = ∑ (n-1 - deg- (vi ) )2 = ∑[(n-1) 2 -2(n-1) deg- (vi ) +( deg- (vi ) )2 ] ∑(deg+ (vi ))2 = ∑ (n-1 - deg- (vi ) )2 = ∑[(n-1) 2 -2(n-1) deg- (vi ) + ( deg- (vi ) )2 ] = n(n-1) 2 –2n(n-1) ∑deg- (vi ) + ∑( deg- (vi ) )2 =n(n-1) 2 –2(n-1) ∑deg- (vi ) + ∑( deg- (vi ) )2 由（2）有 ∑ deg- (vi ) = n(n-1)/2 代入上式即得
Σ(degw)2=Σ（degw))2 6、子图 定义7-1.7：设图G=<W,E>,如果有图G=<W’,E'>,且E'cE,V' V,则称G'为G的子图。当V'=V时，则称G'为G的生成子图。 7、相对于图G的补图 定义7-1.8：设G'=<W',E'>是G=<W,E>的子图，若给定另一个图G” =<W”,E”>使得E”=E-E',且V”中仅包含E”的边所关联的结点， 则称G”是子图G'相对于图G的补图。 见图7-1.7图(c)是图b)相对于图(a)的补图。 8、同构 在图的定义中，强调的是结点集、边集以及边与结点的关联关系， 既没有涉及到联结两个结点的边的长度、形状和位置，也没有给出结 点的位置或者规定任何次序。因此，对于给定的两个图，在它们的图 形表示中，即在用小圆圈表示结点和用直线或曲线表示联结两个结点 的边的图解中，看起来很不一样，但实际上却是表示同一个图。因而， 引入两图的同构概念便是十分必要的了。 定义7-1.9：设图G=<V,E>及图G'=<W',E'>,如果存在一一对应 的映射g:V1→v'且e=(w1,v)(或<w1,v)是G的一条边，当且 仅当e'=(gv),g(v)(或<g(v),g(w)>)是G'的一条边，则称 G与G'同构，记作G2G'。 由同构的定义可知，不仅结点之间要具有一一对应关系，而且要 求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保 持边的方向。 显然，两图的同构是相互的，即G1同构于G2,G2同构于G1 两图同构的一些必要条件： 1.结点数目相同： 2.边数相等： 3.度数相同的结点数目相等 以上几个条件不是两个图同构的充分条件。 同构必须是结点和边分别存在一一对应。 对应结点度数不同，所以两图不同构。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而 未决的重要课题。 7-2路与回路 在无向图（或有向图）的研究中，常常考虑从一个结点出发，沿者
7 ∑(deg+ (vi ))2 = ∑ ( deg- (vi ) )2 6、子图 定义 7-1.7：设图 G=<V，E>，如果有图 G’=<V’，E’>，且 E’E，V’ V，则称 G’为 G 的子图。当 V’=V 时，则称 G’为 G 的生成子图。 7、相对于图 G 的补图 定义 7-1.8：设 G’=<V’，E’>是 G=<V，E>的子图，若给定另一个图 G” =<V”，E”>使得 E”=E-E’，且 V”中仅包含 E”的边所关联的结点， 则称 G”是子图 G’相对于图 G 的补图。 见图 7-1.7 图(c)是图(b)相对于图(a)的补图。 8、同构 在图的定义中，强调的是结点集、边集以及边与结点的关联关系， 既没有涉及到联结两个结点的边的长度、形状和位置，也没有给出结 点的位置或者规定任何次序。因此，对于给定的两个图，在它们的图 形表示中，即在用小圆圈表示结点和用直线或曲线表示联结两个结点 的边的图解中，看起来很不一样，但实际上却是表示同一个图。因而， 引入两图的同构概念便是十分必要的了。 定义 7-1.9：设图 G=<V，E>及图 G’=<V’，E’>，如果存在一一对应 的映射 g：vi→vi’且 e=(vi，vj )(或<vi，vj >)是 G 的一条边，当且 仅当 e’=(g(vi )，g(vj ))(或<g(vi )，g(vj )>)是 G’的一条边，则称 G 与 G’同构，记作 G ≌ G’。 由同构的定义可知，不仅结点之间要具有一一对应关系，而且要 求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保 持边的方向。 显然，两图的同构是相互的，即 G 1 同构于 G 2，G 2 同构于 G 1。 两图同构的一些必要条件： 1.结点数目相同； 2.边数相等； 3.度数相同的结点数目相等。 以上几个条件不是两个图同构的充分条件。 同构必须是结点和边分别存在一一对应。 对应结点度数不同，所以两图不同构。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而 未决的重要课题。 7-2 路与回路 在无向图(或有向图)的研究中，常常考虑从一个结点出发，沿着
一些边（或弧）连续移动而达到另一个指定结点，这种依次由结点和边 (或弧)组成的序列，便形成了链（或路）的概念。 学习本节要熟悉如下概念(23个)：路、路的长度、回路、迹、通路、 圈、连通、连通分支、点割集、割点、点连通度、边割集、割边、边 连通度、可达性、节点之间的距离、图的直径、单侧连通、强连通、 弱连通、强分图、单侧分图、弱分图。 掌握5个定理，一个推论。 一、路 1定义7-2.1：给定图G=W,BD,设vg.,vn∈Ve1e2., emE,其中e1是关联于结点1-1v1的边，交替序列v0e1Y12enn 称为联结vo到vn的路。 o和Vn分别称作路的起点和终点，边的数目n称作路的长度。当v0vn 时，这条路称作回路。 若一条路中所有的边©1©2，e均不相同，称作迹。 若一条路中所有的结点oV1,Vn均不相同，则称作通路。 闭的通路，即除VOV。外，其余的结点均不相同的路，就称作圈。 例如 el e2 e3 20 v3 e4 e5 e6 e7 40 0w5 e8 8
8 一些边(或弧)连续移动而达到另一个指定结点，这种依次由结点和边 (或弧)组成的序列，便形成了链(或路)的概念。 学习本节要熟悉如下概念(23个)：路、路的长度、回路、迹、通路、 圈、连通、连通分支、点割集、割点、点连通度、边割集、割边、边 连通度、可达性、节点之间的距离、图的直径、单侧连通、强连通、 弱连通、强分图、单侧分图、弱分图。 掌握5个定理，一个推论。 一、路 1、定义 7-2.1：给定图 G＝<V，E>，设 v 0 ，v 1 ，.，v n V，e 1 ，e 2 ，.， e m E，其中 e i 是关联于结点 v i-1，v i 的边，交替序列 v 0 e 1 v 1 e 2.e n v n 称为联结 v 0 到 v n 的路。 v 0 和 v n 分别称作路的起点和终点，边的数目 n 称作路的长度。当 v 0 =v n 时，这条路称作回路。 若一条路中所有的边 e 1，e 2，.，e m 均不相同，称作迹。 若一条路中所有的结点 v 0 ，v 1 ，.，v n 均不相同，则称作通路。 闭的通路，即除 v 0 =v n 外，其余的结点均不相同的路，就称作圈。 例如
路：v1e2v3e3v2e3v3e4v2e6v5e7V3 迹：v5egv4e5v26v5e7V3e4v2 通路：v4egv56v2e1V1e2v3 圈：v2e1V1e23e7V5e6v2 在简单图中一条路v0112“enY由它的结点序列g1?,Vn 确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数 大于一的一条路亦可由边序列e12en表示。 2、定理7-2.1：在一个具有n个结点的图中，如果从结点v:到v存 在一条路，则从结点v:到yk存在一条不多于1条边的路。 3、推论：在一个具有n个结点的图中，若从结点v;到vk存在一条路 则必存在一条从y;到"k而边数小于n的通路。 定理7-2.1的证明 如果从结点v:到y存在一条路，该路上的结点序列是vV k,如果在这条中有1条边，则序列中必有1+1个结点，若1>-1， 则必有结点Vs,它在序列中不止出现一次，即必有结点序列vVs. VsVk在路中去掉从Vs到vs的这些边，仍是v;到vk的一条路， 但此路比原来的路边数要少，如此重复进行下去，必可得到一条从] 到k的不多于1条边的路。 9
9 路：v1 e2 v3 e3 v2 e3 v3 e4 v2 e6 v5 e7 v3 迹：v5 e8 v4 e5 v2 e6 v5 e7 v3 e4 v2 通路：v4 e8 v5 e6 v2 e1 v1 e2 v3 圈：v2 e1 v1 e2 v3 e7 v5 e6 v2 在简单图中一条路 v 0 e 1 v 1 e 2 .e n v n ，由它的结点序列 v 0 ，v 1 ，.，v n 确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数 大于一的—条路亦可由边序列 e 1 e 2.e n 表示。 2、定理 7-2.1：在一个具有 n 个结点的图中，如果从结点 v j 到 v k 存 在一条路，则从结点 v j 到 v k 存在一条不多于 n-1 条边的路。 3、推论：在一个具有 n 个结点的图中，若从结点 v j 到 v k 存在一条路， 则必存在一条从 v j 到 v k 而边数小于 n 的通路。 定理 7-2.1 的证明 如果从结点 v j 到 v k 存在一条路，该路上的结点序列是 vj.vi. vk，如果在这条中有 l 条边，则序列中必有 l+1 个结点，若 l>n-1， 则必有结点 vs，它在序列中不止出现一次，即必有结点序列 vj.vs. vs.vk，在路中去掉从 vs 到 vs 的这些边，仍是 vj 到 vk 的一条路， 但此路比原来的路边数要少，如此重复进行下去，必可得到一条从 v j 到 v k 的 不多于 n-1 条边的路
el e2 e3 el e3 v3 3 94 e4 e6 e e6 e7 40 0w540 05 e8 e8 el e2 e3 2 w3 e4 e6 e7 40 0v5 e8 如在图7-2.1中有5个结点。V1到3的一条路为： v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有6条边，去掉e3有路1e2v3e4v26v5e7v3 有4条边。 y1到v3最短的路为v1e23 二、无向图的连通性： 1、连通 定义7-2.2：在无向图G中，结点u和v之间若存在一条路，则称结 点u和结点v是连通的。 不难证明，结点之间连通性是结点集V上的等价关系，因此对应这个 等价关系，必可对结点集V作出一个划分，把V分成非空子集V1V2
10 如在图 7-2.1 中 有 5 个 结 点 。 v1 到 v3 的 一 条 路 为 ： v1 e2 v3 e3 v2 e3 v3 e4 v2 e6 v5 e7 v3 此路中有 6 条边，去掉 e3 有路 v1 e2 v3 e4 v2 e6 v5 e7 v3 有 4 条边。 v1 到 v3 最短的路为 v1 e2 v3 二、无向图的连通性： 1、连通 定义 7-2.2：在无向图 G 中，结点 u 和 v 之间若存在一条路，则称结 点 u 和结点 v 是连通的。 不难证明，结点之间连通性是结点集 V 上的等价关系，因此对应这个 等价关系，必可对结点集V作出一个划分，把V分成非空子集V 1，V 2