第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 顺序：