整数流与子图覆盖

Integer flows and subgraph covers

整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函数值之和等于离开该点的边函数值之和.整数流理论与数学其他领域一些著名问题有一定的关联,如组合学的孤独跑步者、数论的丢番图逼近、几何学的视线阻碍和线性空间堆垒基等.四色问题还等价于平面图的偶子图覆盖问题:是否存在3个偶子图,覆盖一个2-边连通平面图的每条边恰好两次.著名的Fulkerson猜想认为,对每个2-边连通图(不必是平面图),存在6个偶子图,覆盖该图的每条边恰好4次.本文对整数流和子图覆盖这两个研究方向及相关问题的历史和现状作一个综述.

Integer flows and subgraph covers are two important subjects in graph theory. They are closely related to the famous four color problem, which is equivalent to the integer 4-flow problem in planar graphs. A graph has an integer k-flow if for some orientation, there is a function from its edge set to an abelian group such that at each vertex the sum of the values on the edges into the vertex is equal to the sum of the values on the edges out of the vertex. Integer flows are related to several well-known problems in other fields of mathematics, such as lonely runner problem in combinatorics, diophantine approximation in number theory, view obstruction in geometry and additive basis in linear vector space. Four color problem is also equivalent to the problem of Eulerian subgraph covering of planar graphs： Every 2-edge-connected planar graph has three Eulerian subgraphs covering each edge precisely twice. The well-known Fulkerson conjecture claims that every 2-edge-connected graph （not necessary to be planar） has six Eulerian subgraphs covering each edge precisely four times. In this paper, we shall give a brief survey of the two subjects and other related problems.