第08讲 图的基本概念及最小支撑树问题.ppt

图的基本概念及最小支撑树问题 无向图 定义无向图G 其中 1 V 为顶点集 元素称为顶点 2 E为V V的多重集 其元素称为无向边 简称边实例设V v1 v2 v5 E v1 v1 v1 v2 v2 v3 v2 v3 v2 v5 v1 v5 v4 v5 则G 为一无向图 相关定义 邻接 两个点有公共边 两条边有公共顶点 关联 边与其顶点 环 一条边的两个顶点重合 重边 两个点之间有多于一条边 简单图 既无环也无重边的图 补图 图G的补图定义为 与G有相同的顶点集 中两个点相邻当且仅当它们在G中不相邻 二部分图 二分图 支撑子图导出子图点度 通路 回路 有向图 定义有向图D 只需注意E是V V的多重子集图2表示的是一个有向图 试写出它的V和E注意 图的数学定义与图形表示 在同构的意义下是一一对应的 网络 带权图 对于图G的每条边e都赋予一个值w e 称为边的权 则G连同边上的权称为一个网络 记为G V E w 无向图的关联矩阵 无向图的关联矩阵 对图无限制 定义无向图G V n E m 令mij为vi与ej的关联次数 称 mij n m为G的关联矩阵 记为M G 性质 定义有向图D 则称 mij n m为D的关联矩阵 记为M D 4 平行边对应的列相同 性质 有向图的关联矩阵 邻接矩阵 定义设无向图D V v1 v2 vn E e1 e2 em 令cij为顶点vi和vj之间边的条数 称 cij 为D的邻接矩阵 记作A D 或简记为A 定义设有向图D V v1 v2 vn E e1 e2 em 令cij为顶点vi邻接到顶点vj边的条数 称 cij 为D cij 的邻接矩阵 记作A D 或简记为A 图的连通性 无向图的连通性 1 顶点之间的连通关系 G 为无向图 若vi与vj之间有通路 则vi vj 是V上的等价关系R u v V且u v 2 G的连通性与连通分支 若 u v V u v 则称G连通 V R V1 V2 Vk 称G V1 G V2 G Vk 为连通分支 其个数p G k k 1 k 1 G连通 割集 1 删除顶点及删除边G v 从G中将v及关联的边去掉G V 从G中删除V 中所有的顶点G e 将e从G中去掉G E 删除E 中所有边2 点割集与边割集点割集与割点定义G V VV 为点割集 p G V p G 且有极小性v为割点 v 为点割集定义G E EE 是边割集 p G E p G 且有极小性e是割边 桥 e 为边割集 无向树 定义 1 无向树 连通无回路的无向图 2 平凡树 平凡图 3 森林 至少由两个连通分支 每个都是树 组成 4 树叶 1度顶点 5 分支点 度数 2的顶点 树的充要条件 定理16 1设G 是n阶m条边的无向图 则下面各命题是等价的 1 G是树 2 G中任意两个顶点之间存在惟一的路径 3 G中无回路且m n 1 4 G是连通的且m n 1 5 G是连通的且G中任何边均为桥 6 G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到惟一的一个含新边的圈 支撑树 定义 T为G的支撑子图 且T为树 称T为G的支撑树 定理 G有支撑树当且仅当G为连通图 支撑树 最小值支撑 生成 树 定义 网络中权值最小的支撑树 称为该网络的最小支撑树 Kruskal算法 Kruskal算法 设G 将G中非环边按权从小到大排序 e1 e2 em 1 取e1在T中 2 查e2 若e2与e1不构成回路 取e2也在T中 否则弃e2 3 再查e3 直到得到生成树为