設T是無向圖G的生成子圖

1、1定義定義12.2.1 設設T是無向圖是無向圖G的生成子圖，若的生成子圖，若T是樹，是樹，則稱則稱T是是G的生成樹。的生成樹。 從從G中刪去中刪去T 的邊后得到的圖稱為的邊后得到的圖稱為T 的余樹，記為的余樹，記為T。T 中的邊稱為中的邊稱為T 的樹枝，的樹枝，T 中的邊稱為中的邊稱為T 的弦的弦（或余枝）。（或余枝）。e5e8e6e1e2e7e4e32定理定理12.2.1 無向圖無向圖G是連通圖當且僅當是連通圖當且僅當G有生成樹有生成樹.證證 充分性充分性 顯然，因為生成樹本身是連通的。顯然，因為生成樹本身是連通的。 必要性必要性 設設G是連通圖。如果是連通圖。如果G中無回路，那么中無回路，

2、那么G本身就是生成樹；如果本身就是生成樹；如果G中存在回路中存在回路C1，則去掉，則去掉C1上的一條邊，仍保持連通性；若還有回路上的一條邊，仍保持連通性；若還有回路C2 ，則再去掉則再去掉C2上的一條邊，直到無回路為止，最后上的一條邊，直到無回路為止，最后得到一棵生成樹。得到一棵生成樹。3推論推論1 設設G為連通圖，為連通圖，V(G)=n, E(G)=m, 則則m n-1推論推論2 設設T 為為G 的一棵生成樹，則的一棵生成樹，則T 的余樹的余樹T 有有 m-n+1條邊。條邊。4定義定義12.2.2 設設T為連通圖為連通圖G的生的生成樹，成樹，e為為T的弦，稱回路的弦，稱回路T e為為G的的(

3、關于關于T的弦的弦e 的的)基本回路，基本回路，記為記為C(e)；集合集合C = C(ei)|ei為為T 的弦的弦稱為稱為G的的(關于關于T 的的)基本回基本回路系統。路系統。圖圖G及其生成樹及其生成樹Tabcdste4e2e3e1e5e6e7e8C(e1)abse4e1e5C(e2)abcde2e5e6e7C(e3)abcdte3e5e6e7e85例例12.2.2 求圖求圖G的全部回路。的全部回路。解：利用解：利用G關于關于T 的基本回路系統。記的基本回路系統。記Ck=C(ek) 且作映射且作映射 Ck (d d1k, d d2k, , d d8k)圖圖Gabcdste4e2e3e1e5e6

4、e7e810ikikikeCeCd d 12345678123100110000100111000101111eeeeeeeeCCC 6 其中其中C1 C2 C3為基本回路為基本回路；C1 C2 C2 C3 C1 C3為為G的回路，但非基本回路；的回路，但非基本回路； C1 C2 C3為為G的環(huán)路，的環(huán)路，但非回路，但非回路， 1234567812312132312310011000010011100010111111010110101101110110000111111001eeeeeeeeCCCCCCCCCCCC 7C1abse4e1e5C2abcde2e5e6e7C3abcdte3e5e6e7e8abcdse4e2e1e6e7abcd