文档介绍：排列图,牧ㄐ指导教师学位类别学科专业学位授予单位理学硕士运筹学与控制论作者徐辉马美杰浙江师范大学论文提交日期月锻觕一,
排列图缘牧ㄐ摘要关键词:排列图;尼·一连通图;容器;连通性;超支撑连通性本文第一章给出一些基本概念,第二、三、四章分不同情况研究了傻闹结论盩/时,≥琻—时,,,其中嵋抟籯尼∞一尼琸≥,图的顶点代表网络中的组件,,它是星图的一类推广,但它的阶却比星图更具有灵活性,,保帕型嘉M耆迹辟ⅰ,:结论盩/,一时,..
篴纾蒳尼一⒁,佗≥帷儋⒁,,七【尼黄】籧,尼荒,七≥琻—..痗,霍狄籧籧;≥琸.,七,,七≥⒁籯≥褚籯≥—,.瑆礼.Ⅱ●■■■
籹
目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.日录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯Ⅳ髀邸ぁ基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·本文的主要结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯帕型糀的支撑连通性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯·帕型糀叩膕‘一连通性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯崾铩参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.在学期间的研究成果及发表的论文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯⋯⋯⋯致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯学位沧文独创性声及授权声;月⋯⋯⋯一⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯学位论文诚信承诺书⋯⋯⋯⋯⋯⋯..⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.⋯⋯..Ⅱ
髀基本概念任何不同两点间都有边相连的简单无向图称为完全图,佗阶完全图记为%,,来表示顶点牧诘慵希鳱】渲的度数,,二部划分为琘的二部图可记为,∈争,口∈日图是一个有序对,,,则称这一条边为环;,贕中相邻,或也,,,用表示与顶点嗬氩怀齣的全部顶点形成的集械拿扛龆サ鉼都有,则称图囚蛲迹若无环图的顶点集可以划分为两个非空子集蛓,械娜魏瘟降阒涠济有边相连,儿械娜魏瘟降阋参薇呦嗔虺仆糋为二部图,:
扛⋯龟七墨七.·,∞琘琘∈,琧,,卸加谐ざ任獄的茫瑅路,则称7毫ǖ摹】.点甄和边交替出现的序列蚘称为路牧礁龆说悖溆嗟亩サ愠莆D诓康悖粢惶趼稰中含有图兴械亩サ悖虺普馓趼肺9芏俾罚礁龆说阆嗤穆烦莆HΓ俏璭。⋯记圈某ざ任<粢桓鋈χ邪糋中所有的顶点,则称这个圈为哈密顿圈,并称图9芏偻肌】.图辛蕉サ鉛和实淖疃搪返某ざ瘸为两点问的距离,记为,.图腥我饬降慵涞淖畲笾担莆M糋的直径,,一路,则称A图,,对于一个连通图绻嬖诜,使得猄不连通,则称M糋的点分离集,乃械惴离集中最小点数称为牡懔ǘ龋俏#琧同理,若存在非空子集,使得猅是非连通的,则称狦的边分离集,乃斜叻掷爰凶钚”呤莆狦的边连通度,记为盯对于一个连通图莸萔蔞茫瑄间都存在图的哈密顿路,则称图9芏倭ㄍ肌唬龇强沼杓疭,使得猄依然是哈密顿连通图,则称图H荽淼愎芏倭ㄍ迹院笥钟型乒愕墓芏俦吡ㄍ肌】.如果图嬖谌我獬ざ鹊奈≤躭的圈,则称图哂蟹喝π裕喝π宰早是鱰岢龅模罄蠢┱沟降惴喝π院捅叻喝π浴】.设蛈是图腥我饬礁霾煌牡悖舳杂谌我庹齔琘躾≤若图且桓龉芏偻迹鑥和峭糋中任意两个不同的点,若对于任意空子集髀‘
义可知雠垡厶’七一厥獾模眎时,将铝简写为疋弦同理,若集合排列图哐芯扛趴对于尼时,定义⋯歹,躨≤七,歹∈,由定整数,≤堋綶糋中都含有一个哈密顿圈,使让,谌ι系定义杂诒取蕐瑉都在尼一茫瑄萜髦械囊惶跄诓唤坏穆飞希虺定义舳杂赩∈,让与识即嬖谄一茫瑄萜鳎虺仆糋为定义糋是七’一连通图,且芎蟆茇,则称图3С帕ㄍ迹本文中使用的图论的基本术语和符号,与文献【坑玫耐悸凼跤锖头乓恢拢,⋯,死礼,七慌帕,唯一的沟肞籴罚≤,