本文選題：圖論 + 邊連通子圖�。� 參考：《東華大學(xué)》2017年碩士論文

【摘要】：現(xiàn)代社會中,無論是日常的工作、生活、學(xué)習(xí)都離不開網(wǎng)絡(luò)。而隨著人口數(shù)量、信息量等的不斷增大,網(wǎng)絡(luò)的規(guī)模和復(fù)雜度也日益增加。網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈接的失效都有可能導(dǎo)致整個網(wǎng)絡(luò)的癱瘓,對社會造成巨大的損失。因此,網(wǎng)絡(luò)的抗毀性研究也變得至關(guān)重要。本文介紹了抗毀性網(wǎng)絡(luò)的研究背景及意義,并綜述了國內(nèi)外對于抗毀性網(wǎng)絡(luò)的研究現(xiàn)狀,得出目前的兩大主要研究方向:(1)復(fù)雜網(wǎng)絡(luò)抗毀度的測量;(2)抗毀性能好的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)。本文從第二個方向出發(fā),考慮節(jié)點(diǎn)和鏈接均失效的情況下,設(shè)計(jì)抗毀性能好,并且傳輸速率不受影響的網(wǎng)絡(luò)。首先,為了保證網(wǎng)絡(luò)的傳輸速率,本文建立了以最小成本流模型為基礎(chǔ),基于直徑約束的最小生成樹模型,簡稱為DCMST模型。其次,為了使得網(wǎng)絡(luò)在節(jié)點(diǎn)和鏈接均失效的情況下,仍能保持網(wǎng)絡(luò)的正常運(yùn)行,本文建立了λ-邊連通k節(jié)點(diǎn)-子圖(k-MST問題和λ-邊連通問題的一般化)的整數(shù)規(guī)劃模型,簡稱為(k,λ)子圖模型。根據(jù)圖論的特性,建立有效的不等式約束,簡化模型。另一方面,由于(k,2)子圖模型具有獨(dú)特的特征,如:無橋性,故根據(jù)特征構(gòu)建(k,2)-子圖的整數(shù)規(guī)劃模型。采用C++調(diào)用Cplex求解模型,比較不同模型,以及不同模型加入不同不等式約束后的求解時間。最后構(gòu)建通信網(wǎng)絡(luò),驗(yàn)證網(wǎng)絡(luò)在不同邊連通度下的抗毀能力。然后綜合考慮DCMST問題和(k,λ)子圖問題,建立基于直徑約束的λ-邊連通k節(jié)點(diǎn)-子圖模型,簡稱為DC(k,λ)子圖模型,運(yùn)用整數(shù)規(guī)劃求解。之后根據(jù)直徑D的奇偶性,采用Hop約束,分別建立當(dāng)D為偶數(shù),以及當(dāng)D為奇數(shù)時的模型。采用C++調(diào)用Cplex求解模型,比較不同模型在不同條件下的求解時間。最后構(gòu)建通信網(wǎng)絡(luò),驗(yàn)證網(wǎng)絡(luò)在不同直徑下的抗毀能力。
[Abstract]:In modern society, whether daily work, life, learning are inseparable from the network. With the increase of population and information, the scale and complexity of network are increasing. The failure of nodes or links in the network may lead to the paralysis of the whole network, causing huge losses to the society. Therefore, the research of network survivability becomes very important. This paper introduces the research background and significance of the invulnerability network, and summarizes the research status of the invulnerable network at home and abroad, and concludes two main research directions: (1) the measurement of the survivability of the complex network; (2) the optimal design of the network with good survivability. From the second direction, considering the failure of both nodes and links, a network with good survivability and unaffected transmission rate is designed. Firstly, in order to guarantee the transmission rate of the network, a minimum spanning tree model based on the minimum cost flow model and diameter constraint is established in this paper, which is called DCMST model for short. Secondly, in order to keep the network running normally when the nodes and links fail, the integer programming model of 位 -edge connected k-node-subgraph (k-MST problem and 位 -edge connected problem) is established. It is referred to as (k, 位) subgraph model. According to the characteristics of graph theory, an effective inequality constraint is established and the model is simplified. On the other hand, due to the unique characteristics of the (kt2) subgraph model, for example, there is no bridge, the integer programming model of (kk2) -subgraph is constructed according to the feature. C call Cplex is used to solve the model, and the solving time of different models and different inequality constraints is compared. Finally, the communication network is constructed to verify the survivability of the network under different edge connectivity. Then considering the DCMST problem and (k, 位) subgraph problem, a 位 -edge-connected k-node-subgraph model based on diameter constraint is established, which is called DC (k, 位) subgraph model, and solved by integer programming. Then, according to the parity of diameter D, using the Hop constraint, the models are established when D is even and if D is odd. C call Cplex is used to solve the model, and the solving time of different models under different conditions is compared. Finally, the communication network is constructed to verify the survivability of the network under different diameters.
【學(xué)位授予單位】：東華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN915.02;O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 劉潤然;賈春曉;章劍林;汪秉宏;;相依網(wǎng)絡(luò)在不同攻擊策略下的魯棒性[J];上海理工大學(xué)學(xué)報(bào);2012年03期

2 陳忠學(xué),靳蕃,鄒盛唐,朱紅琛;短波網(wǎng)基于節(jié)點(diǎn)的抗毀性評估[J];通信技術(shù);2000年03期

，

本文編號：2102093