（应用数学专业论文）图论在无限拟阵及格论在网络中的应用.pdf

摘要摘要本文首先回顾任意基数集上的拟阵、图论和格论的一些基本知识之后，通过研究任意基数集上的拟阵的圈性质，得出当任意基数集上的拟阵连通时，它可由含任一给定元素的圈集唯一确定第二部分，推广有限拟阵的约束概念到任意基数集上的拟阵，并应用个图定义的圈拟阵验证该推广的正确性最后一部分，应用格论方法，引入零元和单位元将网络图形转化成格结构，并讨论此格结构的性质关键词任意基数集上的拟阵；约束；无限图；网络；格a b s t r a c ta b s t r a c tt h i sd i s s e r t a t i o n 丘r s t l yr e c a l l 8s o l eb 鹪i cl 【n o w l e d g ea b o u tm a t r o i d so fa r b i t r a 巧c a r d i n a l i t y ig r a p ht h e 0 巧a n dl a t t i c et h e o t h ef o l l o w i n gi 8t od e a lw i t h8 0 n l ep r o p e r t 洒o fc i r c u i t so fm a t r o i d so fa r b i t r a 巧c a r d i n a l i 饥舭l d 七og e tt h a ti fam a t r o i d0 f 盯b i t r a r yc a r d i n a l i t yi sc o n n e e t e d ，i tw i ub ed e t e r r n j n e db yt h ec o l l e c t i o n0 fc i r c u i t sw h i c hc o n t a i na 缸e de l e m e n t i nt h es e c o n dp 盯t ，i te 】( t e n d 8t h ec o n c e p to fr t r i c t i o n 矗o m6 n i t em a t r o i d 8t 0m a t r o i d s0 fa r b i t r a 巧c a r d i n “i 妞b y8 | n 咖p l e ，i tc h e c ：k st h ec o r r e c t0 ft h i se ) ( t e 璐i o n t h e 丘n a lp 吼谵t op r o v et h a tan e 伽o r kg r a p hb yd e 矗n e dz e r 0a n du n i te l e m e n t si sa1 a t t i c eu n d e rag i v e i np a r t i a lo r d e r ，f 1 1 r t h e r m o r e ，i td i s c u s s e ss o m ep r o p e r t i e s0 fn e t w o r k 酎a p hb a s e do nl a t t i c et h e o 眄k e y w o r d sm a t r o i d so fa r b i t r a 叮c a r d i n a l i 锣；r e 8 t r i c t i o n ；i n f i n i t eg r a p h ；n 咖o r k ；l a t t i c ei i 河北大学学位论文独创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了致谢。作者签名：篮三猢越日期：2 趣年月卫日学位论文使用授权声明本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。本学位论文属于1 、保密口，在i年月日解密后适用本授权声明。2 、不保密。( 请在以上相应方格内打“”)作者签名：盆蛆逍导师签名：日期：2 1 里鳘年工月三l 日日期：三! 壑年月卫日保护知识产权声明本人为申请河北大学学位所提交的题目为( 目彻酾删列豁所裥的学位论文，是我个人在导师( 乏烨) 指导并与导师合作下取得的研究成果；研究工作及取得i的研究成果是在河北大学所提供的研究经费及导师的研究经费资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法律、行政法规以及河北大学的相关规定。本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。如果违反本声明，本人愿意承担相应法律责任。声明人：螽汹邋日期：2 监年月2 ，l 日作者签名：盒蛆逊导师签名：敖亿p日期：兰翌墨年上月二! l 日日期：至哩呈年上月望日引言已i 古- ，i 口拟阵理论起源于2 0 世纪3 0 年代w h i t n e y 将向量线性相关关系进行抽象推广，在【1 】中首次提出拟阵的概念拟阵论主要研究定义在一个集合的子集上的抽象相关关系如，个图由边集生成有圈子图所确定的相关关系定义集合上的一个拟阵就是要指出该集合的子集族中所有的独立集或相关集等这是因为一个拟阵可有许多不同的但是相互等价的定义方法，即，拟阵的公理系统( 见【2 4 】) 由【5 】我们得知：当底集为有限时，拟阵的公理系统是等价的；但当底集为无限，这种等价性将不再成立因此至今也没有给出无限拟阵的统一定义，无限拟阵理论的研究成果也远远少于有限拟阵但是一些学者出于不同的研究目的，在无限集上定义了许多类似于拟阵的结构无限拟阵的每一种研究方法都与有限拟阵的一个特定的定义方式有密切关系，比如，w b l s h 在 3 】中提到的，运用准独立空间和独立空间的概念定义无限拟阵的方法，就是对有限拟阵中独立集公理系统的两种推广2 0 0 3 年，b e t t e n 和w 色n z e l 从闭集的角度，将有限底集推广到任意基数集，给出了任意基数集上的拟阵的定义，并将之应用于线性空间的研究此后许多学者也在其研究中使用了该定义( 见【6 。9 】等) 本文主要研究任意基数集上的拟阵的一些与图论相关的概念和性质类似于研究图的连通性，在拟阵中也引入了连通的概念w h i t n e y 在 1 】中指出：图的2 一连通性可以在拟阵中得到合理的推广此后，连通性的理论逐渐发展为研究拟阵结构的一个重要工具应用约束可以从一个拟阵导出一些“较小”的拟阵，这些“较小。拟阵在某些方面保持着原拟阵的结构因此可通过研究。较小”拟阵来认识原拟阵的某些性质图论是离散数学的骨干分支，至今只有2 0 0 多年的历史它在运筹学、计算机科学、社会学及经济管理等方面有着广泛的应用我们可以看到，一方面，拟阵理论自其诞生之时起就与图论有着千丝万缕的联系，其中的不少概念和性质可看作是图论中一些相应概念和性质的推广( 见 2 】) ；另一方面，w 出h 在 3 】中指出：简单拟阵与几何格之间存在相互确定的关系因此有许多拟阵的研究是通过几何格来进行的( 见【1 0 】) 基于以上两个方面，本文试图直接讨论格论与网络图形的关系，应用格论的观点研究网络的性质自然科学和社会科学中存在着大量的序关系，计数、选择和包含都是序的表现形式用数学语言概括，序就是一个集合中元素间的二元关系，序理论的本质在于：可传递性和反对称性偏序关系要求在集合的诸元素之间成立：反身性、反对称性和传递性2 0河北大学理学硕士学位论文世纪3 0 年代，人们开始研究一类较为普遍的序结构一格它要求偏序集中的任意两元素均存在“上确界”和。下确界”由于格所具有的良好性质，使其成为研究数学的其它分支，逻辑学，组合学以及计算机科学的重要工具其中最值得一提的是，由w i l l e 于1 9 8 2 年提出的“概念格”，它是格论在形式概念分析中的应用，是近年来获得飞速发展的数据分析的有力工具( 见【1 1 】) 全文共分四章第一章对文中涉及的无限拟阵、图论和格论的基本知识作简要叙述第二章研究图论在无限拟阵中的应用，包括：圈、连通性和约束第三章应用格论观点讨论网络图形的性质第四章总结全文并展望未来工作最后排列参考文献及致谢以下是本文的主要结论；结论1 设m 是一任意基数集s 上的连通的拟阵任意给定e s ，则 z 可由含e的圈集唯一确定结论2 设m = ( s 厂) 为任意基数集s 上的拟阵，x s 令厅= f n x i f 厂) ，则了x 是一个任意基数集x 上的拟阵的闭集族用m i x 表示这个拟阵，称它为m 在x 的约束，触表示它的秩函数结论3 设= ( v ) 是一个网络，任取o ，1gy ，令l = yu o ，1 ) ，定义l 上的二元关系为；( i ) 令o o 且vn vo o ；( i i ) 令1 1 且vn kn 1 ；( i i i ) 若n ，6 y ，则口6 当且仅当存在一条由6 指向口的有向轨尸( 6 ，口) 或者口= 6 ，则( l ，s ) 是一个格第1 章预备知识第1 章预备知识本章给出后续内容中所需的一些基本知识首先介绍无限拟阵的概念和引理( 1 1 节) ，然后介绍与图论和格论有关的预备知识( 1 2 节) 1 1 无限拟阵的基本知识首先介绍本文所讨论的无限拟阵一任意基数集上的拟阵的定义及相关结论下文中令n o = o ，1 ，2 ，) ；s 表示一个任意集，当然有可能是无限的；p ( s ) 表示s 所有子集构成的集合定义1 1 1 【6 】假设仇n o 而厂尹( s ) 若下面的条件成立，则称m ：= ( s 厂) 为任意基数集s 上的拟阵，它的秩为m 且歹为其闭集族，( f 1 ) s 厂；( f 2 ) 若r ，足厂，则日n 而厂；( f 3 ) 若r ，且z 1 ，z 2 s 厢，则有下列两条之一成立， f 丁i 昂u z 1 ) 冬f ) = f 厂i ru z 2 ) f ) ，或者存在乃，足厂且分别包含有昂u z 1 ) 或昂u z 2 】，然而毋n 玛= r ；( f 4 ) m = m n z 讥n o i 存在昂，日，r 厂满足rc 日c cr = s ) m 的闭包算子盯= 嘶：p ( s ) _ 厂定义为：盯( a ) = 盯m ( a ) ：= nf f e ，a c fm 的秩函数p = p m ：p ( s ) 一 o ，1 ，m ) 定义为：p ( a ) ：= m 口z 南n o i 存在娲，r ，r 厂满足晶cnc c 以= 盯( a ) ) 定义1 1 2 若a z = a s i z a ，zg 盯m ( a z ) ) ，则称a 为m 的独立集；不属于z 的s 的子集称为m 的相关集m 的圈( c i r c u i t ) 是极小相关集引理1 1 1 ( 独立集公理) 设z 是个任意基数集s 上的拟阵的独立集族，当且仅当z 满足以下条件：( i 1 ) z 谚；( i 2 ) 若a z 且b a ，则b z ；( i 3 ) 若a ，b z 且1 4 i ，i bj 。，i a i 二i b l + 1 ，贝0 存在n a b 满足bu 口z ；河北大学理学硕士学位论文( i 4 ) 若a s 且当4 的每一个有限子集均属于z ，必有a z ；( i 5 ) m n z 七n oj 存在尼， ，厶z 满足如c c ，c 厶) o o 基于引理1 1 1 可定义，若b z 且p ( b ) = p ( s ) ，则称b 为m 的基，即b 为m的极大独立集，记基的全体召= b l b z ，p ( b ) = p ( s ) ) 引理1 1 2 令m = ( s ，厂) 是秩为m 的任意基数集s 上的拟阵p 和c 分别是它的秩函数和圈集，则有：( i ) 对于所有，z 均有i ，i m 令x s ，奴z 为x 中的极大独立集，则p ( 奴) = p ( x ) 特别地，对于任意的，z 有p ( ，) = i n( i i ) 若c c ，贝! il c i m + 1 且j d ( c ) = f c l l ；( i i i ) 若a ，岛e ，q q 且z qnq ，则存在岛c ，使q ( gnq ) z 注定义1 1 2 、引理1 1 1 和引理1 1 2 均出自h m a o p a v i n gm a t r o i d s0 fa r b i t r a 珂e a r d i n a l i t y a r sc o m m n a t o r i a ( a c c e p t e d ，i np r e s s )引理1 1 - 3 【7 】设m = ( s 厂) 是任意基数集s 上的拟阵，p 是其秩函数令t s 函数力：p ( 丁) _ n o 定义为；对于a z 力( a ) = p ( a ) 则阳是定义在任意基数集丁上的某拟阵的秩函数，将此拟阵记为 r 引t 引理1 1 4 【8 】设舰= ( & ，五) 是秩为m i 的任意基数集& 上的拟阵( i = 1 ，2 ) ，岛n岛= 仍则m = ( s ，厂) 是一个秩为m 1 + m 2 的任意基数集s 上的拟阵，其中s =岛u 岛，厂= 只u 尼l n 五，岛兀) 称m 为舰与的直和，记为m = 尬+ 如根据引理1 1 4 及【6 】有：设m 是个任意基数集上的拟阵，若m 不为直和，则称m 是连通的1 2 图论和格论的基本知识首先列出文中所涉及的图论概念定义1 2 1 【1 2 】( 1 ) 令 a ，b ，c ) 是个点集，若某些“点对”被一条或多条线相连，则称这种构形为图若一个图的顶点集和边集都是有限的，则称图是有限的，否则，图是无限的( 2 ) 设g 7 和g 是两个图，其中y ( g ，) 和y ( g ) 分别表示g 7 和g 的顶点集，e ( g )和e ( g ) 分别表示g 7 和g 的边集，若y ( g ) 冬y ( g ) 且e ( g 7 ) e ( g ) ，则称g 7 为g的子图一乒第1 章预备知识( 3 ) 若图g 的所有边能够排列成形式：a b ，j e i ec d ，k 厶l m 其中顶点和边均可重复出现，那么g 就可用通道( w a l k ) 表示若a = m 且a ，b ，l 相异，那么称这种闭合的通道为圈( c y c l e ) 下文中如无特别说明，所指均为有限图另外，图论中的圈( c y c l e ) 与拟阵论中的圈( c i r c u i t ，见定义1 1 2 ) 是不同的概念定义1 2 2 【1 3 】设= ( ku ) 为一个有向图，满足：( i ) y 中有两个非空不相交子集x ，fx 中任一顶点的入度为零，y 中任一顶点的出度为零；( i i ) 弧集u 上定义一个取非负整数值的函数c ，则称为一个网络( n e t w d r k ) x 中的顶点称为源，y 中的顶点称为汇定义1 2 3 【1 4 】若g 是有向图，如果对钆，u y ( g ) ，存在从仳到u 的有向轨尸( ，u ) ，则称乱可达口；任取u ，移y ( g ) ，u 可达 或u 可达 时，则称g 是单向连通有向图以下定义中的各项均为本文所需的格论知识定义1 2 4 【1 5 l ( 1 ) 设a 是一个非空集，其上定义二元关系，满足vn ，6 ，c a 有：( p 1 ) 自反性口口；( p 2 ) 反对称性若n 6 且6 n ，则a = 6 ；( p 3 ) 传递性若o 6 且6 c ，则口c ，则称二元关系为一个偏序关系，定义了偏序关系的集合a 称为偏序集，记为( a ，) ( 2 ) 若偏序集a 中任意两个不同的元素均可比，则称4 是一个链c 是偏序集a的一条极大链，当且仅当，c 是链且对a 的任意链d 都有，若c d 则c = d ( 3 ) 一个偏序集( l ，) 是格，当且仅当，v o ，6 l n ， 口，耐和s 婶 o ，6 ) 都存在( 4 ) 设偏序集a ，v 口，6 a 且a 6 若6 o 且不存在茁a 使6 z 口，则称口覆盖6 ，记为6 口若a 是格l 中的元素且0 口，则称。是的一个原子说明本文所研究的无限拟阵为 6 】中定义的任意基数集上的拟阵，它是将有限底集拓展到任意基数集上得到的无限拟阵另外，关于拟阵的其它知识可参见 2 4 】，图论和格论的其它内容可分别参见【1 2 1 4 】和【l5 】河北大学理学硕士学位论文第2 章图论在无限拟阵中的应用本章所研究的无限拟阵是将有限拟阵的底集推广到任意基数集上得到的，即 6 】或定义1 1 1 中定义的任意基数集上的拟阵首先，讨论任意基数集上的拟阵的圈性质，得到：当任意基数上的拟阵连通时，它可被含任意给定元素的圈集唯一确定；然后，将约束概念从有限推广到无限，并通过一个在无限图上定义的圈拟阵验证该推广的正确性2 1 圈及连通性本节首先给出任意基数集上的拟阵的圈性质( 见引理2 1 1 ) ，然后利用这些性质，得到当任意基数集上的拟阵连通时的一个重要结论，即定理2 1 1 下文中，设m = ( s 厂) 是秩为m 的任意基数集s 上的拟阵，记 彳的独立集族为z ，圈集为c 由引理1 1 1 即独立集公理知，m 由z 唯一确定再根据定义1 1 2 中圈及独立集的定义知，m 也可由c 唯一确定这是因为z 与c之间有等价关系：任取x s ，有x z 乍号不存在c c 使c x 基于以上分析，我们进一步研究任意基数集上的拟阵可以由什么样的圈确定为此先给出以下引理引理2 1 1 ( 1 ) 圈g 的每个真子集均属于z ；( 2 ) 任取q ，q c 且q 岛，则qn 岛z ；( 3 ) 若q ，q c 且q q ，则q 茌岛；( 4 ) 若g ，q c ，g q 且z qnq ，则对任意的! ，q 岛，存在c c ，使! ，c ( c 1uq ) z 证明由定义1 1 2 中关于圈的定义，易知( 1 ) 一( 3 ) 成立对于( 4 ) ，用反证法给予证明假若不然则存在g ，q c 及元素z gnq ，g q ，但不存在( 4 ) 所求的c 由引理1 1 2 ( i i ) 可知l q l ，i q i o o ，则有i guq i 因此可找到使l gu 岛i 为极小的集合，不妨设为gu 岛由引理1 1 2 ( i i i ) 知存在圈g ，使g ( guq ) z ，但第2 章图论在无限拟阵中的应用由假设条件可乒岛另外gn ( q q ) d ，否则qcq ，这与引理2 1 1 ( 3 ) 矛盾若取z 岛n ( q q ) 现仅考虑q 和岛，则z 岛nq 且z g 岛由g 岛uq 及岛冬( gu 岛) z 得岛u 岛cquq 则由quq 极小性知，存在圈q 使z q ( 岛u 岛) z 再考虑g 和q ，则有z 仍nq 由可童qu 岛及as ( qu 岛) z 可得耖q q 又由q ( 岛u 岛) z 及zgquq 可知quacguq ，则根据q u q 极小性可推知，存在圈g ，使j ! g ( qua ) z 因为已证q u qcauq ，则有圈g ，使秒g ( quq ) z ，与假设( 4 ) 不成立矛盾口以下是本节主要结论及其证明定理2 1 1 设m 是一任意基数集s 上的连通的拟阵任意给定e s ，则m 可由含e 的圈集唯一确定证明令巳= 1 c c i e c ) 对每个x s ，置d ( x ) = x n c c e l c x ) 由2 1 节开始时的分析知，m 可由c 唯一确定，则对于任意给定元素e ，m 中只有两类圈：含e 的圈及不含e 的圈因此只需证明m 不含e 的圈均是形如d ( quq ) 的极小集，其中a ，q c e 且q q 分三步完成所需证明第一步证明巳的存在性用反证法假设c e = 谚，即已知e s 但e 譬c c ；亦即任取c c 均有c s e 则可取岛= s e ，岛= e ，有毋n 岛= 仍且研u 岛= s 由引理1 1 3 可令舰= m i & ( i = 1 ，2 ) 则根据引理1 1 4 可得m = 舰+ 这与m 是连通的相矛盾第二步由引理1 1 2 ( i i i ) 可知存在圈岛使岛( quq ) e 本步完成岛口( qu 岛) 的证明即，任取秒岛均有! ，口( qu 岛) 由! ，岛( guq ) e 知耖q 或岛不妨设秒q 则可qn 岛且e q 岛由引理2 1 1 ( 4 ) 可知，存在圈c 7 ，使e c ( qu 仍) 可，c e 且( guq ) 这样gn c 巳i c qu 岛) 又guq ，故纱口( quq ) = ( quq ) n c 丘l c guq ) ，即d ( 研uq ) 是m 的相关集第三步设c 是m 的任意不含e 的圈本步完成c = d ( guq ) 的证明由a ，是连通的知，必存在q 巳使qnc 谚0 = 1 ，2 ，) 设c 1 c e 且为使河北大学理学硕士学位论文i quc i o 。为极小的集合若取z qnc 且有e q c ，由引理2 1 1 ( 4 ) 可知，存在圈岛，使e q ( guc ) z 显然岛q ，这是因为z q 而zg 岛任取auq ，显然巳，则必有nc d 成立，这是因为岛( quc ) ，quq qug ，若e ng = 谚，则q ，由引理2 1 1 ( 3 ) 可知c = q ，但是anc d ，二者矛盾由quc 的极小性知，( c ug ) 茌( 研ug ) 但ug ququc ，又由岛c luc 可知qu 岛uc = 研uc ，故c uc c 1uc 因此c uc = c 1uc 令c 。= 巳sgu 岛 则由上段已证c u c = auc 及qu 岛u c = aug 可知n ( c u c ) = 研u c ，c c 7则cu ( nc ) = quc = ququc 故c2 口( gu 岛) c c 由第二步已证d ( qu 岛) 是一个相关集，则c = 口( quq ) 再由c 的任意性，可知定理成立口2 2 约束本节将有限拟阵中的约束概念，推广到任意基数集上的拟阵，继而讨论该类拟阵的约束所具有的性质，最后用例子验证推广的正确性首先从闭集的角度定义任意基数集上的拟阵的约束定理2 2 1 设m = ( s ，厂) 为任意基数集s 上的拟阵，x s 令厅= f n x i f 厂) ，则乃r 是一个任意基数集x 上的拟阵的闭集族用m i x 表示这个拟阵，称它为m在x 的约束，似表示它的秩函数证明由定义1 1 1 ，只需验证( f 1 ) 一( f 4 ) 成立由s fsnx = x ，故x 厅，即( f 1 ) 成立若有r ，易厅，则存在s l ，岛兀使得研nx = r ，nx = 乃，故( ( 两n 岛) nx ) = ( & nx ) n ( 岛nx ) = rn 而，而& n 岛厂，故日n 足厅，满足( f 2 ) 设r 厅，z 1 ，z 2 x r 令五= f 厅l ru 甄 f ) ( i = 1 ，2 ) 分两种情况讨论五，五的关系f k第2 章图论在无限拟阵中的应用情况1当z 1 = z 2 时，显然兀= 元；情况2当z 1 z 2 时，由五的定义可知，五是厅中所有包含ru 婉) 的闭集族且z 1 z 2 ，则必有万n 五= r ，因此( f 3 ) 成立由定义1 1 1 可知，p m ( x ) = m n z 七n o i 存在r ，以厂满足凡c cr = 盯m ( x ) )= m n z 尼n o i 存在rnx ，兄nx 及满足( rnx ) c c ( rnx ) = 口m ( x ) nx )。= m 彻 七n o l 存在，及满足瓦c c 砭= x )= p x ( x ) ，故( f 4 ) 成立综上可知，m l x 是一个任意基数集x 上的拟阵口从定理2 2 1 验证( f 4 ) 成立的过程知，触( x ) = p m ( x ) 完全类似地讨论可得，任取y x ，有肷( y ) = j d m ( y ) 这与引理1 1 3 结论一致而 7 】是从几何格的角度给出的定义及证明继而讨论m l x 所具有的性质，进一步揭示m i x 与m 的关系性质2 2 1 设m 的闭包算子为盯m ，独立集为2 k ，基的全体为召m ；记m i x 的闭包算子为x ，独立集为z 又，基的全体为召x 则m l x 具有以下性质；( 1 ) 任取y x 有，啾( y ) = 仃m ( y ) nx ；( 2 ) y x 是m i x 的独立集，当且仅当，y 是m 的独立集；( 3 ) 反= xn 知；( 4 ) y x 是m i x 的相关集，当且仅当，y 是m 的相关集；( 5 ) bn x l p ( bnx ) = j d ( x ) ，b 侈m ) 取；( 6 ) csx 为m l x 的圈，当且仅当，c 为m 的圈证明( 1 ) 取y x ，根据闭包算子的定义，可记y 在m i x 中的闭包为啾( y ) =n 取i y 取，取及) ，则由定理2 。2 1 ，对每一个段都存在m 中的闭集，使河北大学理学硕士学位论文取= 砌nx ，故盯x ( y ) = n ，knx i y f knx ，f knx 厂nx )=xn ( n 砌l y ，砌s 厂) )=xn ( y ) ( 2 ) 若y 是m i x 的独立集且y x s 由定义1 1 2 中关于独立集的定义，可记m i x 的独立集族五= a x i z a ，z 茌取( a z ) ) 已知y 致由x 冬s 知x = snx ；由a x 及( 1 ) 可推出a = anx 及啾( a z ) = 仃m ( a z ) nx ( z a ) ，则奴= a snx i z anx ，zg ( 盯m ( a z ) n x ) )=xn a s l z a ，zg 莎m ( 4 z ) =xn 功，因此y 功若y x ，y 是m 的独立集，即y = a s l z a ，zg 盯m ( a z ) ) 由x s 得s n x = x ；由a x 及( 1 ) 可推出a n x = 4 及盯m ( a z ) n x = 呶( a z ) ( z a )则z 0nx= a 冬snx l z anx ，zg ( 盯m ( a z ) nx ) )= a x l z a ，zg 盯x ( a z ) )= 致，因此y 反( 3 ) 由( 2 ) 显然有z 支= xn ( 4 ) 由( 2 ) 的逆否即得( 4 ) 成立( 5 ) 取y bnx l p ( bnx ) = p ( x ) ，b ) ，则在b m 中必有b 使得y = b n x且p ( y ) = p ( x ) 由 ，= 曰n x 知y 冬b ，根据基的定有y 又从l ，x 和( 3 ) 可推出y 反已知p ( y ) = j d ( x ) ，根据基的定义得y 取( 6 ) 当c 为m l x 的圈时，即c 为m i x 的极小相关集，由( 4 ) ，c 为m 的相关集，假设c 在肘非极小，则必有口c 使c 以为m 的相关集，再由( 4 ) ，g o 为a 引x的相关集，这与c 在j 7 i 彳i x 中极小矛盾，故c 为m 的圈1n -第2 章图论在无限拟阵中的应用反之，当c 为m 的圈时，即p 为m 的极小相关集且已知c x ，由( 4 ) ，c 为m l x 的相关集，假设g 在m l x 非极小，则必有口c 使c 口为m l x 的相关集，再由( 4 ) ，c 口为m 的相关集，这与c 在m 中极小矛盾，故c 为m l x 的圈口给出一个任意基数集上的拟阵，验证以上推广及性质的正确性例设图g = ( ve ) ，g 可以是无限的，满足以下条件：( i ) i y l = n ，佗2 且n 为有限正整数；( i i ) 任取a 冬e ，若有l a l n ，则a 中必含圈如，当n = 2 时，若g 为无限图，y ( g ) = u 1 ，忱) ，则e ( g ) 为由连接口1 和砚的无限条重边构成这时取a e ，若i a i 2 ，则a 必含圈令z = x i x e ，x 中任意边子集不构成圈) ，则z 是边集e 上的一个任意基数集上的拟阵的独立集族下面验证z 满足引理1 1 2 根据z 的定义，z 中必有xse ，i x l = 1 ，则z 非空，( i 1 ) 成立若4 互a 的任意边子集不构成圈，即有b a ，b z ，( i 2 ) 成立若a ，b z 且l a i ，l b i o 。，有俐= i b i + 1 利用反证法证明z 满足( i 3 ) ，假设任取口a b 均使bu 口含圈设g ( b ) 为g 中边子集b 生成的子图因b z 则g ( b ) 是森林设g ( b ) 的连通分支为g 1 ，g 七，则q 必为树( 1 ts 七) 记鼠和k 分别为g 的边集和顶点集，则由图论知识可知l 鼠l = i l l ，且当i 歹时，鼠nb j = 谚而u b i = b 因任取口= 伽a b 均使buo 含圈，则有u u 磁设a i = 口i o = u u a ，“，移k ) 显然u a = a 且当l 歹时，有an 如= 谚成立因4 k 且4 无圈，故l a i l k i 一1 ；ib l ，于是l a i = i a 引l b 引= i b l ，这与i a l = i b l + 1 矛盾故( i 3 ) 成立若4 互e 且a 的每一个有限的子集均属于z ，分两种情况讨论4 情况1当1 4 i n 时，易知a z ；情况2当礼i a i = o 。，假设a 乒z 则4 含圈，可取以7 4 ，h l = n ，由4 的所有有限子集均属于z 知，a z ，即4 无圈，与图g 满足( i i ) 矛盾河北大学理学硕士学位论文故( i 4 ) 成立假设存在，o ， ，厶，厶+ 1 z 满足如c c c 厶c 如+ 1 设u 易=4 e0 = 1 ，2 ) ，则川= o 。且a 的每一个有限子集均属于z ，由( i 4 ) 得a z ，但当a 的某有限子集拥有的元素个数等于或大于n 时，由图g 满足( i i ) 知a 必含圈，矛盾故假设不成立满足( i 5 ) 综上，由引理1 1 2 可知，m = ( e ，z ) 是个任意基数集上的拟阵，记之为 ，( g ) 下面利用上述例题验证性质2 2 1 中各结论的正确性任取t e ，则m ( t ) 是关于边子集t 的一个任意基数集上的拟阵，它的独立集族历= x 丁i x 中任意边子集不含圈) 另一方面，由定理2 2 1 及性质2 2 1 ( 3 ) 知，m ( g ) 在丁的约束m ( g ) l t 的独立集族可表示为互= ，n 丁i ，刁已知z 中每个元素均不含圈，设，nt = y z ，故弓= y 丁l y 中任意边子集不含圈) = 易因底集均为丁，故m ( 丁) = m ( g ) i 丁由此可得知，定理2 2 1 给出的约束确为丁上的一个任意基数集上的拟阵继而验证性质2 2 1 ( 2 ) 若xszx 乃，即x 中无圈，则x 乃，昆为m ( g )的独立集反之，若x ，则x 中无圈，又由已知x t 可得x 易故x 丁为m ( t ) 的独立集当且仅当x 为m ( g ) 的独立集关于性质2 2 1 中的其它几个性质可类似地得以验证，在此不一一赘述综合上述验证，本节对约束概念从有限拟阵到任意基数集上的拟阵的推广是正确的第3 章格论在网络中的应用第3 章格论在网络中的应用图的概念是现实生活中图形的数学抽象，由于其具有直观性与艺术性等特点，被广泛应用于各学科领域本章所讨论的网络属于有向单图它是一类比树形结构更为一般的特殊有向图，是描述公共子式的表达式和一项工程或系统进行过程的有效工具通过引入零元o 和单位元1 的概念将网络图形转化成格结构，进而应用格论观点讨论网络所具有的格性质本章内容已发表网络本身并不能构成格结构，因此首先给出它的转化定理定理3 1 设= ( vu ) 是一个网络，任取o ，1 叠y ，令l = yu o ，1 ) ，定义上的二元关系为：( i ) 令o o 且v 口kosa ；( i i ) 令1 1 且v 口kns1 ；( i i i ) 若n ，6 y ，则n 6 当且仅当存在一条由6 指向口的有向轨p ( 6 ，口) 或者o = 6 ，则( 己，) 是一个格证明首先证( 厶) 是一个偏序集vz ，y ，z l 显然z z ，因此( l ，) 满足( p 1 ) 已知z ，若z = o ，则由条件( i ) ，不会有z 的情况出现；若! ，= 1 ，则由条件( i i ) ，亦不会有z 的情况出现；若z ，y o ，1 ，根据条件( i i i ) ，存在一条由可指向z 的有向轨p ( 耖，z ) ，则一定不会有p ( z ，) ，否则会形成圈，因此总有! ，z 不成立，( 厶) 满足( p 2 ) 已知z 可，! ，z ，若z = o ，贝0 由条件( i ) ，有。茎z ，即zsz ；若z = 1 ，则由条件( i i ) ，亦有z 1 ，即z z ；若z ，y ，z o ，1 ，根据条件( i i i ) ，存在尸( 可，z ) 和尸( z ，耖) ，因此存在p ( z ，z ) ，即z z ，因此( l ，) 满足( p 3 ) 接下来证明偏序集( ，) 是一个格v z ，! ，l ，分两种情况讨论情况1z ，秒可比，显然，l 礼， z ，可) 和s 印 z ，j ) 都存在；河北大学理学硕士学位论文情况2z ，y 不可比，则有z ，y 若s 卸 z ，可) 不存在，由于单位元1 是z ，可的上界，故z ，v 有多个上界而无最小上界，即存在口，6 己，z ，鲈口，6 且口，6 不可比，与z ，剪的情况类似，再取口，6 的上界，这样一直取上界至源点，由假设，可知源点亦无上确界，矛盾故s 叩 o ，) = 1 与上确界的情况类似，对于不可比的z ，y ，可找到多个不可比得下界，再取这些下界的下界，取到汇时，即有i n ， z ，) = o 综上，根据格定义，偏序集( l ，) 是一个格口在定理3 1 中引入的。可视为格三的最小元，1 可视为最大元因为网络的顶点有限，所以由构造的格l 的元素也是有限的，也就是说，l 是有界有限格接下来通过一个例子来说明定理3 1 的作用过程9u围1 网络妒t 和矗围2 格址t 记e图1 是本文所讨论的多源多汇的网络结构，按照定理3 1 构造出的格结构如图2 所示从图中可以看出，在顶点方面，由定理3 1 生成的格结构加入了单位元l 和零元0 ，从而二元关系s 的h a s s e 示图比网络图形多出了从单位元1 到所有源的边，以及从零元。到所有汇的边因此可以说，图2 完整地保持了网络图形的连接关系，故格论的一些理论和性质可以运用于网络图形的分析中下面讨论基于格论的网络图形所具有的性质性质3 1 设网络= ( vu ) 转化成格( l ，) ，若z ，可y ，则可 z 的充要条件是( z ，) 证明充分性，由定理3 1 显然成立必要性，因y 毛故由定理3 1 知存在p ( z ，秒) ，且不存在口y ，使 口 z ，即不存在p ( o ，! ，) 和p ( z ，n ) 假设( z ，y ) gu ，显然z 和可不能同时为源顶点，由网络的连通性，必有顶点在p ( z ，可)上，不妨设为6 且6 z ，可使得可 6 z ，这与3 1 ， z 的条件矛盾，故( z ，y ) u 口第3 章格论在网络中的应用性质3 2 设格l 中的顶点z 是原子当且仅当z 是网络中的汇证明若任取原子z l ，假设z 不是汇，那么至少存在一条有向边从z 射出，不妨设为( z ，妙) 由定理3 1 知，o 剪 z ，这与z 是原子矛盾，所以z 是汇若任取中汇z ，则z 的出度为o 假设z 不是原子，则存在可厶且秒o ，1 使o 耖 z ，由定理3 1 必存在p ( z ，秒) ，z 的出度为1 ，这与z 是汇矛盾，故z 是原子口性质3 3 设格l ，z 1 当且仅当z 是网络中的源证明设z 1 ，若z 不是源，那么至少有一条有向边射入z ，使z 的入度为1 ，不妨设为( 可，z ) ，又由定理3 1 知，z 秒 l ，这与z l 矛盾，所以z 是源设z 是源，若z 不被1 覆盖，则存在! l 且彭0 ，l ，使得z 彭 1 ，又由定理3 1 ，存在p ( ，z ) 使得z 入度为l ，这与z 是源矛盾，所以z 1 口性质3 4 设格l 中的一条有限极大链去掉0 和1 后就是网络中的一条由源到汇的极大有向轨，反之亦然证明设格三中去掉。和1 后的极大链c = 1 ，忱， ，仇) ，根据格的性质不妨设o 1 眈一 ， 仇 1 根据性质3 2 覆盖与边的关系可知，c r 为中顶点不重复的一条有向轨，若假设c 不是极大的有向轨，则由网络图形的连通性，一定可以找到一条有向轨p ( 忱，u 1 ) ，使g 尸又根据性质3 2 ，可推出pu o ，1 ) 为格l 的一条链且cu o ，1 ) 尸u o ，1 ) ，这与cu o ，1 为极大链矛盾，所以c 为的极大有向轨反之，设p = 吼，忱，仇) 为的极大有向轨，不妨设忱为源，t ，l 为汇由性质3 2 知，尸u o ，1 ) 为格l 的链且o 移1 屹 ， 耽 1 假设尸u o ，1 ) 不是极大链，则必可找到一条包含p 的链根据前半部分的证明知，找到的这条链去掉0 和1 后是中的一条有向轨，这与尸是极大的矛盾，因此pu o ，1 ) 为格l 的极大链口1 5 -河北大学理学硕士学位论文第4 章总结与展望本文主要完成了三方面的工作第一，通过讨论任意基数集上的拟阵m 的圈及连通的性质，我们可知，为了完全确定m ，当它连通时不必知道所有的圈集，即，m 可由含任一给定元素的圈集唯一确定第二，研究m 的约束是为了导出一些“较小”的拟阵，进一步地，通过它们研究m的结构与性质第三，拟阵论建立了图论与格论的桥梁，本文首次直接讨论图论和格论的关系借鉴格论的语言及研究方法，将一类有向图转化为格结构，并得出基于格论的网络图形的性质有关任意基数集上的拟阵m 的图论性质还有待于进一步地研究与讨论比如，是否可以通过一系列的约束与收缩得到m 的子拟阵，这些子拟阵是否保持了m 的性质，同时又具有哪些特殊性质等问题再者，对m 的圈性质的讨论为深入研究m 的连通性提供了可能图论与格论的相互借鉴是一种新的研究思路，接下来有必要研究能否利用格论特有的性质简化网络算法的表达，以便更快更好地解决实际问题参考文献参考文献【1 】h w h i t n e y o nt h ea b s t r a u c tp r o p e r t i e 8o fl i n e a rd e p e n d e n c e a m e r i c a nj o u m a lm a t h e m a t i c s ，1 9 3 5 ，5 7 ( 3 ) ：5 0 9 5 3 3 【2 】刘桂真，陈庆华拟阵长沙；国防科技大学出版社，1 9 9 3 【3 】d w b l s h m a t r o i dt h e o r y - l o n d o n ：a c a d e m i cp r e s si n c ，1 9 7 6 【4 】赖虹建拟阵论北京：高等教育出版社，2 0 0 2 5 】j o x l e y i n 矗n i t em a t r o i d s i nm a t r o i d sa p p l i c a t i o n s ( e d b yn w h i t e ) c a m b r i d g e