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

前言

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

內(nèi)容概要

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

書籍目錄

序前言第一章  引言和基本概念  1.1  圖論的一些基本概念和記號  1.2  k限制邊連通度的應(yīng)用背景和研究進(jìn)展第二章  超級k限制邊連通圖的鄰域充分條件  2.1  相關(guān)概念和結(jié)果  2.2  準(zhǔn)備工作  2.3  極大k限制邊連通圖的鄰域條件  2.4  超級k限制邊連通圖的鄰域條件  2.5  極大和超級k等周邊連通圖第三章  直徑為2的圖的超級限制邊連通性  3.1  相關(guān)概念和結(jié)果  3.2  準(zhǔn)備工作  3.3  超級限制邊連通圖的鄰域條件  3.4  結(jié)果的相互獨(dú)立性第四章  二部圖的超級k限制邊連通性  4.1  相關(guān)結(jié)果  4.2  超級限制邊連通二部圖  4.3  極大k限制邊連通二部圖  4.4  超級k限制邊連通二部圖第五章  用直徑和圍長表示的超級k限制邊連通圖的充分條件  5.1  相關(guān)概念和結(jié)果  5.2  準(zhǔn)備工作  5.3  超級限制邊連通圖的直徑圍長條件  5.4  極大k限制邊連通圖的直徑圍長條件  5.5  超級k限制邊連通圖的條件直徑圍長條件第六章  線圖的超級k限制邊連通性  6.1  相關(guān)概念和結(jié)果  6.2  k限制邊連通度與(1，k)限制連通度相等時(shí)圖的性質(zhì)  6.3  k限制邊連通度與(1，k)限制連通度相等時(shí)超級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限制邊連通度第八章  無向Kautz圖的極大k限制邊連通性  8.1  相關(guān)概念和結(jié)果  8.2  準(zhǔn)備工作  8.3  無向Kautz圖的超級限制邊連通性  8.4  無向Kautz圖的k限制邊連通度第九章  一類無向Kautz圖的k限制邊連通度  9.1  相關(guān)結(jié)果  9.2  一類無向Kautz圖的k限制邊連通度的上界  9.3  一類無向Kautz圖的超級4限制邊連通性第十章  定向圖的超級弧連通性  10.1  相關(guān)概念和結(jié)果  10.2  超級弧連通定向圖的最小度條件  10.3  超級弧連通定向圖的半度序列條件第十一章  有向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)主要符號表

圖書封面

評論、評分、閱讀與下載

---

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

---