图论模型的构建

格式：pptx
大小：2.05 MB
文档页数：25

下载文档原格式

图论模型的构建

为此，我们必须寻找解决问题的更好途径。
【方形柱体堆砌问题分析】
对符合要求的方形柱体来讲，交换任意两个正方体的上下位置，得到的方形柱体仍是符合要求的，即它的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；
【奇怪的数列分析】
显然，按照上面的定义，如果建立的图可以拓扑排序，其顶点的拓扑序列可以对应满足条件的整数数列；反之，不存在这样的整数数列。算法框架为：

数学建模-图论模型

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

图论方法及其建模

95-B
天车与冶炼炉的作业调度 — 动态规划、排队
论、图论
97-B
98-B
截断切割的最优排列 — 随机模拟、图论
灾情巡视的最佳路线 — 图论、组合优化
99-B
07-B
钻井布局 — 0-1规划、图论
乘公交,看奥运 — 双目标规划、图论图论 0-1规划
5
11-B 交巡警服务平台的设置与调度
13
设 Pt { p1 , p2 , p3 , p4 } 是 t 时刻运行的程序集合，
Rt {r1 , r2 , r3 , r4 } 是 t 时刻所需的资源集合．资源的分配状况如下： p1 占有资源 r4 且申请资源 r1； p2 占有资源 r1 且申请资源 r2 及 r3； p3 占有资源 r2 且申请资源 r3； p4 占有资源 r3 且申请资源 r1 及 r4 ．它们的资源分配情况可用
25
2、根树
一棵非平凡的有向树，如果恰有一个结点的入度为0，其余结点的入度均为1，则称此有向树为根树. 入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点。
习惯上我们把根树的根画在最上方，叶画在下方，有向边的方向均指向下方，这样就可以省去全部箭头。
26
3、欧拉图
如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。
(4) 有向图 G 是(弱)连通图当且仅当以它的邻接矩阵
A
A AT 作为邻接矩阵而得到及其转置 A 的布尔和
T
的可达矩阵的元素全为 1。
21
另外，也可以利用图的可达性矩阵判断有无回路：图G中存在回路当且仅当它的可达性矩阵的主对角元不全为零。也可以利用可达矩阵求出无向图的连通分支等。

图论数学模型

关于工序流程图画法的说明
• （1） “拆卸”，“清洗”等这些具体工作称为工序，用实箭线“→”来表示。工序名称写在箭线上方，完成这项工序的时间写在箭线下面，箭线的方向代表了工序时间的流向 . • （2）工序之间交接处表示的圆圈称为事项或结点，用以标志前面工序的结束和允许后面工序的开始，是工序完成或开始的瞬间符号，具有承上启下、把工序衔接起来的作用 . • （3）若 A 工序必须在 B 工序完成之后才有条件进行，则称 A 是 B 的紧后工序，或称 B 是 A 的紧前工序 . 另外，同一对结点间不能表示两个及其以上个工序，如图 2 － 21 （左图）的画法是不允许的，为此引进了虚工序概念而将此表示式画成图 2 － 21 （右图）的形式 .
• 解：TCP;ABS;RD
• 例 3 工程流程图 • （第五届北京高中数学知识应用竞赛题） • 机床的大修有如下的工作项目：拆卸③，清洗④，电器检修④，部件检查①，零件加工④，零件修理⑤，床身和工作台研合②，部件组装（不含电器）②，变速器组装①，试车③ . • 1. 画出工序的流程图，即用图表示出各项工作的衔接关系 . • 2. 假定大修期间没有耽误任何时间，并把开始拆卸时刻记为 0 ，试问：大修完成的时刻最早是多少？ • 3. 在不影响最短时间完工的条件下，每个工作项目最早和最迟开工时间各是多少？
第二章
图论数学模型及其应用
2.3 建立图模型解决实际问题的趣例
• 例 1 节目排序问题 • 一场文艺演出共有 8 个节目 , 全体演员中有 10 人须参加两个以上的节目演出 , 情况如表，表中的√号所示 , 如演员 1 要参加三个节目 A 、 B 和 H. 若节目主办单位希望首尾两个节目为 A 和 H, 或为 H 和 A, 并且希望每个演员不连续参加两个节目的演出 , 试为主办单位安排一个节目顺序表 .

5、图论模型的建立

