| 一类循环图中的Eulerian定向数 |
| |
| 引用本文： | 张远平,沈小玲.一类循环图中的Eulerian定向数[J].数学的实践与认识,2007,37(13):114-117. |
| |
| 作者姓名： | 张远平 沈小玲 |
| |
| 作者单位： | 1. 兰州理工大学,计算机与通信学院,兰州,730050
2. 湖南师范大学,数学与计算机科学学院,长沙,410081 |
| |
| 基金项目： | 兰州理工大学校科研和教改项目;甘肃省自然科学基金 |
| |
| 摘 要： | 一般的图中Eulerian定向数的计数是#P-完全问题,但对于某些特殊图中的Eulerian定向数给出精确计数是完全有可能的.通过拆分解构的方法可以找到与一类循环图中Eulerian定向数有关的递推关系,从而给出该数的精确计数.前人的工作在于给出了一些近似估计.
|
| 关 键 词： | Eulerian定向数 #P-完全问题 循环图 |
| 修稿时间： | 2005年3月10日 |
Counting the Eulerian Orientations of One Class of Circulant Graphs |
| |
| ZHANG Yuan-ping,SHEN Xiao-ling.Counting the Eulerian Orientations of One Class of Circulant Graphs[J].Mathematics in Practice and Theory,2007,37(13):114-117. |
| |
| Authors: | ZHANG Yuan-ping SHEN Xiao-ling |
| |
| Abstract: | Even though counting Eulerian orientations in general graphs is #P-complete problem,it is possible to count Eulerian orientations in some special graphs explicitly.By disassembling and unhooking circulant links we can find the recurrence relation for the number of Eulerian orientations of one class of circulant graphs,so to give the explicit counting.The previous work devoted to give some approximate estimations. |
| |
| Keywords: | number of Eulerian orientations #P-complete problem circulant graphs |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
