当前位置：文档之家 › 图论模型的构建共42页文档

图论模型的构建共42页文档

  • 格式：ppt
  • 大小：5.13 MB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

图论模型

图论模型

图论模型此模型解决的是垃圾清运路线的最佳方案。

1、收集路线方案：用中国邮递员问题解决达到最佳经济效益和环保效果的垃圾清运路线问题是在车辆限载约束条件下的最优路径选择的问题，同时本项目涉及到深圳市南山区38个垃圾中转站，而每个中转站所覆盖的收集区域的选取需要满足最大覆盖域（即总体能够消耗最少资源来覆盖整片区域），收集区域的划分又要同时考虑实地情况（地形、路线、用地性质、人流量、垃圾量等）。

1.1模型建立：为简化问题讨论，在转运站覆盖区域的划分的问题上，需要运用“最大覆盖”及“模糊划分”的思想，具体划分出每个转运站所对应 的片区的近似最优划分。

将问题简化后，所要求解的问题就是每个垃圾中转站所对应的每个小分区的街道所构成的收集网络的垃圾收运车辆优化路线的问题，也就是要求每一条街道至少有一辆垃圾收运车经过并且车辆重复走过的街道的总长度最小化的问题。

对于这个问题，我们采用图论模型，将每个小分区的街道及收集点简化成网络图（也叫赋权图）。

对于网络图中的圈用圈点来表示，计算各个圈点的垃圾量（也即围成圈的街道上的垃圾量的和），将相邻（有公共顶点）的圈点用线连接起来，这就构成了圈点图。

遵循以垃圾中转站为圆心沿径向发散求最小生成树的原则将圈点图中相邻的圈点组块，使得每块的垃圾量近似于垃圾收运车载限，对应于圈点分块，网络图分开成了各个子网络图，对于每一个子网络图即可利用欧拉回路求得其最小路径线路。

现在给出最短欧拉回路求解举例：图代表的是其中一个收集子网络图，其中直线表示车辆需要经过的街道，线上的数字表示该街道的长度，该子网络图各条街道的垃圾量之和近似于收集车辆的载限。

现要求的是车辆经过每一条街道至少一次的最短回路，现在对这个问题分步求解：第一步：找出图中的奇点，如图中橙色小圆点所在处为奇点。

第二步：将各对奇点沿街道连接起来，使得连接奇点的所有街道总长度最小。

如下图绿色线条：第三步：得出经过每条街道至少一次的最短路径长度为所有街道的总长加上连接奇点的街道的长度。

图论模型的构建

图论模型的构建
为此，我们必须寻找解决问题的更好途径。
【方形柱体堆砌问题分析】
对符合要求的方形柱体来讲，交换任意两个正 方体的上下位置，得到的方形柱体仍是符合要求的， 即它的4个侧面都有4种颜色。它的每一对对面由4 个正方体各一个对面组成，因此问题的要素是4个正 方体各3个对面的颜色的构成，于是从每个对面的着 色考虑。用字母b,g,r,y分别表示蓝、绿、红、黄4种 颜色，并作为图的4个 顶点，4个正方体的各三个对 面依各对面的颜色连以边，并分别标以e1、e2、e3、 e4，比如第一个正方体有一对面着蓝、黄两色，则 从顶点b到y引一条边标以e1,另两对面为红对红、红 对绿，故联结r,e和r,g,均标以 e1。同样地根据第二、 三、四正方体的各对面着色分别连以边并分别标以 e2 、e3、e4。则得图G，如图1—3所示。
si<si+p
(0≤i≤n-p)
si+q<si
(0≤i≤n-q)
【奇怪的数列分析】
下面，我们把每个si抽象成一个点，则根据上述两个不 等式可以建立一个有向图，图中共有n+1个顶点，分别 为s0，s1，……，sn。若si>sj(0≤i，j≤n)，则从si往sj 引出一条有向边。例如对于n=6，p=5，q=3的情况， 我们可以建立图4
begin
if i+p<=n then begin
g[i+p，i]=1；
d[i]=d[i]+1；
end；
if i+q<=n then begin
g[i，i+q]=1；
d[i+q]=d[i+q]+1；
end；
end；
【奇怪的数列分析】
显然，按照上面的定义，如果建立的图可以拓扑排序，其 顶点的拓扑序列可以对应满足条件的整数数列；反之，不 存在这样的整数数列。 算法框架为：