图论建模
信息学竞赛解题的一个重要步骤是数学建模，如几何模型、代数模型、运筹学模型等。图论模型的构造（图论建模）也是数学建模的一个分支。在建立一个问题的模型之前，首先要对研究对象进行全面的调查，将原型理想化、简单化（对于竞赛而言，这一步大部分已经由命题者完成）；然后对原型进行初步的分析，分清其中的各个要素及求解目标，理出它们之间的联系；然后用恰当的模型来描述这些要素及联系。
图论建模
[问题分析] 1、问题的数据规模只有200，所以很容易想到用搜索，由于要输出最优解（要求的是最快的次数）,所以是宽搜。 2、对于A楼而言，实际上对它最多只能做2个操作，上到A+X层或下到A-X层，当然前提是存在A+X或A-X层。显然，如果把每一层楼看做一个顶点，如果A楼可以到B楼，则从顶点A引一条到顶点B的边。对于样例，如下图：
下面，我们把每个si抽象成一个点，则根据上述两个不等式可以建立一个有向图，图中共有n+1个顶点，分别为 s0 ，s1 ，……，sn 。若 si>sj(0≤i， j≤n)，则从si往sj引出一条有向边。例如对于n=6，p=5，q=3的情况，我们可以建立下图。
常州市第一中学林厚从
图论建模
图论模型和其它模型在研究方法上有着很大的不同，例如可以运用典型的图论算法来对图论模型进行求解，或是根据图论的基本理论来分析图论模型的性质，这些特殊的算法和理论都是其它模型所不具备的，而且在其它模型中，能用类似于图这种直观的结构来描述的也很少。
常州市第一中学林厚从
是指对一些客观事物进行抽象、化简，并利用图来描述事物特征及其内在联系的过程。建立图论模型的目的和建立其它数学模型一样，都是为了简化问题，突出要点，以便更深入地研究问题的本质；它的求解目标可以是最优化问题，也可以是存在性或构造性问题；并且和几何模型、运筹学模型一样，在建立图论模型的过程中，也需要用到集合、映射、函数等基本的数学概念和工具。

图论基础知识

常州市第一中学林厚从
图论算法与实现
一、图论基础知识
4、图的遍历：对下面两个图分别进行深度优先遍历，写出遍历结果。注意：分别从a和V1出发。
左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f 右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7
邻接矩阵
边集数组
邻接表
优点O（1）
存储稀疏图时，空间效率比较好，也比较直观
便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为O(e/n)
存储稀疏图，会造成很大的空间浪费
不适合对顶点的运算和对任意一条边的运算
要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O （n+e）。可以用十字邻接表改进
被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。
图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。图的深度优先遍历：类似于树的先序遍历。从图中某个顶点Vi出发，访问此顶点并作已访问标记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。
常州市第一中学林厚从
图论算法与实现
一、图论基础知识
4、图的遍历：对于一个连通图，深度优先遍历的递归过程如下：
Procedure dfs(i:integer)； {图用邻接矩阵存储} Begin
访问顶点i； Visited[i]:=True； For j:=1 to n do {按深度优先搜索的顺序遍历与i相关联的所有顶点}

图论建模方法

• 定理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,使得

图论模型的建立

常州市第一中学林厚从
图论建模
例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导刊-图论模型的构建

• 例如，对于上图所示的有向图，可以得到下表：
• 所以，得到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

定义图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、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

