pascal算法讲义-第六讲.pdf

百度Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第六讲 第六讲 图 一、图论初步 计算机科学中，图(Graph)是一种相当常见的数据结构，在 NOIP 考试中，图论所占的比重很大，普及组平均一年一题，提高组一年两 题。NOI、IOI、ACM 等考试中图论也是重点考察的对象。 在数学中，一个图（Graph ）是表示物件与物件之间的关系的数 学对象，是图论的基本研究对象。 图可以用二元组和三元组两种方法定义，通常我们采用图的二元 组定义。 图G 是一个有序二元组(V,E)，其中V 称为顶点集(Vertices Set)， E 称为边集(Edges set)，E 与V 不相交。它们亦可写成V(G)和E(G)。 E 的元素都是二元组，用(x,y)表示，其中x,y ∈V 。 众所周知，图论起源于一个非常经典的问题——柯尼斯堡 （Konigsberg）问题。 在哥尼斯堡的一个公园里，有七座桥将普 雷格尔河中两个岛及岛与河岸连接起来(如 图) 。问是否可能从这四块陆地中任一块出发， 恰好通过每座桥一次，再回到起点？欧拉于 1736 年研究并解决了此问题，他把问题归结 为如左图的“一笔画”问题，证明上述走法 是不可能的。 1738 年，瑞典数学家欧拉(Leornhard Euler)解决了柯尼斯堡问题。 第1 页，共115 页 百度Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第六讲 由此图论诞生。欧拉也成为图论的创始人。 图可以分为两大类：有向图和无向图。 如果给图的每条边规定一个方向，那么得到的 图称为有向图(左图) 。在有向图中，与一个节点相 关联的边有出边和入边之分。 相反，边没有方向的图称为无向图 （如右 图）。 图也可以根据边是否有权值分为带权图和无权图。前面两个图均 为无权图，下图为带权图。 值得注意的是，不能简单地将权(weight)看为两点间的距离，图 论中的图是抽象的，不规定其边的曲直长短，只是描述一些点之间的 关系。 值得注意的是，下面三个图是同构的（顶点集、边集均相同）。 第2 页，共115 页 百度Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第六讲 下面在介绍一些名词。 阶 （Order ）：图G 中顶集V 的大小称作图G 的阶。（简单地说就 是边的顶点数） 子图 （Sub-Graph ）：当图G=(V,E)其中V’ ⊆V ，E’ ⊆E，则G称作 图 G=(V,E) 的子图。每个图都是本身的子图。简单地说，从原图中删 去一些点或删去一些线或既删去一些点又删去一些线，剩下的部分 （当然必须仍然是图）。允许两种极端情况：什么都不删；删去所有 点和所有线。 真子图：当图G=(V,E)其中 V’ ⊆V ，E’⊆E，但 G≠G’ ，则 G称 作图G=(V,E) 的真子图。简单地说，类似 “子图”，但不允许什么都不 删。 生成子图 （Spanning Sub-Graph ）：指满足条件V’ = V 的G 的子图 G’ 。简单地说，类似 “子图”，但只允许删去线，不允许删去点 导出子图 （Induced Subgraph）：以图G 的顶点集V 的非空子集 V1 为顶点集，以两端点均在V1 中的全体边为边集的G 的子图，称为 V1 导出的导出子图 （点导出子图）；以图G 的边集E 的非空子集E1 为边集，以E1 中边关联的顶点的全体为顶点集的G 的子图，称为E1 导出的导出子图 （边导出子图）。简单地来说，点导出子图就是把一 个图的一些顶点与包含这些顶点的边删了，但是原先连结的两个顶点 如果都留了下来，这条边是不能删除的。边导出子图类似，把一个图 的一些边删了