離散數(shù)學圖論

《離散數(shù)學圖論》由會員分享，可在線閱讀，更多相關《離散數(shù)學圖論（22頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、v圖的術語v度數(shù)v完全圖v子圖v補圖v圖的同構7-1 圖 的 基 本 概 念 定 義 一 個 圖 是 一 個 三 元 組 ,簡 記 為 G ，其 中 ： V v1,v2,v3,vn是 一 個 非 空 集 合 ,vi(i 1,2,3,n)稱 為 結點 ,簡 稱 點 ,V為 結 點 集 ；1) E e1,e2,e3,em是 一 個 有 限 集 ， ei(i 1,2,3,m)稱 為邊 ,E為 邊 集 ， E中 的 每 個 元 素 都 有 V中 的 結 點 對 （ 有 序 偶或 無 序 偶 ） 與 之 對 應 。一 、 圖 的 術 語 圖 的 術 語 若 邊 e與 結 點 無 序 偶 (u， v)相

2、對 應 ， 則 稱 邊 e為 無 向 邊 ,記 為e (u， v)， 這 時 稱 u， v是 邊 e的 兩 個 端 點 ； 若 邊 e與 結 點 有 序 偶 相 對 應 ， 則 稱 邊 e為 有 向 邊 (或弧 )， 記 為 e ， 這 時 稱 u是 邊 e的 始 點 (或 弧 尾 )， v是邊 e的 終 點 (或 弧 頭 )， 統(tǒng) 稱 為 e的 端 點 ； 在 一 個 圖 中 ， 關 聯(lián) 結 點 vi和 vj的 邊 e， 無 論 是 有 向 的 還 是 無向 的 ， 均 稱 邊 e與 結 點 vi和 vj相 關 聯(lián) ， 而 vi和 vj稱 為 鄰 接 點 ，否 則 稱 為 不 鄰 接 的 ；

3、 關 聯(lián) 于 同 一 個 結 點 的 兩 條 邊 稱 為 鄰 接 邊 ； 圖 中 關 聯(lián) 同 一 個 結 點 的 邊 稱 為 自 回 路 (或 環(huán) )； 圖 中 不 與 任 何 結 點 相 鄰 接 的 結 點 稱 為 孤 立 結 點 ； 僅 由 孤 立 結 點 組 成 的 圖 稱 為 零 圖 ； 僅 含 一 個 結 點 的 零 圖 稱 為 平 凡 圖 ； 續(xù) ： 含 有 n個 結 點 、 m條 邊 的 圖 稱 為 (n， m)圖 ； 每 條 邊 都 是 無 向 邊 的 圖 稱 為 無 向 圖 ； 每 條 邊 都 是 有 向 邊 的 圖 稱 為 有 向 圖 ； 有 些 邊 是 無 向 邊 ， 而

4、 另 一 些 是 有 向 邊 的 圖 稱 為 混 合 圖 。 在 有 向 圖 中 ， 兩 個 結 點 間 (包 括 結 點 自 身 間 )若 有 同 始 點 和 同終 點 的 幾 條 邊 ， 則 這 幾 條 邊 稱 為 平 行 邊 ， 在 無 向 圖 中 ， 兩 個結 點 間 (包 括 結 點 自 身 間 )若 有 幾 條 邊 ， 則 這 幾 條 邊 稱 為 平 行邊 ， 兩 結 點 vi， vj間 相 互 平 行 的 邊 的 條 數(shù) 稱 為 邊 (vi， vj)或 的 重 數(shù) ； 含 有 平 行 邊 的 圖 稱 為 多 重 圖 。 非 多 重 圖 稱 為 線 圖 ； 無 自 回 路的 線 圖

