（应用数学专业论文）图的度序列和竞赛矩阵.pdf

a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rt h ev a r i a t i o n so ft h ec l a s s i c a lw o o d a l lt h e o r e mi ne x t r e m a l g r a p ht h e o r ya n da na p p l i c a t i o no fs c h u rf u n c t i o n so nt h ep o s e ro fs c o r ev e c t o r s i nc h a p t e r1 ，w ed i s c u s sav a r i a t i o no ft h ec l a s s i c a lw o o d a l lt h e o r e m ：d e n o t eb y 盯( 3 c lj 凡) t h es m a l l e s te v e ni n t e r g e r r ns u c ht h a te v e r yn t e r m g r a p h i cs e q u e n c e 丌= ( d 1 ，d 2 ，d n ) w i t ht e r ms u m 口( ”) = d l + d 2 + - + d 。t o , h a sar e a l i z a t i o nc o n t a i n i n ga c y c l eo f l e n g t hrf o re a c hr ，3 r f w ed e t e r m i n et h ev a l u e so f t t ( 3 c l ， ) f o r4s ls8 a n dn fa n d 口( 3 ( 奄，n ) f o rn 1 2 i nc h a p t e r2 ，w ed i s c u s ss c h u rf u n c t i o n so nt h ep o s e to fs c o r ev e c t o r s ：t h es e tl no f a l ln t e r ms c o r ev e c t o r si sap o s e r ( i , e ，p a r t i a l l yo r d e r e ds e t lu n d e rm a j o r i z a t i o nr e l a t i o n ar e a lf u n c t i o ng ( s ) o nt h ep o s e tl ni s ( s t r i c t ) s c h u rc o n v e xi fg ( s ) ( ) g ( s 7 ) f o ra n y s ，5 7 l n ，s s ) sm a j o r i z e ss 7 w ep r o v et h a t ( s ) = s t sa n dc 3 ( s ) ，t h en u m b e ro f 3 - c y c l ei na n yt o u r n a m e n t w i t hs c o r ev e c t o r ss ，a r es t r i c ts c h u rc o n v e xa n ds t r i c ts c h u r c o n c a v er e s p e c t i v e l y an t e r ms c o r ev e c t o rsi ss i n g u l a ri fe v e r yt o u r n a m e n tm a t r i xw i t h s c o r ev e c t o r ssi ss i n g u l a rb yu s i n gt h es t r i c ts c h u rf u n c t i o n ( s ) o nt h ep o s e tl nw e g i v eas u f f i c i e n tc o n d i t i o nf o ras c o r ev e c t o rb e i n gs i n g u l a r 1 1 基本概念 第一章蕴含s g 可图序列 所有满足n 一1 d l d ：d 。0 的整数序列”= ( d l ，d 2 ，如) 的集合记作 n s 。设”n s 。，称”是可图的，若”是n 阶简单图的度序列这样的图称作” 的一个实现记g ( ”) 为”的所有实现的集合所有n 项可图序列的集合记作g s 对可图序列”= ( d 1 ，d 2 ，d 。) g s ，记( ”) = d - + d 2 + + d 。，称口( ”) 为”的度 和另记，( ) = m a z i ：d l i ，lsisn ) 为”的迹记 ，i ( d l 1 ，d k l 一1 ，d k + l l ，- 一，d d k + 1 1 ，d d + 2 ，d 。) ，若d k k ， 一1 ( d 1 一l ，d 以一1 ，d d k + 1 ，一，d k 一1 ，d k + l ，一，d 。) ， 若d k 一1 ， 则”称为从”删掉( 1 a y i n go f f ) d k 后得到的剩余序列 对给定的z 晶，定义n 阶矩阵万( z ) = ( a i j ) 如下： 当1 i 曼，( ”) 时， f1 ，l j i d i + 1 ， ，2 1o ，其它， 而当，( ”) + l 茎isn 时， = 菇剑” 称万( 丌) 为”的对角限制极左矩阵 对任意的n 阶矩阵a = ( 。) ，记7 i = 墨。a i j ，s j = ，n 。1 i ，jsn ，向量 ( r 2 1 ，h ) 与( s 1 】，s 。) 分别称为a 的行和向量与列和向量由万( ”) 的定义可 知万( ”) 的行和向量为”记其列和向量为开，开称为”的校正共轭易知a ( ”) = 一( _ ) 一个可图序列”是蕴含( 强迫) g 可图的，若存在”的实现含有子图g ( ”的每个 实现都含有子图g ) 设n 和l 是正整数，且n f 3 称n 阶简单图g 具有性质3 a ， 若g 含长为r 的圈g ，其中r = 3 ，4 ，l 特别的，当l = n 时，也称g 是泛圈的称 可图序列”为蕴含。a f 可图的，若”有一个实现具有性质。白称可图序列”为强迫 。a 可图的，若”每个实现都具有性质。q 特别的，当f _ n 时，也称”是蕴含( 或强 迫) 泛圈可图的本章考虑了w o o d a l l 问题的变形：求最小的正偶数一( 。a ，n ) ，使得 所有满足a ( ”) a ( s c l ，n ) 的n 项可图序列”都是蕴含。o 可图的另外，设图g 和 日没有公共顶点，则用g u h 表示g 和日的不相交的并，用g + 日表示具有顶点 4 1 1 基本概念 第一章蕴含s g 可图序列 所有满足n 一1 d l d ：d 。0 的整数序列”= ( d l ，d 2 ，如) 的集合记作 n s 。设”n s 。，称”是可图的，若”是n 阶简单图的度序列这样的图称作” 的一个实现记g ( ”) 为”的所有实现的集合所有n 项可图序列的集合记作g s 对可图序列”= ( d 1 ，d 2 ，d 。) g s ，记( ”) = d - + d 2 + + d 。，称口( ”) 为”的度 和另记，( ) = m a z i ：d l i ，lsisn ) 为”的迹记 ，i ( d l 1 ，d k l 一1 ，d k + l l ，- 一，d d k + 1 1 ，d d + 2 ，d 。) ，若d k k ， 一1 ( d 1 一l ，d 以一1 ，d d k + 1 ，一，d k 一1 ，d k + l ，一，d 。) ， 若d k 一1 ， 则”称为从”删掉( 1 a y i n go f f ) d k 后得到的剩余序列 对给定的z 晶，定义n 阶矩阵万( z ) = ( a i j ) 如下： 当1 i 曼，( ”) 时， f1 ，l j i d i + 1 ， ，2 1o ，其它， 而当，( ”) + l 茎isn 时， = 菇剑” 称万( 丌) 为”的对角限制极左矩阵 对任意的n 阶矩阵a = ( 。) ，记7 i = 墨。a i j ，s j = ，n 。1 i ，jsn ，向量 ( r 2 1 ，h ) 与( s 1 】，s 。) 分别称为a 的行和向量与列和向量由万( ”) 的定义可 知万( ”) 的行和向量为”记其列和向量为开，开称为”的校正共轭易知a ( ”) = 一( _ ) 一个可图序列”是蕴含( 强迫) g 可图的，若存在”的实现含有子图g ( ”的每个 实现都含有子图g ) 设n 和l 是正整数，且n f 3 称n 阶简单图g 具有性质3 a ， 若g 含长为r 的圈g ，其中r = 3 ，4 ，l 特别的，当l = n 时，也称g 是泛圈的称 可图序列”为蕴含。a f 可图的，若”有一个实现具有性质。白称可图序列”为强迫 。a 可图的，若”每个实现都具有性质。q 特别的，当f _ n 时，也称”是蕴含( 或强 迫) 泛圈可图的本章考虑了w o o d a l l 问题的变形：求最小的正偶数一( 。a ，n ) ，使得 所有满足a ( ”) a ( s c l ，n ) 的n 项可图序列”都是蕴含。o 可图的另外，设图g 和 日没有公共顶点，则用g u h 表示g 和日的不相交的并，用g + 日表示具有顶点 4 v ( c + h ) = v ( c ) u v ( h ) 和边e ( g + 日) = e ( c ) u e ( h ) u 2 v ：z y ( g ) ，g 矿( 日) ) 的图 1 2 引言 极值图论是图论的一个重要分支它主要研究当一个图的边数超过某个界时，该图 必定含某种特殊结构的问题极值图论的核心问题是t u r d n 问题所谓t u r d n 问题 是：设日是一个图，求最小的正整数e x ( h ，”) ，使得当边数e ( g ) e x ( h ，n ) 时，每 个n 阶图g 都含有子图日数e x ( h ，n ) 称为图h 的t u r t 2 n 数经典的t u r t i n 定理 确定了k 阶完全图虬的t u r 6 n 数e x ( k k ，n ) ，即 定理1 2 _ 1 17 】设n 和为正整数，且n = ( 一1 ) m + r ，其中m 和r 为非负整数 且0sr 一 n 没 23 理定 现在设( 7 ) 对n 一1 1 2 成立，即，d ( 3 c 9 ，n 一1 ) s ( n 一1 ) 一1 8 下面我们证明 ( 7 ) 对n 成立设”= ( d l ，d 2 ，d n ) 是一可图序列且，( ”) 28 n 一1 8 只须证明一是 蕴含3 岛可图的因为f ( ”) 8 n 一1 8 且n 1 3 ，d l27 ，d 2 6 ，所以由定理1 2 9 ，” 是蕴含r t 6 可图的 若d 。4 ，则口( 7 r ) 口( ”) 一2 4 s ( n 1 ) 一1 8 由归纳假设，”是蕴含3 g 可 图的从而”也是蕴含s 西可图的 若厶5 ，则由引理1 3 8 ，”是蕴含3 岛可图的 因此( 7 ) 对n 1 2 成立所以当n 1 2 时，f ( 3 岛，n ) = 8 n 一1 8 口 1 4 结束语 如果比较一下a ( ，n ) 和口( 3 c z ，n ) 的结果是有益的，从定理1 2 7 ，定理1 2 8 ，定理 1 2 1 1 和定理1 33 ，定理l 3 6 ，定理1 3 1 4 ，有 憷兰麓1 托美竺 慨羔心篡n l o ： 口( 3 c 9 ，1 7 , ) = 口( 5 ，n ) ，当n21 3 时 我们猜想，当n 充分大时，有 ( 9 j f 1 0 1 换言之，利用a ( m ，n ) 来确定a ( 。c 2 。山n ) 和一( 。c 2 。，n ) 的值，可能是解决经典 w o o d a l l 问题的变形的一个有效途径我们将进一步研究之 1 8 第二章得分向量偏序集上s c h u r 函数和奇异得分向量 2 1 基本概念 设m = ( m i j ) 是n 阶( o ，1 ) 矩阵， 和k 分别是n 阶全1 矩阵和n 阶单位矩阵， e 是n 维全1 向量s = m e = ( s l ，8 2 ，s 。) 7 为m 的行和向量，其中a t 表示矩 阵a 的转置，而s ，是m 的第i 行上元素之和如果m 满足( o ，1 ) 矩阵方程 则m 称为竞赛矩阵易知竞赛矩阵m 是某个n 阶竞赛图t n 的邻接矩阵当m 为竞赛矩阵时，s = m e 称为m 或矗的得分向量易知对竞赛矩阵m 进行行 与列的同步置换。得到的矩阵m 7 仍是竞赛矩阵，而以m 7 为邻接矩阵的竞赛图 是由重新排列其顶点次序得到的，因此和砭是同构的所以可设得分向量 s = m e = ( s ，8 z ，s 。) 7 满足s 1 8 2 s n 称竞赛图为奇异( 非奇异) 的， 如果它的邻接矩阵m 是奇异( 非奇异) 的设s = ( s l s z ，) t 是得分向量，所 有以s 为得分向量的竞赛矩阵集合记作g ( s ) 如果任意m ( s ) 是奇异( 非奇异) 的，则s 称为奇异( 非奇异) 的 设g = ( ke ) 是n 阶简单图，其中y 和e 分别是g 的顶点集和边集设a = ( n 。) 是g 的邻接矩阵若a ( g ) 是奇异( 非奇异) 的，则g 称为奇异( 非奇异) 的，则g 称为奇异( 非奇异) 的 2 2 引言 图的特征值问题一直是图论中的一个重要的研究课题1 9 7 8 年，a j s c h w e n k 和 r j w i l s o n 在其综述性文章 2 5 中列出了有关图的特征值的5 个未解决问题中将刻 划非奇异图列为第一个问题从而激发了大家对图的奇异性的注意9 0 年代以来， 许多作者，如t k i t a m u r a 和m n i k e i 1 4 ，f k b e l l 和p r o w l i n s o n 1 等研究了图的奇 异性问题 图的奇异性问题概念自然地要推广到组合对称矩阵和竞赛图d c a r l s o n 吼d c a r l s o n 和d h e r s h k o w i t z 6 】研究了非奇异组合对称矩阵至于竞赛矩阵，r a b r u a l d i 和 h j r y s e r ( 1 ，第4 章第一节习题2 ) 指出 定理2 2 1 设r a n k m 是n 阶竞赛矩阵m 的秩，则n 一1sr a n k m n 1 9 第二章得分向量偏序集上s c h u r 函数和奇异得分向量 2 1 基本概念 设m = ( m i j ) 是n 阶( o ，1 ) 矩阵， 和k 分别是n 阶全1 矩阵和n 阶单位矩阵， e 是n 维全1 向量s = m e = ( s l ，8 2 ，s 。) 7 为m 的行和向量，其中a t 表示矩 阵a 的转置，而s ，是m 的第i 行上元素之和如果m 满足( o ，1 ) 矩阵方程 则m 称为竞赛矩阵易知竞赛矩阵m 是某个n 阶竞赛图t n 的邻接矩阵当m 为竞赛矩阵时，s = m e 称为m 或矗的得分向量易知对竞赛矩阵m 进行行 与列的同步置换。得到的矩阵m 7 仍是竞赛矩阵，而以m 7 为邻接矩阵的竞赛图 是由重新排列其顶点次序得到的，因此和砭是同构的所以可设得分向量 s = m e = ( s ，8 z ，s 。) 7 满足s 1 8 2 s n 称竞赛图为奇异( 非奇异) 的， 如果它的邻接矩阵m 是奇异( 非奇异) 的设s = ( s l s z ，) t 是得分向量，所 有以s 为得分向量的竞赛矩阵集合记作g ( s ) 如果任意m ( s ) 是奇异( 非奇异) 的，则s 称为奇异( 非奇异) 的 设g = ( ke ) 是n 阶简单图，其中y 和e 分别是g 的顶点集和边集设a = ( n 。) 是g 的邻接矩阵若a ( g ) 是奇异( 非奇异) 的，则g 称为奇异( 非奇异) 的，则g 称为奇异( 非奇异) 的 2 2 引言 图的特征值问题一直是图论中的一个重要的研究课题1 9 7 8 年，a j s c h w e n k 和 r j w i l s o n 在其综述性文章 2 5 中列出了有关图的特征值的5 个未解决问题中将刻 划非奇异图列为第一个问题从而激发了大家对图的奇异性的注意9 0 年代以来， 许多作者，如t k i t a m u r a 和m n i k e i 1 4 ，f k b e l l 和p r o w l i n s o n 1 等研究了图的奇 异性问题 图的奇异性问题概念自然地要推广到组合对称矩阵和竞赛图d c a r l s o n 吼d c a r l s o n 和d h e r s h k o w i t z 6 】研究了非奇异组合对称矩阵至于竞赛矩阵，r a b r u a l d i 和 h j r y s e r ( 1 ，第4 章第一节习题2 ) 指出 定理2 2 1 设r a n k m 是n 阶竞赛矩阵m 的秩，则n 一1sr a n k m - 5 易知n 维得分向量集合l 。在优超关系下是一个偏序集由定理2 3 3 易知，s 是偏序集l 。中的极大元，也是l 。中最大元记 i ( 孚，孚，孚) & ， 当n 为奇数， s = ( i n l ，虿n 一1 ，；一1 ，；，；，；) n s 。，当n 为偶数， 【了一r 容易验证，对于任意s l 。，均有s - 8 m i 。因此，s 。抑是偏序集k 中的极小元， 且是三。中的最小元 设s l 。，称s 是强得分向量，如果任意雪( s ) 都是强连通的f h a r a r y 和 l m o s e r 1 0 刻化了l 。中所有强得分向量下面是他们的结论： 定理2 3 4 设s l 。，且；= ( 1 ，1 ，2 ，3 ，- - ，n 一3 ，n 一2 ，n 一2 ) r ，则s 是强得分向 量，当且仅当；卜8 2 1 工。中所有强得分向量集合记作e 易知三：在优超关系下是一个偏序集，且i 和s 。i 。分别是e 的最大元和最小元记；= l 。，称s 三：为可约的由定理 2 3 3 和2 3 4 可知，s 是偏序集l ：的极大元从非负矩阵的角度而言，s l 。， 当且仅当任意r 雪( s ) 的邻接矩阵m ( ) 是不可约的 设x 是偏序集，g ( x ) 是偏序集x 上的实函数称g ( x ) 是s c h u r 凸( 凹) 的，如 果对任意。，y x ，z - y ，有g ( x ) g ( y ) ( 9 ( x ) g ( y ) ) 称g ( x ) 是严格s c h u r 凸( 凹) 的，如果对任意z ，y x ，。y ，z _ y ，有g ( z ) g ( y ) ( g ( x ) ，( s ( t + 1 ) ) ，i = 1 ，2 ，m 因此f ( s ) ，( s ，) 即f ( s ) 是l 。上严格s c h u r 凸 的 口 推论2 3 6 设s l 。，则 ( i ) ，( s ) 坐丑菩! ! 型，等式当且仅当s = s 时成立； ( i i ) 当n 为奇数时，( s ) 坐亍竖；当n 为偶数时，( s ) 坐；卿，其中等式 当且仅当s = 8 m i 。时成立 证明易得，( s 。) = 1 2 + 2 2 + + ( n 1 ) 2 = 业三攀堡坐，且 、i 旦与业， 当n 为奇数时， f ( s m i n ) 牮，雪：妥描蓑爵： 由于s 和8 m i 。分别是偏序集l 。的最大元和最小元，而f ( 8 ) 在工。上是严格s c h u r 凸的，因此推论2 3 6 成立 口 推论2 3 7 设s ，则，( s ) 坐兰擎业一2 ( n 一2 ) ，等式当且仅当s = ；时成 立 证明由于是偏序集l 。的子集，而，( s ) 在l 。j ：2 ：是严格s c h u r 凸的，因此，( s ) 在 上是严格s c h u r 凸的容易算得，( 司= 1 2 + 2 2 + 3 2 + + ( n 一3 ) 2 + ( n 一2 ) 2 + ( n 一2 ) 2 = 出生灿6 2 ( n 一2 ) 因此推论2 3 7 成立 注存在s 工：使得f ( s ) = ，( 功例如，当n = 6 时，( 司= 4 7 取s ： ( 1 ，2 ，2 ，2 ，3 ，5 ) 7 l 6 由于每个s ( s ) 均有一顶点”，它的得分( 即出度) 为5 ，故 矗不是强连通的，所以s 掣工6 易算得，( s ) = 4 7 = ，( ) 设矗es ( s ) ，r 中所有3 圈的个数记作c 3 ( 矗) j w m o o n 2 3 证明， c 3 ( b ) ： 坐；垮生型2 一 s 7 s = ( ，( s ) 一，( s ) ) 这表明c 3 ( t n ) 只和矗的得分向量s 有关， 而和矗本身无关因此，可将c a ( w ) 记作c 3 ( s ) 由于f ( s ) 在l 。上是严格s c h u r 凸 的，而c 3 ( s ) = ( ，( s ) 一，( s ) ) ，因此，c 3 ( s ) 在l 。上是严格s c h u r 凹的于是有 推论2 3 8 设s l 。，则c a ( s ) 0 ，等式当且仅当s = s 时成立 州泌 攀2 4 ，耋攥淼 等式当且仅当8 = s 。讯时成立 推论2 3 9 设s ，则c 3 ( s ) n 一2 ，等式当且仅当s ：；时成立 证明由于c 3 ( s ) 在上是严格s c h u r 凹的，且c 。( 功= ( ，( s 。) 一，( 司) ：n 一2 ， 因此推论2 3 9 成立口 2 4 奇异得分序列 本节将给出得分序列s = ( 钆s 。，s 。) 7 为奇异得分序列的一个充分条件 记靠= ( 1 ，1 ，2 ，3 ，n 一3 ，n 一2 ，n 一2 ) 了1 ，n 芝3 ，雪( 薪) 中n 阶竞赛图露的邻接矩 由于s 和8 m i 。分别是偏序集l 。的最大元和最小元，而f ( 8 ) 在工。上是严格s c h u r 凸的，因此推论2 3 6 成立 口 推论2 3 7 设s ，则，( s ) 坐兰擎业一2 ( n 一2 ) ，等式当且仅当s = ；时成 立 证明由于是偏序集l 。的子集，而，( s ) 在l 。j ：2 ：是严格s c h u r 凸的，因此，( s ) 在 上是严格s c h u r 凸的容易算得，( 司= 1 2 + 2 2 + 3 2 + + ( n 一3 ) 2 + ( n 一2 ) 2 + ( n 一2 ) 2 = 出生灿6 2 ( n 一2 ) 因此推论2 3 7 成立 注存在s 工：使得f ( s ) = ，( 功例如，当n = 6 时，( 司= 4 7 取s ： ( 1 ，2 ，2 ，2 ，3 ，5 ) 7 l 6 由于每个s ( s ) 均有一顶点”，它的得分( 即出度) 为5 ，故 矗不是强连通的，所以s 掣工6 易算得，( s ) = 4 7 = ，( ) 设矗es ( s ) ，r 中所有3 圈的个数记作c 3 ( 矗) j w m o o n 2 3 证明， c 3 ( b ) ： 坐；垮生型2 一 s 7 s = ( ，( s ) 一，( s ) ) 这表明c 3 ( t n ) 只和矗的得分向量s 有关， 而和矗本身无关因此，可将c a ( w ) 记作c 3 ( s ) 由于f ( s ) 在l 。上是严格s c h u r 凸 的，而c 3 ( s ) = ( ，( s ) 一，( s ) ) ，因此，c 3 ( s ) 在l 。上是严格s c h u r 凹的于是有 推论2 3 8 设s l 。，则c a ( s ) 0 ，等式当且仅当s = s 时成立 州泌 攀2 4 ，耋攥淼 等式当且仅当8 = s 。讯时成立 推论2 3 9 设s ，则c 3 ( s ) n 一2 ，等式当且仅当s ：；时成立 证明由于c 3 ( s ) 在上是严格s c h u r 凹的，且c 。( 功= ( ，( s 。) 一，( 司) ：n 一2 ， 因此推论2 3 9 成立口 2 4 奇异得分序列 本节将给出得分序列s = ( 钆s 。，s 。) 7 为奇异得分序列的一个充分条件 记靠= ( 1 ，1 ，2 ，3 ，n 一3 ，n 一2 ，n 一2 ) 了1 ，n 芝3 ，雪( 薪) 中n 阶竞赛图露的邻接矩 阵记为a 。( 霸) 可以看作。阶竞赛矩阵的集合记n 阶( o ，1 ) 矩阵磁为 m n2 a 。1 0 厶2 m a n 2 0 0 蓁鑫a ：i 幽鳓氐= 拼舅蠢+ 卜咖易知矾是。阶竞赛矩 矩阵，n i , n j 3 , 1i , j 茎，且 - + 3 , n l + - 2 , + h i ”- f - 2 ) t “, j 易r , 刘“no n 悬n i ”n 田j i 兄除贯k 怒t 3 j 1 l2 n ln 2 阵，其得分向量( 即行向量) 记作s i ，则有 定理2 4 1 ，( s ：) = ，( 蠢) + 4 ( t 一1 ) 证明当j ：2 时，易知s i = 霸一e 。十e 。，+ 1 因此 八爵) = ( 一8 n e n l + e n l + 1 ，露一e n l + e n l + 1 ) = ( 茹，写) 一2 ( 霸，e 。) + 2 ( 薪，e n l + 1 ) + ( e n ， 由于e 。，和是正交的单位向量，故( e e 。，) = ( e n ，+ 1 ，+ 1 ) 51 ，( 。，e n ，+ 1 ) - o 又( 霸，) ：。，一1 ，( 磊，e 。，+ 1 ) = n 。，且，( 霸) = ( 靠，霸) = 霸7 霸因此 ，( s i ) = ，( 霸) 一2 ( n l 一1 ) + 2 n l + 2 = ，( 露) + 4 同理，当f 3 时，s i = 霸一( e 。，一e n l + 1 ) 一( e 。，十n ：一e n i + n ：+ 1 ) 一( e 一e n - n t + i ) 容易验证，( s ：) = ，( 蠢) + 4 ( 1 一1 ) 口 定理2 4 1 说明，( s ：) 的值和面：中对角块a 。、，a 。：，。的次序和块的大小 无关只依赖于块的个数1 设s 。= ( s i ，s ： m 。雪( s 。) ，记 s ：) 7 ，n ，3 ，i = l ，2 ，一，f ，且n 1 + n 2 + + n f = n 设 螈= m n l 0 厶2 n la “2 易知尬。是训喻竞赛矩阵，其得分向量记作爵 0 0 j m 。 定理2 4 2 ，( 爵) s ，( s ：) ，且当且仅当爵= s ：时等式成立 证明由于石，s ：k ，( s 。) 是l 。上严格s c h u r 凸函数，因此只需证明，s i 优 超爵即可 记螈的第i 行上严格非零块组成的n i ( n + n z + + m ) 矩阵为 厶。n 1 ，厶，厶n t _ l ，埘n 。j ， 其行和向量记为一$ n l ，i = 1 ，2 ，f ，则瓦。= s 。+ ( n l + n 2 + + m 1 ) 屯。，其中e n 。 是m 维全1 列向量，且丽= ( s ：。一s t ：，s 乏) ? ，同样，记i 磊的第i 行上非零 块组成的啦( n 1 + n 2 + + n i ) 矩阵。n 1 ，厶。，厶m “a n 。 ，的行和向 量为s ：，i = 1 ，2 ，f ，则s ：= 甄+ ( n l + n 2 + + 啦一1 ) e n ，由于s n ，民工m 且露是瓦的最大元，故s 。 民，从而i i _ ，( ；) ，故由推论2 3 7 ，s 是可约的 设矗雪( s ) ，则瓦的邻接矩阵置换相似于如下矩阵 m 。 0 厶2 n i 尬1 2 0 0 ， 其中l 2 ，n ，+ n 2 + + n f _ n ，且螈；是n i 阶不可约竞赛矩阵设尬，中每个不 可约块。的阶数不小于3 ，则由定理2 4 1 和定理2 4 2 ， f ( s ) f ( s + ) = ，( 功+ 4 ( 1 1 ) 由于n = 3 + i ，0 i 2 ，故尬；中不可约块慨的块数f 至多是，因此 ，( s ) ，( 司+ 4 ( 一1 ) = ! 兰尘掣 等 | | s ， 一 s ， 矛盾这表明，尬。的不可约块。 m n 。必是零矩阵因此 矗是奇异的 注存在5 = ( 8 l ，8 2 例如 a 3 = 00 10 01 中必有一个是1 阶的，而1 阶不可约竞赛矩阵 s 。) t 三。，使得，( s ) = 型芷趔一 i ，且s 不是奇异的 a 4 = 都是不可约非奇异竞赛矩阵，记 m 弘2 m 3 k + l2 m j 女+ 2 = 0o 1 0 11 1 1 01 00 00 1o a 3 0 如3a 3 如3j 3 3 a 3 0 j 3 3 如x 3 3j 4 3 a 3 0 j 3 3a 3 j 3 3 如3 j 3 3 以3 a 5 = 0 0 00001 l 0000 1l 000 l 1 100 11110 00 00 a 3 0 j 4 3a 4 o0 00 a 3 0 j s 3a 5 口 且记n = 3 k + i ，0si 2 ，则尬，是非奇异竞赛矩阵容易验证，尬，的得分向量s 满足，( s ) = 到生孑趔一扣因此，s 不是奇异的 2 5 结束语 由前面的结论，易知f ( s ) 的范围是 半划蛇 拳，耋：舅翥萋筹 2 6 矛盾这表明，尬。的不可约块。 m n 。必是零矩阵因此 矗是奇异的 注存在5 = ( 8 l ，8 2 例如 a 3 = 00 10 01 中必有一个是1 阶的，而1 阶不可约竞赛矩阵 s 。) t 三。，使得，( s ) = 型芷趔一 i ，且s 不是奇异的 a 4 = 都是不可约非奇异竞赛矩阵，记 m 弘2 m 3 k + l2 m j 女+ 2 = 0o 1 0 11 1 1 01 00 00 1o a 3 0 如3a 3 如3j 3 3 a 3 0 j 3 3 如x 3 3j 4 3 a 3 0 j 3 3a 3 j 3 3 如3 j 3 3 以3 a 5 = 0 0 00001 l 0000 1l 000 l 1 100 11110 00 00 a 3 0 j 4 3a 4 o0 00 a 3 0 j s 3a 5 口 且记n = 3 k + i ，0si 2 ，则尬，是非奇异竞赛矩阵容易验证，尬，的得分向量s 满足，( s ) = 到生孑趔一扣因此，s 不是奇异的 2 5 结束语 由前面的结论，易知f ( s ) 的范围是 半划蛇 拳，耋：舅翥萋筹 2 6 其中，( s ) = 坐i 擎型当且仅当s = ( o ，1 ，2 ，n 一1 ) ，( s ) = 坐e 当且仅当n 为奇数且5 = ( n 2 - i ，n - 2i ，n - 21 ) 、- _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ - _ - _ 一 ，( s ) = 坐学当且仅当n 为偶数，且s = ( ；，；，字，孚 由b r y a n l s h a d e r l 2 6 可知当，( s ) ! l 号边时，雪( s ) 中的每个矩阵都是非奇异 但是当! i 三业，( s ) 型生i ! 卿一；i 时，雪( s ) 中矩阵的奇异性与得分向量的 关系还有待我们的研究 r e f e r e n c e s 1 】f k b e l l a n d p r o w l i n s o n ，c e r t a i ng r a p h s w i t h o u tz e r o a n a n e i g e n v a l u e m a t h j a p o n i a c ，3 8 ( 1 9 9 3 ) ，9 6 1 9 6 7 2 】c b e r g e ，g r a p h sa n dh y p e r g r a p h s ，a m s t e r d a m ：n o r t h h o l l a n dp u b l i s h i n gc o ，1 9 7 3 3 b b o l l o b & ，e x t r e m a lg r a p ht h e o r y jl o n d o n ：a c a d e m i cp r e s s ，1 9 7 8 【4 】r a b r u a l d ia n dh j r y s e r j c o m b i n a t o r i a lm a t r i xt h e o r y ，c a m b r i d g eu n i v e r s i t y p r e s s ，c a m b r i d g e ，1 9 9 1 d c a r l s o n ，n o n s i n g u l a r i t yc r i t e r i af o rm a t r i c e si n v o l u i n gc o m b i n a t o r i a lc o n s i d e r a t i o n s ，l i n e a ra l g e b r aa n di t sa p p l i c a t i o n ，1 0 7 ( 1 9 8 8 ) ，4 1 5 6 6 d c a r l s o na n dd h e r s h k o w i t z ，n o n s i n g u l a r i t yc r i t e r i af o rg e n e r a lc o m b i n a t o r i a l l y s y m m e t r