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

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

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

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

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

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