不含c-,4-、c-,5-和不含c-,6-的极图硕士论文.pdf

大连理工大学硕士学位论文摘要图论是数学的一个分支，它与数学的其他分支有密切的关系这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等随着计算机科学与数学的发展，图论已经成为人们研究自然科学以及社会科学的一个重要工具极图理论是图论中的重要组成部分极图问题中最主要的一类问题是：给定一族y - - - { G I ，G 2 ，⋯，G 0 > ，积巧y ) 表示由撑个顶点组成的不包含任一G ，∈y 的图的最多边数E X ( n ；y ) 表示由／, ／个顶点组成的不包含任一G ，∈1 | f r 的边数最多的图( 极图) 的集合在不包含多边形的极图问题中，对于y = { C 4 ) 的极图问题，C l a ：p h a m 等人给出了所有砧≤2 1 的极图，杨元生等人给出了所有2 2 s 丹s 3 1 时的极图；对于妒= { C ，C } 的极图问题，G a r n i e k 等人给出了n s 2 4 的所有极图对于y = { C s ，c } 的极图问题，杨元生等人给出了珂≤4 2 时瞰疗；{ G ，c 4 ，G ) ) 的值以及相应的所有极图，并对于胛> 4 2 的情形给出了上界。

．本文在此基础上主要研究了禁止子图族y = { C C 5 ) 时的极图问题和禁止子图族y = { c 6 } 时的极图问题本文主要采用的方法是：用已有的临界图构造算法对不含四边形五边形和不含六边形的临界图进行构造，以此构造的图的边数作为极图边数的下界，然后使用反证法和数学归纳法对边数的上界进行证明，直到推出极图边数上界与下界相同，对于极图的证明也要采用数学归纳法对其正确性和完备性一一证明主要给出如下结果：( 1 ) 当y = { c 4 ，C ，) 时，本文给出了顶点个数珂≤2 1 时e x ( n ；{ C C ) ) 的值以及相应得极图，并对极图的边数给出了数学证明；( 2 ) 当y = { c 6 > 时，本文给出了当顶点个数胛≤1 0 时e x ( n ；{ C ) ) 的值和相应的极图，并对极图的边数以及极图集合的正确性和完备性给出了证明；对于顶点个数1 0 相关联，则称该边为有向边；每一条边都是无向边的图称为无向图：每一条边都是有向边的图称为有向图：既有无向边，又有有向边的图称为混合图图中与一条边相关联的两个顶点称为是邻接点，不与任何顶点相邻接的顶点称为孤立点，仅由孤立点组成的图称为零图，仅由一个孤立点组成的图称为平凡图。

关联同一个顶点的两条边称为邻接边，关联同一个顶点的边称为自环关联同一对顶点的两条或两条以上的边称为多重边无自环，无多重边的图称为简单图本文所涉及的图均为简单无向图图G = ( y ，E ) 中的任意一条边( 甜，1 ，) 可简记为w ；图G 的顶点数称为阶( O r d e r ) ，用ⅨG ) = j 矿( G ) i 来表示：G 的边数( s i z e ) ，用口( G ) = f E ( G ) | 来表示与顶点v ( v ∈矿) 相邻接的点的集合记作Ⅳ( v ) ，N ( v ) = 缸：Ⅷ∈E ( G ) ) ；用川v 】表示Ⅳ【v 】= { 嵋U Ⅳ( v ) 与顶点v 和∈矿) 相关联的边数，称为该顶点的度，记作以v ) ；其中顶点度中的最大值称为图G 的最大度，记作△( G ) m a x { d ( v ) ：1 ，∈“ ：顶点度中的最小值称为图G 的最一、度，记作6 ( G ) = m i n { d ( v ) ：v ∈矿，图G = ∥，E ) 和图G = ( 矿’，E ’) ，若矿’￡矿，E ’￡昱，则称G ’为G 的子图；若V ’c y或E 7 c E ，则称G ’为G 的真子图；若∥= 矿，F 量E ，则称G ’为G 的生成子图；若y ’c y ，Ⅷ∈F ，当且仅当w ∈E 且“，v ∈矿’，则称G ，为G 的导出子图。

大连理工大学硕士学位论文若图日不是图G 的子图，则称日是G 的一个禁止子图由一族图组成的集合y = { G 1 ，G 2 ，⋯，6 I } ，若y 中的图都不是G 的子图，则称y 为图G 的一个禁止子图族图G = ( 矿，E ) 和图G = ( y ’，E 7 ) ，若存在∥到y 的一一映射g ，使得Ⅳ，v ∈V ，w ∈E当且仅当g ( Ⅳ) g ( v ) ∈E ’，则称G 和G ’同构，简记为G 兰G ’对于图G 中顶点组成的集合，如果集合中的顶点均不相互邻接，称这些顶点相互独立，由相互独立顶点组成的集合称为独立集G 的独立集中，顶点个数最多的集合称为G 的最大独立集用o r ( G ) 表示G 中最大独立集的顶点数图G 的一个着色是指对G 中的每一个顶点指定一种颜色，使得相邻接顶点的颜色不同其中，具有相同颜色的顶点是相互独立的，称为一个色组；若用了行种颜色实现对G 的着色，则把这种着色方法称为G 的一个n ．着色；图G 能”．着色的最小疗值称为图G的色数，记作z ( G ) ；若X ( G ) = k ，那么图G 称为k ．可着色的1 ．1 ．2 路图G = ∥，芑) ，设v 0 ，q ，V 2 ，⋯，％∈y ，则由v o v l ，M 吃，⋯，V 。

