25366.若干圖的反饋數(shù)上下界研究

1、碩士學(xué)位論文若干圖的反饋數(shù)上下界研究ResearchonTheUpperandLowerBoundofFeedbackNumbersofSeveralGraphs作者姓名：塞l』聰學(xué)號(hào)：望1091兇完成日期：2Q!壘生壘旦大連理工大學(xué)DalianUniversityofTechnology大連理工大學(xué)碩士學(xué)位論文摘要圖的反饋數(shù)問(wèn)題來(lái)源于實(shí)際問(wèn)題，在諸多領(lǐng)域如預(yù)防計(jì)算機(jī)死鎖，互連網(wǎng)避免廣播風(fēng)暴以及電子電路檢測(cè)等問(wèn)題中有著廣泛的應(yīng)用。已經(jīng)被

2、證明求圖的反饋數(shù)問(wèn)題是NP困難問(wèn)題，研究它對(duì)解決一般NP困難問(wèn)題有借鑒意義。對(duì)簡(jiǎn)單圖G=(礦，E)，子集F屬于兒如果從圖G中去掉頂點(diǎn)集F及其關(guān)聯(lián)的所有邊產(chǎn)生的子圖沒(méi)有回路，則稱(chēng)頂點(diǎn)集F是圖G的反饋點(diǎn)集。我們希望反饋點(diǎn)集越小越好，最小的反饋點(diǎn)集稱(chēng)為圖的最小反饋點(diǎn)集，其對(duì)應(yīng)的點(diǎn)的個(gè)數(shù)稱(chēng)為圖的反饋數(shù)。交叉立方體CQ和局部扭立方體LTQ是超立方體Q的兩個(gè)重要變形，它們都保留了Q的一些重要性質(zhì)，如維數(shù)都為n時(shí)，其均有2”個(gè)頂點(diǎn)，胛2”1條邊，且均

3、為，z一正則圖，同時(shí)，CQ和￡覡有比超立方體Q更好的性質(zhì)，如同樣維數(shù)的情況下，CQ和￡覡的直徑是Q的一半，正因?yàn)檫@樣的優(yōu)質(zhì)特性，所以研究超立方體Q的變形具有重要意義。本文通過(guò)構(gòu)造剩余子圖G少(嗡)＼F】的極大無(wú)圈子圖得到極小反饋集，從而得到反饋數(shù)的上界的方法，來(lái)研究交叉立方體的反饋數(shù)問(wèn)題，并證明了交叉立方體的反饋數(shù)為：f(n)=2”～(1一—二_)，，2≥2，c∈[o，1】。n～l根據(jù)局部扭立方體頂點(diǎn)集合中最后一位字節(jié)不同的特點(diǎn)，將其頂

4、點(diǎn)集合劃分為兩個(gè)不相交的子集，并構(gòu)造極大無(wú)圈子圖得到反饋數(shù)的上界，從而研究局部扭立方體的反饋數(shù)問(wèn)題，并證明了11維局部扭立方體的反饋數(shù)為：f(n)=2”～(1一—二_)，，2≥2，c∈[o，1]。，z—l花圖(FlowerSnark)及其相關(guān)圖是三正則圖，花圖及其相關(guān)圖的定義實(shí)質(zhì)是相同的，只是當(dāng)其維數(shù)n是奇數(shù)且有n≥5時(shí)稱(chēng)之為花圖，當(dāng)n為其他情況時(shí)，則生成的圖被稱(chēng)為花圖的相關(guān)圖。本文采用計(jì)算機(jī)搜索與數(shù)學(xué)證明相結(jié)合的方式得到了花圖的反饋數(shù)