不超过9个顶点的所有图的交叉数

• 作者: 孙艳春 杨元生 陆维明
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 交叉数 正则图 围长
• 年，卷（期）: 2003,（6）
• 页码范围: 954-958
• 页数: 5页
• 分类号: TP18
• 字数: 2334字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2003.06.003

摘要

利用本文作者研制的计算图的交叉数的算法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正则图的平均交叉数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙艳春	大连理工大学计算机系	1	8	1.0	1.0