图与网络分析2.ppt

运筹学授课教师：宋彩平博士东北林业大学经济管理学院工商管理教研室（OperationsResearch,Ｏ.Ｒ.）

第六章图与网络分析东北林业大学1.基本概念2.一笔画问题3.最小树问题4.最短路问题5.最大流问题本章内容

本章引子东北林业大学引例1七桥问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。C岛D岛AB哥尼斯堡城(加里宁格勒)中的普雷格尔河：ABCD1736年瑞士数学家欧拉在求解七桥一笔画难题时，用了点线图来分析论证，指出:每个点均有奇数条边时，一笔画问题无解。

本章引子东北林业大学引例2比赛项目排序问题：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛。下表打√的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续的参加比赛。AABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√BCFED不相邻的点序：A、C、B、F、E、D把比赛项目作为研究对象，用点表示。若两个项目有同一名运动员参加，在代表两个项目的点之间连一条线。

本章引子东北林业大学真实系统数据准备系统分析问题描述模型建立与修改模型求解与检验结果分析与实施运筹学研究基本步骤框图运筹学研究的步骤（绪论）：ABCD

§6.1图的基本概念东北林业大学一、图的概念1.图的定义：一个图G是由点集V={vi}和边集E={ek}所组成的集合，记为G=（V，E）。其中:V={vi}=｛v1,v2,…,vn｝称为点集，vi为点。E={ek}=｛e1,e2,…,em｝称为边集,ek为边(或弧)。因此，图也可表述为：用若干点和连接这些点的线来描述系统各单元及其之间特定关系的图形。在图中：点间连线表示对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及结果)。点表示研究对象（陆地、路口、国家、球队）；

§6.1图的基本概念东北林业大学在几何学中，图中点的位置，线的长度和斜率等都十分重要，而在此只关心图中有多少个点以及哪些点之间有线连接。●●●●●ABCDE交通图可抽象为ABCDE网络图●●●●●

§6.1图的基本概念东北林业大学由点及边构成，边（vi，vj）图可分为：无向图和有向图。2345574v3v1v2v4v5v616由点及弧构成，弧（vi，vj）2345574v3v1v2v4v5v616如果给图中的点和线赋以具体的含义和权数，则称为网络图。

§6.1图的基本概念东北林业大学2.端点、关联边、相邻若有边可表示为称和是边的端点，反之称边为点或的关联边。若、与同一条关联，称点和相邻。若、具有公共的端点，称边和相邻。v1e1e2e3v2v3e4v4e5

§6.1图的基本概念东北林业大学3.环、多重边、简单图v1e1v3v2v5v4e2e4e3e5e6e7e8若两点之间有多于一条的边，称这些边具有多重边。若某条边的两个端点相同，称这条边为环。无环、无多重边的图称为简单图。

§6.1图的基本概念东北林业大学4.次、奇点、偶点、孤立点v1e1e2e3v2v3e4v4e5与某一个点vi相关联的边的数目，称为vi的次数，记为d(vi)。d(v1)=2,d(v2)=3,d(v3)=4,d(v4)=1次为奇数的点称为奇点。次为偶数的点称为偶点。次为零的点称为孤立点。次为1的点为悬挂点，悬挂点的关联边称为悬挂边。

§6.1图的基本概念东北林业大学1.链：图G中的一个点、边交错序列称为链。如（v5，e8，v3，e3，v1，e2，v2，e4，v3，e7，v4）。v1e1v3v2v5v4e2e4e3e5e6e7e8首尾相连的链称为圈。2.路：链中所有的点不相同，称为路。如（v5，e8，v3，e7，v4，）。而（v5，e8，v3，e3，v1，e2，v2，e4，v3，e7，v4）不是路。首尾相连的路称为回路。3.连通图：在一个图中，任意两点之间至少存在一条链，这样的图叫连通图。否则,称为非连通图。二、链、路、连通图的概念

§6.1图的基本概念东北林业大学三、子图与部分图的概念(3)部分图：若V2=V1，E2?E1中，则称G2是G1的一个部分图，即包含原图全部顶点的子图。(2)真子