运筹08(第六章图与网络分析)运筹学第五版课件(历史上最好的,最全面的课件)

运筹学第五版课件(历史上最好的,最全面的课件)

运筹学OPERATIONS RESEARCH

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

第六章 图与网络分析§ 1.图的基本概念与模型§ 2.树图和图的最小部分树

§ 3.最短路问题§ 4.网络的最大流 § 5.最小费用流

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

哥尼斯堡的七桥问题当地的居民热衷于这 样一个问题： 一个漫步者如何能够走过 这七座桥，并且每座桥只 能走过一次，最终回到原 出发地。 尽管试验者很多， 但是都没有成功。

A D

CB

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

为了寻找答案，1736年欧拉把 陆地缩为一点，把桥作为连接点的 边，将这个问题抽象成图形的一笔 画问题。即能否从某一点开始不重 复地一笔画出这个图形，最终回到 原点。欧拉在他的论文中证明了这 是不可能的，因为这个图形中每一 个顶点都与奇数条边相连接，不可 能将它一笔画出，这就是古典图论 中的第一个著名问题。

A D

CB

A

C

D

B

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

在实际的生产和生活中，人们为了反映事物之间的关系， 常常在纸上用点和线来画出各式各样的示意图。

例 有六支球队进行足球比赛，我们分别用点v1…v6 表示这六支球队，它们之间的比赛情况，也可以用图反 映出来，已知v1 队战胜v2 队，v2 队战胜v3队，v3 队战 胜 v5 队，如此等等。这个胜负情况，可以用下图所示 v v4 的有向图反映出来。 2

v1

v6

2013-8-6

v3

v5

运筹学第五版课件(历史上最好的,最全面的课件)

§6.1.图的基本概念与模型一、 基本概念图(graph)是由一些结点或顶点( nodes or vertices ) 以及连接点的边(edges)构成。记做G = {V,E },其中 V 是顶点的集合，E 是边的集合。

给图中的点和边赋以具体的含义和权值，我们称这样的 图为网络图(赋权图)

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

图中的点用 v 表示，边用 e 表示，对每条边可用它所 联结的点表示，如图，则有：

e1 = [v1 , v1],e2 = [v1 , v2]或e2= [v2 , v1]用点和点之间的线所构成的图，反映实际生产和 生活中的某些特定对象之间的特定关系。通常用 点表示研究对象,用点与点之间的线表示研究对象 之间的特定关系。一般情况下，图中点的相对位 置如何，点与点之间线的长短曲直，对于反映研 究对象之间的关系，显的并不重要，因此，图论 中的图与几何图，工程图等本质上是不同的。2013-8-6 7

运筹学第五版课件(历史上最好的,最全面的课件)

端点，关联边，相邻若边 e 可表示为e = [vi , vj],称 vi 和 vj 是边 e 的端点，同时称边 e 为点 vi 和 vj 的关联边，若点 vi ,

vj 与同一条边关联，称点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称边 ei 和 ej 相邻；

环，多重边，简单图如果边 e 的两个端点相重，称 该边为环，如果两个点之间的边多

于一条，称为具有多重边，对无环、 无多重边的图称为简单图。2013-8-6 8

运筹学第五版课件(历史上最好的,最全面的课件)

次，奇点，偶点，孤立点与某个点相关联的边的数目，称

为该点的次(或度、

线度),记作 d(v)。次为奇数的点称为奇点，次为偶数的 点称为偶点，次为零的点称为孤立点。如图：

奇点为 v5 , v3偶点为 v1 , v2 , v4 , v6 孤立点为 v6

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

链，圈，路，回路，连通图图中有些点和边的交替序列 μ={v0 , e1 , v1 ,

e2 , … , ek , vk},若其各边 e1 , e2 , … , ek 各不相 同，且任意 vi,t-1 , vit (2 ≤ t ≤ k)都相邻，称 μ 为链，如果链中所有的顶点 v0 , v1 , … , vk也不相同， 这样的链成为路，起点和终点重合的链称为圈，起点和终 点重合的路称为回路，若在一个图中，每一对顶点之间至少存在一条链，称 这样的图为连通图，否则称该图为 不连通的。 链 v1 , e2 , v2 , e4 , v3 , e7 , v4 , e6 , v2 , e5 , v3 路 圈2013-8-6

v1 , e2 , v2 , e4 , v3 , e7 , v4

v1 , e2 , v2 , e4 , v3 , e7 , v4 , e6 , v2 , e5 , v3 , e3 , v1 ,

运筹学第五版课件(历史上最好的,最全面的课件)

完全图，偶图一个简单图中若任意两点之间均有边相连，称这样的图为 完全图，含有 n 个顶点的完全图，其边数有 n(n 1) 条。 2 如果图的顶点能分成两个互不相交的非空集合 V1 和V2 ,

使在同一集合中任意两个顶点均不相邻，称这样的图为偶图 (也称二分图),如果偶图的顶点集合V1 和V2 之间的每一对 顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1 含m 个顶点，V2 含有 n 个顶点，则其边数共 m ·n 条。

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

子图，部分图图 G1={V1 , E1} 和 G2={V2 , E2},如果有 V1 V2 和 E1 E 2 ,称 G1 是 G2 的一个子图； 若有 V1 V2 , E1 E2 ,则称 G1 是 G2 的一个部分图。 注意：部分图也是子图，但子图不一定是部分图。 子图： 部分图

2013-8-6

运筹学第五版课件(历史上最好的,最全面的课件)

§2.树图和最小部分树树图(简 …… 此处隐藏：1392字，全部文档内容请下载后查看。喜欢就下载吧 ……