图论模型

图论模型

d v j min d v j , d v3 w3 j
2

4
7
4

8
8
∞
∞
3
7
2
4
v2
3 7
v3
5 1
v7
8
4 2
v1
1
2
7
3
v5
4
3
6
v4
4
v6
6
v8
d(vj) v1 v2 v3 v4 v5 7 v6 4 v7 v8 ∞ 9 3 8 8
d v j min d v j , d v4 w4 j
v1
1
v5
v4
v6
v8
Edsger· Wybe· Dijkstra
———结构程序设计之父
contents
1. Dijkstra简介 2. 杰出成就 3. 获得的奖项 4. 生平经历 5. Dijkstra的经典言论
南京邮电大学
简介
艾兹格· 迪科斯彻，荷兰人。 计算机科学家，毕业并就职于 W· 荷兰莱顿大学，早年钻研物理及数学，而后转为计算机学。 迪科斯彻于1930年5月11日生于鹿特丹，他的父亲是一位化学 家，他的母亲是一位数学家，这种充满科学气息的家庭背景 对于他的职业生涯乃至他的整个人生都有着深刻的影响。 迪科斯彻是计算机先驱之一，开发了程序设计的框架结构。曾 经提出“goto有害论” ，解决了有趣的“哲学家聚餐”问题 ，提出了目前离散数学应用广泛的最短路径算法。与唐纳德
南岸
1736年欧拉把这个问题的物理背景变换并简化为一种 数学设计（称作图）：即把每一块陆地用一个点来代 替，将每一座桥用连接相应的两个点的一条线来代替， 从而相当于得到一个图。欧拉证明了这个问题没有解， 并指出欧几里得几何并不适用于这个问题，因为桥不 涉及“大小”，也不能用“量化计算”来解决。

图论模型实例优秀课件

图论模型实例优秀课件
▪ 几个优化原则 ▪ 扩环原则 子图有孤立枝，扩环后权值应减小 ▪ 增环原则 环路上某个顶点有两枝，且有使两枝成环的边
存在，考虑增环，增环后权值应减小 ▪ 换枝原则 环路上某顶点长出一条枝，该枝末梢和环路另
一顶点接近，可考虑换枝
问题1的分析与求解--最小生成树法
问题1的分析与求解 --TSP方法
公路边的数字为该路段的公里数.
问题分析：
本题给出了某县的公路网络图，要求的是在不 同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡 镇、村之间的公路看作此图对应顶点间的边，各条 公路的长度（或行驶时间）看作对应边上的权，所 给公路网就转化为加权网络图，问题就转化图论中 一类称之为旅行售货员问题，即在给定的加权网络 图中寻找从给定点O出发，行遍所有顶点至少一次 再回到点O，使得总权（路程或时间）最小.
图论模型实例
专题
❖ 图的表示与锁具问题 ❖ 最小生成树、TSP和灾区巡视问题 ❖ 最短路、网络流和运输问题 ❖ 作业
图的表示与锁具问题
不积硅步，无以至千里 --荀子·劝学
图的矩阵表示
邻接矩阵: (以下均假设图为简单图).
1) 对无向图 G，其邻接矩阵 A(aij)，其中：
1, aij 0,
若vi与vj相邻 , 若vi与vj不相.邻
i1
定义 称
为最大容许均衡度.
为该分组的实际均衡度.
显然0 0 1，0越小，说明分组的均衡性越 好. 取定一个 后，0与 满足条件 3）的分组是
一个均衡分组. 条件 4）表示总巡视路线最短.
此问题包含两方面：a)对顶点分组, b)在每组中求 (单个售货员)最佳旅行售货员回路.
因单个售货员的最佳旅行售货员回路问题不存在多 项式时间内的精确算法.因此多个售货员的最佳旅行售 货员回路问题也不存在多项式时间内的精确算法.

