網(wǎng)絡(luò)圖論的基本概念

?????? 對(duì)于一個(gè)電路圖，如果用點(diǎn)表示其節(jié)點(diǎn)，用線段表示其支路，得到一個(gè)由點(diǎn)和線段組成的圖，這個(gè)圖被稱為對(duì)應(yīng)電路圖的拓?fù)鋱D，通常用符號(hào)G表示。例如：圖2-1-1（a）所示電路，其對(duì)應(yīng)的拓?fù)鋱D如圖2-1-1 (b) 所示。

圖2-1-1

圖2-1-2

?????? 拓?fù)鋱D是線段和點(diǎn)組成的集合，它反映了對(duì)應(yīng)的電路圖中的支路數(shù)、節(jié)點(diǎn)數(shù)以及各支路與節(jié)點(diǎn)之間相互連接的信息。

圖2-1-3

?????? 在拓?fù)鋱D中，如果任意兩點(diǎn)之間至少有一條連通的途徑，那么這樣的圖稱為連通圖，例如圖2-1-1（b）所示的圖，否則稱為非連通圖，例如圖2-1-2（b）所示的圖。如果圖G₁中所有的線段與點(diǎn)均是圖G中的全部或部分線段與點(diǎn)，且線段與點(diǎn)的連接關(guān)系與圖G中的一致，那么圖G₁稱為圖G的子圖。例如圖2-1-3（b）（c）（d）（e）均是圖2-1-3（a）的子圖。

?????? 下面介紹網(wǎng)絡(luò)圖論中非常重要的一個(gè)概念——樹。樹是連通圖G的一個(gè)特殊子圖，必須同時(shí)滿足以下三個(gè)條件：

（1）子圖本身是連通的；

（2）包括連通圖G所有節(jié)點(diǎn)；

（3）不包含任意回路。

組成樹的支路稱為樹支，不包含在樹上的支路稱為連支（或鏈支）。如果用表示樹支的數(shù)目，則：（式2-1-1）

連支的數(shù)目等于支路數(shù)b減去樹支的數(shù)目，即：（式2-1-2）????

?????? 如果將一個(gè)電路鋪在一個(gè)平面上，除節(jié)點(diǎn)之外再?zèng)]有其他交點(diǎn)，這樣的電路被稱為平面電路，否則，稱為非平面電路。

?????? 在平面電路中，內(nèi)部沒有任何支路的回路稱為網(wǎng)孔。它是一種特殊的回路。

?????? 一個(gè)有b條支路、n個(gè)節(jié)點(diǎn)的連通平面圖的網(wǎng)孔數(shù)m為：（式2-1-3）

?????? 接下來介紹割集的概念。割集是連通圖G的一個(gè)子圖，它滿足以下兩個(gè)條件：

?????? （1）移去該子圖的全部支路，連通圖G將被分為兩個(gè)獨(dú)立部分；

?????? （2）當(dāng)少移去該子圖中任一條支路時(shí)，則圖仍然保持連通。????

?????? 一個(gè)具有n個(gè)節(jié)點(diǎn)的連通圖，有（n-1）條樹，有（n-1）個(gè)單樹支割集。