用数学建模方法解决哥尼斯堡七桥问题

篇一：数学建模方法的应用

数学建模方法的应用

应用数学 ***

（广东惠州学院数学系****，广东惠州516007）

（E-mail: *******@qq.com）

摘要: 数学建模是培养学生应用数学能力, 培养学生的创造性的一种重要手段, 介绍了数

学建模的基本概念, 并通过实例说明数学建模的过程。 关键词：LP；IP；拉格朗日多项式插值

把数学应用到任何一个实际问题中去, 都需要把这个问题的内在规律运用数字、图表、公式、符号表示出来, 经过数学的处理, 得出供人们作出分析预报、决策或者控制的定量结果, 这个过程就是人们常说的建立数学模型。

一线性规划

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(LinearProgramming 简记LP)则是数学规划的一个重要分支。自从1947 年 G. B.Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

例 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标x，y表示，距离单位：km)及水泥日用量d(t)由下表给出.目前有两个临时料场位于A（5，1），B（2，7），日储量各有20t.假设从料场到工地之间均有直线道路相连，试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨公

?x,y?a,b水泥日用量为

模型 记工地的位置为ii，；料场位置为jj，

ec

日储量为j（j=1，2，分别表示A，B），从料场j向工地i的运送量为ij，这个优化问题的目标函数（总吨公里数）可表示为

j?1i?1

（1） 个工地的日用量必须满足，所以

di(i?1,2,...,6)

minf???cij(xj?ai)2?(yj?bi)2

2

26

j?1，i=1,2,...,6（2） 各料场的运送量不能超过日储量，所以

?c

ij

?dij

i?1 （3） 问题归结为在约束（2），（3）及决策变量非负的条件下，使（1）式最小.决策变

c

量只有ij，所以这是线性规划模型.

?c

6

ij

?eij,j?1,2

二、整数规划

规划中的变量（部分或全部）限制为整数时，称为整数规划（IP）。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

（一）整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1、 变量全限制为整数时，称纯（完全）整数规划。 2、变量部分限制为整数的，称混合整数规划。 整数规划特点

原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：

①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例 求解如下IP模型：

minz?5x1?8x2 s.t. x1?x2?6

5x1?9x2?45

x1,x2?0且为整数. 解 模型去掉整数限制后记作LP，其可行域为图中由点（0，0），（6，0），P（2.25，

z?zmax

3.75），（0，5）围成的四边形，过P点的等值线（图中虚线）为，最优解在P点取得.图中小圆点为整数点，四边形中的小圆点才是IP的可行解. 将P点舍入成整数或者找最靠近它的整数，都得不到IP的最优解.经在可行解中试探、比较得到下表: 表

可见IP最优解不一定能从LP经过简单的“移动 ”得到.求解整数规划没有统一的有效方法，不同方法的效果与问题的性质有很大关系.

三、非线性规划

实例与定义

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问 题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。

下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。

例 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金 A元，投资于第i(i = 1，...，n)个项目

ab

需花资金i元，并预计可收益i 元。试选择最佳投资方案。 解 设投资决策变量为

?1，决定投资第i个项目xi??

?0，决定不投资第i个项目 ，i=1，...，n， 则投资总额为

?ax，投资总收益为?bx。因为该公司至少要对一个项目投资

ii

ii

i?1

i?1

nn

，并且总的投

资金额不能超过A，故有限制条件

i?1

另外，由于xi(i?1，...，n)只取值0或1，所以还有

0??aixi?A

n

xi(1?xi)?0，i?1，...，n

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：

maxQ?

?bx

i?1ni?1

n

ii

?ax

n

ii

o??aixi?A

i?1

...，ns.t.xi?1?xi??0，i?1，

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问 题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式

min f (x)

h?x??0，j?1，...，q

s.t.j（NP）

g?x??0，i?1，...，p

i

T

x??x1...xn?其中 称为模型（NP）的决策变量，f 称为目标函数，gi?i?1，...，p?和hj?j?1，...，q?g?x??0

称为约束函数。另外，i（i=1，...,p）称

h?0?j?1,...,q?为等式约束，j称为不等式的约束。

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点： （i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基

础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。

（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化 或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或

“坏”的价值标准，并用某种数量形式来描述它。 （iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些

不等式或等式来表示。

四、拉格朗日多项式插值

1、插值多项式