图论模型的构建
•
•二．图论建模方法
1. 要素的选取
• 在建立模型之前，我们首先要对研究对象进
行全面的调查，将原型理想化、简单化；然后对
原型进行初步的分析，分清其中的各个要素及求
解目标，理出它们之间的联系；下一步就是用恰
当的模型来描述这些要素及联系。
• 【例1】渡河问题
•
一个人带了一只狼、一只羊和一筐白菜想要
•e
•e3
4
•
•2. 选择合适的理论体系
• 图由点、边、权三部分组成，根据这三部分的性质的不同，就有着不同的图论模型，有着不同的理论和算法，也就构成了不同的理论体系。图论建模依据的是图论的基本理论和基本算法。
• 例如二分图把整个点集V分为两个子集，规定子集内部的点之间没有边，因此二分图就有着不同于一般图的特殊性质，而它的匹配算法也就比一般图的算法简单；此外还有树、有向无环图等，它们属于不同的理论体系，有着各自不同的性质，适于用不同的算法求解。
•问题的求解目标：求河上往返次数最少的渡河方案。
• 对于要素（1），用字母m代表人，w代表狼，s代表羊，v代表白菜。 • 要素（2）、（3）可抽象为开始时设人和其他三样东西在河的左岸，这种情况用集合{mwsv}表示。在过河过程中左岸出现的情况有以下16种： •{wmsv} {mws} {mwv} {msv} {wsv} {mw} {ms} {mv} •{ws} {wv} {sv} {m} {s} {v} {w} {φ}
过河。河上有一只小船，每次除了人以外，只能
带一样东西。另外，如果人不在时狼就会吃掉羊
，羊就要吃白菜。问怎样安排渡河，才能做到既
把所有东西都带过河，而且在河上往返次数最少
？
•
•问题的要素有三点：（1）人及他所带的3样东西；（ 2）人不在时狼就会吃掉羊，羊就要吃白菜，即人在渡河时，一岸上不能同时留下狼和羊或羊和白菜；（3）人每次至多带一样东西渡河，并要保证岸上的安全。
形柱体，堆成的方形柱体每个侧面4种颜色都有。
•求解任务：1、这4个正方体能否堆成符合要求的方形柱体？
•
2、若能，找出一种堆砌方法。
•
•【方形柱体堆砌问题分析】
• 一个正方体有6个面，所以4个正方体可以堆砌出为数十分可观的不同状态。就是确定了4个正方体依Ⅰ，Ⅱ，Ⅲ，Ⅳ次序从上到下排列，只考虑两两接触面不同，也有6^4=1296种排列，这里还没有考虑4个侧面的不同组合。若考虑到后者，又会衍生出许多各异的形式，先令第Ⅰ个正方体保持不动，Ⅱ，Ⅲ，Ⅳ正方体个有4个侧面，故有4^3=64 种状态。因此即使在从上到下按序排列情况下，仍然有1296×64=82944种状态。若用穷举法求这类问题，将是不胜其烦的。 •为此，我们必须寻找解决问题的更好途径。
•
•权的加入使图论模型和求解目标变得更加复杂多样
•
有的权则表示容量或是流量，它们的运算特征是“
串联求最值，并联求和”，即一条路径上最大或是最小
的权决定了整条路径的权，而求解目标则是求图中或是
两点之间所有路径的权的加和。
•
还有的图不仅包含边权（边集E到实数集R的映射
），还包含点权（点集V到实数集R的映射）；或是包
•
•问题的求解目标就归结为：在图G中找一条连接顶点mwsv与 φ，并且包含边数最少的路径。把图的边长设为1，那么渡河问题归结为求顶点mwsv到顶点φ的最短路径问题。
•
•【例2】方形柱体堆砌
• 有4个正立方体，它们的6个侧面各着以绿、蓝、红、黄4
种颜色之一，如图1-2所示。现在要把这4个正方体堆成一方
•
•剔除下述6种可能发生狼吃羊，羊吃白菜的情况：（注意照顾右岸的情况） •{wsv} {ws} {sv} {mw} {mv} {m} •将剩下的10种情况作为图G的顶点，图G的边是按下述规则来连接的：如果情况A经过一次渡河可以变成情况B，就在情况A与情况B之间连一条边。根据这一规则，构造的图G如下面所示：
含好几类不同性质的权。
•
有的权表示长度或是时间等等，它们的运算特征是
“串联求和，并联求最值”，即一条路径的权由这条路
径上每条边的权相加得到，求解目标往往是求图中或是
两点之间所有路径的权的最优值。
•
• 权的运算也会产生一些变形，例如权的运算由简单的相加、求最值扩展到相乘，或是更复杂的函数计算等等。
问给定的棋盘，最多可以放置多少个机器人，使
它们不能互相攻击。
• 空地 •E草m地ptGyrass
•墙 Wall
•
•【模型一】 • 在问题的原型中，草地，墙这些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：
•
•e4
•b
•e3
•e1 •e2
•e4 •e3
•y
•e2
•e3
•r
•e1
•从图中，能找到两个 •e2 Hamiltion回路，每个回路
•e1
的4条边分别是
•g •e4 •e1,e2,e3,e4 。
•(见下页 )
•
•e4
•b
•e3
•r
•e1
•e1 •e2
•e4
•e2
•e3
•e1
•y
•e2
•g
•
•【方形柱体堆砌问题分析 •】对符合要求的方形柱体来讲，交换任意两个正
方体的上下位置，得到的方形柱体仍是符合要求的，即它的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所示。
• 以上这些差异形成了图论模型的多样化，使图论模型可以广泛地适应各类问题，但这些丰富的选择同时也增加3】机器人布阵
•
有一个N*M(N,M<=50)的棋盘，棋盘的每
一格是三种类型之一：空地、草地、墙。机器人
只能放在空地上。在同一行或同一列的两个机器
人，若它们之间没有墙，则它们可以互相攻击。

图论模型的构建

合集下载