（运筹学与控制论专业论文）关于图的测地数的一些结果.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本文不 包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名：董逊日期：全么至么圣7作者签名：值确奎日期：0 6 么6 么2 7 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的 电子版和纸质版有权将学位论文用于非盈利目的的少量复制并允许 论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据 库进行检索。有权将学位论文的标题和摘要汇编出版保密的学位论 文在解密后适用本规定。 学位论蓦佧者签名：，导师签名：匕多铲 日期：三鞯d 5 ) 7 日期：眨弹己7 论文摘要 图的测地数以及测地谱是揭示图的结构特性的一个重要参数它可以看 作凸集概念在图论中的某种推广 本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工 作，主要的工作包括以下四个部分：( 1 ) 无向图及其定向图的测地集的一些性 质；( 2 ) 下测地数g _ ( g ) 的一些界；( 3 ) 对问题烈g ) 羔矿( g ) 的努力以及从中得到 的二者的一些界；( 4 ) 特殊定向规则下的几类特殊图的测地谱的探讨。 本文的主要结果有t 1 测地集与点割集，连通分支间的一些关系。 2 对于连通图g 的任意一棵生成树r ，下测地数g - ( g ) 不超过树r 叶子的个 数f ( 丁) 。 3 对于弦图，不含3 圈的图，以及色数z ( g ) 4 或z ( g ) 玎一4 的”阶连通图， 都有烈g ) 旷( g ) 。 4 当肝充分大时，几乎所有的h 阶竞赛图g 的测地数 _ ” 甙g ) 【兰j + l 二 且当n 3 时，行阶完全图的强连通定向测地谱 s ，( ) ( 2 ，3 ，f 兰1 l 关键词：凸集；测地集；测地谱；测地数；弦图；竞赛图；强连通 a b s t r a c t t h eg e o d e t i c 肌m b e ro fg r 印h si sa ni m p o n a n tp a r a m e t e rr e v e a l i n g 恤es t m c t l l r a lc h a r - a c t e ro fg r a p h s t h eg e o d e t i cn u m b e ro fg r a p h so r i 酉n a t e d 丘d m 1 ec o n v e xs e tt l l e o r yo f g e o m e t 阱t o p o l o g ya i l df i l n c t i o n a la 1 1 a l y s i sa n di s 也eg e n e r a l i z a t i o na i l da p p l i c a t i o no fc o n - v e xs e tt h e o r yi ng r a p ht h e o r y i nt h i st h e s i s ，w ew i l lc o n s i d e rt h eg e o d e t i cn 啪b e ro fg r a p h sa n dd i a g r a p h s ，a l l d r e s e a r c hr e s u l t so fm i n e 盯em a i n l yp r e s e n t e d m em a i nc o n t e mo ft h e 也e s i si v o l v e st h e f o l l a w i n gf o u rp a n s ：( 1 ) s o m ep r o p e r t i e sa b o u tt l l eg e o d e t i cs e to fg r a p h sa n dt h e i ro r i e n t a t i o n s ( 2 ) s o m eb o u n d so f 也el o w e rg e o d e t i cn u n l b e r 旷( g ) ( 3 ) s o m ee n d e a v o rf o rm ep m b l e m 烈回矿( g ) a n ds o m eb o l l i l d so f t h e s e 俩op a r a m e t e r s ( 4 ) s e v e m ls p e c i a lg r 印h s g e o d e t i c s p e c t n l mu n d e r t 、) l ，op a n i c u l a ro r i e n t a lm l e s h e r ei st h em a i nr e s u l t so f t l l i st h e s i s ： 1 s o m er e l a t i o n sb e t w e e nv e r t e x c u ts c t ，c o m p o n c 呲a n dt h eg e o d e t i cs e t ； 2 f o ra n yc o n n e c t e dg r a p hga n da n ys p 锄i n g 仃e er o f g 髫_ ( g ) “妁，w h e r cf ( 乃i st h e n u m b e ro fl e a v e so fr ： 3 烈回矿( g ) i st m ef o rc h o r d a lg r 印h so rg r a p h sw i i hn o3 - c y c l eo rg r a p h sw i t hc h m m a t i c n u m b e r 名( g ) 4 0 r z ( g ) 疗一4 ； 4 w h e nhi sl a r g ee n o u g h ，f o ra l m o s te v e r yt o u m a i n e n t sgo f o r d e f 行，g sg e o d e t i c 肌m b c r 甙面 网的独立集s ， 则称s 为g 的最大独立集向甜泐“研加却翻加f s p 砂。图g 的最大独立集的顶点 数称为g 的独立数删劬删如肼删珊6 圳，记为似g ) 本论文中涉及的图都将是简单图，以下我们先介绍几类简单图；如果”阶 图g 中每一对不同的顶点间都有一条边关联，则称g 为完全图r c d 唧把把g 唧矽， 记作。如果图g 的顶点集可以分成两个非空子集石和】，使得每条边都有一 个端点在x 中，另一个端点在y 中，则称图g 为二部图伪和d ，打，e g r 印砂；如果z 中的顶点与y 中的顶点均有边相连，且闺= 搠，| 】1 = ”，则称图g 为完全二部 图，记作。= 仪】，) 连通的无圈图称为树一愆砂，树中度为l 的顶点称为树的 叶子似劝，记树r 中所有叶子的个数为，( 树的叶子均是树中的极点称r 为图g 的生成树细册”垤抛叫如果丁既是g 的生成子图又是树。 给定一系列概率空间，令g 。为第雅个概率空间中性质q 成立的概率，称性 质q 几乎总是向锄f 口吲成立，如果l i _ + 。吼= 1 相应地在图论中，第月个 概率空间即为h 阶图的概率分布，而称几乎所有向砌f 讹圳的图都具有性质 q ，如果此时性质q 几乎总是成立 1 2 图的测地数的由来与相关概念 凸集是几何学、拓扑学和函数分析的基本概念对于任意j 。y 彳，一为度 量空间力中的点集，每条连接x 和_ y 的最短路( 曲线或弧) 完全位于彳中， 则称点集爿为度量空间的凸集；点集爿( z ) 的凸包阻】是在z 中包含彳的最 小凸集或包含一所有凸集的交图论中的度量空间( h g ) ，这里h 回是连通 图g 的点集，撒，力( 或简记为印是指两点工和y 之间的距离( 被定义为最短路 x y 的长度) ，我们把长度为以五力的工一y 路也称为z y 测地线如果对于爿中 的任意两点工和y ，每条工一y 测地线上的点完全含于彳中，那么连通图g 的点 集a 就是凸集。显然，y ( g ) 是一个凸集点集爿y ( g ) 的凸包口】是包含a 的 最小的凸集在b o n n e s e n 和f e n c h e i 所著的书【l 】前页初始段指出t 凸图形在几 何学已经起了重要作用；而m i n k o w s k i 创建一个恰当的工具被借用来处理凸 区域和几何的问题，并且也得到广泛地应用在b u c k l e y 和h a 州所著的书 4 中讨论了图的凸性，并在文献【1 5 被h 掘町和n i e m i n c n 所研究i 而图的凸数在 文献 1 4 】被e v e r e t t 和s e i d m a n 引入，并在文献 6 ，1 1 】中作了进一步研究在此研 究的基础上，人们提出了反映图的结构特性的参数一测地数图的测地数在 文献【3 中被引入，在文献 5 ，7 ，8 和【9 中作了深入地研究在文献 1 l 】中又被 g c h a r t r a n da n dp l z h a n g 推广到有向图 6 第一章引言 在连通图g ( 有向图否) 中，一条群一删地线侮d 妇叫是指顶点“，v 间的最 短路( 从”出发到达v 的有向最短路) 令j ( “，v ) 表示“一v 所有测地线上顶点 的集合。对于以回( 以g ) ) 的非空子集s ，令岛 ) ( 如岱) ) = u 。，。s ( “，v ) 如果 如( s ) = h g ) ( 如岱) = y ( g ) ) ，则称s 是g ( g ) 的测地集f l d 幽斑j p 砂，并把测地集 的最小基数称为g ( g ) 的测地数瞧d 如“c 聆“卅6 p 一，记为甙g ) ( 烈g ) ) 对于任何一个无向图g ，将它的每条边赋予一个方向得到一个有向图g ，称 g 为g 的一个定向图向r 泐把d g 唧彬对于每一个定向图g ，我们类似定义g 的测 地线，测地集和测地数，不过应该注意的是：在定向图中，“一v 测地线和v 一群测地 线是两条不同的有向路；如( “，v ) ) 表示g 中所有位于“一v 测地线和v 一甜测地线上 的顶点集合。定义g 的测地谱n 弘d 沈f j c 印卯n w 圳s ( g ) = i 烈g ) ：g 是g 的定向图1 而定义图g 的下测地数阳懈g 即如如盯绷6 9 ，炒( g ) = 小胁s ( q ；图g 的上测地数 n 衅妒p ，萨。出比n “m 6 圳，记为矿( 回= 晰甄s ( g ) 而定向图g 被称作g 的最小谱定 向阳加f 州“埘印b c f ，w m o r 明细踟砂，如果烈g ) = g _ ( g ) ；类似地称g 为g 的最大谱定 向阳甜砌聊印p c f ，w 晰d r f 8 招f f d 彬，如果g ( g ) = 矿( g ) 本节中未介绍的符号和概念，若在下文中出现请参考所出现的相应章节 7 第二章关于测地集的一些性质 2 1 测地集以及测地数的一些已有结果 由测地集的定义，我们可以体会到：无向图的最小测地集关于顶点间 邻接关系的变化是极其敏感的，比如说对于玎阶完全图。g ( ) = 即如 的最小测地集就是h ) ；但是对于图妫e ，p = v 1v 2 为蜀中的任意一条边， 则有甙蜀8 ) = 2 ，l ，屹) = 以蚝e ) 。同样对于定向图g 而言，g 的最小测地 集关于边定向的变化也是敏感的，比如对于月阶完全图的传递定向图 6 = v l ，v 2 ，1 ( 其中h 指向，当且仅当f ，) ，我们有甙g ) = n 。但是仅改变边 v ，h 的方向，则对于得到的蜀新的定向图g 7 ，有甙g ，) = 2 且如( v l ，h ) = 嗽，) 。 由此可以看出对于研究测地集问题而言数学归纳法可能很难起到很大的帮 助在文献【3 】中。已经征鲳判定图酌某个顶点子集是否是图的测地集是n p 完全问题。 以下我们列出部分国内外文献中已有的关于测地集、测地谱以及测地数 一些性质的重要结果t 定理2 1 1 【8 g 中任意一个测地集均包含g 中所有的极点。 定理2 1 2 【8 】对于n 阶完全图局、树丁、以及完全二部图墨。s 2 ) ，分别 有反) = h ；烈r ) = r ) ；甙墨。) = m i n s ，4 定理2 1 3 1 1 】定向图g 的任意一个测地集均包含g 中的所有的源顶点与 汇顶点。 定理2 1 4 【1 1 对任意”阶连通图g 3 ) ，矿( g ) 旷( g ) 定理2 1 5 1 1 】令d 为玎阶有向图，则烈d ) = n 当且仅当d 是传递定向的。 定理2 。1 6 【l l 】任给自然数m ，玎。其中l 珂一l 扰( 象烈存在边数为加的 ”阶连通图g ，使得矿( g ) = 以。 定理2 1 7 5 任给自然数肌，h ，其中l 珂一l 埘( ；) ，则存在边数为m 的 阶连通图g ，使得s ( g ) = 2 ，3 ，l 定理2 1 8 5 】对于完全图羁、圈g 、树丁、以及完全，部图娲。0 l 。脚 2 ) ，分另4 有s ( ) = s ( 为0 = s ( 如。，。) = f 2 ，3 ，月 ；s ( c ；) = 3 u ( 2 s ：2s2 ss h ) ；s ( r ) = f 坝r ) ，m 8 第二章关于测地集的一些性质 2 2 点割集、连通分支与测地集 定理2 2 1 设s 为连通图g 的点割集，c 为g s 的任意一个连通分支，若 g 【s 】构成一个圃，则 1 对图g 的任意一个测地集，以c ) n 妒 2 设g 为g 的一个定向图，对g 的任意一个测地集，若g 中不含有向圈， 则h o n ；进一步地，若s 仅为一割点，则对g 的任意的定向图g ， 上述结论成立。 证明1 假设存在g 厣的一个连通分支c ，使得h c ) n = 驴，则v v r ( c ) 必存在两个不同的顶点，v f ( 其中，u 联c ) ) ，使得v ，g 帆，h ) 。 因为s 是图g 一个点割集，则如( v ，) n s 妒，尼( v ，h ) n s 妒对v 如( v ，k ) n s ，v 6 坫( v ，m ) n s ，显然，否则v 岛，v ，) ，又因为s 的导出 子图为一个团，则v 6 e ( g ) ，而路k 一一一一一一h 其长度小于，v f 间的最短路b 一一一一v 一一v 6 一一v f ，矛盾 2 假设存在g 厣的一个连通分支c ，使得h c ) n = 驴，则v v h c ) 依然 存在两个不同的顶点k ，v f v ( 其中k ，h 以c ) ) ，使得v 如帆，v f ) ，同上 曩( v ，) n s 庐，岛( v ，u ) n s 妒不妨设最( ，v ) n s ，v 6 岛( v ，v ，) n s ，显 然”如因为定向图g 中不含有向圈，则v 口e ( g ) ，类似地g 中存在一 条更短的从出发经过边到m 的有向路，所以矛盾若s 仅是一个割 点，则证明是简单而类似的。 由此我们得到下面的推论，这些推论包含了 1 1 】的部分结果 推论2 2 1 连通图g 的任意一个极点都属于g 的每一个测地集；而对于g 的任意一个不含有向圈的定向图弓，图g 的任意一个极点也属于否的每一个 测地集。 推论2 2 2 ( i ) 连通图g 中任意一个最小测地集m 都不包含g 的任何割点， 因此对于树丁，有烈丁) = “r ) ； ( i i ) 若v 为图g 的割点，且g v 具有至少3 个连通分支，则v 不属于g 的任意 一个最小谱定向图的任意一个最小测地集中 证明1 设v 为图g 的割点，c l 与岛为g v 的两个连通分支，假定m 为g 的 一个最小测地集且1 ，时，则由定理2 2 1 知m n h c l ) 驴，肘n 以c 2 ) 妒不 妨设吖n h c l ) ，v f m n 联c 2 ) ，显然岛，v ) c 尼“，u ) ，如( v ，计) c 尼饥，h ) ， 9 董琳：关于图的测地数的一些结果 因此岛( m v ) = ，g ( 旧= 以g ) ，而这与m 为g 的最小测地集矛盾。 2 设g 为g 的最小谱定向图，甙g ) = 矿( g ) ，而 为g 的最小测地集。假定v m 且c l t q ( 女3 ) 为g 一_ l ，的连通分支，则由定理2 2 1 知时n h c l ) 妒( 1 i 妁 对于每一个连通分支c f ( 1 f d 都必定存在一个顶点v f m n 以c f ) 使得 与顶点v 之间总有一条有向路连接，否则不妨设存在_ ，l ，2 ，七使得c ，中 不存在m n h g ) 中的顶点与u 间的有向路，因此如( m n h c ) ) = 以c ) - 设 x g ( v ) n h g ，) ，显然xgm ，而x 必定位于m n h c f ) 中的某两个顶点的 有向测地线上，因此无论边肼如何定向，m n 以c f ) 与顶点v 间一定有一 条有向路。 由于七3 ，那么通过改变某些连通分支中所有边的定向，( 如果有必要的话) 我 们可以得到g 的另一个新的定向图g 7 ，使得对每一个v mnh c f ) ( 1 f 妨 如果在g 中存在一条由v i 出发到v 的有向路那么g 7 中也一定存在一 条由v 出发通向顶点f 的有向路，其中”，m nh c 从f ) ，反之如 果在g 7 中存在一条由v 出发到v ，的有向路，则同上亦然。所以如( v ，f ) = ( v f ，v ) u 吩( v ，u ) ，抑或略，v 1 ) 2 ( 叶，v ) u ( v ，v j ) ) ，即白( m v ) = ( m ) = “g ) ，此与g 7 为g 的一个最小谱定向矛盾 注；如果g v 仅有两个连通分支，则推论2 2 2 中的结论则不一定正确，如下 图所示，割点v 属于g 的任意一个最小测地集，而g 为g 的一个最小谱定向。 以下，我们再给出一个与定向图测地集有关的结构。 定义2 2 1 定向图g 中，称s 为g 的极大无有向圈定向子图，如果当s 的 诱导子图弓陋 不含有向圈且对于任意v h 否) 郴) ，弓陋u v ) 中含有有向圈 性质2 2 1 定向图否中的任意一个极大无有向圈定向子图s ，其顶点集 “s ) 是g 的测地集。 证明由于极大无有向圈定向子图定义中的极大性，与2 ，可知对于 任意顶点v 以g ) 博) ，在s 中都存在至少两个顶点地，轨，使得顶点v 指向 ，顶点蜥指向v ，而且在s 中只存在从至蜥有向路所以v 5 ( 嘶，“s ) 。所以 ( h s ) ) = h g ) 。 1 0 第三章图的测地数及其上、下测地数 3 1 下测地数的一些界 我们先把无向连通图g 的顶点进行标号，接着根据标号按某种规则对g 的边进行定向得到定向图g ，我们将通过g 考察g 的下测地数的一些性质。 令三为由h g ) 映射至正整数的函数，根据如下规则，我们可由标号函数工得 到g 的一个定向图g ： 对任意昱( g ) 】如果j 三( “) 一上( 卜l ，那么g 中 v 间的方向是由标号较小的顶点指向标号 较大的顶点 2 如果1 三( “) 一工( j 2 ，那么g 中”v 间的方向是由标号较大的顶点指向标号 较小的顶点。 3 如果i ( “) 一上( v ) 悻o ，那么任意定义：n j 间的方向 引理3 1 1 设g 为由无向连通图g 通过上述标号方法而生成的定向图，则 对于g 中的一条有向路p ：= v l ，v 2 h = v 。如果p 中顶点的标号从h 至v 依次 增加1 ，那么p 是g 中的一条“一v 测地线 证明不妨设p = 以“、) ，v 2 咖) 是弓中的一条“一v 测地线，由如上的定向规 则可知鲰) ! 工j - 1 ) 1 1 ( 2 墨f 0 ，因此0 ) 十卜。1 由于( y ) = 上( 砷+ t 一1 ， 所以t 蔓f 因此p 为g 中“v 问的一条测地线。 定义3 1 。l 设g 的路覆盖c ( g ) = p i 兄，只 为g 中点不相交的路只( 1 f 蔓0 的集合，且h g ) 中的每一个顶点都位于c ( g ) 中的某一条路上 对于g 的每一个路覆盖c ( g ) = p 1 ，p 2 ，只】，令c l ( g ) ，c 2 ( g ) 是对集合c ( g ) 的一 个分戈0 。如果路只的两个端点中至少有一个墒点与b 上的任意一个顶点关联， 其中1 ， 遮c ，则p j c i ( 回；否则只e 巴( g ) 不妨令i a ( g ) bc l ，ic 2 ( g ) bc 2 引理3 1 2 对于连通图g 的任意一个路覆盖c ( g ) ，矿( g ) c 1 + 2 c 2 证明先利用如下算法为路覆盖a g ) 中的路标号； 步骤l 令f - l 步骤2 为只上的顶点标号，如果只= ，v 2 ，ec l ( g ) ，则不妨设( v 1 ) n 咿，) 妒( 15 ， f 0 并任取“( v 1 ) nh 毋) 如果已有0 ) = t ，那么令 l ( v i ) = 七+ f ( 1 f 曲 如果p j = v l ，也，k c 2 ( g ) ，那么令( v ，) = r ( 1 r s ) 如果p j = v l 也，k c 2 ( g ) ，那么令( v ，) = ，( 1 r s ) 董琳：关于图的测地数的一些结果 步骤3 如果f - c ，那么算法结束，否则f = f + l ，并返回步骤2 通过如上的标号，我们同样可以生成图g 的一个定向图g ，显然如果 尸= v i ，v 2 ) c 2 ( g ) ，则根据引理3 1 1 只为g 中v l 至k 间的一条有向测地线， 所以矿( p f ) 如( v l ，) ；又如果p l = v l ，v 2 ，b c 1 ( g ) ，由于尸l c 2 ( g ) ，那么必定 存在p _ 叫，v ；，q c 2 ( g ) ( 1 ， f c ) 使得从嵋一一v 1 一一的标号连续地 递增l 。因此根据引理3 1 2h p f ) 如( 嵋，) ，所以矿( g ) 烈g ) c l + 2 c 2 o 定理3 1 2 对于连通图g 的任意一棵生成树丁，矿( g ) “n 证明令v l ，v 2 r ) 为图g 的生成树r 的叶子，则对r 而言存在如下的一个 路覆盖c ( r ) = p 1 ，p 2 p m t ) 一1 】，其中p 1 = ( v 1 v i ( f ) ) c 2 ( r ) 而对于( 2 曼f f ( r ) 一1 ) 有只c 1 ( r ) 且p f 的其中一个端点为 显然c ( 丁) 也是对图g 的一个路覆盖， 由弓i 理3 1 2 可知旷( g ) 2 + f ( r ) 一2 = ，( r ) 。 由定理3 1 2 我们可直接得出如下推论 推论3 1 1 1 1 如果图g 包含一条汉密尔顿路，则矿( 回= 2 我们试图回答：无向图g 的测地数甙回是否总位于其测地谱中，在 1 3 】中 吕长虹老师给出了如下的反例： x i ： w 一 图3 1 ：图日g ( 哪= 3 而g - ( 印4 进而他证明了对于任意正整数m ，n ( 9 n 蔓m 虻警苎+ 9 ) ，都存在边数 为川的h 阶图g 使得甙回 g - ( g ) 。但是对于旷( g ) 墨甙g ) 目前还没有2 连通图的 反例，而对于测地数甙回与上测地数矿( g ) 而言，是否一定有甙g ) 矿( 回呢? 1 2 第三章图的测地数及其上、下测地数 3 2 关于问题g ( g ) 矿( g ) 及其相应的一些界 在本节中，我们对问题g ( g ) 旷( g ) 作了如下的努力，并在其间分别给出 了这两个参数的一些界首先，解决此问题的一个很自然的想法是找到g 的 一个定向图g ，使得图g 的某个最小测地集中的顶点在g 中均为源顶点或者 汇顶点，即根据定理2 1 3 就可证明并且吕长虹老师在 1 3 中利用这一想法 得到如下结论：如果连通图g 其直径为d ，则矿( g ) d + 1 且矿( g ) = d + l 当且 仅当g 是一条长为n 的路。但是由于我们对无论是有向图还是无向图的测地 集的性质都知之不多，这种思路无法进一步展开以下本节的努力很大部分 都是建立在引理3 2 1 的想法之上 引理3 2 l 设图g 的任意一个定向图g ，对任意甜，v h g ) ，如果( ( “，v 1 ) ，g ( v 】) ，则反g ) 矿( g ) 证明不妨设g 的最小测地集为 v 】，则如( f v l h ) ) 如( v 1 ，虬1 ) = 以g ) ，因此旷( g ) 烈g ) 甙g ) 。 定义3 2 1 有向图g 中从顶点“到顶点v 间的距离折s f ( 甜，v ) 为从“到v 的最短 有向路的长度，若g 中不存在任何从“到v 的有向路，则锇s 如，v ) = o o 而有向 图g 的直径出口聊( g ) = m 口x i 硪s f 似，v ) o o ：v 甜，v 以g ) 引理3 2 2 设图g 的任意一个定向图g ，如果g 无有向圈，且矾硎( g ) 蔓2 ， 则烈g ) 旷( g ) 证明因为g 中不含有向圈，则对任意l f ，v “g ) ，如果磙s f ( 甜，v ) o 。，那么 就意味着d 括f ( v ，“) = o o 。如果讲s f ，v ) = 讲s 如，“) = o o ，那么如( v 1 ) u 如( u “1 ) = f “，v ) 七( ，v ) ；如果讲s f ( “，v ) = l ，则砖( ，v 1 ) u 岛( f v ，甜) ) = 地v ) 七( “，v ) ；一如 果矾s f ( “，v ) = 2 ，那么( f “，v j ) u 是( v ，“”= 墨( 似，v ”尼( ”，v ) 由引理3 2 1 可知 颤g 矿( g ) o 图g 的一个后顶点着色是指i 种颜色l ，2 ，i 对于g 的各顶点的一个分 配；称着色正常的，如果任意两个相邻顶点都分配到不同的颜色于是无环 图g 的一个正常七顶点着色是把联g ) 分成足个( 可能有空的) 独立集的一个分 类( 巧，琏，圪) 当g 有一个正常七顶点着色时，就称g 是后顶点可着色的g 的色撕( g ) 是指使g 为七顶点可着色的数七的最小值 定理3 2 1 对于栉阶连通图g ，假设其色数从g ) = 克，如果| | 4 或者| 报一4 ， 1 3 董琳；关于图的测地数的一些结果 那么g ( g ) 矿( g ) 证明1 令雎是着色为f 的顶点集( f 1 ，2 ，喊ls 忌4 ) ) ，则k 为一独 立集。现在我们对e ( 回按如下规则定向：对v w e ( g ) ，其中甜k ，v 巧。则 ”v 间的方向为指向v 当且仅当f ( s ：。) 则无论成s f ( ”，v ) = 2 或者3 ，根据引理3 2 2 都有 如( 1 甜。y j ) 如( 甜，v ) 因此，对于情形2 结论成立，同样地我们对于n = ，“2 ，) ，玛= v l ，也，v 3 ，v 4 ，2 = ( 1 j 玎一6 ) 也可类似地完成证明。 情形3 t 假设n = ，“2 l ，圪= ( ”l ，v 2 ，巧= l ，赴，如) ，k 柏= 协 ( 1sf ”一7 ) 且设 ，= k ，品一7 则k 中一定存在至少一个顶点，不妨设为地，对于任 意的顶点m ( 1 f 玎一6 ) 都有“l j e ( g ) 否则的话，假定存在5 ，u 使得甜1 3 ，ge ( g ) ，那么一定有“2 8 ，日( g ) ，交换“2 5 ，所着的颜色使得 n = “s ，l ，u = 叫忸，】u ( “2 ，而此时由于g 的色数为胛一4 ，则5 f 与u 中 所有的顶点均有边关联同样地我们设v 1 岛e ( g ) ( i f s 玎一7 ) 通 过交换着色，我们令u l 着色1 。u 2 着色2 ，而u 3 着色n 一4 并且同时使 得工( s 纛) 三( j 麓。) 。则对于按如此着色生成的定向图g ，我们将仅讨论 如下的情况，并已略去情形2 中已经罗列过的类似情况： i 对于任意顶点地n ，。，k ( 1s i ，_ ，2 ) ，则在g 中矾s f ( ，v ，) = 1 或者 讲s f ( 嘶，叶) = 试对于l f n 一7 。”l s f ，v 1 日e ( g ) 且对于任意蚝( 1sf 3 ) ，g 中 d 扭“t ，鑫) s2 ，d 括瑾v h 矗) 2 i i i _ 对于n 中任意顶点，不妨设为“，如果三( s ：。) f 此与 l + + 2 + + 旷已达到最大值矛盾不失一般性，我们假定存在虬巩。蜥巩， 其中j _ 1 - 如果s 则且s ) x l 一l f ，否则假设 ，则必定存在j ( 1 f 砷使得，蜥乩，由于边“h 蜥的定向， 则 f f 且 即+ l f ，由于顶点的简单消去序的性质，则蜥，坼e ( g ) ，因此存在有 向路p = ( ) 一圾。一一蛾，一地的长度小于最短路p ，矛盾所以 岛( ，嘶) u ( 广) 尼( 矿) u ( “矗七( f ，“d ul ，) 如果s r ，则类似地由简单消去序的性质，我们可以得到最短路p 的长 1 8 第三章图的测地数及其上、下测地数 度小于等于2 因此如“蜥，嘶l 如( ，“，) 4 如果驴，砘e ，则类似于3 中的证明，我们可得如( ) u 矿) 站( 嘶 u ) 因此，对g 的任意一个最小测地集m 都有如( 均七( 均，则矿( g ) 甙g ) = i m 烈g ) 。o 在某种程度上，本文中的定理具有些个对称的意味，比如在上文中对于问 题甙回sg + ( g ) ，我们完成了对于不含3 圈的图以及弦图，或者z ( g ) 4 以及 z ( g ) i h 回卜4 的图的证明，即对于边相对较少或边相对较密集的图，结论 均成立。但是在证明中所采用的方法基本也都是针对那些特殊图类性质本身 的，可能很难推广到更一般的图上其根本原因还是在于我们对测地集本身 性质刻画的不够深入，在此我们将问题t 对于任意连通图g 都有矿( 回烈g ) 作为猜想提出。 1 9 第四章几类特殊图在限制定向下的测地谱 在本章，我们考虑两类具有相对意义的定向图，无有向圈定向图与强连 通定向图，并比较在此两种定向的影响下几类特殊图测地谱的差异，从而进 一步体会测地集与不同定向间的关系 4 1 无有向圈定向下几类特殊图的测地谱 首先我们考察由连通图g 的所有无有向圈定向的定向图构成的集合g 7 1 ， 并仿照测地谱与上下测地数的定义，给出 定义4 1 1g 的无有向圈定向测地谱为s r ( g ) = 甙弓) ：弓eg 丁 而相应 地定义图g 的下传递测地数簖( g ) = m i 心r ( 回，图g 的上传递测地数薛( g ) = m a 心r ( g ) 图g 的传递定向图总是无有向圈定向图，由定理2 1 5 我们可类似地推出 定理4 l 1s r ( g ) = 脚当且仅当图g 为完全图 证明当g 为完全图，设g 为6 的无有向圈的定向图，则g 在同构意义 下是唯一确定的，所以g i ( g ) = 酵( g ) = 行 不妨假设g 不是完全图，则存在虬v h g ) ，使得甜vg e ( g ) 所以顶点“，v 闻存在一条长度大于l 的测地线p = 甜，材i ，v 则对于6 的任意无有向圈 的定向图g 而言，如果在g 中p 仍是有向最短路0 比是容易构造的) ，那么 如( h g ) m 1 ) = 以g ) 所以甙g ) ，而此与无有向圈定向测地谱仅 为 ” 矛盾n 由定理2 ，1 ，8 ，我们可直接推出如下的结论，需要注意的是当h 为奇数时， 由于考虑的是不含有向圈的定向，则f 2 g s r ( g ) 定理4 1 2 仃长圈0 3 ) 的无有向圈定向测地谱 s r c g ，= ：； ：塞；! 塞i ：耋：舅罢萋5 定理4 ，l 。3 对于完全二都图，。( 掰，托4 ) ，s r ( 瓦。) = 1 4 ，5 。m + m 证明1 对于完全二部图。= ( u 即( i 硼= 小，i 卅= n ；m ，疗4 ) ，假设 存在蚝。的一个无有向圈定向图g ，使得烈g ) 3 不妨设百的一个测 地集为协l ，地，n l 。如果甜l ，地u 7 1 矿时，由于g 是无有离圈定向，不 第四章几类特殊图在限制定向下的测地谱 畲有有向圈，则是( 【”l ，h ) = 枷b v l ，而毛“，v l ) = ，1 ，l 那么对于顶点 啦( f 1 ，2 ) 而言，啦一定落在甜l ，“2 问的某条测地线p 上，不失一般性我们 设尸= “l ，叶撕，“2 ，那么边“i 的定向必定是由指向甜i ，此与g 中 不含有向圈矛盾。同样地当材l ，“2 ，v - 都同时属于顶点集u 或者y 时，证明 类似所以对于，。的任意无有向圈定向图g ，都有g ( g ) 4 。 2 不妨设在完全二部图如，。= ( un 中，顶点集u = “n ，。 ，矿= v 且州胛。我们将按照如下规则为，。定向以生成定向图g ，使得g ( g ) = 缸 i 当4s 詹n 时： 定义顶点集 v ，一3l 与顶点集u 间所有边的方向为由( 1 f 七一3 ) 指向u ； 定义顶点与顶点集u 间所有边的方向为由u 中的顶点指向h ； 定义顶点集f m ，甜。一l 与址2 ，v 州 间所有边的方向为由煎者 指向后者； 定义顶点与f ，2 ，h 1 ) 间所有边的方向为后者指向前者 显然g 是无有向圈定向的由推论2 2 1 可知源顶点v ，睢3 与汇顶 点h 属于g 的任何测堍集又容易知道毛( v ，h 。甜i ，) ) = h g ) ， 而如( v l ，3 ，h j ) = u u ( w 协2 ，h 1 1 ) ch g ) ，且疗一七十2 2 ，所以 七一ls 窖( g ) | | 对于任意顶点v j ，当f s ，f 时，v fg 厶( 他，v 。 ) ；而同时当 f 5 时，都有砖圣 比，砧= z 娟k ，鲍 ) 所以甙g ) 七一l ，即g ( g ) = 女， i i 当n + l l j + n 时： 定义顶点集w m l 与顶点集u 间所有边的方向为由v f ( 1 冬f 蔓”一1 ) 指向u ； 如果t 聊十疗，那么定义顶点h 与顶点集协，仇一。】间所有边的方 向为前者指向后者；而h 与顶点集叫( “昧。 间所有边的方向 为后者指向前者 如果七= 州+ 珂，那么定义顶点h 与u 间所有边的方向为由v 月指向u 。 同样，在如此定向下生成的定向图g 是无有向圈定向的，且容易知道 ”i h l 为源顶点同时“l ，坼。为汇顶点，而且如( v l ，h - l l i ，鲰一。 ) = ( ”l ，小“1 ，姗一。) c 以g ) 但是如( 矿uf “1 ，“扣。1 ) = 以g ) 所以 一l 反g ) 竞，鄢反g ) = 露 综上所述，完全二部图麟。( m ，行4 ) 的无有向圈定向测地谱 s r ( ，1 ) = 4 ，5 ，埘+ 以 口 2 1 董琳t 关于图的测地数的一些结果 4 2 强连通定向下几类图的测地谱 最后我们考察由连通图g 的所有强连通定向( s 讯i n 9 0 r i e n t a t i o n ) 的定向图 构成的集合g s ，给出 定义4 2 1g 的强连通定向测地谱为s s ( g ) = 烈6 ) ：g 傩) 而相应地定 义图g 的下强连通测地数菇( g ) = m i 酊s ( g ) ，图g 的上强连通测地数醇( g ) = m a