【正文】 /63 推論 在圖 G＝ V， E中 ， 其 V＝ {v1,v2,v3,… ,vn}， E＝ {e1， e2， …… ， em}，度數(shù)為奇數(shù)的結(jié)點個數(shù)為偶數(shù)。 5) 各點度數(shù)相等的圖稱為 正則圖 ， 特別將點度為k的正則圖稱為 k度正則圖 。 5) 各點度數(shù)相等的圖稱為正則圖 ， 特別將點度為k的正則圖稱為 k度正則圖 。 5) 各點度數(shù)相等的圖稱為正則圖 ， 特別將點度為k的正則圖稱為 k度正則圖 。 2) 在有向圖 G＝ V， E中 ， 以結(jié)點 v為始點引出的邊的條數(shù) ， 稱為該結(jié)點的出度 ,記為 deg+(v)；以結(jié)點 v為終點引入的邊的條數(shù) ， 稱為該結(jié)點的入度 ,記為 deg(v)；而結(jié)點的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點的度數(shù) ， 記為 deg(v)，即 deg(v)＝ deg+(v)+deg(v)； 2022/2/13 計算機學院 20/63 結(jié)點的度數(shù) 1) 在無向圖 G＝ V， E中 ， 與結(jié)點 v(v?V)關聯(lián)的邊的條數(shù) （ 有環(huán)時計算兩次 ） ， 稱為該結(jié)點的度數(shù) ， 記為 deg(v)；最大點度和最小點度分別記為 ?和 ?。 非賦權圖稱為 無權圖 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個簡單圖 ， 稱為原來圖的 基圖 。 2022/2/13 計算機學院 17/63 圖的分類 (按邊的重數(shù) ) 1) 在有向圖中 ， 兩個結(jié)點間 (包括結(jié)點自身間 )若有同始點和同終點的幾條邊 ， 則這幾條邊稱為平行邊 。 2) 在無向圖中 ， 兩個結(jié)點間 (包括結(jié)點自身間 )若有幾條邊 ， 則這幾條邊稱為平行邊； 3) 含有平行邊的圖稱為 多重圖 ； 4) 含有 環(huán) 的多重圖稱為 廣義圖 （ 偽圖 ） ； 5) 滿足定義 簡單圖 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個簡單圖 ， 稱為原來圖的基圖 。 2022/2/13 計算機學院 12/63 幾個概念 1) 在一個圖中 ， 關聯(lián)結(jié)點 vi和 vj的邊 e， 無論是有向的還是無向的 ， 均稱邊 e與結(jié)點 vI和 vj相關聯(lián) ， 而 vi和 vj稱為 鄰接點 ， 否則稱為 不鄰接的 ； 2) 關聯(lián)于同一個結(jié)點的兩條邊稱為鄰接邊； 3) 圖中關聯(lián)同一個結(jié)點的邊稱為環(huán) (或自回路 )； 4) 圖中不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點； 5) 僅由孤立結(jié)點組成的圖稱為零圖； 6) 僅含一個結(jié)點的零圖稱為平凡圖； 7) 含有 n個結(jié)點 、 m條邊的圖 稱為 (n， m)圖； e1 e2 e5 v3 v2 v1 e3 e4 e6 v5 v4 2022/2/13 計算機學院 13/63 幾個概念 1) 在一個圖中 ， 關聯(lián)結(jié)點 vi和 vj的邊 e， 無論是有向的還是無向的 ， 均稱邊 e與結(jié)點 vI和 vj相關聯(lián) ， 而 vi和 vj稱為鄰接點 ， 否則稱為不鄰接的； 2) 關聯(lián)于同一個結(jié)點的兩條邊稱為 鄰接邊 ； 3) 圖中關聯(lián)同一個結(jié)點的邊稱為 環(huán) (或 自回路 )； 4) 圖中不與任何結(jié)點相鄰接的結(jié)點稱為 孤立結(jié)點 ； 5) 僅由孤立結(jié)點組成的圖稱為零圖； 6) 僅含一個結(jié)點的零圖稱為平凡圖； 7) 含有 n個結(jié)點 、 m條邊的圖 稱為 (n， m)圖； e1 e2 e5 v3 v2 v1 e3 e4 e6 v5 v4 2022/2/13 計算機學院 14/63 幾個概念 1) 在一個圖中 ， 關聯(lián)結(jié)點 vi和 vj的邊 e， 無論是有向的還是無向的 ， 均稱邊 e與結(jié)點 vI和 vj相關聯(lián) ， 而 vi和 vj稱為鄰接點 ， 否則稱為不鄰接的； 2) 關聯(lián)于同一個結(jié)點的兩條邊稱為鄰接邊； 3) 圖中關聯(lián)同一個結(jié)點的邊稱為環(huán) (或自回路 )； 4) 圖中不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點； 5) 僅由孤立結(jié)點組成的圖稱為 零圖 ； 6) 僅含一個結(jié)點的零圖稱為 平凡圖 ； 7) 含有 n個結(jié)點 、 m條邊的圖 稱為 (n， m)圖 ； e1 e2 e5 v3 v2 v1 e3 e4 e6 v5 v4 2022/2/13 計算機學院 15/63 圖的分類 (按邊的重數(shù) ) 1) 在有向圖中 ， 兩個結(jié)點間 (包括結(jié)點自身間 )若有同始點和同終點的幾條邊 ， 則這幾條邊稱為 平行邊 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計算機學院 11/63 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點對 (u， v)相對應 ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時稱 u， v是邊 e的兩個端點； 2) 若邊 e與有序結(jié)點對 u， v相對應 ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時稱 u是邊 e的始點 。 3) 每條邊都是無向邊的圖稱為 無向圖 ； 4) 每條邊都是有向邊的圖稱為 有向圖 ； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為 混合圖 。 2022/2/13 計算機學院 10/63 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點對 (u， v)相對應 ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時稱 u， v是邊 e的兩個端點； 2) 若邊 e與有序結(jié)點對 u， v相對應 ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時稱 u是邊 e的始點 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計算機學院 9/63 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點對 (u， v)相對應 ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時稱 u， v是邊 e的兩個端點 ； 2) 若邊 e與有序結(jié)點對 u， v相對應 ， 則稱邊 e為 有向邊 ，記為 e＝ u， v， 這時稱 u是邊 e的 始點 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計算機學院 8/63 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點對 (u， v)相對應 ， 則稱邊 e為 無向邊 ,記為 e＝ (u， v)， 這時稱 u， v是邊 e的兩個 端點 ； 2) 若邊 e與有序結(jié)點對 u， v相對應 ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時稱 u是邊 e的始