图论模型(最优连线问题最短路问题)PPT课件

图论模型(最优连线问题最短路问题)PPT课件
择的边组成图为无圈图，②新选边是满足①的尽可能 小的权。
（3）当（2）不能继续执行时停止。
（其思想是：在剩余边集中找边权最小的边添加到生成树中，同时又 不能产生回路即以局部的最优谋求全局的最优。）
上述的描述实际上是最小生成树的逐 步生长过程，上例的最小生成树如下：
A 5
1 3
D
8 E
水厂
9
B 7
6 10
著名数学家欧拉
七桥问题
图的基本概念
无 向 图
1 定义：由顶点和边组成的图形称为图。 有 向 图
赋
权
图
2 边e与顶点u、v相关联。顶点u与v相邻。
e
u
边e1与e2相邻。
e1
v
e2
u=v时，边e称为环。
3度
定义：与顶点v关联的边的数目称为顶点的度数， 记为d(v)。（注：环算2度。）
对于有向图的顶点的度数，还可分为出度 d ( v ) 和 入度 d ( v ) 。
u3
u6
0 8
1
6
u8
5
10
5
2
6
1
1
u4
10
u7
第五步：min{8,11,11,9,8,12,7,11,11}，u3。
u2
1
2
u5
3
2
7
5
3
9
u1
u3
u6
0
8
7
1
6
u8
5
10
5
2
6
1
1
u4
10
u7
第六步：min{11,12,11,11,9}，u7。
u2
1
2

数学建模图论模型课件

数学建模图论模型课件

1, aij 0,
vij E; vij E.
0 1 0 1
A
0 1 1
0 0 0
1 0 1
0
1 0
21
无向图G的邻接矩阵A是一个对称矩阵.
0 1 1 1
A
1 1 1
0 1 0
1 0 1
0
1 0
⑵ 权矩阵 一个n阶赋权图G = (V, E, F)的权矩阵A = (aij ) n×n , 其中
矩阵A = (aij )n×m ,
其中 1,
若vi是ej的始点;
aij 1, 若vi是ej的终点;
0, 若vi与ej不关联.
有向图的关联矩阵每列的元素中有且仅有一个1,有且仅 有一个 - 1.
1 0 0 1 1 0 1
A
1 0 0
1 1 0
0 1 1
0 0 1
0 1 0
0 0
1 1
01
① V称为G的顶点集, V≠, 其元素称为顶点或结点, 简称点;
② E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如 果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.
如果V = {v1, v2, … , vn}是有限非空点集, 则称G为有限图或 n阶图.
如果E的每一条边都是无向边, 则称G为无向图(如图1); 如 果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称 G为混合图.
若v0 v1 … vm 是图G中从v0到vm的最短路, 则1≤k≤m, v0v1 … vk 必为G中从v0到vk的最短路.
即：最短路是一条路，且最短路的任一段也是最短路. 求非负赋权图G中某一点到其它各点最短路，一般用 Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般 用Floyd算法. 这两种算法均适用于有向非负赋权图. 下面分别介绍两种算法的基本过程.

数学建模-图论模型

数学建模-图论模型