％组成的边的序列( 简记为v o M ⋯％一) 称为联结v o 到1 ，，的路％，v 分别称作路的起点和终点，路中边的数目称为路的长度若一条路中V 0 = 1 ，则这条路称为回路；若一条路中所有的边均不相同，则称作迹；若一条路中所有的顶点均不相同，则称作通路或道路；除v n = v 外，其余的顶点均不相同的路，被称为圈或闭通路若图中的每一对顶点都能由一条道路所联结，就称该图为连通图图中最大的连通子图称为一个连通分支’若图G 中有圈，则G 中最短圈的长度称为G 的围长，记作g ( G ) ；G 中最长圈的长度称为G 的周长，记作c ( G ) 对于G 中的两个顶点甜与1 ，，当存在联结甜与v 的道路时，其中最短道路的长度称作”与v 2 _ 间的距离d ( u ，1 ，) 如果不存在联结“与v 的道路，则d ( u ，v ) = m 图G 中任意两点间最长的距离称作图G 的直径若图G 中存在一条路，经过G 中的每个顶点恰好一次，这条路称为G 的哈密顿路若存在一条回路，经过G 的每一个顶点恰好一次，则称该回路为图G 的哈密顿回路哈密顿回路是图G 的一个生成圈，所以也被称作哈密顿圈具有哈密顿回路的图称作哈密顿图。

不舍c ．、已和不含已的极图1 ．1 ．3 树一个连通的且无回路的图称为树树中的顶点称为结点指定树中的一个结点为根结点，树中任一结点到根结点的距离称为该结点的层数对于第i 层的一个结点掰，与其相邻接的第i + I 层的结点称为是结点T ．／的子结点；把结点“称为其子结点的父结点没有子结点的结点称为叶结点树中的根结点没有父结点，树中的一个父结点可以有多个子结点，而一个结点最多只能有一个父结点连通图至少有～颗生成树树是一类简单、特殊的图，探讨图的问题，通常是先从树来进行的本文的证明就是在树的基础上，通过有选择地增删点和边来构造满足条件的图1 ．1 ．4 常用的图和标记C 表示由咒个顶点组成的圈例如C ，表示三边形，C 4 表示四边形，C ，表示五边形只表示由挖个顶点组成的道路，即从C 上删掉任意一条边所褥的图表示由1 , ／个顶点组成完全图，即由疗个顶点组成的所有顶点都相互邻接的图表示完全二分图，该图有A + P ：个项点，这些顶点被分到两个集合中，各个集合分别包含A ( P l > O ) 和P 2 ( p 2 > 0 ) 个顶点，属于同一个集合中的顶点均不相互邻接，属于不同集合中的顶点均相互邻接。

K “附表示完全所( m > 1 ) 分图，该图共有马+ p 2 + ⋯+ p 个顶点，这些顶点被分到珊个集合中·各个集合分别包含p ．，P ：，⋯，P > 0 ) 个顶点，属于同一个集合中的顶点均不相互邻接，属于不同集合中的顶点均相互邻接k 一正则图表示所有顶点度均为k 的图 七，g ) 一图表示围长为g 的七一正则图 j } ，g ) 一笼是指( 膏，g ) 一图中顶点数最少的图，它必须满足下面3 个条件：( 1 ) 为j } 一正则图；( 2 ) 围长为g ；( 3 ) 在满足前两个条件的图中，为顶点数最少的图一4 一大连理工大学硕士学位论文1 ．1 ．5 常用的图的运算石= ( 瓦两表示图G = ∥，D 的补图，其中矿( 百) = 矿( G ) ，E ( G ) = { @ ，V ) I 村，V ∈矿( G ) ^ @ ，v ) 茌E ( G ) )若H ，吃，⋯以∈以G ) ，岛，e 2 ，⋯，e ，∈E ( G ) ，那么G - { e P ：，⋯，e ．} 表示在图G 上删除一些边后得到的图若m = l ，简记为G —q ；G 4 ．{ e 1 ，吃，⋯，e 表示在图G 上添加一些边后得到的图。

若m = 1 ，简记为G + e 1 ；G - { v ．，v ：，⋯，v } 表示在图G 上删除一些顶点以及这些顶点相关联的边后得到的图若聍：l ，简记为G —v ' ．若v 仨V ( G 1 ，那么G U { ' ，} 表示在图G 上增加一个孤立点后得到的图；G + v 表示在图G U { v ) 上添加邻接v 与矿( G ) 中所有顶点的边后得到的图若图日为图G 的一个子图，那么G —H 表示在图G 中删除E ( 日) 后得到的图若图G j = ( K ，置) ，图G 2 = ( ％，E ：) 那么G i U G ：表示图( K U V 2 ，巨U 易) Ⅳ、口表示从集合Ⅳ中删除元素口后得到的集合1 ．2 极图问题1 ．2 ．1T u r f i n 原始极图问题图论中的许多问题都含有求极值的内容，这些问题被统称为“极图问题”T u r i n是极图领域的先驱，极图理论是在T u r d n 原始极图问题的基础上发展起来的1 9 3 0 年R a m s e y 证明了R a m s c y 定理，首先我们了解一下R a m s e y 定理定理1 ．1 ．( R a m s e y 定理用) 对于任意一个大等于3 的正整数P ，一定可以找到一个最小的正整数k ，使得对完全图K 。

∽≥七) 的边进行任意的一种2 着色中，必存在由同种颜色的边组成的足，；其中整数七称为是不包含K ，的经典R a m s c y 数，记作R ( 力口为了进一步了解经典R a m s e y 数，下面给出R ( 3 ) = 6 的证明，即对置∞≥6 ) 进行边的2 着色时，必存在由同种颜色的边组成的瓦定理1 ．2 ．五( 3 ) = 6 ．不含c “c 5 和不含G 的极图证明：显然，可以将K ，的边着色成两个G ，而c ，中不包含墨·所以R ( 3 ) ≥6a 接下来证明R ( 3 1 = 6 设将E ( 玎≥6 ) 两着色为G 和虿，设v 是疋中的一个顶点，因为v 与其余捍一1 个顶点或者在G 中邻接，或者在否中邻接因为n - - 1 2 5 ，不失一般性，不妨设至少有三个顶点％，如，屹在G 中与v 邻接如果这些点中任意两个相邻接，则它们与v 就形成一个蜀；如果在G 中坞，甜：，码均不相邻接，则％，屹，坞在舀中就形成为，所以对K 0 ≥6 ) 边的任意2 着色中，必存在由固种颜色的边组成的毛，哉震( 3 ) = 6 口在R a m s e y 定理的启发下，在1 9 4 0 年T u r d n 提出了这样的问蹶：由万个顶点组成的不包含K p ( 3 ≤P 3 时，纵押；{ c 4 ) ) ) ( 疗≤2 1 ) 的值T a b ．2 ．1T h e v a l u e s o f 积( 甩；{ c ‘} ) @ ≤2 1 )不含已、G 和不含& 的极图2 ．2 ) 。