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

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

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

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

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