Adm猜想初探

A RESEARCH FOR ADA'M'S CONJECTURE

有向图的Adam猜想是图论中的一个尚未解决的问题。本文根据有向图中含一已知弧的有向圈数目同这弧的从头到尾的有向路数目的相等关系得到Adam猜想的一个等价命题:若D是包含有向圈的有向图,则存在某弧,把它反向之后将减少D中有向圈的数目当且仅当在D中存在一条弧(v_i,v_j),满足r_(?)≤r_(ij),其中r_(ij)表示D中从点v_i到点v_j的有向路的数目。据此我们可以证明Adam猜想对满足一定条件的许多有向图是成立的。

Adam's conjecture for the digraph is a problem which is not resolved as yet in graph theory. According to the equal relation between the number of directed cycles with a known arc and the number of directed paths from the head to the tail of the arc in a digraph, the paper obtains the following equivalent proposition for Adam's conjecture: If D is a di graph which contains a directed cYcle, then there is some arc whose reversal decreases the number of directed cYcles in D if and only if there is some arc(v_i, v_i) such that r_(ij)≤r_(ji), where r_(ij) denotes the number of the directed paths from v to v in D. Thus the paper shows that the Adam's conjecture is tenable for many directed graphs which satisfies some specific conditions.