5、 稱 為 簡 單 圖 。 賦 權 圖 G 是 一 個 三 元 組 或 四 元 組 ， 其 中 ， V是 結 點 集 合 ， E是 邊 的 集 合 ， g是 從 E到 非 負 實 數(shù) 集 合 的 函 數(shù) 。 (a) 例 ：(b)(c) (d)例 ： (e) (f)(g) (h) 例 ：例 ： (i) (j)(k) (l) 例 ：例 ： (m) (n)(o) (p)例 ：例 ： 定 義 在 無 向 圖 G 中 ， 與 結 點 v(vV)關 聯(lián) 的 邊 的 條數(shù) ， 稱 為 該 結 點 的 度 數(shù) ， 記 為 deg(v)；定 義 在 有 向 圖 G 中 ， 以 結 點 v(vV)為 始 點 引 出

6、 的邊 的 條 數(shù) ， 稱 為 該 結 點 的 引 出 度 數(shù) ,簡 稱 出 度 ,記 為 deg+(v)；以 結 點 v(vV)為 終 點 引 入 的 邊 的 條 數(shù) ， 稱 為 該 結 點 的 引入 度 數(shù) ， 簡 稱 入 度 ,記 為 deg-(v)； 而 結 點 的 出 度 和 入 度 之和 稱 為 該 結 點 的 度 數(shù) ， 記 為 deg(v)， 即deg(v) deg+(v)+deg-(v)；(G)最 小 度 ， (G)最 大 度定 義 在 圖 G 中 ， 對 任 意 結 點 vV， 若 度 數(shù) deg(v)為奇 數(shù) ， 則 稱 此 結 點 為 奇 度 數(shù) 結 點 ， 若 度 數(shù)

7、 deg(v)為 偶 數(shù) ，則 稱 此 結 點 為 偶 度 數(shù) 結 點 。 二 、 度 數(shù) 例 ：deg(v1) 3， deg+(v1) 2， deg-(v1) 1；deg(v2) 3， deg+(v2) 2， deg-(v2) 1；deg(v3) 5， deg+(v3) 2， deg-(v3) 3；deg(v4) deg+(v4) deg-(v4) 0；deg(v5) 1， deg+(v5) 0， deg-(v5) 1； 例 ： 定 理1.在 無 向 圖 G 中 ， 所 有 結 點 的 度 數(shù) 的 總 和 等 于邊 數(shù) 的 兩 倍 ， 即 ： ；m2)vdeg(Vv ，m)v(deg)v(d

8、eg VvVv 在 有 向 圖 G 中 ， 所 有 結 點 的 出 度 之 和 等 于 所有 結 點 的 入 度 之 和 ， 所 有 結 點 的 度 數(shù) 的 總 和 等 于 邊 數(shù)的 兩 倍 ， 即 ： 。m2)v(deg)v(deg)vdeg( VvVvVv 定 理 定 理 在 圖 G 中 ， 其 V v1,v2,v3,vn， Ee1， e2， ， em， 度 數(shù) 為 奇 數(shù) 的 結 點 個 數(shù) 為 偶 數(shù) 。證 明 設 V1 v|vV且 deg(v) 奇 數(shù) ， V2 v|vV且deg(v) 偶 數(shù) 。 顯 然 ， V1V2 ， 且 V1 V2 V， 于 是有 ： 。m2)vdeg()vd

