+8++图与网络分析.ppt

第八章图与网络分析 第一节 图与网络的基本知识 第二节 树 第三节 最短路问题 第四节 最大流问题 第五节 最小费用流问题 §8-1 图与网络的基本知识 一、图与网络的基本概念 1、图及其分类 图是反映对象之间关系的一种工具。 例如，在一个人群中，对相互认识这种关系可以用图来表示。 例1 在图8-7中：V={v1,v2,v3,v4,v5} E={e1,e2,e3,e4,e5,e6} 两条边ei, ej 属于E，如果它们有公共端点u，则称ei,ej相邻。边ei,ej称为u的关联边。 对于任一条边(vi,vj)属于E，如果边(vi,vj)端点无序，则它是无向边，此时图为无向图.图8-7是无向图.如果边(vi,vj)端点有序,即它表示以vi为始点,vj为终点的有向边(或称弧),这时图G称为有向图。 一条边的两个端点如果相同,称此边为环(自回路).如图8-7中的e1。 两个点之间多于一条边的，称为多重边,如图8-7中的e4,e5 。 定义 2 不含环和多重边的图称为简单图，含有多重边的图称为多重图。 有向图中两点之间有不同方向的两条边，不是多重边。 定义3 每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作Kn 。 每一对顶点间有且仅有一条有向边的简单图，称为有向完全图。 定义4 图G＝( V,E ) 的点集V可以分为两个非空子集X，Y，即XUY＝V,X∩Y＝f，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G＝( X,Y,E )。 例如图8-9中的(a)是明显的二部图，点集X：{v1,v3,v5)，Y：{v2,v4,v6}，(b)也是二部图，但是不像 (a)那样明显，改画为(c)时可以清楚地看出。 2. 顶点的次定义5 以点v为端点的边数叫做点v的次,记作deg(v),简记d(v)。 如图8-7中点v1的次d(v1)=4,因为边e1要计算两次。点v3的次d(v3)=4，点v4的次d(v4)=1。 次为1的点称为悬挂点,连接悬挂点的边称为悬挂边.如8-7图中v4,e6。 次为零的点称为孤立点，如图8-7中的点v5。次为奇数的点称为奇点。次为偶数的点称为偶点。 定理2 任何图中，次为奇数的顶点必为偶数个。证明：设V1和V2分别为G中奇点与偶点的集合(V1UV2=V).由定理1知 二、连通图 对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈，此时不考虑边的方向。而当链（圈）上的边方向相同时，称为道路（回路）。 图 8-13 中, S={v6,e6,v5,e8,v1,e9,v4,e10,v2,e3,v3}为一条链。 S1={v6 ,e6 ,v5 ,e7 ,v1 ,e9 ,v4 ,e4 ,v3}为一条道路。 S2={v1 ,e2 ,v2 ,e11 ,v4 ,e5 ,v5 ,e8 ,v1}为一个圈。 S3={v1 ,e2 ,v2 ,e10 ,v4 ,e5 ,v5 ,e7 ,v1}为一个回路。 三、图的矩阵表示 定义11 网络(赋权)图G=(V,E),其边(vi ,vj)有权wij，构造矩阵A=(ai j)n?n，其中 定义12 对于图G=(V,E),|V|=n,构造一个矩阵A=(aij)n?n,其中： 四、欧拉回路与中国邮路问题 1 .欧拉回路与道路 定义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图（E图）。 定理3 无向连通图G是欧拉图，当且仅当G中无奇点。 推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。 推论2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。 定理4 连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。 连通有向图G有欧拉道路，当且仅当这个图中除去两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个顶点 的入次比出次少1。 2. 中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？国际上通称这个问题为中国邮路问题。用图论的语言描述：给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。中国邮路问题也可以转为如下问题： 在连通图G=(V,E)中，求一个边集E1∈E，把G中属于E1的边均变为二重边得到图G*=G+E1，使其满足 G*无奇点,且L(E1)=Sl(e) (e∈E1)最小。 定理5 己知图G*=G+E1无奇点 ,则L(E1)=Sl(e) (e∈E1)最小的充分