东北大学秦皇岛分校数学与统计学院，河北 秦皇岛

收稿日期：2021年1月2日；录用日期：2021年2月2日；发布日期：2021年2月9日

摘要

本文对一道组合最值问题的更一般情况进行了猜测和证明，利用了图论方法证明满足要求的值不小于目标值，再利用归纳构造证明目标值是可行的。以此得到了Euclid辗转相除法与二部图的一个对应。

关键词

图论，最大连通图，映射，第二数学归纳法

A Correspondence between Euclid’s Division Method and Bipartite Graph

Changsong Jin, He Chen

School of Mathematics and Statistics, Northeastern University at Qinhuangdao, Qinhuangdao Hebei

Received: Jan. 2^nd, 2021; accepted: Feb. 2^nd, 2021; published: Feb. 9^th, 2021

ABSTRACT

This article guesses and proves a more general case of a combined maximum value problem. It uses graph theory to prove that the value that meets the requirements is not less than the target value, and then uses the induction structure to prove that the target value is feasible. In this way, a correspondence between Euclid’s division and bipartite graph is obtained.

Keywords:Graph Theory, Maximum Connected Graph, Mapping, Second Mathematical Induction

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

Euclid辗转相除法是对两正整数每次进行同一个操作，即一个数除以另一数，然后用所得余数代替原数，直到不能再进行操作。这一过程是可以类比归纳构造某个图的。笔者在思考一道组合最值问题时，发现了这样的图。

2. 预备知识 [1] [2] [3] [4]

图论是用来表示某类事物之间的联系的学科，通常是研究一个由若干不同顶点和连接其中某些顶点的边组成的图形。我们用点代表这些事物，用连接两点的边(或者不连接，或者给它们赋权)表示两个事物的特定联系。顶点和边的位置以及它们是否交叉等等情况都是不需要考虑的，我们关心的是图中顶点和边的组合情况。图论为任何一个包含了一种二元关系的系统提供了一个数学模型，利用图论的理论和方法可以对该模型求解。

一个由若干不同顶点和连接其中某些顶点的边组成的图形，通常记作 $G\left(V,E\right)$，其中是V所有顶点的集合，E是所有边的集合。

如果图中的两个顶点之间有边相连，则称它们相邻。

如果图中有两条边与同一顶点相连，则称这两条边相邻。

若中，存在点集满足且各自的顶点互不相邻，则称是二分图。

顶点的权在本文定义为它所有邻边的权之和。

3. 正文

3.1. 一道组合最值问题

有若干正整数，它们和为 $m\cdot n$，且既可以分为和相等的m个组，又可以分为和相等的n个组，求这些正整数个数的最小值 $f\left(m,n\right)$。

经过对一些较小的m和n的试验我们猜测 $f\left(m,n\right)$ 可能是 $m+n-\left(m,n\right)$ 。我们的证明如下：

3.2. 对下界的估计

我们将上述m + n个组看作平面上m+n个点，若其中的两个点所代表的组都含有 $f\left(m,n\right)$ 中的某个数，则在它们之间连一条边，这样就构成了一个简单图G。考虑其中最大的连通图G'，设其中和为m的点有s个，和为n的点有t个。显然每个数恰在一个和为m的组里，一个和为n的组里。对于图G涉及的点，其所在组里的正整数必定出现两次，否则一定可以再加进一个新的点与图T连通，与G'的最大性

矛盾。对这些数求和，得到ms = nt，于是其中点的个数为 $s+t=\frac{m+n}{x}$，这里 $x|\left(m,n\right)$ 因为图G'是连通图，所以图G'边个数 $\ge s+t-1$。

接下来重复上面的做法，考虑第二大连通图，依次进行下去。这样我们就可以得到图G的边数：

${\displaystyle \underset{x|\left(m,n\right)}{\sum }\left(\frac{m+n}{x}-1\right)}=m+n-{\displaystyle \underset{x|\left(m,n\right)}{\sum }\frac{1}{x}}\ge m+n-\left(m,n\right)$

由于图G的连线方法，如果两个点所代表的组都含有 $f\left(m,n\right)\ge m+n-\left(m,n\right)$ 中的某个数，则它们之间就连一条边，我们就将此正整数映射到这条边，得到映射 $\sigma$。注意到每个数恰在一个和为m的组里，一个和为n的组里，所以这样的映射 $\sigma$ 是合理的。显然此映射 $\sigma$ 是满射，所以点的个数不小于边的个数。

因此 $f\left(m,n\right)\ge m+n-\left(m,n\right)$。

3.3. 归构造解决存在性问题

对m + n作归纳构造，证明对任意正整数m，n，存在 $m+n-\left(m,n\right)$ 个正整数满足要求。

$m+n=\text{2}$ 时，取两个2即可。

假设 $m+n\le k$ 结论成立 $m+n=k+\text{1}$ 时，若m与n相等，取n个n即可；

若m与n不等，不妨设m > n， $m\cdot n=n^2+\left(m-n\right)\cdot n$。

由归纳假设，存在 $m-n+n-\left(m-n,n\right)=m-\left(m,n\right)$ 个数既可以分为和相等的m − n个组，又可以分为和相等的n个组，这些数再添上n个n，这样它们既可以分为和等于n的m − n + n个组，又可以分为和等于m − n + n的n个组，这样就满足 $m+n=k+\text{1}$ 时的构造。因此 $f\left(m,n\right)=m+n-\left(m,n\right)$。

综上所述 $f\left(m,n\right)=m+n-\left(m,n\right)$。

这样，对两个不同的正整数进行Euclid辗转相除法的过程，与我们上面的归纳构造得到的图是一一对应的。因为对这两个正整数每进行一次辗转相除，与上述的一次删去一些点与边的过程是相对应的。

而由上述对下界的估计知，归纳构造的图使f达到了最小值，一定有每个正整数和图G的边一一对应。将图中的顶点按权为m或n分类，可知道归纳构造图是一个二部图。

文章引用

金长松,陈 贺. Euclid辗转相除法与二部图的一个对应
A Correspondence between Euclid’s Division Method and Bipartite Graph[J]. 理论数学, 2021, 11(02): 219-221. https://doi.org/10.12677/PM.2021.112030

参考文献