網(wǎng)絡(luò)邊連通性的最優(yōu)化

前言

　　組合數(shù)學(xué)，或廣言之，離散性數(shù)學(xué)，主要研究“狀態(tài)模式”的存在、計(jì)數(shù)、構(gòu)造和優(yōu)化。所謂狀態(tài)模式，就是一個(gè)集合中各個(gè)元素賦予狀態(tài)的方式。常見(jiàn)的狀態(tài)模式有連接、選取、匹配、排序、劃分、覆蓋、裝填等方式。對(duì)一個(gè)離散系統(tǒng)而言，各元素之間的聯(lián)系，即連通性，應(yīng)該是最基本的模式。特別對(duì)圖與網(wǎng)絡(luò)這樣具有典型意義的組合構(gòu)形，連通性是首要的研究專題。　　圖論歷史悠久，其應(yīng)用范圍已遍及自然科學(xué)與系統(tǒng)科學(xué)等領(lǐng)域。之所以受到普遍重視，與它的簡(jiǎn)潔清晰而富有表現(xiàn)力是分不開(kāi)的。在圖論的經(jīng)典發(fā)展時(shí)期，人們往往用圖來(lái)表示日常生活的事理關(guān)系，如游歷過(guò)橋、連線選點(diǎn)、染色劃分等。其中問(wèn)題的提法都比較簡(jiǎn)單明白（求解不一定容易）。隨著學(xué)科的發(fā)展，圖所描寫(xiě)的關(guān)聯(lián)關(guān)系越來(lái)越復(fù)雜，從游戲規(guī)則到物質(zhì)結(jié)構(gòu)和工程系統(tǒng)，研究層面不斷向縱深推進(jìn)?！　?0世紀(jì)電子計(jì)算機(jī)的出現(xiàn)，引發(fā)了信息科學(xué)的突飛猛進(jìn)。大量離散問(wèn)題的涌現(xiàn)，使圖論獲得了新的生長(zhǎng)點(diǎn)和肥沃的土壤，推動(dòng)圖論進(jìn)入繁榮發(fā)展的新階段。尤其是計(jì)算機(jī)系統(tǒng)互聯(lián)網(wǎng)絡(luò)的興起，帶來(lái)許多新概念和新課題?？梢杂镁W(wǎng)絡(luò)把眾多的計(jì)算機(jī)連接起來(lái)，相互配合，發(fā)揮更強(qiáng)的功能。比如說(shuō)，已有的計(jì)算機(jī)系統(tǒng)（分布式或并行式計(jì)算系統(tǒng)）用一個(gè)圖H來(lái)表示，稱為“主圖”；而互聯(lián)網(wǎng)絡(luò)用一個(gè)圖G來(lái)表示，稱為“客圖”。那么設(shè)計(jì)互聯(lián)網(wǎng)絡(luò)就是把圖G嵌入圖日中，使得嵌入方式的某些性能指標(biāo)達(dá)到最優(yōu)。這些性能指標(biāo)主要是指交換信息的有效性、可靠性、容錯(cuò)性以及電路布線上的其他指標(biāo)，如延伸、擁擠、轉(zhuǎn)折、交叉等。簡(jiǎn)單地說(shuō)，一個(gè)好的互聯(lián)網(wǎng)絡(luò)應(yīng)該有盡可能大的“連通度”和盡可能小的“直徑”。進(jìn)而，還要對(duì)稱性好，傳輸延遲小，布線與路由算法簡(jiǎn)單，容易嵌入其他拓?fù)浣Y(jié)構(gòu)等。由此提出一系列重要的研究課題，形成現(xiàn)代圖論中十分活躍的研究方向“通信網(wǎng)絡(luò)理論”，吸引著眾多的圖論學(xué)者。

內(nèi)容概要

