整数流与子图覆盖

发布时间：2018-10-08 15:59

【摘要】：整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函数值之和等于离开该点的边函数值之和.整数流理论与数学其他领域一些著名问题有一定的关联,如组合学的孤独跑步者、数论的丢番图逼近、几何学的视线阻碍和线性空间堆垒基等.四色问题还等价于平面图的偶子图覆盖问题:是否存在3个偶子图,覆盖一个2-边连通平面图的每条边恰好两次.著名的Fulkerson猜想认为,对每个2-边连通图(不必是平面图),存在6个偶子图,覆盖该图的每条边恰好4次.本文对整数流和子图覆盖这两个研究方向及相关问题的历史和现状作一个综述.
[Abstract]:Integer flow and subgraph coverage are two important research directions in the field of graph theory and are closely related to the famous four-color problem. The four-color problem is equivalent to the integer 4-flow problem of planar graphs. A graph has an integer k-stream if and only if there is a function from the edge set to the k-order commutative group for some direction of the graph such that the sum of the values of the edge functions entering the point is equal to the sum of the values of the edge functions leaving the point. The theory of integer flow is related to some famous problems in other fields of mathematics, such as solitary runners in combinatorial theory, Diophantine approximation in number theory, visual obstruction in geometry, and stacking of bases in linear space, and so on. The four-color problem is also equivalent to the dual subgraph covering problem of a planar graph: whether there are three pairs of subgraphs covering each edge of a 2-edge-connected planar graph is exactly twice. The famous Fulkerson conjecture holds that for every 2-edge-connected graph (not necessarily a planar graph), there are six even subgraphs covering each edge of the graph exactly four times. In this paper, the history and present situation of integer flow and subgraph covering are reviewed.
【作者单位】：福州大学离散数学研究中心;
【基金】：国家自然科学基金(批准号:11331003)资助项目
【分类号】：O157.5

【相似文献】