網絡圖論的基本概念

?????? 對于一個電路圖，如果用點表示其節(jié)點，用線段表示其支路，得到一個由點和線段組成的圖，這個圖被稱為對應電路圖的拓撲圖，通常用符號G表示。例如：圖2-1-1（a）所示電路，其對應的拓撲圖如圖2-1-1 (b) 所示。

圖2-1-1

圖2-1-2

?????? 拓撲圖是線段和點組成的集合，它反映了對應的電路圖中的支路數、節(jié)點數以及各支路與節(jié)點之間相互連接的信息。

圖2-1-3

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

?????? 下面介紹網絡圖論中非常重要的一個概念——樹。樹是連通圖G的一個特殊子圖，必須同時滿足以下三個條件：

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

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

（3）不包含任意回路。

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

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

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

?????? 在平面電路中，內部沒有任何支路的回路稱為網孔。它是一種特殊的回路。

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

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

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

?????? （2）當少移去該子圖中任一條支路時，則圖仍然保持連通。????

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