9、eg()vdeg( 21 VvVvVv 由 于 上 式 中 的 2m和 偶 度 數(shù) 結 點 度 數(shù) 之 和 均 為 偶 數(shù) ， 因 而奇 數(shù) 的 結 點 個 數(shù) 也 為 偶 數(shù) 。 于 是 |V1|為 偶 數(shù) (因 為 V1中 的結 點 v之 deg(v)都 為 奇 數(shù) )， 即 奇 度 數(shù) 的 結 點 個 數(shù) 為 偶 數(shù) 。 三 、 完 全 圖定 義 在 圖 G 中 ， 若 所 有 結 點 的 度 數(shù) 均 有 相同 度 數(shù) d， 則 稱 此 圖 為 d次 正 則 圖 。定 義 一 個 ( n ， m ) ( n 2 ) 的 簡 單 無 向 圖 ， 若 它為 n-1次 正 則 圖 ， 則 稱

10、該 (n， m)圖 為 無 向 簡 單完 全 圖 ， 簡 稱 完 全 圖 ,記 為 K n。有 向 完 全 圖定 理 設 無 向 完 全 圖 G 有 n個 頂 點 ， 則 G 有 n(n-1)/2條 邊 。 例 ：例 ： 如 圖 (a)、 (b)、 (c)、 (d)所 示 ， 它 們 分 別 是 無 向 的 簡單 完 全 圖 K 3， K 4， K 5和 有 向 的 簡 單 完 全 圖 K 3。 定 義 設 有 圖 G 和 圖 G 1 ， 若 G 和G 1滿 足 ： 若 V1V， E1E， 則 稱 G 1是 G 的 子 圖 ， 記 為 G 1G ； 若 G 1G ， 且 G 1G (即 V1V

11、或 E1E)， 則 稱 G 1是 G 的 真子 圖 ， 記 為 G 1G ；定 義 若 V1 V， E1E， 則 稱 G 1是 G 的 生 成 子 圖 ；定 義 若 V2V， V2， 以 V2為 結 點 集 ， 以 兩 個 端 點 均在 V 2中 的 邊 的 全 體 為 邊 集 的 G 的 子 圖 稱 為 V2導 出 的子 圖 ， 簡 稱 G 的 導 出 子 圖 。 四 、 子 圖 例 ：例 ： 在 下 圖 中 ， 給 出 了 圖 G 以 及 它 的 真 子 圖 G 和 生 成 子 圖G 。 G 是 結 點 集 v1， v2， v4， v5， v6的 導 出 子 圖 。 定 義 設 G 為 具

12、 有 n個 結 點 的 簡 單 圖 ,從 完全 圖 K n中 刪 去 G 中 的 所 有 的 邊 而 得 到 的 圖 稱 為 G 的補 圖 (或 G 的 補 )， 記 為 。定 義 是 圖 ， 是 的 子 圖 ， ” ， ” 是 ” 中 邊 所 關聯(lián) 的 所 有 頂 點 集 合 ， 則 ” 稱 為 關 于 的 相 對 補 圖 。關 于 完 全 圖 的 子 圖 的 補 圖 稱 為 此 子 圖 的 絕 對補 圖 。 五 、 補 圖G 例 ：例 ： 在 下 圖 (a)、 (b)、 (c)、 (d)中 ， (a)與 (b)是 互 為 補 圖 ； (c)和 (d)是 互 為 補 圖 。 六 、 圖 的

13、同 構例 :如 下 圖 所 示 ， 圖 (a)、 圖 (b)、 圖 (c)和 圖 (d)所表 示 的 圖 形 實 際 上 都 是 一 樣 的 。 定 義 定 義 設 有 圖 G 和 圖 G 1 ,如 果 存 在 雙射 函 數(shù) g:VV1,使 得 對 于 任 意 的 邊 e (vi,vj)E(或E)當 且 僅 當 e1 (g(vi),g(vj)E1(或 E1) 則 稱 G 和 G 1同 構 ， 記 為 G G 1。同 構 的 充 要 條 件 ： 兩 個 圖 的 結 點 和 邊 分 別 存 在 一 一 對 應 ，且 保 持 關 聯(lián) 關 系 。 例 ：例 ： 如 圖 (a)、 (b)所 示 的 兩 個 圖 G 和 G 1 ，證 明 G G 1。解 ： 定 義 函 數(shù) g:VV 1， 滿 足 g(vi) vi(i 1， 2， 3， 4， 5)，可 以 驗 證 g是 一 個 滿 足 定 義 的 雙 射 ， 所 以 G G 1。 必 要 條 件兩 個 圖 同 構 的 必 要 條 件 ：結 點 數(shù) 目 相 同 ；邊 數(shù) 相 同 ；度 數(shù) 相 同 的 結 點 數(shù) 相 同 。注 意 ： 這 三 個 條 件 并 不 是 充 分 條 件 。 例 如 下 面 兩 個 圖 滿足 這 三 個 條 件 ， 但 它 們 不 同 構 。