第六章图与劂络分析 §1.图的基本概念与模型 §2.树图和图的最小部分树 §3.最短路问题 §4.网络的最大流 §5.最小费用流
§ 1．图的基本概念与模型 § 2．树图和图的最小部分树 § 3．最短路问题 § 4．网络的最大流 § 5．最小费用流 第六章 图与网络分析
§1.图的基本概念与模型 个图(grph)是由一些结点互项点( nodes or vertices)以及连接点的边(eges)构成。记做G={V,E}, 其中V是顶点的集合,E是边的集合。 给图中的点和边赋以具体的含义和权值,我们称这样 的图为网给图(赋权图) 图中的点用v表示,边用e表示,对每条边可用它所 联结的点表示,如图,则有: 2=[v1,2或e2=[v2,v
§1．图的基本概念与模型 一个图（graph）是由一些结点或顶点（nodes or vertices ）以及连接点的边（edges）构成。记做G = {V,E}， 其中 V 是顶点的集合，E 是边的集合。 给图中的点和边赋以具体的含义和权值，我们称这样 的图为网络图（赋权图） 图中的点用 v 表示，边用 e 表示，对每条边可用它所 联结的点表示，如图，则有： e1 = [v1 , v1 ]， e2 = [v1 , v2 ]或e2= [v2 , v1 ]
端点,关联边,相邻 若边c可表示为e=[,,称v和是边c的端点, 同时称边e为点v和v的关联边,若点v,v与同一条 边关联,称点v和v相若边e与有公共端点,称 边2和c据 环,多重边,简单图 如果边e的两个端点相重,称该 边为环,如果两个点之间的边多于 条,称为具有多重边,对无环 无多重边的图称为篇单图。 y3gy
端点，关联边，相邻 若边 e 可表示为e = [vi , vj ]，称 vi 和 vj 是边 e 的端点， 同时称边 e 为点 vi 和 vj 的关联边，若点 vi , vj 与同一条 边关联，称点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称 边 ei 和 ej 相邻； 环，多重边，简单图 如果边 e 的两个端点相重，称该 边为环，如果两个点之间的边多于 一条，称为具有多重边，对无环、 无多重边的图称为简单图
次,奇点,偶点,孤立点 与某个点相关联的边的数目,称为该点的次(或度 线度),记作小次为奇数的点称为奇点,次为偶数 的点称为/点,次为零的点称为孤立点。 如图: 奇点为v;,n 偶点为v1,v2,v4,v6 孤立点为v
次，奇点，偶点，孤立点 与某个点相关联的边的数目，称为该点的次（或度、 线度），记作 d(v)。次为奇数的点称为奇点，次为偶数 的点称为偶点，次为零的点称为孤立点。 如图： 奇点为 v5 ， v3 偶点为 v1 , v2 , v4 , v6 孤立点为 v6
链,圈,路,回路,连通图 图中有些点和边的交替序列={v,1,n,2,…,ek, ,若其各边e1,e2,…,k各不相同,且任意vin1,v(2 ≤t≤)都相邻,称为链,如果链中所有的顶点v,n1, vk也不相同,这样的链成为路,起点和终点重合的 链称为圈,起点和终点重合的路称为回路,若在一个图 中,每一对顶点之间至少存在一条链,称这样的图为连 通图,否则称该图为不连通的
链，圈，路，回路，连通图 图中有些点和边的交替序列 μ={v0 , e1 , v1 , e2 , … , ek , vk }，若其各边 e1 , e2 , … , ek 各不相同，且任意 vi,t-1 , vit (2 ≤ t ≤ k)都相邻，称 μ 为链，如果链中所有的顶点 v0 , v1 , … , vk也不相同，这样的链成为路，起点和终点重合的 链称为圈，起点和终点重合的路称为回路，若在一个图 中，每一对顶点之间至少存在一条链，称这样的图为连 通图，否则称该图为不连通的
完全图,偶图 个简单图中若任意两点之间均有边相连,称这样的 图为完全图,含有n个顶点的完全图,其边数有 2|n(n-1)条 如果图的顶点能分成两个互不相交的非空集合v1和 V2,使在同一集合中任意两个顶点均不相郐,称这样的图 为偶图(也称二分图),如果偶图的顶点集合v和v2之 间的每一对顶点都有一条边相连,称这样的图为完全偶图, 完全偶图中V含m个顶点,V2含有n个顶点,则其边数 共m·n条 人
完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的 图为完全图，含有 n 个顶点的完全图，其边数有 1/2[n(n-1)] 条。 如果图的顶点能分成两个互不相交的非空集合 V1 和 V2 , 使在同一集合中任意两个顶点均不相邻，称这样的图 为偶图（也称二分图），如果偶图的顶点集合V1 和V2 之 间的每一对顶点都有一条边相连，称这样的图为完全偶图， 完全偶图中V1 含m 个顶点，V2 含有 n 个顶点，则其边数 共 m · n 条
子图,部分图 图G1{V1,E}和G2={V2,E2},如果有VcV2和 ESE2,称G1是G2的一个子图,若有v=V2E1cE2 则称G1是G2的一个部分图。注意部分图也是子图,但 子图不一定是部分图 子图: 部分图
子图，部分图 图 G1={V1 , E1 } 和 G2={V2 , E2 }，如果有 和 ，称 G1 是 G2 的一个子图，若有 则称 G1 是 G2 的一个部分图。注意部分图也是子图，但 子图不一定是部分图。 V1 V2 E1 E2 1 2 1 2 V =V ,E E 子图： 部分图
§2.树图和最小部分树 树图(简称,记作T(v,E))是简单连通图。(无 圈,无重边) 树的性质 性质1.任何树中必存在次为1的点。 次为1的点称为悬挂点,与之关联的边称为悬挂边。 性质2.具有n个顶点的树恰有(n-1)条边。 性质3.任何具有n个点、(m-1)条边连通图是树。 说明: 1.树中只要任意再加一条边,必出现圈 2.树中任意两点之间有且只有一条通路,从树中任 意删掉一条边,就不再连通
§2．树图和最小部分树 树图（简称树，记作 T(V, E)）是简单连通图。（无 圈，无重边） 一 . 树的性质 性质1. 任何树中必存在次为1 的点。 次为1的点称为悬挂点，与之关联的边称为悬挂边。 性质2. 具有 n 个顶点的树恰有（n-1）条边。 性质3. 任何具有n 个点、(n - 1)条边连通图是树。 说明： 1. 树中只要任意再加一条边，必出现圈。 2. 树中任意两点之间有且只有一条通路，从树中任 意删掉一条边，就不再连通
二。图的最小部分树 如果G1是G2的部分图,又是树图,则称G1是G2的 部分树(或支撑树)。树图的各条边称为树枝(假定各边 均有权重),一般图G2含有多个部分树,其中树枝总长 最小的部分树,称为该图的最小部分树也称最小支撑 树)。 定理1.图中任一个点i,若j是与i相邻点中距离最 近的,则边[i,一定包含在该图的最小部分树中。 推论.把图的所有点分成V和V两个集合,则两集 合之间连线的最短边一定包含在最小部分树内
二. 图的最小部分树 如果 G1 是 G2 的部分图，又是树图，则称G1 是 G2 的 部分树（或支撑树）。树图的各条边称为树枝(假定各边 均有权重)，一般图 G2 含有多个部分树，其中树枝总长 最小的部分树，称为该图的最小部分树(也称最小支撑 树)。 定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最 近的，则边 [ i , j ] 一定包含在该图的最小部分树中。 推论. 把图的所有点分成 V 和 两个集合，则两集 合之间连线的最短边一定包含在最小部分树内。 V
三。避團法和破圈法 寻找最小部分树的方法主要有避圈法和破圈法两种 避圈法步骤: 从图中任选一点v,让v∈V,图中其余点均包 含在中; 2.从V与V的连线中找出最小边,这条边一定包含 在最小部分树中,不妨设这条边为v,v将其加粗,标记 为最小部分树中的边 3.令VUv→V,V 4.重复2、3两步,一直到图中所有点均包含在V中
三. 避圈法和破圈法 寻找最小部分树的方法主要有避圈法和破圈法两种。 避圈法步骤： 1. 从图中任选一点 vi ，让 vi ∈V ，图中其余点均包 含在 V 中； 2. 从 V 与 的连线中找出最小边，这条边一定包含 在最小部分树中，不妨设这条边为[vi , vj ]将其加粗，标记 为最小部分树中的边。 V 3. 令 V∪vj→V， V - vj→ V ； 4. 重复2、3两步，一直到图中所有点均包含在 V 中