廣義斐波那契立方與Z-變換圖.pdf

1、Hsu基于斐波那契數(shù)給出了一個(gè)多用戶互聯(lián)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，即斐波那契立方圖.斐波那契立方圖是超立方圖中由不含兩個(gè)相繼1的二元串所代表的結(jié)點(diǎn)導(dǎo)出的子圖.斐波那契立方圖具有許多優(yōu)秀的性質(zhì)，它在網(wǎng)絡(luò)設(shè)計(jì)中能有效趕超許多超立方圖的算法.斐波那契立方圖的許多有趣的拓?fù)湫再|(zhì)已被發(fā)現(xiàn)，其中一個(gè)有趣的性質(zhì)是由Klav(z)ar等給出的，他們證明了斐波那契立方圖恰好是鋸齒形六角鏈(或fibonaccenes)的Z-變換圖(也稱為共振圖).此外，一些與斐波那

2、契立方圖類似的圖類也不斷的被提了出來，例如擴(kuò)展斐波那契立方圖，盧卡斯立方圖，Enhanced斐波那契立方圖，Widened斐波那契立方圖，廣義的斐波那契(p，r)-立方圖等.
　　 Z-變換圖的概念早期是對(duì)一些有著化學(xué)背景的圖類提出的，并稱之為共振圖.張?；淌诘葟臄?shù)學(xué)的角度提出了六角系統(tǒng)的完美匹配集上Z-變換圖的概念.張和平等將此概念推廣到了一般的平面二部圖上，并且對(duì)此進(jìn)行了廣泛深入的研究.平面二部圖G的Z-變換圖記作Z(G)

3、，它的頂點(diǎn)是G的完美匹配，兩個(gè)完美匹配相鄰當(dāng)且僅當(dāng)它們的對(duì)稱差是一個(gè)內(nèi)面的邊界，并且該內(nèi)面的邊界是一個(gè)圈.
　　 本文我們主要考慮斐波那契立方圖以及各種廣義斐波那契立方圖和Z-變換圖之間的聯(lián)系.全文分為以下四個(gè)部分.
　　 在第一章中，我們綜述了斐波那契類立方圖和Z-變換圖的研究背景及進(jìn)展，給出了一些基本概念和術(shù)語，并列出了本文得到的主要結(jié)論.
　　 在第二章中，我們完全刻畫了Z-變換圖是斐波那契立方圖的六角系統(tǒng)

4、.由于六角系統(tǒng)是一類平面二部圖，所以進(jìn)一步的，我們也完全確定了Z-變換圖是斐波那契立方圖的所有平面二部圖.
　　 在第三章中，我們給出一些與斐波那契立方圖構(gòu)造方式類似的圖類.我們刻畫了Z-變換圖是擴(kuò)展斐波那契立方圖的所有平面二部圖；證明了盧卡斯立方圖，Enhanced斐波那契立方圖和Widened斐波那契立方圖不是任何平面基本二部圖的Z-變換圖；此外，我們還提出了一類近似于盧卡斯立方圖的圖類，證明了該圖類可以成為平面二部圖的Z-

5、變換圖，并確定了Z-變換圖是該圖類的所有平面二部圖.
　　 在第四章中，我們介紹一類廣義的互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)，即斐波那契(p，r)-立方圖.斐波那契(p，r)-立方圖涵蓋了許多互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)，比如說超立方圖、斐波那契立方圖、郵遞網(wǎng)絡(luò)圖等作為它的特殊情況.我們討論p，r和n取哪些值時(shí)，斐波那契(p，r)-立方圖可以成為平面二部圖的Z-變換圖.為此，我們先將平面二部圖Z-變換圖的概念推廣到平面圖上，然后主要刻畫能夠成為平面圖Z-變換圖的