最后更新: 2025-01-22 09:30 查看: 37 次反馈刷题

图论模型初步

我们可以用数学模型来抽象和简化现实世界，将一个现实世界中的问题 A 对应到一个便于思考或有求解方法的数学模型 B 。

图论模型是数学模型的一个分支。在图论模型中，顶点可以代表任何事物，如人，城市等；边表示顶点间的关系；因此图是关系的数学表示。而图论建模就是对一些客观事物进行抽象，化简，并用图来描述事物特征及内在联系的过程。

在前几节中已经给出了几个通过图论模型解决问题的实例。在本节中，将通过一些实例来初步说明如何利用图论模型求解问题。

例 8.6 一个部门有 25 人，对于某个问题，这 25 人存在着各自的看法，那么是否存在这样的情况：在这 25 个人中，每个人恰与另外 5 个人对该问题的看法一致？

利用图论模型求解问题，首先就要明确在建立一个图论模型时，这个图是什么？即什么是顶点？什么是边？

图是关系的数学表示，在本例中，顶点表示人，边表示两个顶点之间＂意见一致＂的关系，因此在两个＂意见一致＂的人对应的顶点之间有一条边。所以本例的图论模型由 25 个顶点组成，如果要求＂每个人恰与另外 5 个人对该问题的看法一致＂，则要求每个顶点的度数为 5 。由定理 8.3 可知，这样的图不存在，所以不存在这样的情况：＂在这 25 个人中，每个人恰与另外 5 个人对该问题的看法一致＂。

例 $8.7 n$ 支篮球队（ $n \geqslant 4$ ）进行比赛，比赛已经进行了 $n+1$ 场，则存在一个球队，它至少参加过 3 场比赛。
证明：首先，用图论模型表示这一问题：$n$ 个球队用 $n$ 个顶点表示；两个球队之间进行了一场比赛，则在相应的两个顶点之间有一条边相连。这样，原问题就转化为：图 $G$ 有 $n$ 个顶点 $(n \geqslant 4), n+1$ 条边，要求证明在图 $G$ 中存在顶点 $v, d(v) \geqslant 3$ 。

如果在图 $G$ 中不存在这样顶点 $v$ ，即在图 $G$ 中所有的顶点度数都是小于等于 2 ，因为图 $G$ 有 $n$ 个顶点，所以图 $G$ 的所有顶点度数之和小于或等于 $2 n$ ，又因图 $G$ 有 $n+1$ 条边，由定理 8.2 可知，图 $G$ 的所有顶点度数之和为 $2(n+1)$ 。因此导致矛盾，所以命题成立。

例 8.8 今有 $a, b, c, d, e, f, g 7$ 人，其中 $a$ 会讲英语；$b$ 会讲英语和汉语；$c$ 会讲英语，意大利语和俄语；$d$ 会讲日语和汉语；$e$ 会讲意大利语和西班牙语；$f$ 会讲法语，日语和俄语； $g$ 会讲法语和西班牙语；问这 7 个人应该如何安排圆桌座位，才能使每个人都能与他身边的人用同一种语言进行交谈？

也通过建立一个图论模型来表示这一问题：图 $G=(V, E)$ ，其中 $V=\{a, b, c, d, e, f, g\}, E=\{\{u$ ， $v\} \mid u, v \in V$ 且 $u, v$ 有共同语言 $\}$ 。这样，原问题就转化为在图 $G$ 中是否存在哈密顿回路的问题。

由上述三例，我们可以给出图问题分析与求解的技术小结：对现实的问题建立一个图论模型，首先需要决定顶点和边分别代表什么？在一个图论模型中，顶点通常用于表示对象，边通常表示对象之间的关系。通过对现实的问题建立一个图论模型，把现实的问题对应为一个便于思考和有求解方法的图论问题，从而解决问题。

下面，我们讨论比较复杂的图论模型问题。
例8．9 过河问题：某人携带一只羊，一只狼和一捆草过河。主人不在时，羊要吃草，狼要吃羊。船很小，每次摆渡主人只能带一个＂乘客＂。问：主人应如何将它们摆渡到彼岸，共有几种方案？

