| 摘要: |
| 利用计算机对图的交叉数进行研究,给出了利用分支界限法计算图的交叉数的算法CCN(calculatecrossing number),并利用该算法计算出n≤12的所有四正则图的交叉数以及n≤16的随机四正则图的交叉数.同时计算出n≤12的所有四正则图的平均交叉数Aac(n)和n≤16的随机四正则图的平均交叉数Aac(n),根据计算结果提出四正则图的平均交叉数为O(n
|
| 关键词: 交叉数 正则图 同构 平面图 分支界限法 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金资助项目(60073013;60143002);中国科学院数学与系统科学研究院基金资助 |
|
| The Crossing Number of 4-Regular Graphs |
|
YANG Yuan-sheng,WANG Dan,LU Wei-ming
|
| Abstract: |
| The CCN (calculate crossing number) algorithm using branch and bound method to calculate the crossing number of graph with small order is put forward to study the crossing number using computer. With the algorithm, the crossing number of all of the 4-regular graphs Aac(n) for n≤12 and the crossing number of some random 4-regular graphs Arc(n) for n≤16 are calculated. At the end of the paper, the average crossing number is shown, and a conjecture is given that the average crossing number of 4-regular graph is O(n2). |
| Key words: crossing number regular graph isomorphic plane graph branch and bound method |
