论文部分内容阅读
在分子生物学中,DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型,因此,DNA图得到广泛的研究.为了读取DNA序列,Blazewicz等人提出了可(k,α)-标号有向图的概念,并称有向图D是DNA图,如果D是可(k,4)-标号的.2008年,原军等证明了可(k,α)-标号的有向路和有向圈的充要条件.本文证明了有向路和有向圈可(k,α)-标号的一个性质,并利用有向线图的理论证明了本文所指的伪二部单向完全图(D0)(A,B)、k部广义路(P)(V0,V1,…,Vk-1)、k部广义圈(C)(V0,V1,…,Vk-1)以及k部广义树(T)(V0,V1,…,Vk-1)均是DXA标号图.进而给出并证明了二部单向完全图(D)(V1,V2)和k部广义路(P)(V0,V1,…,Vk-1)为DNA图的充要条件.
2007年,Wang等(中国科学(A),37(9))得到了关于不包含环的DNA标号图的一个结果,在此基础上我们推广到一般有向图上,即任何无孤立点的有向图在友关系下恰有一个等价类的充要条件,并得出几个相应的改进结果.本文还给出了一个定理的反例,进而得到定理的修正和完善.由此容易推出Wang等的一个定理的必要条件也是充分的.
最后,我们给出了DNA图与DNA标号图之间关系的一个特征刻画.