?????? 對于一個電路圖,如果用點表示其節(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)所示的圖。如果圖G1中所有的線段與點均是圖G中的全部或部分線段與點,且線段與點的連接關系與圖G中的一致,那么圖G1稱為圖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)個單樹支割集。
評論
查看更多