第6章图与网络分析 第六章 图与网络分析 图是一种模型,如公路、铁路交通图 通讯网络图等。 图示对现实的抽象,以点和线段的连 接组合表示。 2021/2/21
2021/2/21 --第6章 图与网络分析-- --2-- 第六章 图与网络分析 • 图是一种模型，如公路、铁路交通图， 通讯网络图等。 • 图示对现实的抽象，以点和线段的连 接组合表示
第6章图与网络分析 §6.1图的基本概念和模型 、概念 (1)图:点Ⅴ和边E的集合,用以表示对某种现实事物 的抽象。记作G={V,E},V={V1,V2;…,vn}, E={e1e2;…,em} 点:表示所研究的事物对象; 边:表示事物之间的联系 0 (2)若边e的两个端点重 合,则称e为环。 (3)多重边:若某两端点之 间多于一条边,则称为多重边 2021/221
2021/2/21 --第6章 图与网络分析-- --3-- §6.1 图的基本概念和模型 一、概念 （1）图：点V和边E的集合，用以表示对某种现实事物 的抽象。记作 G=｛V,E｝, V=｛v1 ,v2 ,···,vn｝, E=｛e1 ,e2 ,···,em｝ 点：表示所研究的事物对象； 边：表示事物之间的联系。 v1 v2 v3 v4 v0 e1 e2 e3 e4 e5 e6 e7 e0 （2）若边e的两个端点重 合，则称e为环。 （3）多重边：若某两端点之 间多于一条边，则称为多重边
第6章图与网络分析 (4)简单图:无环、无多重边的图称为简单图 5)链:点和边的交替序列,其中点可重复,但边不能 重复。 (6)路:点和边的交替序列,但点和边均不能重复 7)圈:始点和终点重合的链。 (8)回路:始点和终点重合的路 (9)连通图:若一个图中,任意两点之间至少存在一条 链,称这样的图为连通图。 (10)子图,部分图:设图G1={V1,E1},G2={V2E2} 如果有VlV2,E1cE2,则称G1是G2的一个子图;若 V=V2,E1cE2,则称G1是G2的一个部分图 (11)次:某点的关联边的个数称为该点的次,以d()表示 2021/221
2021/2/21 --第6章 图与网络分析-- --4-- （4）简单图：无环、无多重边的图称为简单图。 （5）链：点和边的交替序列，其中点可重复，但边不能 重复。 （6）路：点和边的交替序列，但点和边均不能重复。 （7）圈：始点和终点重合的链。 （8）回路：始点和终点重合的路。 （9）连通图：若一个图中，任意两点之间至少存在一条 链，称这样的图为连通图。 （10）子图，部分图：设图G1=｛V1,E1｝, G2={V2,E2}, 如果有V1V2，E1E2，则称G1是G2的一个子图；若 V1=V2，E1E2，则称G1是G2的一个部分图。 （11）次：某点的关联边的个数称为该点的次，以d(vi )表示
第6章图与网络分析 、图的模型 例:有甲、乙、丙、丁、戊、已六名运动员报名参加A B、C、D、E、F六个项目的比赛。如表中所示,打“√”的 项目是各运动员报名参加比赛的项目。问:六个项目的比赛 顺序应如何安排,才能做到使每名运动员不连续地参加两项 比赛? 人 A B C E 甲乙丙丁戊己 2021/2/21
2021/2/21 --第6章 图与网络分析-- --5-- 二、图的模型 例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、 B、C、D、E、F六个项目的比赛。如表中所示，打“√”的 项目是各运动员报名参加比赛的项目。问：六个项目的比赛 顺序应如何安排，才能做到使每名运动员不连续地参加两项 比赛？ 甲 乙 丙 丁 戊 己 人 A B C D E F √ √ √ √ √ √ √ √ √ √ √ √ √
第6章图与网络分析 建立模型: 解:项目作为研究对象,排序 设点:表示运动项目 边:若两个项目之间无同一名运动员参加 顺序: B A-C-D--E--F-B AFE—DCB AC-BFE—D E A--F-B--C--D-E 2021/2/21
2021/2/21 --第6章 图与网络分析-- --6-- 建立模型： 解：项目作为研究对象，排序。 设 点：表示运动项目。 边：若两个项目之间无同一名运动员参加。 A B C D E F A—C—D—E—F—B A—F—E—D—C—B A—C—B—F—E—D A—F—B—C—D—E 顺序：
第6章图与网络分析 §6.2树图和图的最小部分树 、树图的概念 (1)树:无圈的连通图称为树图,简称为树, 2021/2/21
2021/2/21 --第6章 图与网络分析-- --7-- §6.2 树图和图的最小部分树 （1）树：无圈的连通图称为树图，简称为树。 一、树图的概念
第6章图与网络分析 (2)树的特性: ①树是边数最多的无圈连通图。在树中任加一条边,就会形成圈 ②树是边数最少的连通图。在树中任减一条边,则不连通。 (3)图的最小部分树: 定义:若G1是G2的一个部分图,且为树图,则称G1是 G2的一个部分树。 A 5 A G2: Gl D B 2021/221 B
2021/2/21 --第6章 图与网络分析-- --8-- （2）树的特性： ① 树是边数最多的无圈连通图。在树中任加一条边，就会形成圈。 ② 树是边数最少的连通图。在树中任减一条边，则不连通。 （3）图的最小部分树： 定义：若G1是G2的一个部分图，且为树图，则称G1是 G2的一个部分树。 G2： A B C D 5 4 7 3 6 5 5 7 6 G1： A C B D
第6章图与网络分析 定义:树枝总长为最短的部分树称为图的最小部分树 树枝:树图中的边称为树枝。 最小部分树的求法 例:要在下图所示的各个位置之间建立起通信网 络,试确定使总距离最佳的方案。 2021/221
2021/2/21 --第6章 图与网络分析-- --9-- 定义：树枝总长为最短的部分树称为图的最小部分树。 二、最小部分树的求法 例：要在下图所示的各个位置之间建立起通信网 络，试确定使总距离最佳的方案。 树枝：树图中的边称为树枝
第6章图与网络分析 A 5 S B D T C E 4 最小部分树长Lmm=14 2021/2/21
2021/2/21 --第6章 图与网络分析-- --10-- S A B C D E T 5 4 5 5 最小部分树长Lmin=14
第6章图与网络分析 1.避圈法:将图中所有的点分V为V两部分, V—最小部分树内点的集合 V非最小部分树内点的集合 (1)任取一点v加粗,令v∈V, (2)取V中与V相连的边中一条最短的边(v2y), 加粗(v,V),令v;∈V (3)重复(2),至所有的点均在V之内。 2.破圈法: (1)任取一圈,去掉其中一条最长的边, (2)重复,至图中不存在任何的圈为止。 2021/221 11
2021/2/21 --第6章 图与网络分析-- --11-- 1. 避圈法：将图中所有的点分V为V两部分， V——最小部分树内点的集合 V——非最小部分树内点的集合 ⑴ 任取一点vi加粗，令vi∈V， ⑵ 取V中与V相连的边中一条最短的边(vi ,vj )， 加粗(vi ,vj )，令vj∈V ⑶ 重复⑵ ，至所有的点均在V之内。 2. 破圈法： ⑴ 任取一圈，去掉其中一条最长的边， ⑵ 重复，至图中不存在任何的圈为止