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

Crossing Numbers of Graphs With at Most Nine Vertices

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

Using the algorithm CCN( Calculate Crossing Number ) invented by the author of this paper ,we investigate the crossing numbers of all graphs for n≤9. Since the crossing numbers of graph equal the sum of the crossing numbers of all its 2 connected blocks, we work on the crossing numbers of graphs for n≤9 with unique 2 connected block. In this paper, three correlative results are given: 1) The average crossing number of graph with n vertices and q edges can be signified approximately by quadratic equation of q. 2) The average crossing number of graphs with bigger girth is greater than that with smaller girth within given vertices and edges. 3) The average crossing number of r regular graphs greater than that of non regular graphs within given vertices and edges where n is odd or r≤n/2.