也可以建立一个图论模型表示这一问题：分别用 $M, S, W, G$ 表示主人，羊，狼和草。原岸所有的允许状态用点表示：原岸的原始状态为 $v_0=\{M, S, W, G\}$ ，原岸其余允许状态分别为 $v_1=\{M, S, W\}, v_2=\{M, S, G\}, v_3=\{M, W, G\}, v_4=\{M, S\}, v_5=\{W, G\}, v_6=\{G\}, v_7=\{W\}, v_8=\{S\}$ ，原岸的最终状态 $v_9=\varnothing$ 。过河问题就用带权有向图 $G=(V, E, g)$ 表示，其中 $V=\left\{v_0, v_1, v_2, \cdots, v_9\right\}$ ， $E=\{(u, v) \mid u, v \in V$ 且 $u$ 一步可达 $v\}, g$ 表示每条弧上的权为 1 。这样，过河问题就转化为用Dijkstra算法在带权有向图 $G$ 中寻找 $v_0$ 到 $v_9$ 的最短路问题。

例 8.10 有一条用彩色珠子做的漂亮项链。每个珠子由两种颜色组成，相继的两个珠子在邻接处共享一种颜色，如（green $\mid$ red）（red $\mid$ white）（white $\mid$ green）（green $\mid$ blue）。有一天，项链线断了，珠子撒了一地。我们收集了地上的珠子，但我们无法确定是否收齐。例如，如果我们收集了 5 颗珠子，珠子的情况是（green \｜red），（red｜white），（white \｜blue），（blue｜yellow）和（yellow｜black），则我们可以判定一些珠子遗失了；如果我们收集了 5 颗珠子，珠子的情况是（red｜green），（red｜red），（white｜blue），（white｜green）和（red｜blue），则这些珠子可以串接成（red｜green）（green｜white）（white｜blue）（blue｜red）（red｜red）。

现在，我们想知道用目前收集的珠子是否能够联成项链？

建立图模型的首要问题是：在图中什么为顶点？什么为边？如果以珠子为顶点，珠子串接的可能为边，则无法将问题的内容表达完全。如 3 颗珠子（red｜green），（red｜white）和（red｜ red），则在图中可以给出回路（green $\mid$ red）（red $\mid$ white）（red $\mid$ red），但得到的项链不符合题意。设图 $G=(V, E)$ ，每种颜色对应一个顶点，$V=\left\{v_1, v_2, \cdots, v_m\right\}$ ，每颗珠子对应一条边，若有珠子 $(c 1, c 2)$ ，就有无向边 $\left\{v_{c 1}, v_{c 2}\right\}$ 。收集的珠子是否能够联成项链的问题就转化为在图 $G$ 中是否存在欧拉链的问题。

例 8.11 国际象棋马的遍历问题：国际象棋棋盘是个正方形，由横纵各 8 格，颜色一黑一白交错排列的 64 个小方格组成，如图 8.15 所示。马的走发是先横走或直走一格，然后再斜走一格，即走法相似于字母＂L＂。现在的问题是：在国际象棋的棋盘上，马是否可以遍历，即它从任意一格出发，跳到每格一次且仅一次，最后又回到原来出发的那个格子？

首先考虑图的建模问题：以棋盘每格为顶点，仅当马从甲格能一步跳到乙格时，甲乙两格对应的顶点之间连一条边，这样构成的图称为＂马图＂。

![图片](/uploads/2025-01/e9d956.jpg)

所以国际象棋马的遍历问题就转化为马图是否为哈密顿图的问题。证明马图是哈密顿图留作习题。

图论在现实世界中还有许多的应用。比如超文本（Hypertexts），一个网页包含了到其他
网页的超链接，这样整个网络就可以表示为一个图，页面对应顶点，页面间的链接对应于相
应顶点间的弧，而设计一个搜索引擎就需要图处理算法。又比如，在大型软件系统中函数（模
块）之间调用关系也可以表示为一个图，分析调用关系图可以确定如何最好分配资源才能使
程序更有效率。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：最短路

下一篇：平面图与欧拉公式

本文对您是否有用？有用 (0) 无用 (0)