思路分析
• 每学期任课老师都有一定工作量的要求往往可能要上不止一门课 程。
• 每位同学需要在学期内完成若干门课程的学习。 • 某些对上课设施有特殊要求的课程，也不可以安排在同一时间。 • 为了方便开展一些全校性的活动，有些时段不安排课程。 • 受到教室数量的限制，在同一时段无法安排太多的课程。
模型建立
• 以每个课程为顶点，任何两个顶点之间连一条边当且仅当两门课 程的任课老师为同一人，或有学生同时选了这两门课或上课教室 冲突。
• 那么一个合理的课程安排就是将图中的点进行分化，使得每一个 部分里的点为一个独立集。
• 通过极小覆盖找出图中的极 大独立集，然后删去该极大 独立集，在剩下的图中找出 极大独立集，直到剩下的图 为一个独立集。
匈牙利算法
• 饱和点：Ｍ是图Ｇ的一个匹配，若Ｇ中顶点ｖ是Ｍ中某条边的端 点，则称Ｍ饱和ｖ,否则称ｖ是Ｍ的非饱和点。
• 可扩路：一条连接两个非饱和点x和y的由Ｍ外的边和Ｍ的边交错 组成的路称为Ｍ的(x,y)可扩路。
• 算法基本步骤：
Kuhn-Munkres算法
1.2 图的独立集应用
• 问题描述：各大学学期临近结束时，需要根据老师任课 计划和学生选课情况，再结合教室资源情况安排下一学 期的课程及上课时间和地点。下表所示是某大学电信学 院的大三各专业部分课程情况。该学院每届学生按专业 分班，统一选课。另外，学院只有一间普通机房和一间 高级机房。那么应该如何合理地排这些课程呢?
则称其是双连通或强连通的。对于不是双连通的图，都可以分解成 若干个极大的双连通分支，且任意两分支之间的边是同向的。
举例：
• 右图所示竞赛图不是双连通的
•
为一条有向
的D哈密尔A顿路B。 C E

图论模型讲义

图论模型讲义

目录目录 (1)第8章图论模型 (1)8.1图的基本知识 (2)8.1.1图的相关定义 (2)8.1.2图的顶点的度 (3)8.1.3子图及运算 (4)8.1.4 图的连通性 (5)8.1.5一些特殊图 (7)8.2图的矩阵表示 (7)8.2.1邻接矩阵 (7)8.2.2 关联矩阵 (8)8.3图的方法建模 (9)8.3.1 图的最小生成树问题及算法 (10)1．树及最小生成树 (10)2．克鲁斯卡尔算法 (11)3．普利姆算法 (13)8.3.2图的最短路问题及算法 (15)1．迪克斯特拉算法 (15)8.3.3图的匹配及应用 (20)1. 图的匹配 (20)2．指派问题： (23)3．最优指派 (27)8.3.4 图的覆盖及应用 (33)1. 逻辑算法 (34)2．启发式算法： (35)3．利用关联矩阵求极小覆盖： (37)8.3.5图的遍历问题 (38)1．边的遍历-中国邮差问题 (38)2．点的遍历-旅行商问题 (41)8.3.6 竞赛图问题 (48)1．竞赛图的定义 (48)2．循环比赛排名 (50)8.4 实战篇 (51)第8章图论模型图论（Graph Theory）18世纪起源于欧洲。

