局部弱连通度与对集理论的研究

《局部弱连通度与对集理论的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中山大学硕士学位论文局部弱连通度与对集理论的研究姓名：饶东宁申请学位级别：硕士专业：计算机软件与理论指导教师：娄定俊2003.5.4中山大学硕士研究生毕业论文饶东宁000182013摘要／本论文主要内容有3点：首先是图论中的重要分支一对集理论中的刻划在两点间＼没有M交错路的情况，其二是因子临界图的判定算法，其三是引入了一种新的连通度一一局部弱连通度并且给出了局部弱2连通和局部弱4连通的充要条件和有效判定算法夸夺、”l佣冬：第一章是综述部分。@'-gT本文中将要用到的一些基本概念。同时简要阐述了一些关于完美对集、n一可扩图和n-I[$界图以及连通度理论的重要结论，局部弱连通

2、度的定义也将在这里引入。第二章刻划了在两点间没有M交错路的情况，也就是给出两点间没有M交错路的充要条件。这是对集理论中一个相对基础的研究。在本文论文的第三章节中，我们首先给出一个因子临界图的充要条件。然后基于此充要条件，我们设计出一个判定给定的图G是否是因子临界的高效算法。这个高效算法在最坏情况下的时间复杂度的上界是odVl沈IEI)，这是目前已经知道的最好的结果。接下来在第四章中，将给出局部弱2连通和局部弱4连通图的充要条件，并由此得到判别局部弱2连通图和局部弱4连通图的有效算法。(最后一章是本文的总结。j＼／关键词：对集又完美对集÷M交错路，‘有效算法；因子临界图，’

3、局部弱连通度。II孛出大学硬士辑究生荜照论文饶东中000182013LocallyWeakConnectivityandSomeResearchOnMatchingTheoryMajor：ComputerScienceName：DongningRaoSupervisor：DingjunLouA积S墨鼗ACTThisthesisdisettssesthreeproblems．TlaefirstproblemistocharacterizetwoverticeswithnOM-alternatingpathjointhem，Thesecondproblemistod蛾andc

4、h篮筏嚆妇factor-criticalgraphs．Thethirdproblemistoinlrodueeanewconnectivity---locallyweakconnectivityintographtheory，andtodeterminemadcharae徽fizeIoealtyweak2-conneaedandioc棚yw龃k4田onn氍积graphs．ChapterOneinlrodueessomeconceptsusedinthisthesis。Somemainresultsonperfect筠躺堍n-emendabtegrap殛，n-eritiea

5、lgraphsarrdconnectivityarestatedbriefly。locallyweakconnectivitywillbeintmdueedhereaswell．虹髓l印擞Two,we蒜ho黼8nece蜘略and翱魑c童萱燃。强d遗强{妇l穗黼躐葭扛翳鼬in硝aiehtwoverriceswithaaoM-aitematiag-pathjointhem．五a蝴1输％撕蕊low曩卫∞嘴站搿aDd瑚

6、妇iciemca恤iidonlh戤曲站ac蛔娩esall蠡幽转q粼营嵴觚Usingthismcessmyandsufficientcondition,wedeve

7、lopahightydfieientalgcailhmtodetmninewhetheragraphGisfactor-critical,ofwhichthelimecomplexityisboundedbyodV闩嚣})，删珏isis翻b髂t鼬恤蛾洲be瞰蜘眦+Thea,inCbapt髓Four，twonecessm'yandsufficientconditionthat懒alllocallyw蜮2-∞越。cl髓劫d董oca酝w嗽耷。0强。cljed鼬尊糙gi慨Usingthesenecessaryandsufficientconditions*wealsodevelo

8、phighlyet蠢eientalgorithmstode．minev,q蹙theragivengraphGislocallyw燃tk2-connectedorlocallywlmk恻graph．Thelastchapteristhestnnnlaryofthisthesis．嘲掣猢鞘哇s：'黼蜒hln垂静雕融眺捌姻，濑剜糖臻蜘釉拳，。eZ融．ientaigortthm，柏幽梯傩髓l浮掰p晦t-．10cally蜊粕暾拍舶孽穗嗨。孛出大学磺士辑究生毕堑论文饶券宁0001s2013致谢蓄先，我≤#蘩感谢我豹每拜娄定俊教授，盘予豫豹