一些DNA图的标号  

The Labelings of Some DNA Graphs

作　　者：原军[1] 王世英[1] 刘爱霞[1] 

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《中北大学学报（自然科学版）》2008年第1期4-7,共4页Journal of North University of China(Natural Science Edition)

基　　金：国家自然科学基金资助项目(1047108)

摘　　要：为了读取DNA序列,Blazewicz等人提出了(α,k)-可标号的有向图的概念,称有向图D是DNA图若D是(4,k)-可标号的.基于此,证明了(α,k)-可标号的有向路和有向圈的充要条件.设T是一棵只有一个入(出)度为0的点的定向树,还证明了T是(α,k)-可标号的有向图的必要条件和T是DNA图的充要条件.In order to read a DNA sequence, Blazewicz et al. propose the definition of （α,k）-labeled digraphs. A digraph D is called a DNA graph if D is （4,k）-labeled. Sufficient and necessary conditions for directed paths and directed cycles to be （α,k）-labeled are proved. Let T be an oriented tree with only one vertex u satisfied that the in（out）-degree of u is 0. A necessary condition for T to be （α,k）-labeled and a sufficient and necessary condition for T to be a DNA graph are also proved.

关 键 词：DNA图 DE BRUIJN有向图 有向线图 

分 类 号：O157.5[理学—数学]