瑞士著名数学家欧拉(Euler）于1736 年发表的第一篇图论论文—“哥尼斯堡七桥问题”，不但解决了曾经困扰了人们多年的难题，同时它宣告了图论这门学科的诞生。

在普鲁士的小镇哥尼斯堡，一条河穿城而过，河中央有两个小岛，小岛之间及岛与河岸共有七座桥连接。

能否从四块陆地中的任何一处出发，恰好通过每座桥一次再回到起点，这就是著名的“哥尼斯堡七桥问题”。

人们曾经做过很多尝试，但是都没有获得成功。

为了解决这个问题，欧拉将问题进行几何抽象：将陆地分别用“点”代替，将桥用连接这些点的“线”来代替，得到一个包含四个“点”，七条“线”的“图”，将问题转化为“如何从一点出发一笔画出这个图，最后回到起点”的问题。

因为每次经过一个点必须消耗掉两条与该点相关联的边（从一边进入，另一条边离开），所以和每个点相关联的边的数量应该是一个偶数，此问题显然是无解的。

数学建模方法之图论模型

数学建模方法之图论模型
2) 在有向图中，从顶点v引出的边的数目称为顶点 v的出度，记为d+(v)，从顶点v引入的边的数目称为 v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数．
定理 d (v) 2.
vV
推论 任何图中奇点 的个数为偶数． d (v1) 4
d (u3) 1
d (u3) 2
一个顶点记为 ui1，置 Si1 Si {ui1}.
3) 若 i 1，则停Hale Waihona Puke ；若 i 1，则用 i+1 代
替i，并转2).
S0 {u0},l(u j ) , j 1,2,...,7.
u1 S0 l(u1) min{,0 1}
Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
G[{v1,v2,v3}] G[{e3,e4,e5,e6}]
3) 若 V V，且 V ，以 V 为顶点集，以两端点 均在V 中的边的全体为边集的图 G 的子图，称 为G的由V 导出的子图，记为 G[V ] .
4) 若E E，且 E ，以 E为边集，以 E 的端点 集为顶点集的图 G 的子图，称为 G 的由E 导出的
第二讲 图论模型
1. 问题引入与分析
2. 图论的基本概念
3. 最短路问题及算法
4. 最小生成树及算法
回
5. 旅行售货员问题
停
6. 模型建立与求解 下
1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的：
今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府 所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线.

图论建模方法

图论建模方法
• 定理10. 8设T是(n.m)非平凡图.则下列命题等价: • (1) T是树; (2)T无圈.m=n-1; • (3) T连通.m=n-1;(4)T无圈.任加一边有唯一圈; • (5)T连通.任去一边不连通;(6) T的任二顶点恰有一条路连通. • 由定理10. 8可直接导出下面的结果: • (1)树是边数最少的连通图; (2)连通图的极大无圈生成子图是生成树; • (3)连通图的极小连通生成子图是生成树. • 由此可见.在n个城市之间.修建n-1条直通高速公路足以形成连通的
• 称图G与图H同构.记为G= H.如果存在V (G)与V(H)的一一对应.同时存 在E(G)与E(H)的一一对应.且保持顶点与边的关联关系不变.例如.在图 10. 3中·图G与图H同构.同构的图可看成同一个图.只是顶点与边的标 号可能不同而已.
• 定义10. 3在无向图中.与顶点v关联的边的数目(环算两次)称为v的度. 记为dG (v).简记为d (v).对有向图.顶点v少的出关联边数称为出度.记 为dG' (v)或d' (v).人关联边数称为入度.记dG (v)或d(v).显然
• 我们可用定义或图形表示一个图.但注意到图的关联关系和邻接关系. 还可以用矩阵来表示一个图.从而更有利于计算机处理.
• 定义10. 5设G是(n.m)图·则以矩阵A = (aij) nx m表G的关联矩阵.其 中
• 以H=(hij )nx n表T邻接矩阵.其中hij为以顶点vi和vj为端点的边数(i,j =1.2...…n).
• 有n个顶点m条边的图称为(n,m)图.(n,0)图叫零图.特别地.(0,0)图叫空 图.(1 ,0)图叫平凡图.没有环与平行边的图称为简单图.任意两顶点都相 邻的简单图称为完全图.有n个顶点的完全图记为Kn.若V(G)能分解为 V1与V2,使得

第九章 图论模型

第九章 图论模型

