离散数学-图论

第八章图论 GraphTheory 8 1图的基本概念 Graph 8 2路与图的连通性 Walks ConnectivityofGraphs 8 3图的矩阵表示 MatrixNotationofGraph 8 4最短链与关键路 Minimalpath 8 5欧拉图与哈密尔顿图 EulerianGraph Hamilton ianGraph 8 6平面图 PlanarGraph 8 7树与生成树 TreesandSpanningTrees 8 8二部图 bipartitegraph 图8 1 1哥尼斯堡七桥问题 8 1图的基本概念 8 1 1图 现实世界中许多现象能用某种图形表示 这种图形是由一些点和一些连接两点间的连线所组成 例8 1 1 a b c d4个篮球队进行友谊比赛 为了表示 个队之间比赛的情况 我们作出图 8 1 1的图形 在图中 个小圆圈分别表示这 个篮球队 称之为结点 如果两队进行过比赛 则在表示该队的两个结点之间用一条线连接起来 称之为边 这样利用一个图形使各队之间的比赛情况一目了然 1 图的定义 8 1图的基本概念 图8 1 1 如果图8 1 1中的 个结点a b c d分别表示 个人 当某两个人互相认识时 则将其对应点之间用边连接起来 这时的图又反映了这 个人之间的认识关系 8 1图的基本概念 定义8 1 1一个图G是一个序偶 V G E G 记为G V G E G 其中V G 是非空结点集合 E G 是边集合 对E G 中的每条边 有V G 中的结点的有序偶或无序偶与之对应 若边e所对应的结点对是有序偶 a b 则称e是有向边 a叫边e的始点 b叫边e的终点 统称为e的端点 若边e所对应的结点对是无序偶 a b 则称e是无向边 这时统称e与两个结点a和b互相关联 8 1图的基本概念 例8 1 2 设G V G E G 其中V G a b c d E G e1 e2 e3 e4 e5 e6 e7 e1 a b e2 a c e3 b d e4 b c e5 d c e6 a d e7 b b 则图G可用图8 1 2 a 或 b 表示 我们将结点a b的无序结点对记为 a b 有序结点对记为 a b 一个图G可用一个图形来表示且表示是不唯一的 8 1图的基本概念 图8 1 2 8 1图的基本概念 2 图G的结点与边之间的关系邻接点 同一条边的两个端点 孤立点 没有边与之关联的结点 邻接边 关联同一个结点的两条边 孤立边 不与任何边相邻接的边 自回路 环 关联同一个结点的一条边 v v 或 v v 平行边 多重边 关联同一对结点的多条边 8 1图的基本概念 如例8 1 1中的图 结点集V a b c d 边集E e1 e2 e3 e4 e5 其中e1 a b e2 a c e3 a d e4 b c e5 c d d与a d与c是邻接的 但d与b不邻接 边e3与e5是邻接的 8 1图的基本概念 例8 1 3 设图G V E 如图10 1 3所示 这里V v1 v2 v3 E e1 e2 e3 e4 e5 其中e1 v1 v2 e2 v1 v3 e3 v3 v3 e4 v2 v3 e5 v2 v3 在这个图中 e3是关联同一个结点的一条边 即自回路 边e4和e5都与结点v2 v3关联 即它们是平行边 8 1图的基本概念 图8 1 3 3 图G的分类按G的结点个数和边数分为 n m 图 即n个结点 m条边的图 特别地 n 0 称为零图 1 0 图称为平凡图 在零图中边集为空集 2 按G中关联于同一对结点的边数分为多重图和简单图 多重图 含有平行边的图 如图8 1 3 线图 非多重图称为线图 简单图 不含平行边和自环的图 8 1图的基本概念 G1 G2是多重图 G3是线图 G4是简单图 3 按G的边有序 无序分为有向图 无向图和混合图 有向图 每条边都是有向边的图称为有向图 图8 1 4 b 无向图 每条边都是无向边的图称为无向图 混合图 既有无向边 又有有向边的图称为混合图 如果将有向图中的每条边都变成无向边 称为底图 4 按G的边旁有无数量特征分为加权图 无权图 如图8 1 4 8 1图的基本概念 图8 1 4 5 按G的任意两个结点间是否有边分为完全图Kn 如图8 1 5 和不完全图 如图8 1 6 8 1图的基本概念 完全图 任意两个不同的结点都邻接的简单图称为完全图 n个结点的无向完全图记为Kn 图8 1 5给出了K3和K4 从图中可以看出K3有 条边 K4有 条边 容易证明Kn有条边 8 1图的基本概念 图8 1 6 图8 1 5K3与K4示意图 例 有向完全图 无向完全图 8 1 2图的结点的度数及其计算我们常常需要关心图中有多少条边与某一结点关联 这就引出了图的一个重要概念 结点的度数 8 1图的基本概念 定义 在有向图中 以v为终点的边数称为结点v的入度 记为 以v为始点的边数称为结点v的出度 记为 结点v的入度与出度之和称为结点v的度数 记为d v 或deg v 定义 在无向图中 图中结点v所关联的边数 有环时计算两次 称为结点v的度数 记为d v 或deg v 顶点2入度 1出度 3顶点4入度 1出度 0 顶点5的度 3顶点2的度 4 定理8 1 1无向图G V E 中结点度数的总和等于边数的两倍 即证明 因为每条边都与两个结点关联 所以加上一条边就使得各结点度数的和增加2 由此结论成立 定义 无向图中 如果每个结点的度都是k 则称为k 度正则图 8 1图的基本概念 推论 无向图G中度数为奇数的结点必为偶数个 证明 设V1和V2分别是G中奇数度数和偶数度数的结点集 由定理8 1 1知由于是偶数之和 必为偶数 而2 E 也为偶数 故是偶数 由此 V1 必为偶数 8 1图的基本概念 定理8 1 2在任何有向图G V E 中 有 图8 1 4 8 1 3子图和图的同构1 子图在研究和描述图的性质时 子图的概念占有重要地位 定义8 1 5设有图G V E 和图G V E 1 若V V E E 则称G 是G的子图 2 若G 是G的子图 且E E 则称G 是G的真子图 图与子图 3 若V V E E 则称G 是G的生成子图 图8 1 7给出了图G以及它的真子图G1和生成子图G2 图8 1 7图G以及其真子图G1和生成子图G2 8 1图的基本概念 给定任意一个含有n个结点的图G 总可以把它补成一个具有同样结点的完全图 方法是把那些缺少的边添上 定义8 1 2设G V E 是一个具有n个结点的简单图 以V为结点集 以从完全图Kn中删去G的所有边后得到的图 或由G中所有结点和所有能使G成为完全图的添加边组成的图 称为G的补图 记为 例如 零图和完全图互为补图 8 1图的基本概念 G相对于Kn的补图是下图中的 关于补图 1 G与互为补图 1 图的同构 8 1图的基本概念 试观察下面各图有何异同 图8 1 8同构的图 图8 1 9 8 1图的基本概念 定义8 1 6设有图G V E 和图G V E 如果存在双射 V V 使得e u v Ee u v E 且 u v 与 u v 有相同的重数 则称G与G 同构 记作G G 注 由同构的定义可知 不仅结点之间要具有一一对应关系 而且要求这种对应关系保持结点间的邻接关系 对于有向图的同构还要求保持边的方向 8 1图的基本概念 例8 1 5 考察图8 1 9中的两个图G V E 和G V E 显然 定义 V V vi vi 可以验证 是满足定义8 1 6的双射 所以G G 8 1图的基本概念 图8 1 9 一般说来 证明两个图是同构的并非是轻而易举的事情 往往需要花些气力 请证明下图中两个图是同构的 根据图的同构定义 可以给出图同构的必要条件如下 1 结点数目相等 2 边数相等 3 度数相同的结点数目相等 4 有相同重数的边数相同 等等 但这仅仅是必要条件而不是充分条件 下图中的 a 和 b 满足上述三个条件 然而并不同构 因为在 a 中度数为3的结点x与两个度数为1的结点邻接 而 b 中度数为3的结点y仅与一个度数为1的结点邻接 寻找一种简单有效的方法来判定图的同构 至今仍是图论中悬而未决的重要课题 高等学校21世纪教材 对于同构 形象地说 若图的结点可以任意挪动位置 而边是完全弹性的 只要在不拉断的条件下 这个图可以变形为另一个图 那么这两个图是同构的 故同构的两个图从外形上看可能不一样 但它们的拓扑结构是一样的 8 2路与图的连通性 Walks TheConnectivityofGraphs 8 2 1路与回路 WalksandCircuits 8 2 2图的连通性 TheConnectivityofGraphs 8 2 1路与回路 WlaksandCircuits 定义8 2 1给定图G V E 设v0 v1 vk V e1 e2 ek E 其中ei是关联于结点vi 1和vi的边 称交替序列v0e1v1e2 ekvk为连接v0到vk的路 v0和vk分别称为路的起点与终点 路中边的数目k称作路的长度 当v0 vk时 这条路称为回路 在简单图中一条路v0e1v1e2 ekvk由它的结点序列v0v1 vk确定 所以简单图的路 可表示为v0v1 vk 如图8 1 1表示的简单图中 路ae1be4ce5d可写成abcd 定义8 2 2设 v0e1v1e2 ekvk是图G中连接v0到vk的路 1 若e1 e2 ek都不相同 则称路 为简单路或迹 2 若v0 v1 vk都不相同 则称路 为基本路或通路 3 圈中若出现的每条边恰好一次 称简单圈 若出现的每个结点恰好一次 称基本圈 8 2 1路与回路 WlaksandCircuits 8 2 1路与回路 WlaksandCircuits 例如在图8 2 1中 有连接v5到v3的路v5e8v4e5v2e6v5e7v3 这也是一条简单路 路v1e1v2e3v3是一条基本路 路v1e1v2e3v3e4v2e1v1是一条回路 但不是基本圈 路v1e1v2e3v3e2v1是一条简单回路 也是基本圈 图8 2 1 8 2 1路与回路 WlaksandCircuits 定义8 2 3在图G中 若结点vi到vj有路连接 这时称vi和vj是可达的 其中长度最短的路的长度称为vi到vj的距离 用符号d vi vj 表示 若从vi到vj不存在路径 则d vi vj 例如在图8 2 1中 v1 v4 8 2 1路与回路 WlaksandCircuits 注意 在有向图中 d vi vj 不一定等于d vj vi 但一般地满足以下性质 1 d vi vj 0 2 d vi vi 0 3 d vi vj d vj vk d vi vk 图8 2 1 8 2 1路与回路 WlaksandCircuits 定理8 2 1设G是具有n个结点的图 如果从结点v1到另一结点v2存在一条路 则从结点v1到v2必存在一条长度不大于n 1的基本路 通路 8 2 1路与回路 WlaksandCircuits 证明 假定从v1到v2存在一条路径 v1 vi v2 是所经的结点 如果其中有相同的结点vk 例 v1 vi vk vk v2 则删去从vk到vk的这些边 它仍是从v1到v2的路径 如此反复地进行直至 v1 vi v2 中没有重复结点为止 此时 所得的就是通路 通路的长度比所经结点数少1 图中共n个结点 故通路长度不超过n 1 推论设图G V E V n 则G中任一基本圈长度不大于n 8 2 1路与回路 WlaksandCircuits 1 无向图的连通性定义8 2 4在无向图如果一个图的任何两个结点之间都有一条路 那么我们称这个图是连通的 否则是不连通的 定义8 2 5图G的一个连通的子图G 称为连通子图 若不包含在G的任何更大的连通子图中 它就被称作G的连通分支 我们把图G的连通分支个数记作 G 8 2 2图的连通性 TheConnectivityofGraphs 图8 2 3图G与G 在图8 2 3中 G是不连通的 G 而G 是连通的 G 任何一个图都可划分为若干个连通分支 显然 仅当图G的连通分支数 G 时 图G是连通的 8 2 2图的连通性 在图的研究中 常常需要考虑删去与增加结点 结点集 边和边集 或弧集 的问题 所谓从图G 中删去结点集S 是指作V S以及从E中删去与S中的全部结点相联结的边而得到的子图 记作G S 特别当S v 时 简记为G v 所谓从图G 中删去边集 或弧集 T 是指作E T 且T中的全部边所关联的结点仍在V中而得到的子图 记为G T 特别当T e 时 简记作G e 所谓图G 增加结点集S 是指作V S以及向E中并入S中 S与V中所成的边而得到的图 记作G S 特别当S v 时 简记为G v 图G 增加边集 或弧集 T是指作E T所得到的图 记作G T 这里T中全部边 或弧 的关联结点属于V 定义 给定连通无向图G S V 若 G S G 但 T S有 G T G 则称S是G的一个分离结点集 若图G的分离结点集S v 则称v是G的割点 类似地可定义图G的分离边集T 若图G的分离边集T e 则称e是G的割边或桥 P122 对于连通的非平凡图G 称 G S S是G的分离结点集 为图G的结点连通度 它表明产生不连通图而需要删去结点的最少数目 于是 对于分离图G G 0 对于存在割点的连通图G G 1 类似地定义边连通度 G T T是G的分离边集 它表明产生不连通图而需要删去边的最少数目 可见 对于分离图G G 0 对于平凡图G G 0 对于存在割边的连通图G G 1 对于完全图Kn Kn n 1 定理 一个连通无向图G中的边e是割边 存在两个结点u和w 使得联结u与w的每条链都经过e 下面再给出一个判定一条边是割边的充要条件 定理 连通无向图G中的一条边e是割边 e不包含在图的任何基本圈中 2 有向图的连通性定义8 2 6在有向图中 若从结点u到v有一条路 则称u可达v 定义8 2 7设有有向图G 1 若G的任意两个结点中 至少从一个结点可达另一个结点 则称图G是单向连通的 8 2 2图的连通性 2 如果G的任意两个结点都是相互可达的 则称图G是强连通的 3 如果略去边的方向后 G成为连通的无向图 则称图G是弱连通的 从定义可知 若图G是单向连通的 则必是弱连通的 若图G是强连通的 则必是单向连通的 且也是弱连通的 但反之不真 定义8 2 8在有向图G V E 中 G 是G的子图 若G 是强连通的 单向连通的 弱连通的 但在G 中任意增加原图的一些边或一些点 所有子图便不再是强连通的 单向连通的 弱连通的 则称G 是G的强分图 单向分图 弱分图 8 2 2图的连通性 连通图 强连通图 非连通图连通分图 图8 2 5 8 2 2图的连通性 TheConnectivityofGraphs 在图8 2 5中 强分图集合是 1 2 3 e1 e2 e3 4 5 6 7 8 e7 e8 单向分图集合是 1 2 3 4 5 e1 e2 e3 e4 e5 6 5 e6 7 8 e7 e8 弱分图集合是 1 2 3 4 5 6 e1 e2 e3 e4 e5 e6 7 8 e7 e8 8 2 2图的连通性 下面给出简单有向图的一个应用 资源分配图 在多道程序的计算机系统中 可以同时执行多个程序 实际上 程序共享计算机系统中的资源 如磁带机 磁盘设备 CPU 主存贮器和编译程序等 操作系统对这些资源负责分配给各个程序 当一个程序要求使用某种资源 它要发出请求 操作系统必须保证这一请求得到满足 对资源的请求可能发生冲突 如程序A控制着资源r1 请求资源r2 但程序B控制着资源r2 请求资源r1 这种情况称为处于死锁状态 然而冲突的请求必须解决 资源分配图有助发现和纠正死锁 假设某一程序对一些资源的请求 在该程序运行完之前必须都得到满足 在请求的时间里 被请求的资源是不能利用的 程序控制着可利用的资源 但对不可利用的资源则必须等待 令Pt p1 p2 pm 表示计算机系统在时刻t的程序集合 Qt Pt是运行的程序集合 或者说在时刻t至少分配一部分所请求的资源的程序集合 Rt r1 r2 rn 是系统在时刻t的资源集合 资源分配图Gt 是有向图 它表示了时刻t系统中资源分配状态 把每个资源ri看作图中一个结点 其中i 1 2 n 表示有向边 E当且仅当程序pk Qt已分配到资源ri且等待资源rj 例如 令Rt r1 r2 r3 r4 Qt p1 p2 p3 p4 资源分配状态是 p1占用资源r4且请求资源r1 p2占用资源r1且请求资源r2和r3 p3占用资源r2且请求资源r3 p4占用资源r3且请求资源r1和r4 于是 可得到资源分配图Gt 如图8 2 7所示 能够证明 在时刻t计算机系统处于死锁状态 资源分配图Gt中包含强分图 于是 对于图8 2 7 Gt是强连通的 即处于死锁状态 图8 2 7 8 3图的矩阵表示 MatrixNotationofGraph 8 3 1邻接矩阵 AdjacencyMatrices 8 3 2可达性矩阵 ReachabilityMatrices 8 3 1邻接矩阵 AdjacencyMatrices 上面我们介绍了图的一种表示方法 即用图形表示图 它的优点是形象直观 但是这种表示在结点与边的数目很多时是不方便的 下面我们提供另一种用矩阵表示图的方法 利用这种方法 我们能把图用矩阵存储在计算机中 利用矩阵的运算还可以了解到它的一些有关性质 定义8 3 1设G V E 是有n个结点的简单图 则n阶方阵 aij 称为G的邻接矩阵 其中 否则 如图8 3 1所示的图G 其邻接矩阵A为 8 3图的矩阵表示 MatrixNotationofGraph 显然无向图的邻接矩阵必是对称的 下面的定理说明 在邻接矩阵A的幂A2 A3 等矩阵中 每个元素有特定的含义 图8 3 1G 8 3图的矩阵表示 MatrixNotationofGraph 图8 3 1图G 8 3图的矩阵表示 MatrixNotationofGraph 定理8 3 1设G是具有n个结点 v1 v2 vn 的图 其邻接矩阵为A 则Ak k 1 2 的 i j 项元素a k ij是从vi到vj的长度等于k的路的总数 证明 施归纳于k 当k 1时 A1 A 由A的定义 定理显然成立 若k l时定理成立 则当k l 1时 Al 1 Al A 所以 8 3图的矩阵表示 MatrixNotationofGraph 根据邻接矩阵定义arj是联结vr和vj的长度为1的路数目 a l ir是联结vi和vr的长度为l的路数目 故上式右边的每一项表示由vi经过l条边到vr 再由vr经过1条边到vj的总长度为l 1的路的数目 对所有r求和 即得a l 1 ij是所有从vi到vj的长度等于l 1的路的总数 故命题对l 1成立 8 3图的矩阵表示 MatrixNotationofGraph 由定理8 3 1可得出以下结论 1 如果对l 1 2 n 1 Al的 i j 项元素 i j 都为零 那么vi和vj之间无任何路相连接 即vi和vj不连通 因此 vi和vj必属于G的不同的连通分支 8 3图的矩阵表示 MatrixNotationofGraph 2 结点vi到vj i j 间的距离d vi vj 是使Al l 1 2 n 1 的 i j 项元素不为零的最小整数l 3 Al的 i i 项元素a l ii表示开始并结束于vi长度为l的回路的数目 8 3图的矩阵表示 MatrixNotationofGraph 例8 3 1 图G V E 的图形如图8 3 2 求邻接矩阵A和A2 A3 A4 并分析其元素的图论意义 8 3图的矩阵表示 MatrixNotationofGraph 图8 3 2 解 8 3图的矩阵表示 MatrixNotationofGraph 1 由A中a 1 12 1知 v1和v2是邻接的 由A3中a 3 12 2知 v1到v2长度为3的路有两条 从图中可看出是v1v2v1v2和v1v2v3v2 2 由A2的主对角线上元素知 每个结点都有长度为 的回路 其中结点v2有两条 v2v1v2和v2v3v2 其余结点只有一条 3 由于A3的主对角线上元素全为零 所以G中没有长度为 的回路 8 3图的矩阵表示 MatrixNotationofGraph 4 由于所以结点v3和v4间无路 它们属于不同的连通分支 5 d v1 v3 8 3图的矩阵表示 MatrixNotationofGraph 8 6树与生成树 TreesandSpanningTrees 8 6 1无向树 UndirectedTrees 8 6 2无向图中的生成树与最小生成树 SpanningTreesandMinimalSpanningTrees 8 6 1无向树 UndirectedTrees 树是图论中的一个重要概念 早在1847年克希霍夫就用树的理论来研究电网络 1857年凯莱在计算有机化学中 2H2n 2的同分异构物数目时也用到了树的理论 而树在计算机科学中应用更为广泛 本节介绍树的基本知识 其中谈到的图都假定是简单图 定8 6 1一个连通无圈无向图称为无向树 简称为树 记作T 树中度数为1的结点称为树叶 或终端结点 度数大于 的结点称为分枝点 或内点 或非终端结点 一个无圈图称为森林 显然若图G是森林 则G的每个连通分支是树 如图8 6 1 a 所示的是一棵树 b 所示的是森林 8 6树与生成树 TreesandSpanningTrees 图8 6 1树和森林示意图 8 6树与生成树 TreesandSpanningTrees 例8 6 1 判断图8 6 2中各图是否为树 图8 6 2 8 6树与生成树 TreesandSpanningTrees 证 因为T是一棵n 2的 n m 树 所以由定理8 4 1 有 若T中的无树叶 则T中每个顶点的度数 2 则 deg vi 2n 2 1 定理8 6 1任一树T中 至少有两片树叶 n 2时 8 6树与生成树 TreesandSpanningTrees 若T中只有一片树叶 则T中只有一个结点度数为1 其它结点度数 2 所以 3 2 3 都与 1 矛盾 所以T中至少有两片树叶 8 6树与生成树 TreesandSpanningTrees 定理8 6 2一个无向图 n m 图T是树 当且仅当下列5条之一成立 或者说 这5条的任一条都可作为树的定义 1 无圈且m n 1 2 连通且m n 1 3 无圈 但增加任一新边 得到且仅得到一个圈 4 连通但删去任一边 图便不连通 n 2 5 每一对结点间有唯一的一条通路 n 2 8 6树与生成树 TreesandSpanningTrees 例8 6 2 T是一棵树 有两个2度结点 一个3度结点 三个4度结点 T有几片树叶 解 设树T有x片树叶 则T的结点数n 2 1 3 xT的边数m n 1 5 x又由得2 5 x 2 2 3 1 4 3 x所以x 9 即树T有9片树叶 8 6树与生成树 TreesandSpanningTrees 8 6 2无向图中的生成树与最小生成树 SpanningTreesandMinimalSpanningTrees 定义8 6 2若无向 连通图 G的生成子图是一棵树 则称该树是G的生成树 记为TG 生成树TG中的边称为树枝 图G中其它边称为TG的弦 所有这些弦的集合称为TG的补 如图8 6 3中 b c 所示的树T1 T2是 a 图的生成树 而 d 所示的树T3不是 a 图的生成树 一般的 图的生成树不唯一 图8 6 3 考虑生成树T1 可知e1 e2 e3 e4是T1的树枝 e5 e6 e7是T1的弦 集合 e5 e6 e7 是T1的补 生成树有其一定的实际意义 8 6树与生成树 TreesandSpanningTrees 例8 6 3 某地要兴建5个工厂 拟修筑道路连接这5处 经勘测其道路可依如图8 6 3 a 图的无向边铺设 为使这5处都有道路相通 问至少要铺几条路 解这实际上是求G的生成树的边数问题 一般情况下 设连通图G有n个结点 m条边 由树的性质知 T有n个结点 n 1条树枝 m n 1条弦 在图8 6 3 a 中 n 5 则n 1 5 1 4 所以至少要修 条路才行 8 6树与生成树 TreesandSpanningTrees 定义8 6 3设G V E 是一连通的有权图 则G的生成树TG为带权生成树 TG的树枝所带权之和称为 生成树TG的权 记为C TG G中具有最小权的生成树TG称为G的最小生成树 求最小生成树问题是有实际意义的 如要建造一个连接若干城市的铁路网络 已知城市vi和vj之间直达铁路的造价 设计一个总造价为最小的铁路网络 就是求最小生成树TG 下面介绍求TG的克鲁斯克尔 Kruskal 算法 8 6树与生成树 TreesandSpanningTrees 此方法又称为 避圈法 其要点是 在与已选取的边不成圈的边中选取最小者 具体步骤如下 1 在G中选取最小权边 置边数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 转2 8 6树与生成树 TreesandSpanningTrees 例8 6 4 求图8 6 4 0 中有权图的最小生成树 解 因为图中n 8 所以按算法要执行n 1 7次 其过程见图8 6 4中 1 7 8 6树与生成树 TreesandSpanningTrees 图8 6 4 8 6树与生成树 TreesandSpanningTrees 例8 6 5 求图8 6 5中有权图G的最小生成树 解 因为图中n 8 所以按算法要执行n 1 7次 图8 6 5 8 6树与生成树 TreesandSpanningTrees 例8 6 6 图8 6 6所示的赋权图G表示七个城市a b c d e f g及架起城市间直接通讯线路的预测造价 试给出一个设计方案使得各城市间能够通讯且总造价最小 并计算出最小造价 图8 6 6 8 6树与生成树 TreesandSpanningTrees 解 该问题相当于求图的最小生成树问题 此图的最小生成树为图8 6 6中的TG 因此如图TG架线使各城市间能够通讯 且总造价最小 最小造价为 8 6树与生成树 TreesandSpanningTrees 10 7根树及其应用 RootedTreesandItsApplications 10 7 1有向树 directedtree 10 7 2m叉树 m arytree 10 7 3最优二叉树 optimalbinarytree 10 7 1有向树 directedtree 图10 7 1 10 7 1有向树 directedtree 定义10 7 1一个有向图 若不考虑边的方向 它是一棵树 则这个有向图称为有向树 一棵有向树 如果恰有一个结点的入度为 其余所有结点的入度都为 则称为根树 其中入度为 的结点称为树根 出度为 的结点称为树叶 出度不为 的结点称为分枝点或内点 如图10 7 2 a 表示一棵根树 其中v1为树根 v1 v2 v3为分枝点 其余结点为树叶 习惯上我们把根树的根画在上方 叶画在下方 这样就可以省去根树的箭头 如图10 7 2 b 在根树中 称从树根到结点v的距离为该点的层次 这样对图10 7 2中的根树 v1的层次为 v2 v3的层次为 其余结点的层次均为 我们用家族关系表示根树中各结点的关系 10 7根树及其应用 图10 7 2根树示例 10 7根树及其应用 定义10 7 2在根树中 若从vi到vj可达 则称vi是vj的祖先 vj是vi的后代 又若 vi vj 是根树中的有向边 则称vi是vj的父亲 vj是vi的儿子 如果两个结点是同一结点的儿子 则称这两个结点是兄弟 定义10 7 3在根树中 任一结点v及其v的所有后代和从v出发的所有有向路中的边构成的子图称为以v为根的子树 根树中的结点u的子树是以u的儿子为根的子树 10 7根树及其应用 在现实的家族关系中 兄弟之间是有大小顺序的 为此我们又引入有序树的概念 定义10 7 4如果在根树中规定了每一层次上结点的次序 这样的根树称为有序树 我们在有序树中规定同一层次结点的次序是从左至右 10 7根树及其应用