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

時間：2023-04-05 15:30:02 | 來源：營銷百科

時間：2023-04-05 15:30:02 來源：營銷百科

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