用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数 f (x)在

x,x,...,xny?f?xi??i?0,1,...,n?区间[a,b]上n +1个不同点01处的函数值i，求一个

至多n 次多项式

??x??a0?a1x?...?anxnn （1）

使其在给定点处与 f (x)同值，即满足插值条件

??x??f?xi??yi?i?0,1,...,n? （2）

ni

?n?x? 称为插值多项式，xi?i?0,1,...,n?称为插值节点，简称节点，[a,b]称为插值区

?x,f?xi???i?0,1,...,n?，作一

间。从几何上看，n次多项式插值就是过n +1个点i条

y??n?x?多项式曲线 近似曲线 y = f (x)。

n次多项式（1）有n +1个待定系数，由插值条件（2）恰好给出n +1个方程

记此方程组的系数矩阵为 A ，则

x0

det?A??

x1.

.xn

x0x1.xn

222

?a0?a1x0?a2x02?...?anx0n?y0?2n

?a0?a1x1?a2x1?...?anx1?y1?

?................................................?a?ax?ax2?...?axn?y

2nnnn?01n

（3）

...x0....

x1.

nn

x,x,...,xn

是范德蒙特(Vandermonde)行列式。当01 互不相同时，此行列式值不为零。因此方程组（3）有唯一解。这表明，只要n +1个节点互不相同，满足插值要求（2）的插值多项式（1）是唯一的。 插值多项式与被插函数之间的差

R?x??f?x???n?x?n

称为截断误差，又称为插值余项。当 f (x)充分光滑时，

f?n?1????Rn?x??f?x??Ln?x???n?1?x?,???a,b?n?1!

j?0

其中。

2、拉格朗日插值多项式

实际上比较方便的作法不是解方程（3）求待定系数，而是先构造一组基函数

?x?x0?...?x?xi?1??x?xi?1?...?x?xn?li?x??

xi?x0...xi?xi?1xi?xi?1...xi?xn...xn

n

?n?1?x????x?xj?

n

??

j?0j?1

n

x?xjxi?xj

,?i?0,1,...,n?

li?x?

是n 次多项式，满足

?0,j?i

li?xj???

?1,j?i

n

n

?n?

x?xj??

Ln?x???yili?x???yi???

x?xi?0i?0j??j?0ij?i??

上式称为n次 Lagrange 插值多项式，由方程（3）解的唯一性，n +1个节点的n次

Lagrange 插值多项式存在唯一。

五、图与网络模型及方法

篇二：第7章算法程序与计算系统之灵魂练习题答案解析

第7章 算法:程序与计算系统之灵魂

1、算法就是一个有穷规则的集合，其中之规则规定了解决某一特定类型问题的一个运算序列。回答下列问题。

(1)关于算法的特性，下列说法不正确的是_____。

(A)算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；

(B)算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性；

(C)算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；

(D)算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性；

(E)上述说法有不正确的；

答案：C

解释：

本题考查对算法基本性质的理解

（C）算法的输出性：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。因此（C）选项错误。其余选项，（A）（B）（D）分别是对算法的有穷性，确定性和能行性的正确描述。

具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。

(2)关于算法的命题，下列说法不正确的是_____。

(A)算法规定了任务执行/问题求解的一系列、有限的步骤。

(B)算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的。

(C)算法可以没有输入，但必须有输出。

(D)算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成。

答案：B

解释：

本题考查对算法基本性质的理解

（B）违反了算法的有穷性：一个算法在执行有穷步规则之后必须结束。因此（B）选项错误。其余选项，（A）（C）（D）分别是对算法的有穷性，输入输出性和确定性的正确描述。 具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。

(3)关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。

(A)算法是解决问题的步骤，某个问题可能有多个求解算法；

(B)算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行；

(C)算法只能由高级（计算机）语言实现，不能通过机器语言实现；

(D)求解问题的多个算法不一定获得相同的解。

答案：C

解释：

本题考查对算法基本性质的理解

（C）算法是解决问题的步骤，执行的语言是步骤书写的规范、语法规则、标准的集合 是人和计算机都能理解的语言，不仅是高级语言。因此（C）选项错误。其余选项，（A）正确，解决问题的算法可以有多个。（B）选项，程序是算法的实现方式，正确。（D）选项，算法有优劣，对于同一个问题，获得的解可能不同。

具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。

