笛卡尔积图 的交叉数

目 录

中文题目    1

中文摘要、关键词    1

英文题目    1

英文摘要、关键词    1

前 言    3

     1 基本概念、性质和定理    4

     2 主要结果及证明    6

参考文献    25

致 谢    26
  
 
笛卡尔积图 的交叉数

摘要

在主圈不自相交的情况下，确定了笛卡尔积图 、 、 与 的交叉数.我们具体得到了以下结果： 的交叉数为6； 的交叉数为12； 的交叉数为8； 的交叉数为16.
 关键词：交叉数;笛卡尔积图;主圈;Pn;同胚.

The Crossing Numbers of and   

ABSTRACT

In this arcticle,we determine the crossing numbers of  ， ， and  when the main circle isn’t intersected .We obtained the results below: the crossing number of   is six; the crossing number of   is twelve; the crossing number of   is eight; the crossing number of   is sixteen.
Key words: Crossing number; Cartesian product; Main circle; Pn; Homeomorphism.

 
前 言

图论的广泛应用，促进了它自身的发展.20世纪40——60年代，拟阵理论、超图理论、极图理论以及代数理论、拓扑理论都有很大的发展.60——80年代期间，随着计算机科学的迅速发展和计算机应用的广泛普及，它的发展尤为迅速.它所涉及的领域包括物资结构、电气网络、信息传输、交通运输、城市规划、经济管理和计算机科学等几乎包括人类社会的所有领域.图论已经成为人们研究工程技术、自然科学甚至社会科学的一个重要工具.我国在50年代开始开展图论方面的工作，取得了许多可喜的成果.
图的交叉数问题是在实际应用中提出的.在历史上，图的交叉数概念起源于上世纪五十年代Turan的“砖厂问题”（Turan’Brickyard Problem），实际上Turan的“砖厂问题”等价于完全二部图 的交叉数问题 . 图的交叉数问题在CAD领域有着广阔的应用，如：草图的识别与重画、电子线路板设计中的布线、软件开发工具中文档部分ER图的自动生成、生物工程DNA图示等.
图的交叉数是图的一个重要参数.研究图的交叉数不仅具有重要的理论意义，而且具有较强的现实意义，如VTSL中的圈的布局问题.
图的交叉数问题属于NP——问题，目前已研究的交叉数问题主要是那些比较特殊的规律性较强的图，且仅有有限的交叉数得到了精确值.目前我们只知道一些特殊图类的交叉数，如少数完全二部图、圈与圈以及路与顶点数较少的图的笛卡尔积图、循环图以及Petersen 图等. 他们研究的方法主要是对一些图形的交叉数的猜想进行证明和对前人的一些成果加以推广，并取得了新的进展；还有些是利用算法计算图的交叉数.
由于画法的任意性，使得能够确定交叉数的图类非常少，本文根据交叉数问题的理论知识，讨论笛卡尔积图 、 、 与 的交叉数.具体得到了以下结果： 的交叉数为6、 的交叉数为12、 的交叉数为8、 的交叉数为16.

  
1  基本概念、性质和定理
定义 1   图：一个图定义为一个偶对 ,记作 = ,其中
(1) 是一个集合,其中的元素称为顶点;
(2) 是无序积   中的一个子集,其元素称为边.
集合   中的元素可在 中出现不止一次. 
我们用 和 分别表示一个图的顶点集和边集.
定义 2 图 ，它表示由圈 增加边 （ =1，2，3，4，5，6， （mod 6））；图
 ，它表示由圈 增加边 （ =1，2，3，4，5，6，7，8， （mod 8））.我们将圈  、 称为主圈.并规定主圈不自相交.
定义 3  子图： 是图 的子图（Subgraph），写作   ，如果   ，   ，且 中边的重数不能超过 中对应的边的重数.
定义 4  图的好画法指满足下列条件的画法：
（1）任何两条交叉的边最多交叉一次； 
（2）边不能自身相交；
（3）有相同端点的两条边不会相交；
（4）没有三条边交叉于同一个点.