| 有向图的有向圈长分布 |
| |
| 引用本文： | 李炜[],施永兵[].有向图的有向圈长分布[J].上海师范大学学报(自然科学版),2003,32(2):23-27. |
| |
| 作者姓名： | 李炜[] 施永兵[] |
| |
| 作者单位： | 1. 英新达,上海,电子有限公司
2. 上海师范大学,数理信息学院,上海,200234 |
| |
| 基金项目： | Supported by the Foundation of the Development of Science and Technology of Shanghai Higher learing(02KD08) |
| |
| 摘 要： | 阶为v的有向图D的有向圈长分布是序列(c_1,c_2,…,c_v),其中C_i是D中长为i的有向圈的数目。设0≤x_i≤v-i-1,证明了存在v个顶点的有向图D,使D的有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1),并且给出了具有有向圈长分布为(0,0,x_1,x_2,…,x_(v-3),1)的有向图的最大可能的弧数以及具有有向圈长分布为(0,0,k,k,…,k,k-1,…,3,2,1)(其中1≤k≤v-2)的有向图的最小可能弧数的上界。
|
| 关 键 词： | 有向图 有向圈 圈长分布 |
Directed Cycle Length Distribution of Digraphs |
| |
| Abstract.Directed Cycle Length Distribution of Digraphs[J].Journal of Shanghai Normal University(Natural Sciences),2003,32(2):23-27. |
| |
| Authors: | Abstract |
| |
| Abstract: | The directed cycle length distribution(DCLD) of a digraph of order v is the sequence (c1,c2,...,cv), weher ci is the number of directed cycles of length i. Let 0≤xi≤v-i-1 for i=1,2,...,v-3. In this paper, we prove that there exists a digraph of order v such that its DCLD is (0,0,x1,x2,...,xv-3,1), determine the maximum possible number of arcs in a digraph whose DCLD is (0,0,x1,x2,...,xv-3,1) and obtain a upper bound of the mininum possible numbe of arcs in a digraph whose DCLD is (0,0,k,k,...,k,k-1,...,3,2,1) for 1≤k≤v-2. |
| |
| Keywords: | digraph directed cycle cycle length distribution |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《上海师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《上海师范大学学报(自然科学版)》下载免费的PDF全文 |
|