(4)算法是计算系统的灵魂，为什么？不正确的是_____。

(A)计算系统是执行程序的系统，而程序是用计算机语言表达的算法；

(B)一个问题的求解可以通过构造算法来解决，“是否会编程序”本质上章是“能否想出求解该问题的算法”；

(C)一个算法不仅可以解决一个具体问题，它可以在变换输入输出的情况下，求解一个问题系列；

(D)问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛。

(E)上述说法有不正确的；

答案：D

解释：

本题考查算法、程序与系统之间的关系

（D）选项，算法是计算系统的灵魂，因此系统和算法的关系是：系统是龙，算法是睛，好的算法能起到画龙点睛的效果。（A）（B）（C）选项描述正确。

具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。

2、哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答下列问题。

//本题考查问题及其数学建模的作用

(a)

(1)哥尼斯堡七桥问题的路径能够找到吗？ _____。

(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。 (b)

答案：B

解释：

本题考查问题及其数学建模的作用

选择（B），根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中应为0个）。该问题中将四个岛抽象成4个点，每条桥抽象成边，可知图中奇点个数是4个，因此不可能找到。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(2)对河流隔开的m块陆地上建造的n座桥梁，能否找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径呢？ _____。

(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。

答案：C

解释：

本题考查问题及其数学建模的作用

选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。该问题中将m个岛抽象成m个点，每条桥抽象成边，但图中奇点个数未知，因此不能做判断。

具体内容参考第七章视频之“算法与算法类问题的求解，第七章课件或查阅欧拉回路相关资料。

(3)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_____。

(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；

(B)每个顶点的度应为偶数；

(C)既需要满足(A)又需要满足(B)；

(D)上述条件还不够，还需满足更多条件。

答案：C

解释：

本题考查问题及其数学建模的作用

选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。该问题中将m个岛抽象成m个点，每条桥抽象成边，因此应该选择C。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(4)下面所示的图(c)，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？

(c)

(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。

答案：B

解释：

本题考查问题及其数学建模的作用

选择（B）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。图中奇点是C与G，个数为2，不符合要求，因此应该选择B。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(5)参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？

(A)BG边； (B)AG边； (C)CG边； (D)AD边； (E)DE边。

答案：C

解释：

本题考查问题及其数学建模的作用

选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2（该题中因为起点和终点是一个，所以奇点个数应为0个）。图中奇点是C与G，个数为2，不符合要求，因此在CG间增加一条边，将寄点数变成0可满足要求，因此应该选择C。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(6-1)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。

(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；

(B)每个顶点的度应为偶数；

(C)既需要满足(A)又需要满足(B)；

(D)不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径；

答案：D

解释：

本题考查问题及其数学建模的作用

选择（D），此题未要求回到原地，即起点和终点可以不是一个，那么可以有2个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2。不同时满足（A）（B），可以有2个顶点的度为奇数，也可以满足题目要求，因此应该选择D。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(6-2)对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。

(A)m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；

(B)每个顶点的度应为偶数，或者，只有两个顶点的度为奇数而其他顶点的度均为偶数；

(C)既需要满足(A)又需要满足(B)；

(D)不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径；

答案：C

解释：

本题考查问题及其数学建模的作用

选择（C），此题未要求回到原地，即起点和终点可以不是一个，那么可以有2个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点”（相连的边的个数为奇数的点）个数是0或2。因此应该选择C。

具体内容参考第七章视频之“数学建模与算法策略设计--算法思想”，第七章课件或查阅欧拉回路相关资料。

(7)下面所示的图(d)和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？

(d)

(A)图(d)和图(e)都一定不能找到；

(B)图(d)一定能够找到；图(e)一定不能找到；

(C)图(d)一定不能找到；图(e)一定能够找到；

(D)图(d)和图(e)都一定能够找到； (e)

篇三：数学建模数学的巧妙运用

第4章 数学的巧妙应用

[教学目的和要求]

通过一些简单的问题，让学生尝试怎样把数学应用到实际问题中，培养和发挥学生的创造性思维。

[教学内容]

问题：

1. 棋子颜色的变化

任意拿出黑白两种颜色的棋子共8个，排成如下图所示的一个圆圈。然后在两颗颜色相同的棋子中间放一颗黑色棋子，在两颗颜色不同的棋子中间放一颗白色棋子，放完后撤掉原来所放的棋子。在重复以上的过程，这样放一圈后就拿走前次的一圈棋子，问这样重复进行下去各棋子的颜色会怎样变化呢？

2. 跑步问题

在任何一个5min的时间去件内均不跑500m，问10min能否恰好跑完1000m？

3. 铺瓷砖问题

要用40快方形瓷砖铺如下图所示形状的地面，但当时市场上只有长方形瓷砖，

每块大小等于方形的两块。一人买了20块长方形瓷砖，试着铺地面，结果弄来弄去始终无法铺好。试问是这人的工夫不到家还是这个问题根本无解呢？

铺瓷砖地面

4. 七桥问题

18世纪，普鲁士哥尼斯堡镇上有一个小岛，岛旁流过一条河的两条支流，七座

桥跨在河的两支流上（如下图）。

假设A表示岛，B表示河的左岸，C表示右岸，D为两支流间地区，a,b,c,d,e,f,g

分别表示七座桥。

问一个人能否经过每座桥一次且恰好经过每座桥一次并且最后回到原出发点？

图：哥尼斯七桥

5. 相识问题

在6人的集会上，假定认识是相互的，则总能找到或者3个人相互都认识，或

者3个人谁都不认识谁。请问这个结论正确吗？

6. 夫妻过河问题

有三对夫妻要过河，船至多可载2人，条件是任一女子不能在其丈夫不在场的

情况下与另外的男子在一起，问如何安排这3对夫妻过河。

解答：

1． 棋子颜色的变化

这个问题似乎和数学没有关系，纯粹是游戏性的东西。但我们完全可以用数学的推理方法说明最多经过8次变换，各棋子的颜色都会变黑.注意到我们的规则是同色的棋子中间加黑色棋子，两异色的棋子中间加白色棋子，即黑黑得黑，白白得黑，黑白得白，用+1表示黑，-1表示白，则这与+1、-1之间的乘法运算是一致的，开始摆的8颗棋子记为a1,a2,a3,a4,a5,a6,a7,a，我们仅关心的是棋子的颜色，故ak?+1或-1，8

k?1,2,…，8，下一次在a1与a2中间摆的棋子的颜色由a1a2决定，类似的akak?1正好给出了所放棋子的颜色，这样一次次地放下去，各次的颜色均可由下面的数确定：

第0次 a1a2 a3 a4 a5 a6 a7 a8

第1次 a1a2 a2a3a3a4a4a5a5a6a6a7a7a8 a8a1

222第2次 a1a a2a a3a4a5 … … a8a12a2 2a33a4

33333第三次 a1a2a3a4 a2a3a4a5 … … a8a13a2a3

… … … … … …

182856705628182856705628第八次 a1 8 a 1 … …a8 7 a8a2a3a4a5a6a7aa1a2a3a4a5a6a

在原来的基础上，最多经过8次变换以后，各个数都变成了+1，这意味着所有旗子都是黑色，且以后重复上述过程，颜色也就不再变化了。

2． 跑步问题

设[0，t]内跑过的距离为s(t)，则s(t)是t的连续非减函数，假设在10分钟之内能够跑1000m，则有s(0)?0，s(10)?1000，令f(t)?s(t?5)?s(t)?500,f(t)就是t的连续函数，f(0)=s(5)?500，f(5)?500?s(5)，因f(0)f(5)??(500?s(5))2?0，故由连续函数的介值定理，必有t1?[0,5],使f(t1)?0,即s(t1?5)-s(t1)?500，与题意矛盾，所以假设错误，题目中提出的要求无法实现。

3． 瓷砖问题

首先讨论用20块长方形瓷砖铺成题中图所示地面的可能性。

为此，在图上黑白相间地染色。然后仔细观察，发现工有19个白格和21个黑格。一块长方形瓷砖可以盖住一黑一白两个方块两个方块。所以铺上19块长方形瓷砖后，总要剩下2个黑格无法铺，因一块长方形瓷砖是无法盖住两个黑格的，唯一的解决办法是把最后一块瓷砖分为两个正方形瓷砖去盖住两个黑格。

解决这一问题时所用的方法在数学上称为奇偶检验，即可认为图黑色的格子是偶

数，涂白色的格子是奇数，同色的格子有相同的奇偶性，一块长方形瓷砖显然只能覆盖奇偶性相反的一对方格，因此把19块瓷砖在地面上铺好后，只有在剩下的两个方格具有相反的奇偶性时，才可能把最后一块长方形瓷砖铺上。由于剩下的两个方格具有相同的奇偶性，因此无法铺上最后一块瓷砖。

4． 七桥问题

建模 既然岛与陆地无非是桥梁连接的，那么就不妨把4处地点缩小（抽象）成4个点，并把7座桥缩小（抽象）成7条边，便得到七桥问题的模拟图（如下），于是七桥问题就等价为一笔画出上述图形的问题（每条边必须且只须经过一次）。

图：七桥模拟图

欧拉解决七桥问题是先考虑一般化问题：如果给定任意一个河道图与任意河道图与任意多座桥，可否判断每座桥能否恰好走过一次呢？一般化的问题就要有一个一般解法，才有更实际的意义，考查一笔画的结构特征，有个起点和终点（起点和终点重合时即为欧拉图）。除起点与终点处，一笔中出现在交点处的边总是一进一出的，故交点的度数总和为偶数，由此欧拉给出一般结论：

（1） 连接奇数个桥的陆地仅有一个或超过两个以上，不能实现一笔画。

（2） 连接奇数个桥的陆地仅有两个时，则从两者任一陆地出发，则从两者任一陆地

出发，可以实现一笔画而停在另一陆地。

（3） 每个陆地都连接有偶数个桥时，则从任一陆地出发都能实现一笔画，而回到出

发点。

对于模拟图，显然图必须是连通的，当且仅当图为欧拉图时，一笔画问题才能实现，由图可以知道，问题无解。

5． 相识问题

本问题也可以通过图论获解。

用6个点（记为u1,u2,u3,u4,u5,u6）表示6个人，若两个人相互认识，就在相应的两个点之间连一条边，则此图补图的一条边就表示对应于它的关联顶点的人相互不认识，于是问题转化为须证下列命题：

对于一个任意的具有6个顶点的简单图G，要么这图本身要么它的补图含有一个三角形（即具有3个顶点的完全图K3）

.

图：相识图

不妨考虑u1与其余的5个顶点不在G中相邻就在中相邻，因此在G中或在中，至少与三个点相邻，不妨假设在G中，有边u1u2,u1u3,u1u4?E(G)，见下图

（1） 若u2,u3,u4这3个点有两个点在G中相邻，比如说u2u3?E(G)，则有

u1,u2,u3这3个顶点的完全图K3即为所求。

（2） 若u2,u3,u4这3个顶点任两个点在G中不相邻，则在中，则u2,u3,u4这

3个顶点的完全图K3即为所求。

由此，问题得到解决。

6． 夫妻过河问题

用向量(H,W)表示有H个男人和W个女人在左岸，其中0?H,W?3.

（1） 可取状态：一共10个，它们是

(0,i),(i,i),(3,i)i?0,1,2,3

其中(i,i)表示i对夫妻.

（2） 可取运载：取可取运载向量为

(?1)k(m,n)

其中m,n?0,1,2，且1?m?n?2，k?1,2,….当k为奇数时，负向量表示过河；当k为偶数时，正向量表示从对岸返回来。

（3） 可取运算：按普通向量加法运算，一次过河就相当于一个可取状态向量与

一个可取运载向量相加.

问题转化为：由初始状态(3,3)经多少次（奇数次）可取运算才能转化为状态(0,0).

可以验证，经11次可取运算即可完成：

去2女回1女去2女 (三对夫妻)????（3男1女）????（3男两女）????（3男）

留一对夫妻回一对夫妻去2男????（3男1女）????（1男1女）?????（2男2女）????（2女）回1女去2男

??? ?（3女）????（1女）????（2女）????（无人）计算机求解：

记可取状态集合和可取运载集合分别为 回1女去2女回1女去2女

S?{(0,i),(i,i),(3,i),i?0,1,2,3}

D?{(m,n)|1?m?n?2,m,n?0,1,2}

并用s1(m,n),s2(m,n),…(sk?S)表示状态的变化过程，dk(m,n)(dk?D)表示状态sk(m,n)下的过河方案，当k为奇数时，dk表示从左岸到右岸，当k为偶数时，表示从右岸到左岸。状态转移满足如下关系：

本文来源：https://www.bwwdw.com/article/uppb.html