图论模型的建立与简单应用

徐乙富 张俸川 石少俭

摘 要：在近些年的ACM ICPC竞赛中，图论的题目屡见不鲜。图论中的图是由若干给定的点链接两点的线所构成的图形，这种图形常来用于描述某些事物之間的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。

关键词：图论模型；拓扑；欧拉路径

DOI：10.16640/j.cnki.37-1222/t.2018.23.090

0 前言

图论是数学的一个分支，它以图作为研究对象。图论中的图是由若干给定的点链接两点的线所构成的图形，这种图形常来用于描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。利用图论解题，通常具有高效、简洁的便利。有了这门工具，并不意味就能很好地解决问题，还在于我们能否熟练地识别与建立一系列的图论模型。本文通过一些实例，简单地介绍一下图论建模的方法与应用。并通过建立相关的模型来解决相对较为复杂的问题。

1 Cover（HDU）

1.1 题目大意

给一个有n个节点m条边的图，每个节点从1到n标号，题目给出m条边的连接情况（1<=n，m<=100000），问至少需要几笔可以走完所有的m条边，输出最少的笔画数目与每一笔所经过的边的编号。

1.2 分析

容易想到，这个题目需要将最少笔画数目转化为无向图的最小路径覆盖问题，然而，不同于常见的有向图二分图做法，需要建立一个欧拉路径或欧拉回路的模型。当一个连通块是欧拉路径（度数为奇数的顶点的数目为0或者2）时，可以一笔走完所有的边，所以将每个连通块转化为欧拉路径进行搜索，转化的方法是通过对度数为奇数的两点之间加边将连通块转化为欧拉路径。

1.3 步骤

（1）首先，我们应该根据题目的输入将无向图建立出来，由于顶点个数比较多，所以无法建立邻接矩阵，可以建立邻接表储存边的信息。（2）对于每一个连通块进行深度优先搜索，对于每一个连通块内度数为奇数的点，可以两两之间加一条边，这样，对于每一个连通块，最多要加入max（k/2，1）条边，（k为度数为奇数的点的个数）。（3）再次进行深度优先搜索，每次搜索到加入的边时，说明搜到一条路径，进行输出路径（可以用一个以为数组暂时保存路径并进行输出），这样，就正好输出了max（k/2，1）条的路径。

1.4 小结

通过分析相关的问题，将一个复杂的问题转化为构造欧拉路径的简单问题，建立了正确的模型。由此可见，对于问题正确的分析与认识，是建立模型，解决问题中至关重要的一步。本题所用到的欧拉路径模型，在竞赛中比较常见，是一个重要的解决问题的模型与方法。

2 Guess（UVA1423）

2.1 题目大意

给出一个n*n（N>1&&N;<=10）的上三角矩阵S，S[i][j]表示数列a从a[i]+...a[j]和的大小，要求我们求出a[1]到a[n]的所有值，即通过和的值求元素的值。

2.2 分析

首先想到应该求出sum[0]到sum[n]的值，输出即可，而sum[i]的值可以设置在0到10之间，这样的话，任意的sum[i]与sum[i-1]只差的绝对值不会超过10，满足了题目要求的任意a[i]的绝对值小于等于10。 重点在于，这样的前缀和可以转化为拓扑排序，把i看做节点，当a[i]加到a[j]的值大于0时，即sum[j]-sum[i-1]大于0，这样连一条从j到i-1的边，反之，连一条，从i-1到j的边，这样，最大的边入度为0，进行拓扑排序即可。

2.3 步骤

（1）首先，对于输入进行建图，当输入字符为‘+时，在j与i-1间加一条边，当输入字符为‘-时，在i-1到j间建一条边。（2）进行拓扑排序，对于n个点，每次找到入度为0的点 t ，将它的度数变为-1，并标记已经访问过这个点，将所有t指向的点的度数减一，每次记录sum[t]=now--，初始now为10。（3）根据拓扑排序求出的sum数组，求出最终的答案，即ans[i]=sum[i]-sum[i-1]。

2.4 小结

本道题目是一个比较抽象的题目，但是经过对于前缀和性质的认真分析，可以建立了拓扑排序这一模型，将一个复杂的问题转化为一个简单的拓扑过程，在ACM ICPC中，拓扑排序作为一个常见的模型，经常用于简化与解决复杂的问题。

3 结论

问题是千变万化的，如何建立问题的图论模型并没有通用的准则。前面的两个例子都比较简单，在更复杂的问题中，有时会感到难以建立适当的模型，这时，需要在不改变问题原型本身的性质的前提下，对原型进行抽象，简化，在此基础上建立合适，有效的模型。有时，建立了问题的一个模型之后，可能会感到难以求解，这时，可能需要对模型进行修改，转化，或者对原型进行更深入的分析，抽取其中较关键的要素，建立一个易于求解的模型。这些都需要有丰富的经验，灵活的思维以及良好的创造力。在ICPC比赛中，更是要求在规定的时间内可以正确的分析问题，建立相应的模型，并解决问题的能力。

参考文献：

[1]刘汝佳.算法竞赛入门经典.第2版[M].清华大学出版社，2014.

[2]巫泽俊.挑战程序设计竞赛[M].人民邮电出版社，2013.

[3]黄兰，鲁珍珍，尹倩华等.图论及其算法在数学建模中的应用[J].数学学习与研究，2016（05）：106-107.

[4]杨玉军，王大勇.图论在数学建模中的应用[J].教育现代化，2018

（04）.

作者简介：徐乙富（1997-），男，山东临沂人，本科，研究方向：ACM图论建模与应用。