本書(shū)對(duì)網(wǎng)絡(luò)邊連通性的最優(yōu)化問(wèn)題提供了一個(gè)統(tǒng)一的理論框架，其中許多內(nèi)容和方法是作者的研究成果。內(nèi)容包括：  給出極大k限制邊連通圖和超級(jí)k限制邊連通圖的各種充分條件；確定一些著名網(wǎng)絡(luò)的k限制邊連通度和超級(jí)k限制邊連通性；同時(shí)，還提出一些問(wèn)題供有興趣的讀者進(jìn)一步研究。    本書(shū)可供高等院校計(jì)算機(jī)應(yīng)用、網(wǎng)絡(luò)通信、應(yīng)用數(shù)學(xué)等相關(guān)專業(yè)研究生和高年級(jí)本科生學(xué)習(xí)，也可作為相關(guān)領(lǐng)域研究人員的參考用書(shū)。

書(shū)籍目錄

序前言第一章  引言和基本概念  1.1  圖論的一些基本概念和記號(hào)  1.2  k限制邊連通度的應(yīng)用背景和研究進(jìn)展第二章  超級(jí)k限制邊連通圖的鄰域充分條件  2.1  相關(guān)概念和結(jié)果  2.2  準(zhǔn)備工作  2.3  極大k限制邊連通圖的鄰域條件  2.4  超級(jí)k限制邊連通圖的鄰域條件  2.5  極大和超級(jí)k等周邊連通圖第三章  直徑為2的圖的超級(jí)限制邊連通性  3.1  相關(guān)概念和結(jié)果  3.2  準(zhǔn)備工作  3.3  超級(jí)限制邊連通圖的鄰域條件  3.4  結(jié)果的相互獨(dú)立性第四章  二部圖的超級(jí)k限制邊連通性  4.1  相關(guān)結(jié)果  4.2  超級(jí)限制邊連通二部圖  4.3  極大k限制邊連通二部圖  4.4  超級(jí)k限制邊連通二部圖第五章  用直徑和圍長(zhǎng)表示的超級(jí)k限制邊連通圖的充分條件  5.1  相關(guān)概念和結(jié)果  5.2  準(zhǔn)備工作  5.3  超級(jí)限制邊連通圖的直徑圍長(zhǎng)條件  5.4  極大k限制邊連通圖的直徑圍長(zhǎng)條件  5.5  超級(jí)k限制邊連通圖的條件直徑圍長(zhǎng)條件第六章  線圖的超級(jí)k限制邊連通性  6.1  相關(guān)概念和結(jié)果  6.2  k限制邊連通度與(1，k)限制連通度相等時(shí)圖的性質(zhì)  6.3  k限制邊連通度與(1，k)限制連通度相等時(shí)超級(jí)k限制邊連通圖的充分條件第七章  兩類互聯(lián)網(wǎng)絡(luò)的k限制邊連通度  7.1  相關(guān)概念和結(jié)果  7.2  G(Go，G1；Mt)的k限制邊連通度  7.3  G(G0，G1，，Gr-1；Mt)的k限制邊連通度第八章  無(wú)向Kautz圖的極大k限制邊連通性  8.1  相關(guān)概念和結(jié)果  8.2  準(zhǔn)備工作  8.3  無(wú)向Kautz圖的超級(jí)限制邊連通性  8.4  無(wú)向Kautz圖的k限制邊連通度第九章  一類無(wú)向Kautz圖的k限制邊連通度  9.1  相關(guān)結(jié)果  9.2  一類無(wú)向Kautz圖的k限制邊連通度的上界  9.3  一類無(wú)向Kautz圖的超級(jí)4限制邊連通性第十章  定向圖的超級(jí)弧連通性  10.1  相關(guān)概念和結(jié)果  10.2  超級(jí)弧連通定向圖的最小度條件  10.3  超級(jí)弧連通定向圖的半度序列條件第十一章  有向de Brujn圖的強(qiáng)限制弧連通度  11.1  相關(guān)概念和結(jié)果  11.2  準(zhǔn)備工作  11.3  有向de Bruijn圖的強(qiáng)限制弧連通度第十二章  極大限制弧連通有向圖  12.1  相關(guān)概念和結(jié)果  12.2  極大限制弧連通有向圖的定義和性質(zhì)  12.3  極大限制弧連通有向圖的充分條件參考文獻(xiàn)主要符號(hào)表

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

    網(wǎng)絡(luò)邊連通性的最優(yōu)化 PDF格式下載

---