学位论文 > 优秀研究生学位论文题录展示

关于图的交叉数

作　者: 赵琳
导　师: 何卫力
学　校: 北京交通大学
专　业: 运筹学与控制论
关键词: 交叉数循环图笛卡尔积图三部图
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 29次
引　用: 2次
阅　读: 论文下载

内容摘要

图G的交叉数是将G画在平面上时交叉次数的最小值,记为cr(G)。其中画法满足:(1)任何两条边相交叉的边最多交叉一次;(2)边不能自身交叉(3)有相同端点的两条边不交叉;(4)没有3条边交叉于同一点。称含最小交叉数的画法为最优画法。一般而言,确定图的交叉数是一个完全NP-问题,给出给定图的交叉数的具体值是项非常困难的工作。对交叉数的研究主要集中在对完全图,n部图,广义Petersen图,循环图,笛卡尔积图的交叉数的计算上。目前知道交叉数的图类很少,其中知道交叉数的图类主要集中在简单图的特殊图与路,与星图,与圈,简单的特殊图之间的笛卡尔积图等。本文共分两章。第一章中综述了本篇文章主要要用的基本概念,以及前人给出的关于交叉数的已有结果。第二章中给出了一些新的结果:循环图C(11,4)和C(13,4)的交叉数。两个笛卡尔积图的交叉数。一个三部图的交叉数。

全文目录

致谢  5-6
中文摘要  6-7
ABSTRACT  7-9
第一章绪论  9-12
  1 基本概念  9-10
  2 已知结果  10-12
    §1.2.1 关于完全图的交叉数的已知结果  10
    §1.2.2 关于n部图的交叉数的已知结果  10
    §1.2.3 关于循环图的交叉数已知结果  10-11
    §1.2.4 关于广义Petersen图的交叉数的已知结果  11
    §1.2.5 关于笛卡尔积图的交叉数的已知结果  11-12
第二章关于交叉数的进一步探讨  12-32
  1 循环图C(11,4)和C(13,4)的交叉数  12-18
    §2.1.1 主要引理  12
    §2.1.2 主要结果  12-18
  2 两个笛卡尔积图的交叉数  18-23
    §2.2.1 引言  18
    §2.2.2 G_1×P_n的交叉数  18-21
    §2.2.3 G_2×P_n的交叉数  21-23
  3 一个三部图的交叉数  23-32
参考文献  32-34

关于图的交叉数

内容摘要

全文目录

相似论文