Eulid辗转相除法与二部图的一个对应

A Correspondence between Eulid’s Division Method and Bipartite Graph

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

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 Eulid’s division and bipartite graph is obtained.