《離散數(shù)學(xué)圖論》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)圖論（22頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

7、 deg(v)為 偶 數(shù) ，則 稱 此 結(jié) 點(diǎn) 為 偶 度 數(shù) 結(jié) 點(diǎn) 。 二 、 度 數(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.在 無(wú) 向 圖 G 中 ， 所 有 結(jié) 點(diǎn) 的 度 數(shù) 的 總 和 等 于邊 數(shù) 的 兩 倍 ， 即 ： ；m2)vdeg(Vv ，m)v(deg)v(d

8、eg VvVv 在 有 向 圖 G 中 ， 所 有 結(jié) 點(diǎn) 的 出 度 之 和 等 于 所有 結(jié) 點(diǎn) 的 入 度 之 和 ， 所 有 結(jié) 點(diǎn) 的 度 數(shù) 的 總 和 等 于 邊 數(shù)的 兩 倍 ， 即 ： 。m2)v(deg)v(deg)vdeg( VvVvVv 定 理 定 理 在 圖 G 中 ， 其 V v1,v2,v3,vn， Ee1， e2， ， em， 度 數(shù) 為 奇 數(shù) 的 結(jié) 點(diǎn) 個(gè) 數(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ù) 結(jié) 點(diǎn) 度 數(shù) 之 和 均 為 偶 數(shù) ， 因 而奇 數(shù) 的 結(jié) 點(diǎn) 個(gè) 數(shù) 也 為 偶 數(shù) 。 于 是 |V1|為 偶 數(shù) (因 為 V1中 的結(jié) 點(diǎn) v之 deg(v)都 為 奇 數(shù) )， 即 奇 度 數(shù) 的 結(jié) 點(diǎn) 個(gè) 數(shù) 為 偶 數(shù) 。 三 、 完 全 圖定 義 在 圖 G 中 ， 若 所 有 結(jié) 點(diǎn) 的 度 數(shù) 均 有 相同 度 數(shù) d， 則 稱 此 圖 為 d次 正 則 圖 。定 義 一 個(gè) ( n ， m ) ( n 2 ) 的 簡(jiǎn) 單 無(wú) 向 圖 ， 若 它為 n-1次 正 則 圖 ， 則 稱

10、該 (n， m)圖 為 無(wú) 向 簡(jiǎn) 單完 全 圖 ， 簡(jiǎn) 稱 完 全 圖 ,記 為 K n。有 向 完 全 圖定 理 設(shè) 無(wú) 向 完 全 圖 G 有 n個(gè) 頂 點(diǎn) ， 則 G 有 n(n-1)/2條 邊 。 例 ：例 ： 如 圖 (a)、 (b)、 (c)、 (d)所 示 ， 它 們 分 別 是 無(wú) 向 的 簡(jiǎn)單 完 全 圖 K 3， K 4， K 5和 有 向 的 簡(jiǎn) 單 完 全 圖 K 3。 定 義 設(shè) 有 圖 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為 結(jié) 點(diǎn) 集 ， 以 兩 個(gè) 端 點(diǎn) 均在 V 2中 的 邊 的 全 體 為 邊 集 的 G 的 子 圖 稱 為 V2導(dǎo) 出 的子 圖 ， 簡(jiǎn) 稱 G 的 導(dǎo) 出 子 圖 。 四 、 子 圖 例 ：例 ： 在 下 圖 中 ， 給 出 了 圖 G 以 及 它 的 真 子 圖 G 和 生 成 子 圖G 。 G 是 結(jié) 點(diǎn) 集 v1， v2， v4， v5， v6的 導(dǎo) 出 子 圖 。 定 義 設(shè) G 為 具

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

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