关于图形的极大联数

在生产实践和科学实验的斗争中,我们好些时候会遇到这样的一个问题:对给定的一些联络点（比如军事据点、仓库、村镇等）,如何设计它们的联系线路（比如通讯线路）,使得它们相互之间的联系最紧密;把这个问题提炼成为数学问题,就如C.Berege在他所著的《图的理论及其应用》一书中所提出的一个没有解决的问题:“n个顶点m条边的图,其极大联数为何?”,对这个问题本文是这样解答的:首先找出一种具n个顶点的正则h次齐次（当n与h均为奇数时,为亚齐次）的图形,其中h是满足等式2m=nh q的正整数,然后将图形定义出一个运输网络,把求图形的h条互不相交的链转化为求运输网络的最大流量问题;由魏特内（Whitney）定理得知图形是h-联的,最后,在这种图形上添联一些边,直至图形具有m条边时为止,这样构作出来的图形便具极大联数h了。