笛卡尔积图K[33]P[2]以及K[24]P[2]的交叉数

目 录

中文题目……………………………………………………………………………（1）

中文摘要、关键词…………………………………………………………………（1）

英文题目……………………………………………………………………………（1）

英文摘要……………………………………………………………………………（2）

前言…………………………………………………………………………………（3）

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

   2 主要结果及证明 ………………………………………………………………（5）

     2．1  引理 1………………………………………………………………………（6）
     2．2  引理 2………………………………………………………………………（7）
     2．3  引理 3………………………………………………………………………（9）
     2. 4  引理 4………………………………………………………………………（9）
     2．5  引理 5………………………………………………………………………（12）
     2．6  引理 6………………………………………………………………………（13）
     2．7  定理 7………………………………………………………………………（14）

 参考文献…………………………………………………………………………（16）

 致谢词………………………………………………………………………………（17）

笛卡尔积图   以及   的交叉数

摘要

根据交叉数的理论，确定了完全二部图 ， 与路 ， 的笛卡尔积图的交叉数.我们具体得到了以下结论：(1)    ＝3；(2)  ＝6；(3)  ＝7；(4)  ＝13；(5)      =2；  =4；(6)若 是 的一个好画法，每个 ( =0，1，2)上至多有3个交叉，则   8；(7)  =8.
关键词：图；画法；交叉数；路；笛卡尔积图；同胚；

The Crossing Number of Cartesian
Product Graph     and   

  
ABSTRACT

According to the crossing number theory of graph theory,this paper show the crossing number of    and the crossing number of   .We obtained the result below：(1)the crossing number of   is three;(2)the crossing number of  is six;(3)the crossing number of  is seven;(4)the crossing number of is thirteen;(5)the crossing number of    is two; the crossing number of  is four;(6) is a good drawing of ,if each （ ）has at most three crossings,the crossing number of is more than eight;(7)the crossing number of is eight.
Keywords:Graph;Drawing;Crossing number;Path;Cartesian product;Homeomorphism;
 

前言

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

1 基本概念、性质和定理
本文未说明的概念和术语均同文献[1]-[12]，且无特别说明时，所涉及的图均指连通简单图，用
  和  分别表示一个图 的顶点集和边集.
定义１　一个图定义为一个偶对 ， ，记作 ＝ ， ，其中
（1） 是一个集合，其中的元素称为顶点；
（2） 是无序积   中的一个子集合，其元素称为边；集合   中的元素可在 中出现不止一次.
定义   所有的顶点均不相同（从而所有边必然都不相同）的途径称为道路（path）.
定义3  每一对不同的顶点均有一条边相关联的简单图称为完全图（Complete graph）.n阶完全图记作 .
定义4  设 和 是 的顶点子集，使   ＝