|
|||||
|
|
| 四正则图的交叉数 | |
| 引用本文： | 杨元生,王丹,陆维明. 四正则图的交叉数[J]. 软件学报, 2002, 13(12): 2259-2266 |
| 作者姓名： | 杨元生 王丹 陆维明 |
| 作者单位： | 1. 大连理工大学计算机科学与工程系,辽宁,大连,116023;中国科学院数学与系统科学研究院,北京100080 2. 大连理工大学计算机科学与工程系,辽宁,大连,116023 3. 中国科学院数学与系统科学研究院,北京100080 |
| 基金项目： | 国家自然科学基金资助项目(60073013;60143002);中国科学院数学与系统科学研究院基金资助 |
| 摘 要： | 利用计算机对图的交叉数进行研究,给出了利用分支界限法计算图的交叉数的算法CCN(calculatecrossing number),并利用该算法计算出n≤12的所有四正则图的交叉数以及n≤16的随机四正则图的交叉数.同时计算出n≤12的所有四正则图的平均交叉数Aac(n)和n≤16的随机四正则图的平均交叉数Aac(n),根据计算结果提出四正则图的平均交叉数为O(n |
| 关 键 词： | 交叉数 正则图 同构 平面图 分支界限法 |
| 文章编号： | 1000-9825/2002/13(12)2259-08 |
| 收稿时间： | 2001-01-17 |
| 修稿时间： | 2001-01-17 |
The Crossing Number of 4-Regular Graphs |
|
| YANG Yuan-sheng,WANG Dan and LU Wei-ming. The Crossing Number of 4-Regular Graphs[J]. Journal of Software, 2002, 13(12): 2259-2266 | |
| Authors: | YANG Yuan-sheng WANG Dan LU Wei-ming |
| Abstract: | |
| Keywords: | crossing number regular graph isomorphic plane graph branch and bound method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《软件学报》浏览原始摘要信息 | |
| 点击此处可从《软件学报》下载全文 | |