第九章 图论模型现实世界的许多实际问题都可以用图形来解释或说明.例如通讯网络就可以用图的形式直观的表现出来：点可以表示通讯中心，而边表示通讯线路.图论模型是应用十分广泛的数学模型,它已经在物理、化学、控制论、信息论、科学管理和计算机等领域.由于它具有图形直观，方法简单容易掌握的特点，因此在实际、生活和数学建模中，有许多问题可以运用图论的理论和方法解决.§9.1图论起源图论起源于18世纪欧拉对哥尼斯堡七桥问题的研究.哥尼斯堡是18世纪东普鲁士的一个城市，城中有一条普雷格尔河，河中有两个岛，河上有七座桥，如图1所示.图1 当时那里的居民热终于思考这样一个问题，一个人能否经过七座桥且每座桥只走过一次，最后回到出发点.能否用数学的方法解决这个问题一贯成为当时居民的一个悬而未决的问题.1736年欧拉创造性的将陆地用点表示，桥用边表示，从而将这个问题转化为如图2所示的一笔画问题，即能否从某个点开始一笔画出这个图形，最后回到原点而不重复.欧拉证明了这个问题是不可能的.图2欧拉解决七桥问题时，其方法超出了常用的数学方法，充分发挥自己的想象力，用了全新的思想方法，从而使得问题得到完美解决.由于这一项开创性的工作，产生了“图论”这门崭新学科，欧拉被认为是图论的创始人.ABCDABCD1e 2e 5e 6e 7e 4e 3e§9.2基本概念定义1 图G 由两个点集合V 以及边集合E 组成，记为(),G V E =，其中： (1)V 是顶点构成的集合；(2)E 是连接某些顶点对构成的边组成的集合.例1 {}1234,,,V v v v v =，{}12232434,,,E e e e e =，画出图(),G V E =.图3注：图分为无向图和有向图.定义2 若图(),G V E =的边均没有方向，这样的图成为无向图.例如图2，图3为无向图.无向图的边称为无向边，无向边是由两个顶点构成的无序对，无序对通常用圆括号表示. 例2 (),i j v v 表示一条无向边，(),i j v v 与(),j i v v 是同一条边.定义3 若图(),G V E =的边均有方向，这样的图称为有向图.有向图的边称为有向边，有向边是由两个顶点构成的有序对，有序对通常用尖括号表示.有向边又称为弧. 例3,i j v v 表示一条有向边，,i j v v与,j i v v 是两条不同的有向边.定义4 一条边的端点称为与这条边关联，反之，一条边称为与它的端点关联.与同一条边关联的两个端点是邻接的.如果两边有一个公共端点，则这两条边是邻接的。

图论模型的建立

图论模型的建立

常州市第一中学 林厚从
图论建模
例1、奇怪的电梯（LIFT.???） 问题描述： 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层 楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼 层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了 Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2 楼。那么，从A楼到B楼至少要按几次按钮呢？
图论建模
[问题分析] 1、问题的数据规模只有200，所以很容易想到用搜索， 由于要输出最优解（要求的是最快的次数）,所以是宽搜。 2、对于A楼而言，实际上对它最多只能做2个操作， 上到A+X层或下到A-X层，当然前提是存在A+X或A-X层。显 然，如果把每一层楼看做一个顶点，如果A楼可以到B楼， 则从顶点A引一条到顶点B的边。对于样例，如下图：
常州市第一中学 林厚从
图论建模
例2、渡河问题（river） 一个人带了一只狼、一只羊和一棵白菜想要过河，河上有一只独木船， 每次除了人以外，只能带一样东西。另外如果人不在旁边时狼就要吃羊，羊 就要吃白菜。问：应该怎样安排渡河，才能做到既把所有东西带过河，在河 上来回的次数又最少呢？ [问题分析] 我们用变量M代表人、W代表狼、S代表羊、V代表白菜，∮代表空（什 么都没有）。开始时设人和所有东西都在左岸，这种情况用MWSV表示。 我们用一个集合表示目前左岸的情况，很明显，可能出现16种情况： [MWSV] [MWS] [MWV] [MSV] [WSV] [MW] [MS] [MV] [WS] [WV] [SV] [M] [W] [S] [V] [∮] 但要剔除掉6种可能发生狼吃羊和羊吃白菜的情况（红色），实际是10 种。下面我们就把这10种情况作为10个顶点，来构造一个无向图G，图G的边 按下列原则来定义：如果经过一次渡河，情况甲能变成情况乙，那么就在情 况甲与情况乙之间连一条边。得到下图：

