[科普中國]-對剖寬度

網(wǎng)絡(luò)的對剖寬度（Bisection Width）是指對分網(wǎng)絡(luò)所要移去的最少邊數(shù)。

簡介其數(shù)目等于對剖平面的鏈路數(shù)，與每條鏈路的連線數(shù)（或稱作鏈路寬度或通道寬度）二者之間的乘積，即表示穿越對剖平面總共的連線數(shù)。除了對剖寬度，還有網(wǎng)絡(luò)直徑，節(jié)點(diǎn)度，嵌入等都是網(wǎng)絡(luò)的基本術(shù)語。1

網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑（network diameter）是指網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的最長距離，一般用鏈路樹來度量。通常要提高網(wǎng)絡(luò)傳輸?shù)钠焚|(zhì)和速度下，網(wǎng)絡(luò)直徑就會減小。2

節(jié)點(diǎn)度網(wǎng)絡(luò)節(jié)點(diǎn)（頂點(diǎn)）的度是指和該節(jié)點(diǎn)（頂點(diǎn)）相關(guān)聯(lián)的邊的條數(shù)。特別地，對于有向圖，

節(jié)點(diǎn)（頂點(diǎn)）的入度是指進(jìn)入該節(jié)點(diǎn)（頂點(diǎn)）的邊的條數(shù)；

節(jié)點(diǎn)（頂點(diǎn)）的出度是指從該節(jié)點(diǎn)（頂點(diǎn)）出發(fā)的邊的條數(shù)。1

嵌入將一個網(wǎng)絡(luò)A嵌入到另一個網(wǎng)絡(luò)B中是指將A中的各節(jié)點(diǎn)映射到B的節(jié)點(diǎn)。

膨脹系數(shù)（Dilation）膨脹系數(shù)是指被嵌網(wǎng)絡(luò)在主嵌網(wǎng)絡(luò)中對應(yīng)的邊數(shù)（即鏈路數(shù)）。如果系數(shù)為1，則稱為完美嵌入。例如，2-D環(huán)繞可完美嵌入到超立方體連接中去。1

本詞條內(nèi)容貢獻(xiàn)者為:

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所