湖南大学离散数学教案--图论.ppt

第五章图论 杨圣洪 5 1图的概念与描述 由结点和连结两个结点的连线所组成的对象称为 图 至于结点的位置及连线的长度无紧要 形式定义 三元组 V G E G M E V 称为图 其中V G 为点的集合 非空集 E G 是边集 M E V 边与点连接关系 常简化为二元组 V G E G 称为图 简记为G V E 5 1图的概念与描述 邻接矩阵 对于有向图 如果从结点vi到结点vj之间有一条边 则a i j 1 否则为0 由于结点vi到vj有一条边 反过来vj到vi之间不一定有一条 故不一定对称 对于无向图 如果结点vi到Vj有一条边 则a i j 1 否则为0 由于Vi到Vj有一条边时 反过来Vj到Vi肯定也有一条边 故它是对称的 可表示自环 不能表示重边 5 1图的概念与描述 关联矩阵 关联矩阵表示结点与边之间的关联关系 对于有向图 如果Vi是ej的起点 则b i j 1 如果Vi是ej的终点 则b i j 1 如果以上两种情况不存在 则b i j 0 对于无向图 如果Vi到ej某个端点 则b i j 1 否则b i j 0 该矩阵的行对应为 点 列对应 边 n m ej Vi ej Vi ej Vi ej Vi 重边可表示 自环不可能表示 A B C D e1 e2 e3 e4 e5 e6 e7 a b c d e1 e2 e3 e4 e5 e6 V a b c d E e1 e2 e3 e4 e5 e6 V 称为结点数 记为n该值有限 有限图 E 称为边数 记为m 该值有限 有限图无限图 如果每条边都有方向的 则为有向图 如果每条边都没有方向 则为无向图 某些边有方向 某些边没有方向 混合图 有向图无向图 邻接 有向边e1 A与D相邻 e1与A D相关联 称A为D的直接前趋 D为A的后继 点与点相邻 点与边关联无向边e1 a b a与b相邻 e1与a b相关联 只与一个结点关联的自环 自旋 某两个点之间有多条边为重边 多重图 无环无重边简单图 度 某结点关联边的条数 称为该点的度数 D A 5 d入 A 1 d出 A 4 有向图d入 A d出 A d A 5 入 进入某结点的边 也称为 负边 负度 出 离开某结点的边 也称为 正边 正度 各点度数和 边数的2倍 deg v 2 E 2m 为偶数 证明 先去掉所有的边 每个点 整个图的度数为0增加一条边e u v 使结点u与v的度数的各增加1 每增加一条边使整个图的度数增加2 deg v 2 E 2m 为偶数 握手定理 左图 3 2 3 2 10 边数 5 度数和10 边数的2倍 2 5 右图 3 3 3 3 12 边数 6度数和12 边数2倍 2 6 图中度数为奇的结点有偶数个 用Vo表示度数为奇 odd 的结点集合 Ve为偶 even 的结点的集合 则有 edeg v odeg v deg v 2m 因Ve中每点度数均为偶数 edeg v 为偶数 不妨记为2k odeg v 2m 2k 2 m k 由于Vo中每个结点的度数为奇数 不妨依次记为2n1 1 2n2 1 2nt 1 t为个数 其和为2 n1 n2 nt 1 1 1 2n t 2n t 2 m k 个数t 2 m k 2n 2 m k n 左图度数为奇的点有 A 5 B 3 共2个右图度数为奇的点有 B 3 D 3 共2个 有向图中出度 正度 和 入度 负度 和 在有向图中 每条边都有起点 与终点 每加一条边使起点的出度增加1 整图的出度增加1 每加一条边使终点的入度增加1 整图的入度增加1 每边使整图的出度 入度各增加1 所有的边加起来 增加的出度和 入度和 正度 出度 4 1 1 2 8负度 入度 1 2 3 2 8正度和 负度和 n个结点完全图Kn的边数 n n 1 2 Kn n个结点的完全图 该图的任何两个结点之间都有边相连 每个点都与其它n 1个点之间有边相连 每个点度数为 n 1 n个点的度数和n n 1 而整图的度数和为n n 1 边数2倍 2m n n 1 2m 故边数m n n 1 2由组合学可知m C n 2 证明了c n 2 n n 1 2说明 简单图中点的度 n 1 边数 n n 1 2 边数 n n 1 2 非空简单图一定存在度相同的结点 证明 图G的结点数记为n 由于它是简单图 无重复边与自环 每点的度数取值范围是0 n 1 当没有度数为0的结点时 每点度数的取值范围是1 n 1 根据鸽巢原则 这n个点中至少有2个点的度数相同 当有度数为0的结点时 剔除所有度数为0的结点 对剩下来的结点所组成的图使用前面的证明 3 2 2 33 3 3 3 例题某班有23人 班长说每个人恰好只与其他7个人关系密切 请问班长的话可信吗 解 将以上问题用图表示 23个人则23个点表示 i号同学对应结点i 如果某两位同学关系密切 则对应的结点间用一条边相连 说每个人恰好只与其他7个人 说明与每位同学相连的边数为7 即其度数为7 23位同学的度数和 23 7 161 由握手定理有161 2m 一个奇数不可能等于一个偶数 显然矛盾 故班长的话不可信 用图论来解决问题 关键是将问题中的对象表示为结点或边 5 2图的连通性 定义一个有向图中 从任意结点出发 若沿着边的箭头所指方向 连续不断向前走 能到达所有的结点 则此图连通 否 是 5 2图的连通性 定义一个无向图中 从任意结点出发 沿着边连续不断向前走 能到达所有的结点 则此图是连通的 是 5 2图的连通性 看图判断连通性 仅对结点数比较少的图可行 结点数较多时需要寻求更高效的方法 前面求传递闭包时 如果某两个结点之间通过传递可达 则在这两点之间加上一条边 称为复合边 因此求完传递闭包后 如果某二个点之间有边相连 则表明这二个结点 要么未求闭包之前是直接相连的 要么这两个点之前不是直接连接 是通过传递可达 图与其邻接矩阵 相当于关系图与其关系矩阵 因此求传递闭包的方法可用来判断图的连通性 即WarShall算法 邻接矩阵的逻辑幂次方运算 例题判断下图是是否连通 a 1 3 0从结点1不能走到结点3 看图可知 其他0类似a 1 5 1从结点1出发可达结点5 看图可知 其他1类似 例题若求跨越1条边 2条边 n 1条边的路 究竟有多少条 则直接计算邻接矩阵的幂次方A A2 A3 An 1 5 3Euler问题 七桥问题 每桥仅走一次 回到家里 定义5 3 1如果从某点出发 沿着边不断前行又回到起点 那么称沿途经过的边构成一个回路 如下图中 a b d是一个回路 a b a是一个回路 a b d c a也是回路 定义5 3 2如果从某点出发 沿着边不断前行能走遍所有的边 但不回到起点则称为欧拉路 定义5 3 3如果从某点出发 沿着边不断前行能走遍所有的边 并且回到起点则称为欧拉回路 存在欧拉回路的图也称为欧拉图 定理5 3 1无向图G有欧拉回路 所有结点度数为偶数 定理5 3 2无向图G有欧拉路 所有结点度数为偶数 或者只有2个结点度数为奇数 左图中度数为 deg a 5 deg b 3 deg c 3 deg d 3 故没有欧拉回路 故七桥问题无解 中图 deg a deg d 3 有欧拉路没无回路右图 deg 1 2deg 2 4deg 3 4deg 4 2deg 5 2故有欧拉回路 为欧拉图 判断下面图能否可以一笔画出 5 4哈密尔顿图 1859年 英国数学家哈密顿 用一个规则的实心十二面体 标出世界著名的20个城市 5 4哈密尔顿图this 定义5 4 1如果图中存在一条 经过所有结点一次也仅一次的路 则称为哈密尔顿路 如果回到起点称为哈密尔顿回路 存在哈密尔顿回路的图称为哈密尔顿图 定义5 4 2如果图中没有一个结点上有自旋 任意二个结点间最多一条边 则称为简单图 定理5 4 1设G是具有n结点的简单图 如果G中每一对结点度数和 n 1 则G中存在一条哈密尔顿路 即存在一条经过所有点一次的路 定理5 4 2设G是具有n结点的简单图 如果G中每一对结点度数和 n 则G中存在一条哈密尔顿回路 即存在一条经过所有点一次的回路 充分而不必要 5 4哈密尔顿图 左n 5 任意2点和 4有H路 右n 6 任意2点和 5有H路下图n 6 任意2点和 4 5 不满足条件但有回路 充分条件 满足肯定是 不必要 是不一定满足 5 4哈密尔顿图 定理5 4 3若图G 具有哈密尔顿回路 则对于结点集V的每个非空子集S 均有W G S S 当取S 1 5 时上图变成了下图被分成了3块 即W G S 3 而 S 2 故不满足W G S S 故不是H图 5 4哈密尔顿图 去掉1个结点后W G S 1 S 去掉2个结点后W G S 1 S 去掉3个结点后W G S 1 S 去掉4个结点后W G S 1 S 去掉5个结点后即W G S 1 S 去掉6个结点后W G S 4 S 均满足但不是H图 可用AB标记法检测 必要不充分 5 4哈密尔顿图 如果有多条哈密尔顿回路 距离都已标在每条边上 哪条路最短呢 称为 旅行商问题TSP TravelingSalesmanProblem 或货郎担问题 如 1 2 3 4 5 1 路长为4 16 11 13 10 54但是1 2 4 3 5 1 路长为4 3 11 4 10 31 只能一一试探 其计算量相当大 是一个不可能在多项时间内解决的问题 称为NP NonPolynomial 难问题 5 5平面图与染色问题 定义5 5 1如果一个简单图中任意两条边不在中间相交 仅在两个端点相交 或将某些边拉长或缩短后 也可做到不在中间相交 也称为平面图 或可平面化的图 一律称为 平面图 5 5平面图与染色问题 定义5 5 2平面图中由边围成的封闭区域称为为面或域 如下图中 有1 3 4 1围成的面1 1 2 4 1围成的面2 2 4 3 2围成的面3 还有1 3 2 1之外的广阔的外围空间也是一个面 所以该图共有4面 定理5 5 1平面图中面数 边数 点数 2 如下图中 面数d 4 边数m 6 点数n 4 显然有d m n 2 5 5平面图与染色问题 定义5 5 3在点数大于3的平面图中 如果在不相邻的两个点之间添上一条边 新添边肯定与其他边相交 即变成非平面图 则该图为极大可平面图 如果所有点相邻 这种图称为完全图 不可能再加边了 肯定为极大可平面图 如下图每个面的边数为3 定理5 5 2极大平面图中 3d 2m m 3n 6 d 2n 4 5 5平面图与染色问题 证明 极大平面图中任何面的边只有3条 若超过3条如达4条则至少为四边形 还可添加边这与极大平图矛盾 每条边均是面的边界线 是两个面的边界 故数各个面的边界数时 每边被数了2次 所有面的边界数和 2m 极大平面图中每个面只有3条边 d个面共有3d条边 所以3d 2m 将d m n 2代入有 3 m n 2 2m 故m 3n 6 将m 3d 2代入d m n 2中 d 3d 2 n 2 故d 2n 4 5 5平面图与染色问题 定理5 5 3平面图中m 3n 6 d 2n 4m C 5 2 10 点数n 5 3n 6 9 违反了m 3n 6m C 6 2 15 点数n 6 3n 6 12 违反了m 3n 6 5 5平面图与染色问题 对偶图在平面图每个面中取一个代表点 原来相邻的两个面的代表点之间用线相连 得到的图称为对偶图 对原图面的着色问题转换为对偶图的点的着色四色猜想变成 对平面图的对偶图的结点进行着色时 最多4种颜色 可保证相邻两个结点的颜色不一样 如果不是平面图的对偶图可能不止四种颜色 5 5平面图与染色问题 Powell着色算法 1 结点按度数的递减顺序排阶列 2 用第1种颜色对第1个结点着色 并且按排列次序 对与前面已着色点不相邻的每个点着相同的颜色 3 用第二种颜色对尚未着色的点重复 2 步 用第三种颜色对尚未着色的点继续这种过程 直到所有点着色 5 5平面图与染色问题 有6货物需要堆放 两种货物之间若不能放在同一个仓库 则用一条线相连 其相互关系如下图所示 请问共需要几个仓库 1 排序 B 4 D 4 A 3 C 3 E 3 F 3 2 用红色着B 与B不相邻的点是A 故A着成红色 3 用兰色着D 与D不相邻的点是F 故F也着成兰色用黑色着C 与C不相邻的点是E 故E着成黑色 5 6树 定义5 6 1没有回路的连通图 则称为一棵树 右图是一棵树 它将左图中很多边去掉了 回路都不见了 但是各个点仍是连通的 5 6树 定义5 6 2如果一个棵树包含某个图的所有结点 则称为该图的生成树或支撑树 不唯一如右图包括左图的所有结点 故是左图生成树定理5 6 1树所包含的边数等于点数减1 5 6树 定义5 6 3在赋权图的所有生成树中 边权和最小的生成树称为最小生成树 如图5 20 a 的生成树可为5 20 b 5 20 c 谁最小 5 6树 Kruskal最小生成树 1 选取权最小的边e1 置边数i 1 2 i n 1时结束 否则转 3 3 设已选取边为e1 e2 ei 在G中选取不同e1 e2 ei的边ei 1 使 e1 e2 ei ei 1 中无回路 且ei 1是满足此条件的最小边 4 i i 1例题对于图5 20 a 中 1 选长为2的 2 5 3 4 此时i 2 2 选长为3的 2 4 4 5 不能再选了 因与 2 5 2 4 成回路 i 3 3 选择长为4的 1 2 这时i 4 5 6树 Prim最小生成树 1 任选一结点V0构成集合U 2 从U中选到V U 余点 最短边 v r 入树T v U r V U 3 U U r 4 如果 U V 回到 2 如 1 U 1 T 2 T 1 2 U 1 2 3 T 1 2 2 5 U 1 2 5 4 T 1 2 2 5 2 4 U 1 2 5 4 5 T 1 2 2 5 2 4 3 4 U 1 2 5 4 3 5 6树 根树 有向图的生成树中 如图5 21 a 从结点A出发 沿着各边箭头所指方向前行 分多路可走遍图中所有的点 如图 b 其中A C B E F A D 这种生成树称为根树 起点A称为树根 入度为0 对于入度为1出度为0的点为叶子结点 入度为1且出度至少为1的结点称为内点内点与根结点一块统称为分支点 从根结点到各点所包含的边之条数 称为根结点到该点的距离 A到D C的为1 A到B为2 A到E为3 A到F离为4 距离中最大值称为树高或层数 5 6树 根树 如果结点至多有2个后代 称为2叉树 如果正好都只有2个后代 则称为完全二叉树 画根树时 如图5 21 b 习惯将根结点画在最高处所有边都指向远离根结点方向 即整体朝下 对根树的画法适当简化 即去掉所有边的箭头 如图5 21 b 所示的根树可简化为图5 22所示 5 6树 根树 定义5 6 4设根树T有t片树叶v1 v2 vt 给每片树叶赋一个权值w1 w2 wt 则称为T的赋权二叉树 其中l vi 为叶子结点vi的长度 如果存在一种赋权方式 使得值 w i l vi 达到最小 则称为棵树为最优二叉树 或称Huffman树 Huffman树的构造算法 1 对所有权值从低到高排队 2 找出两个最小的权值 记为W1和W2 3 用W1 W2代替W1与W2 产生新的队列 4 若队列中的点数大于1 则回到 1 否则转 5 5 逆序将以上组合过程画出来便得到Huffman树 5 6树 根树 例题汉字 一地在要工上是中国同和的有 出现频率依次为 2 3 5 7 11 13 17 19 23 29 31 37 41 对汉字编译 译出 1000101110100101111 对应的汉字 5 6树 根树 原则 左小右大 组合优先 左0右1 不足补0一1010111 地1010110 在101010 要10100 工0100 上0101 是1011 中1110 国1111 同011 和100 的110 有00 5 6树 根树 原则 左小右大 组合优先 左0右1 不足补01000101110100101111 每次从根结点开始 100 和 0101 上 110 的 100 和 1011 是 110 不足补0 凑成110 译为 的 此处右边5下方的2 3应画在左边 它违反了组合优先 5 7最短路径 问题 二点之间数据路径最短 如图5 24中 求结点1到其他各点的最短距离 再求2到其他各点的距离 Dijkstra算法如下 1 初始化 D 1 0 若1结点i有边直接相连则D i 边权W 1 i 否则D i S 1 2 若 S 则结束 否则 S中寻找D值最小的点i S S i 转 3 3 在 S寻找i的后代j 若d i w i j d j 则置d j d i w i j 回到 2 5 7最短路径 1 初始化 D 1 0 D 2 7 D 3 1 S 1 S 2 3 4 5 6 2 距离最小者i 3 S 1 3 S 2 4 5 6 3 因d 3 w 3 2 6 d 2 故d 2 6 因d 3 w 3 5 3 则d 5 3 因d 3 w 3 6 8 则d 6 8 回到 2 2 距离最小者i 5 S 1 3 5 S 2 4 6 3 因为d 5 w 5 4 8 则d 4 8 回到 2 2 距离最小者i 2 S 1 3 5 2 S 4 6 3 因为d 2 w 2 6 7 8 则d 6 7 回到 2 2 距离最小者i 6 S 1 3 5 2 6 S 4 3 由于结点4不是结点6后代 故迭代结束 D 1 0 D 3 1 D 5 3 D 2 6 D 6 7 D 4 8 5 7最短路径 动态规划算法 适用于分段明显 层次分明