图论及其应用第1章.pptVIP

电子科技大学数学科学学院 王也洲 ;§1.1 图和简单图 ;;注: 也可记边 uv 为e ，即 e = uv。;相关概念: (1) 若边e = uv , 此时称 u 和v 是 e 的端点; 并称 u 和 v 相邻，u (或v)与 e 相关联。若两条边有一个共同的端点，则称这两条边相邻。;;二、图的同构;例如;图中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2;（4）在图的图形表示中我们可以不给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号）图。非标定图实际上是代表一类相互同构的图。 ; 例 证明下面两图同构。; 例 判断下面两图是否同构。;三、完全图 ，偶图 ，补图;具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。;例;例;例如, 下图中的(a)，(b)两图是互补的。;证明 因为G是自补的，则G和其补图有同样多的边数，且边数;四．顶点的度（续）, 度序列;对任意的有m条边的图 G = (V, E)。有;奇(偶)点: 奇(偶)数度的顶点;从而推知 也为偶。而和式中每个d(v)均为奇，故和 式中的被加项的项数应为偶，这表明G 中度为奇数的点有偶数个。 ;;;推论2 正则图的阶数和度数不同时为奇数。;例 偶数4有五种划分： 4，3+1，2+2，1+1+2，1+1+1+1 但属于图划分的却只有两种:;定理5 设有非负整数组Π = (d1, d2,…, dn)，且;因;§1.2 子图与图的运算; 上图中，H1与H2均为G 的子图，其中H2 是G 的生成子图，而H1 则不是。;边导出子图 假设E’是E的非空子集。以E’为边集，以E’中边的端点全体为顶点集所组成的子图称为G的由E’导出的子图，记为G[E’ ]；简称为G的边导出子图，边集为 E \ E’ 的G 的导出子图简记为 G-E’ 。若E’ ={e }，则用G–e来代替 G-{e}。;二. 图的运算;例;例;定义2 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2。;定义3 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G称为G1和G2积图，记为G = G1×G2。其中 ui adj vi 表 ui 和vi邻接，如下图所示。;n-方体Qn ：递推地定义为，Q1= K2，Qn= K2×Qn-1 。 ;§1.3 路和连通性;;例1 在下图G 中，取 w1 = v1v2v3 ，w2 = v1v2v3v4v2 ，w3 = v1v2v3v2v3v4 ( 注：简单图可只用点序列表通路）;2. 图的连通性;连通分支（分支，支）：若H是图G 的连通子图且H不能再扩充为G的任一连通子图，则称H为G的连通分支。用ω(G) 记图G 的连通分支数。;3. 有关定理;定理8 一个图是偶图当且当它不包含奇圈。;;现在证明（X, Y）是G的一个二分类。;§1.4 最短路及其算法; 设Γ是权图G 中的一条路，称Γ 的各边权之和为路Γ的长。赋权图中点 u 到 v 的距离仍定义为点 u 到 v 的最短路的长，仍记为 d(u,v)。;二. 最短路问题 ;并用 ui+1记达到最小值的某点。置S i+1= Si∪{u i+1}，i = i+1（表示赋值语句，以后的算法中相同），转（2）。;例3 求图 G 中 u0 到其它点的距离。;u0 ;（d）对与u1相邻的小圆点， 用 l (u1) + w (u1v) = 2+1 = 3 更新标号4； 2+5=7 更新两个∞；;u4 ;三. 算法分析;例 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。现要将酒平分，求最少的操作次数。;§1.5 图的代数表示及特征;邻接矩阵 A =;说明: (1) 邻接矩阵是一个对称方阵。 ;0 1 0 0;定理10 令G是一个有推广邻接矩阵A的 p阶标定图，则 An的i 行j 列元素 等于由vi到vj的长度为n的通道的数目。;