NOI导刊-图论模型的构建

NOI导刊-图论模型的构建
• 例如，对于上图所示的有向图，可以得到下表：
• 所以，得到s0=0，s1=-3，s2=2，s3=-1，s4=-4，s5=1，s6=-2。再根据s的 定义，由： ai=(a0+a1+…+ai-1+ai) - (a0+a1+…＋ai-1)=si-si-1 ，求出：a1=s1s0=-3，a2=s2-s1=5，a3=s3-s2=-3，a4=s4-s3=-3，a5=s5-s4=5，a6=s6-s5=-3。显 然这个整数数列的任意连续５个整数之和为正，任意连续３个整数之 和为负。
一特点上。设si表示数列前i个整数之和，即si=a1+a2+…+ai。 其中s0=0 (0≤i≤n)。显然根据题意，有：
si<si+p
(0≤i≤n-p)
si+q<si
(0≤i≤n-q)
• 下面，我们把每个si抽象成一个点，则根据上述两个不等 式可以建立一个有向图，图中共有n+1个顶点，分别为s0， s1，……，sn。若si>sj(0≤i，j≤n)，则从si往sj引出一条有向边。
初步构图
• 如果Ai与Aj不相容，那么如果选择了Ai，必须选择 Aj‘ ；同样，如果选择了Aj，就必须选择Ai’ 。
Ai
Aj'
Aj
Ai‘
这样的两条边对称
• 我们从一个例子来看：
• 假设4个组，不和的代表为：1和4，2和3，7和3， 那么构图：
1
3
5
7
2
4
6
假设：
首先选1 3必须选，2不可选 8必须选，4、7不可选
分析：
• 原题可描述为： 有n个组，第i个组里有两个节点Ai, Ai' 。需要从每个 组中选出一个。而某些点不可以同时选出（称之为 不相容）。任务是保证选出的n个点都能两两相容。

(优选)第二讲图论模型Ppt

(优选)第二讲图论模型Ppt
定义 图G的阶是指图的顶点数|V(G)|, 用 v来表示； 图的边的数目|E(G)|用 来表示.
用 G (V (G), E(G)) 表示图，简记 G (V , E). 也用 viv j 来表示边 (vi ,v j ).
例设 G (V (G), E(G)) ， 其中：V (G) {v1,v2,v3,v4}， E(G) {e1,e2, e3,e4,e5,e6} ， e1 v1v1，e2 v2v3，e3 v1v3， e4 v1v4，e5 v3v4，e6 v3v4. （见图 2）
6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv.
7) 若V (G) X Y，X Y ，且X 中任意两顶点不
相邻，Y 中任意两顶点不相邻，则称为二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为 完全二部图或完全偶图,记为Km,n (m=|X|,n=|Y|)．
，
8) 图 K1,n 叫做星.
X : x1 x2 x3 X : x1 x2 x3
Y : y1 y2 y3 y4 Y : y1 y2 y3 y4
K1,4
K6
二部图
K3,4
2) 赋权图与子图
定义 若图 G (V (G), E(G)) 的每一条边e 都赋以 一个实数w(e)，称w(e)为边e的权，G 连同边上的权 称为赋权图.
定义 设 G (V , E)和 G (V , E)是两个图. 1) 若V V , E E ,称 G是 G 的一个子图,记 G G. 2) 若V V，E E ，则称 G是G的生成子图.
常用术语
1) 边和它的两端点称为互相关联.
2)与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边.
3) 端点重合为一点的边称为环， 端点不相同的边称为连杆.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。