|
|||||
|
|
| 不超过9个顶点的所有图的交叉数 | |
| 引用本文： | 杨元生,孙艳春,陆维明. 不超过9个顶点的所有图的交叉数[J]. 小型微型计算机系统, 2003, 24(6): 954-958 |
| 作者姓名： | 杨元生 孙艳春 陆维明 |
| 作者单位： | 1. 大连理工大学,计算机系,辽宁,大连,116023;中国科学院,数学与系统科学研究院,数学所,北京,100080 2. 大连理工大学,计算机系,辽宁,大连,116023 3. 中国科学院,数学与系统科学研究院,数学所,北京,100080 |
| 基金项目： | 国家自然科学基金资助(60073013)并受中国科学院数学与系统科学研究院部分资助. |
| 摘 要： | 利用本文作者研制的计算图的交叉数的算法CCN(Calculate Crossing Number)，本文对n≤9的所有图的交叉数进行了研究．由于图的交叉数等于其所有二连通分支的交叉数的和，本文计算了n≤9的所有单二连通分支图的交叉数．并得出相关的规律：1)n个顶点q条边的单二连通分支图的平均交叉数Ave(n，q)可近似地表示为q的二次多项式，2)在给定顶点数n与边数q的单二连通分支图中围长较大的图的平均交叉数大于围长较小的图的平均交叉数，3)在给定顶点数n与边数q的单二连通分支图中当n为奇数或r≤n／2时，r正则图的平均交叉数大于非r正则图的平均交叉数． |
| 关 键 词： | 交叉数 正则图 围长 |
| 文章编号： | 1000-1220(2003)06-0954-05 |
Crossing Numbers of Graphs With at Most Nine Vertices |
|
| YANG Yuan sheng ,,SUN Yan chun ,LU Wei ming. Crossing Numbers of Graphs With at Most Nine Vertices[J]. Mini-micro Systems, 2003, 24(6): 954-958 | |
| Authors: | YANG Yuan sheng SUN Yan chun LU Wei ming |
| Affiliation: | YANG Yuan sheng 1,2,SUN Yan chun 1,LU Wei ming 2 1 |
| Abstract: | |
| Keywords: | crossing number regular graph girth |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |