（基础数学专业论文）超图及其线图的若干性质的讨论.pdf

中文摘要 在所有通常图的变换中，线图是研究最广泛的一种变换关于通常图的 线图的研究已经产生了很多的成果，如路图和线图的关系，线图与若干典型 图类的交叉数等等随着图论的发展，通常图已经被人们推广到了超图上从 超图的角度看，通常图是2 一致超图，只是超图的一种特殊的结构，作为通常 图中研究最广泛的变换线图可以在超图上进行推广，这样就拓展了线图 的研究领域，使这种变换在更大的范围发挥更大的作用本文讨论了超图及 其线图的若干性质 第一章引言，主要介绍了超图和线图的发展第二章基本概念和基本引 理给出了本文用到的超图中的定义、概念和通常图及其线图的若干引理 第三章超图及其线图的若干性质，本章分三节，分别将第二章的基本引理推 广到3 一致超图、r - 一致超图和一般超图上并给出证明第四章参考文献，列 举了为完成本文所用到的文献资料第五章致谢，感谢在论文完成期间给予 我帮助的老师和同学 关键词图，线图，超图，超图的线图 a b s t r a c t lh el l n eg r 印ht 啪s f o n n a t i o ni sm em o s t w i d e l ys t u d i e do n ea m o n ga 1 1 星阳p h t r a n s f o m a t i o n s t i l l es m d yo fl i n eg r a p hh a sp r o d u c e dal o to fr e s u l t s s u c ha s t h er e l a t i o n s h i po ft h ep a t hg r a p ha n dt h e1 i n eg r a p h ，t h e l i n eg r a p ha n dt h e c r o s s l n gm u m b e r so fs o m et y p i c a l g r a p h sc l a s s e sa n ds oo n w 油 t h e a e v e j 叩m e n to f 脚ht h e o 巧，g r a p ht h e o 拶h a sb e e ne x t e n d e dt ot h eh y p e r g r a p h 。i h eg r a l ) hi s2 u n i f o mh y p e 唱r 印h 劬mt h ep o i n to f h y p e 粤a p h ，a n di ti sa s p e c l a l s 仃u c t u r eo f h y p e 玛r a p h t h el i n e g r a p h ，a st h em o s te x t e n s i v e t r a n s t o n n a t l o no fag r a p hb es m d i e d ，c a nb ee x t e n d e dt o h y p e r g r a p h s ot h e s t u d ya r e ao f t h el i n eg r 印hc a nb ee x t e n d e d ，a n dt h el i n eg r 印ht r a n s f o m a t i o n c a np j a yag r e a t e rr o l ei naw i d e ra r e a t h i sp a p e rd i s c u s s e ss o m e p r o p e r t i e si n h y p e 呼a p ha n dt h el i n eg r a p ho f h y p e 喀r a 【p h c h a p t e rl1 1 1 t r o d u c t i o n t h i sc h 印t e rm a i n l yi n t r o d u c e st h ed e v e l o p m e n to f t h e n y p e 玛r a 】p ha n dt h el i n e 聊h c h 印t e ri ib a s i cc o n c 印t sa n db a s i c1 e m m a s t 1 1 i s c n a p t e rg l v e sd e f m l t l o n sa n d c o n c 印t si nt h eh y p e 玛r a p hb eu s e di nt h i s p 印e r ，a n dg l v es o m e1 e n l m a si n g r 印ha n dl i n eg r a p h c h a p t e ri i is o m e p r o p e r t l e smh y p e 唱r a p ha n dl i n e g r 印h t h i sc h a p t e ri sd i v i d e di n t ot 1 1 r e e s e c t l o n s ，a n de x t e n d st h eb a s i cl e m m ai nt h es e c o n dc h a p t e rt o3 u n i f o n n n y p e 唱r a l ) h ，卜u n l t o mh ) ，p e 唱r a p ha n da r b i t r a 巧h y p e 曙r a p h ，a n d 西v e sp r o o 砖 c h 印t e ri vr e f e r e n c e s t h i sp a p e rg i v e so u ta 1 1t h er e f b r e n c e sb eu s e di nt h i s p a p e r c h a p t e rva c l ( i l o w l e d g e m e n t t h a l l 王( s 南rt h et e a c h e r sa n dt h es t u d e n t s w n og l v em e h e l pd u n n gt h ep e r i o do ft h ec o m p l e t i o no fm y p a p e l k e y w o r dg r a p h ，l i n eg r a p h ，h y p e r g r a p h ，l i n e g r a p ho f h y p e 唱r a p h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果，尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本 人为获得内蒙古师范大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示感谢。 签名：幽猫习 日期：7 泸扩年6 月如日 关于论文使用授权的说明 本学位论文作者完全了解内蒙古师范大学有关保留、使用学位论 文的规定：内蒙古师范大学有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文 的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：确司 导师签名：确t 凌 导师签名：阿旁i 咙 日期：w 。g 年乡月力日 1 引言 图论是一门应用十分广泛其内容非常丰富的数学分支，也是近年来较为活跃的数 学分支之一图论起源于1 7 3 6 年，瑞士数学家l e u l e r ( 欧拉) ，在他的一篇论文中讨论 了哥尼斯堡七桥问题n 1 ，由此诞生了一个全新的数学分支图论( g r a p ht h e o r y ) 在经历了2 0 0 多年的发展之后，图论已经积累了大量的理论和结果，其应用领域 已逐步扩大，在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络 理论、社会科学和管理科学等领域中的应用越来越受到人们的重视在过去的几十年 里，图论已经被证明是解决几何、数论、运筹学和优化等领域中各种组合问题非常有 用的工具 为了解决更多的组合问题，使图论在更多的领域发挥作用，把图的概念进行推广 是非常自然的事情用这种观点来研究集簇的思想大约始于1 9 6 0 年前后关于把集簇 中每个集合看作为“广义的边”，把集簇本身称为“超图”的思想，起初是为了推广 图论中一些经典的结果，如定理t u r a n 乜1 和定理k 6 n i g 乜1 后来，人们注意到这种推广 往往会带来不少便利，且可把图论中的一些定理用统一的、简单的形式加以陈述超图 是有限集合的子集系统，离散数学中最一般的结构，早期的定理有s p e r n e r 定理口1 和 r a m s e y 定理口3 等于2 0 世纪6 0 年代，“超图”这个词正式提出来，是作为通常图的 推广，基本概念和定义都是通常图的相应概念和定义的平移和推广，业已取得了一些 重要结果，如e r d 6 s k o r a d o 定理h 1 等b e r g e 写了一本专著“h y p e r g r a p h s 对其做 了系统的总结进入信息时代，信息科学技术对人类社会各个领域都产生着巨大的影 响，也为创建发展新的数学理论提供了机遇、源泉和动力由于信息科技、生命科技的 不断发展，人们要研究处理的系统也越来越庞大，越来越复杂集成化就成了一个重 要方向就是要把一个大系统化为子系统的集成反映在数据库理论中，就是要把大 数据库化为小数据库的联合首先把数据库的属性集合化为其子集合的并，形成数据 库图式信息科学的发展，特别是数据库理论的发展为超图理论的发展注入了新的活 力，赋予了新的内涵，给予了巨大的动力 随着图论的发展和应用范围的拓展，为了解决更多的问题使图论发挥更大的作用， 对图论的概念和定理进行推广是很自然而且也是必然的事情，所以推广图论中的概念 和定理是非常有意义的事情 有关超图方面更多的介绍请参考综述性文章 5 内蒙古师范大学硕上学位论文 通常图的线图的概念最早是由w h i t n e y 提出的，有所有图的变换中，线图可能是 研究最广泛的一种变换了关于线图的研究已经产生了很多的成果，如路图和线图的 关系n 引，线图与若干典型图类的交叉数n 们超图是通常图的推广，用超图的定义看，通 常图就是2 一一致超图，即通常图仅是超图的比较特殊的结构，因此推广通常图及其线 图的性质是很自然的事，然而从理论上，并不是都能轻而易举地将图及其线图的相关 的性质推广到超图及其线图上本文讨论了致超图的线图的若干性质，其中有些是 通常图的线图的自然推广，还有一些是一致超图具备的，即通常图不具有的性质，从这 一角度说明了超图要比通常图更加深刻 2 基本概念和基本引理 2 基本概念和基本引理 2 1 基本概念 本节主要给出本文中用到的有关超图方面的定义和概念 定义2 1 1 h 1 令x = 五，屯，) 是一个有限集，关于z 上的一个超图 日= k ，吃，p 卅) 是指x 上的一个有限子集簇q x 使得 ( 1 ) 巳a g = 1 ，2 ，掰) ； ( 2 ) u q = x 一个超图日= q ，乞，) 若还满足 ( 3 ) q p ，j 扛， 则称日为简单超图 在超图日中，用y ( 日) 表示日的顶点集合，用e ( 日) 表示日的边集 合，哆( f _ 1 ，2 ，m ) 叫做超图h 的超边，其中y ( ) = x ，e ( 日) = p l ，p 2 ，p 。) 定义2 1 2 若q ，p ，日，称s = qn 巳为q 与勺的关节 当l s l = f 时，称s 为f 一关节；若日所有的关节都是f 一关节，称为f 一均匀关节超图 当h 2 0 时，称乞与巳不相交：当俐o 时，称q 与巳相交 定义2 1 3 设q = ( ，q ，气) 是日中的一个边序列，s = qn q 川f = 0 ，l ，后一1 ， 下标运算取m o dn ，q 称为具有关节序列s = ( & ，墨，最一。) 的一个圈，如果 ( 吼) 当f 时，p f 勺； 3 内蒙古师范大学硕士学位论文 ( 9 2 ) s f 囝( f = o ，l ，尼一1 ) ； ( 9 3 ) 当f _ ，时，s i s ，a ； 2 ( g 。) 对v f o ，l ，七一1 ) ，日中不存在边e 使得p2u s 州 ，= o 超图日的阶是指超图的顶点数，记作刀( 日) 超图的下秩是指含顶点最少的超边中 顶点的数目，记作s ( 日) ，即j ( 日) = 唧n m ：超图的上秩是指含顶点最多的超边中顶点的 数目，记作r ( 日) ，即，( h ) = m 蚓 定义2 1 4 h 1 若s ( h ) = ，( 日) = r ，称超图为，一一致超图 定义2 1 5 川超图的线图记作三( h ) ，是按照如下方法得到的：顶点集 矿( ( 日) ) = q ，乞，) ，巳，e ，y 亿( h ) ) ，q ，巳相邻，记作巳勺，当且仅当 巳np ，囝 对照通常图，在超图中，顶点的度、正则超图、超图的同构等有如下的定义 定义2 1 6 h 3 超图h 的顶点x 的度是指包含x 的超边的数目，记作d ，( x ) 定义2 1 7 超图h 的所有顶点有相同的度j | ，称为七一j 下则超图 定义2 1 8 【l 朝超图日，与2 同构是指存在一一映射g ：矿( h 。) jy ( 日：) ，使得 v p ，p ，矿( 日1 ) ，g ，勺当且仅当( p ? p ；) e ( 2 ) e ( 日2 ) ， 日l 与日：同构记作 日l 兰日2 为了叙述方便，三( x ) 中由x 的诸顶点决定的极大团称为( x ) 的特殊团，有时候 为了使结果更具有完美性，特殊团可以具有重复性为了区别一般的图与超图，在本文 中将一般的图称作通常图，用黑体加粗来着重注释本文所涉及的超图若未加特别说 明均是指简单超图 本文涉及的术语和记号，未加定义的概念或符弓均遵从文献 1 ，9 1 4 4 2 基本概念和基本引理 2 2 基本引理 本文的主要结果是将文献 1 0 中的以下通常图即2 一一致超图的性质推广到3 一一 致超图、r 一一致超图和一般超图上首先由文献 1 0 给出如下引理 引理1 是由通常图的正则性导出它的线图的正则性 引理1 n 设通常图x 是七一正则图，那么三( x ) 是2 ( 七一1 ) 一正则图 下面的引理2 一引理7 都是关于通常图的顶点、边和特殊团的关系的结论 引理2 n 0 1 设x 是通常图，vx y ( x ) ，若d ( 功= 七，那么工决定三( x ) 中的一个七阶 特殊团 引理3 n 0 1 设x 是不含三角形的通常图，若“y ( ( x ) ) 满足“在( x ) 中至少有两 个邻点且这些邻点属于( x ) 的同一个特殊团，那么 也属于这个特殊团 引理4 n 们设x 是刀阶通常图，那么在( x ) 中一定存在，1 个特殊团使得( x ) 中每 个顶点至多属于两个特殊团 如何判别一个通常图是线图呢? 以下的引理给出了线图的一个判别条件 引理5 n 们任意通常图x 的线图的边集是由x 的顶点确定的极大团的边分化 引理6 n 一个非空通常图爿是某个通常图的线图x 的边集可以分成极大团 的集合的并使得x 的每个点至多属于两个团 引理7 n 们一个非空通常图x 是线图营x 的边集可以分成极大团的集合使得它除 了孤立点以外的点恰属于两个团 如果两个通常图是同构的，那么这个两个通常图所对应的线图也同构反之不然 即如果两个通常图的线图同构，那么这两个通常图不一定同构 引理8 吲设x ，】，是通常图，若x 兰y ，那么( x ) 兰三( y ) 内蒙古师范大学硕： = 学位论文 3 超图及其线图的若干性质 文献【8 】从数据库设计的角度研究了超图的理论，建立了超图的公理体系在文献【8 】 的公理体系下，将2 2 节的引理推广到3 一一致超图上、r 一一致超图上，部分引理推广 到任意超图上 3 13 一一致超图的若干性质 3 1 1 正则性 根据引理1 ，3 一一致正则超图与其线图的关系如下： 定理l 设日是3 一致k 正则超图，若日是卜均匀关节的，那么l ( 日) 是3 ( 七一1 ) 一正 则图 证明：v q = 扛 ，黾j e ( h ) ，因为h 是尼一正则3 一一致超图，所以在h 中除q 外 分别存在七一l 条包含屯，吃，气的超边因为h 是卜均匀关节超图，所以上述分别包含 ，气，气的超边不重复否则，设存在某条超边p e ( 日) 包含气，屯中的2 个或3 个 点，那么i p ，n 叫= 2 或i p ，n p l = 3 ，这与日是卜均匀关节超图矛盾，所以与岛相交不为空 的超边有3 ( 七一1 ) 条根据超图线图的定义知，在三( ) 中以q 为端点的边共有3 ( 七一1 ) 条， 再由q 的任意性知( ) 是3 ( 七一1 ) 一j 下则图 证毕 3 1 2 顶点、边和特殊团的关系 通常图的一个点可以决定其线图的一个特殊团，在3 一一致超图和其线图中有： 定理2 设是3 一一致超图，v “y ( 日) ，若d ( ”) = 后，那么“决定( h ) 中的一个 足阶特殊团 6 3 超图及其线图的若干性质 证明：设v “矿( 日) ，若d ( “) = 七，那么根据超图中顶点度的定义，“恰属于日的 后条超边不妨设这七条超边为q ，乞，气，因为这七条超边都包含“，所以在三( 日) 中e l ，乞，吃这七个顶点两两连边，所以“决定三( 日) 中的一个后阶特殊团 证毕 引理3 的结果在3 一一致超图中未必成立，见以下例题分析 例子：日= 函，v ，w p ，其中“= 1 ，2 ，3 ) y = l ，4 ，5 ，w = 2 ，4 ，6 p = 1 ，2 ，4 ) 日中不含三角形且1 ，w 是“在上( 日) 中的两个邻点，在( 日) 中1 ，w 属于顶点4 决 定的特殊团，但“却不属于这个特殊团 分析： “ny = 1 ) ，“nw = 2 ) ，1 ，nw = 4 ) ，“n p = 1 ) ，n p = 1 ，4 ) ，w ng = 2 ，4 ) ，这些 是h 中的所有关节，而这些关节都是p = 1 ，2 ，4 ) 的子集，所以根据定义2 1 3 知，日中 任意3 条超边都不满足超图的圈的定义的条件( g 。) ，即日中不含3 阶圈再根据超 图的线图的定义知，“在三( h ) 中有三个邻点，分别是v ，w ，p ，而，w e 属于由顶点4 ( 4 矿( h ) ) 在三( 日) 中决定的特殊团而“属于顶点1 ，2 ，3 在( h ) 中决定的特殊团， 不属于顶点4 ( 4 y ( ) ) 在( ) 中决定的特殊团 这个例子就很好得说明了引理3 在3 一一致超图中未必成立，从这个角度看，超图 确实是通常图的推广 通常图的顶点决定它的线图的特殊团，使其线图的顶点最多属于两个特+ 殊团， 那么在3 一一致超图和其线图上是不是也有类似的关系昵? 定理3 设日是刀阶3 - 一致超图，那么在三( h ) 中一定存在刀个特殊团使得( ) 中每个顶点至多属于其中的三个特殊团 证明：由定理2 知，v ”y ( 日) ，“决定( 日) 中的一个特殊团因为甩( 日) = ，l ，所 以在( h ) 中存在行个特殊团设p y ( ( h ) ) 被上述聊( 脚4 ) 个特殊团所包含，不 7 内蒙古师范大学硕士学位论文 妨设这胁个团分别由“l ，”2 ，“。y ( h ) 所决定，那么p = “l ，“2 ，“。) e ( h ) 因 为m 4 ，这与日是3 一致超图矛盾 证毕 通常图的线图的边集是特殊团的不相交边的并，3 一一致超图的线图的边和特殊 团的关系由下面的定理来确定 定理4 设日是3 - 一致超图，那么( 日) 中每条边至多属于两个特殊团 证明：v ( 巳一e ，) e 犯( h ) ) ，由超图的线图的定义知岛，勺e ( 日) 当bn e i = l ( f j ) 时，在( h ) 中边岛e 属于弓，巳的唯一公共点决定的特殊 团： 当l en 勺l = 2 ( f ) 时，在( ) 中边q 勺属于q ，巳的2 个公共点决定的特殊 团； 而l p ，n p j i 3 ( f ) 的情况不存在若kn p _ ，l = 3 0 ) ，因为日是3 一一致超图， 每条超边包含3 个顶点，所以q = 巳，这与日是简单超图矛盾：若bn 口，l 3 ( f j f ) ， 那么 3 且蚓 3 ，这与h 是3 一一致超图矛盾 综上所述，三) 中每条边至多属于两个特殊团 证毕 如果一个非空通常图是某个3 一一致超图的线图，那么这个通常图的顶点和特殊 团有下面的关系： 定理5 一个非空通常图x 是3 一一致超图日的线图，那么x 边集可以分成特殊 团的集合的并使得x 的每个顶点恰属于三个特殊团 证明：根据定理2 知，v “矿( ) ， 决定h 的线图x 的一个特殊团根据h 的 顶点对其线图x 的特殊团的决定性，日的顶点可以将x 分成特殊团的集合下面证 明x 的每个顶点恰属于三个特殊团设协y ( x ) ，在日中所对应的边为q ，因为h 是3 一一致超图，所以l 巳| _ 3 不妨设巳2 “，而，) ，那么x 属于，恐，屯在x 中决定的 3 超图及其线图的若干性质 特殊团如果还有其它的特殊团包含x ，那么巳至少还包含一个顶点，这与h 是3 一一 致超图矛盾由x 的任意性知，x 的每个顶点恰属于三个特殊团 证毕 根据文献【8 】知，任意通常图未必是通常图的线图如k 是一个爪形图，在通常图 中是找不到以它为线图的通常图的，但它却是3 - 一致超图日= p ，p 2 ，e 3 ，e 。) ( 其中巳= 1 ，2 ，3 ) ，吃= 1 ，屯5 ) ，p ，= 2 ，6 ，7 ) ，e 。= 3 ，9 ) 的线图根据超图的线图的定 义知，三( 日) 是以巳、e 2 、巳、气为顶点，以p l p 2 、p l 吃、q p 4 为边的通常图k l y 下面再举一个例子下图是p e t e r s e n 图，在通常图中它不是任何通常图的线图，但是在 3 一致超图中却能找到它的原图首先，我们来证明在通常图中它不是任何通常图的 线图利用反证法，假设p e t e r s e l l 图是某个通常图的线图由文献【8 】中通常图的特殊团 的定义知，通常图的特殊团是完全图，所以p e t e r s e i l 图的每条边是一个特殊团p e t e r s 髓 图是一个3 正则通常图，而它的每条边都是一个特殊团，所以p e t e r s e n 图的每个顶点 都属于3 个特殊团，这与引理4 矛盾 p e t e r s 锄图在通常图中不是任何通常图的线图，但它作为一个线图却可以在3 一 致超图中找到原图我们按下面的的方法找一个以p e t e r s l m 图为线图的3 一一致超图 为了下面叙述方便，设p c t e r s e n 图的1 5 条边分别为c l ，c 2 ，c l ，其中 y ( c 1 ) = q ，吃) ，y ( c ：) = 乞，乞) ，y ( c j ) = 巳，吃) ，矿( c 4 ) = 气，吃) ，y ( c ：) = 吃，q ) ， 矿( c ：) = q ，) ，y ( g ) = 乞，岛) ，矿( c ：) = 巳，龟) ，y ( c 9 ) = 气，岛) ，y ( c i 。) = 巳，q 。) ， y ( c ；，) = e 6 ，) ， y ( c l ：) = 龟，q 。) ， 矿( c l ，) = 白，q 。) ， y ( c i 。) = 岛，岛) ， 矿( g ，) = ，岛) 按如下方法作超图：以p e t e r s e n 图的边为顶点，若l c ，n qn c 女l = l ，则c ，c ，g 属于h 的同一条边按上述方法得到一个3 一一致超图h = q ，巳，q 。) ，其中 q = c l ，c 5 ，c 6 ) ，乞= c l ，c 2 ，c 7 ) ，巳= c 2 ，c 3 ，g ) ，q = c 3 ，c 4 ，c 9 ) ，巳= c 4 ，g ，c l 。) ，气= c 6 ，c l 。，c l ，) ，白= c 7 ，c l ，c i 。) ，= c 8 ，c i ，g ：) ，岛= c 9 ，c l 。，c l ，) ， q 。= c i 。，c i ，q ，) 9 内蒙古师范大学硕士学位论文 根据上面的例子有下面的定理6 ： p e t e r s e n 图 定理6x 的边集。可。分成不相交的极大团的集合的并使得x 的每个顶点恰属于 3 个极大团，那么x 是某个3 一一致超图的线图 证明：设c 表示x 的极大团，以x 的极大团为顶点按如下方法作一个超图日： 若l qn qn c i = 1 ( f ，压不相同) ，那么c ，q ，q 属于同一条超边下面证明胃 是3 一一致超图假设在胃中存在一条超边p ，h 3 当i 叫4 时，不妨设超边 p = g ，q ，g ，q ) ，那么巳必包含c f ，q ，g 的公共点，与石的每个顶点恰属于 3 个极大团矛盾：当lpi ，( f _ ，) ， 那么蚓 ，且f p ，l r ，这与日是r 一一致超图矛盾 证毕 综上所述，三( h ) 中每条边至多属于，一1 个特殊团 定理5 给出了一个通常图是某个r 一一致超图的线图时它的顶点和特殊团的关 系 定理5 一个非空通常图x 是r 一一致超图的线图，那么x 本身可以分成特殊 团的集合的并使得x 的每个顶点恰属于r 个特殊团 证明：根据定理2 知，v “y ( h ) ，“决定h 的线图x 的一个特殊团根据h 的 顶点对其线图x 的特殊团的决定性，月的顶点可以将x 分成特殊团的集合下面证 明x 的每个顶点都恰属于r 个特殊团设坛矿( x ) ，在中所对应的边为巳，因为 h 是r 一一致超图，所以i e l _ r 设巳= “，x ：，x ，) ，那么x 属于而，x ：，在x 中决 定的特殊团如果还有其它的特殊团包含石，那么巳至少还包含一个顶点，这与日 是的r 一一致超图矛盾由工的任意性知，x 的每个顶点都恰属于r 个特殊团证毕 定理5 给出的r 一一致超图的线图具有的一个性质，那么什么样的通常图才能作 为r 一一致超图的线图呢? 定理6x 的边集分成不相交的极大团的集合的并使得x 的每个顶点恰属于r 个极大团，那么x 是某个r 一一致超图的线图 证明：设c 表示x 的极大团，以彳的极大团为顶点按如下方法作一个超图： 1 4 3 超图及其线图的若干性质 若i c f lnc j 2n nc j ，l = 1 ( ，如，f ，互不相同) ，那么q ，c j 2 ，c r 属于同一条超边 下面证明h 是r - 一致超图假设在日中存在一条超边p ，h ，- 当h ，+ l 时，不妨设 超边p = g ，c i 2 ，气) ( ，l ，+ 1 ) ，那么c 0 必包含c f i ，吒，q 一。的公共点，与x 的 每个顶点恰属于r 个极大团矛盾：当h ，( 日) ( f _ ，) ，那么川 ，( 日) 且阿l ，( h ) ，这与h 是每条超边最多包含r ( h ) 个顶点矛盾 综上所述，三( ) 中每条边至多属于h 的顶点决定的，( 日) 一1 个特殊团证毕 一个非空的通常图是某个超图的线图，那么它的顶点与特殊团的关系与超图的 边包含的顶点数有关 定理4 一个非空通常图z 是超图日的线图，那么彳的边集可以分成特殊团的 集合使得v p y ( x ) 属于h 个特殊团 证明：根据定理1 知，v “y ( h ) ，“决定日的线图x 的一个特殊团根据日的顶 点对其线图x 的特殊团的决定性，h 的顶点可以将x 边集分成特殊团的集合 v p y ( x ) ，设e 在h 中的对应边p = k ，为，1 ，那么v p y ( x ) 属于 毛，石2 ，1 叫矿( h ) 在x 中决定的特殊团，所以v p 矿( x ) 属于h 个特殊团证毕 任意一个通常图都可以在超图中找到一个原图 定理5x 的边集可分成不相交的极大团的集合的并，则x 是某个超图的线图 证明：设e 表示z 的极大团，以x 的极大团为顶点按如下方法作一个超图： 若lc f ln c 如n n 吒l = l ( f l ，如，互不相同) ，那么g 。，e ：，气属于同一条超边 下面证明x 与( h ) 是同构的设y ( x ) = 五，x ：，) ，根据的作法及超图线图的 3 超图及其线图的若干性质 定义知，l y ( 三( h ) ) l = ，设c f inc f 2n nq = “) ，巳= c f i ，c f 2 ，q ) e 饵) 作映 射g 使得砰= 白( 巳y 犯( 日) ”，那么显然g ：y ( x ) 专y ( 三( 日) ) ，是双射 坛，y ( x ) ，若五，则，t 必属于x 的同一个团，记这个极大团为g 根据 定 理条件可 设 c j inc f 2n nq = “) ，巳nq ：n nc 厶= n ) ，巳= q ，c f 2 ，q ) ， 巳= 巳，巳，巳) ，再根据g 的定义设芹2q ，巧2 勺，而而，t g ，所以 g 白ne ，即在( 日) 中有乞巳，继而群一巧；反之设q ，巳y ( ( 日) ) ，由于g 是 满射， 孔，x y ( x ) ，使得 芹= e ：，碍= 勺 ，其中 巳= c i i ，c f 2 ，q ) ， p ，= 巳，巳，吒) ， q n c f 2n nq = “) 巳nq ：n nq = 0 ) 在( ) 中，当q 巳时，根据超图的线图定义有 q n p ，gjj 岛qnp ，j ，c f fj 一x ，e 似) 综上可得，x 与三( 日) 同构，所以x 是超图片的线图证毕 3 3 2 图的同构和线图的同构 如果两个超图同构，那么它们对应的线图也同构 定理6 设日i ，h 2 是超图，若日l 兰日2 ，那么( h i ) 兰上( 日2 ) 证明：v q ，p 2 y ( ( 1 ) ) ，设p l e 2 ，由线图的定义知，白，e 2 e ( 日1 ) 且 巳np ，a 设g 是且到h ：的同构映射，彳，e ( h 2 ) 且p fn e ；a 由线图的定 义知，在( 皿) 中p f e ；显然巳n p ：gje f np 芋g ，所以三( 日。) 兰( 日：) 证 1 9 内蒙古师范大学硕：士：学位论文 4 参考文献 1 卜月华图论及其应用 m 南京：东南大学出版社，2 0 0 2 7 ：卜2 2 梁达荣m a t h e m a t i c a le x c a l i b u r ，2 0 0 3 8 ( 3 ) ：6 7 3 黄庆学，许康华浙江大学学报( 理学版) ：2 0 0 2 ( 0 6 )