離散數(shù)學(xué)》第6章圖的基本概念-文庫(kù)吧
2025-01-01 20:35 本頁(yè)面
【正文】 v d v為 的 度數(shù)序列 。 G握手定理。 定理 1： 設(shè)圖 為無(wú)向圖或有向圖， ,G V E?? ?11, , , nV v v v? Em? 為邊數(shù) )， m， ( 則 1( ) 2niid v m???定理 2： 設(shè) 為有向圖， ,D V E?? ?11, , , nV v v v? Em? ，則 ， 11( ) ( )nniiiid v d v m????????。 推論： 任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。 例 2（ 1） （ 2， 3， 4， 5， 6， 7） ， （ 1， 2，2， 3， 4） 能否構(gòu)成無(wú)向圖的度數(shù)序列 ？ 為什么 ？ 如能則畫(huà)出圖解 （ 2） 已知圖 中有 11條邊 ， 有 1個(gè) 4度頂點(diǎn) ， 4個(gè)3度頂點(diǎn) ， 其余頂點(diǎn)的度數(shù)均小于等于 2， 問(wèn)中至少有幾個(gè)頂點(diǎn) ？ GG三、子圖，補(bǔ)圖。 子圖定義： 設(shè) 是兩個(gè)圖，若 ,G V E? 39。 39。, 39。G V E?， 39。VV? ，且 39。EE? ，則稱 39。G是 的 子圖 ， G G 是 的 母圖 ，記作 39。GG?39。G 。 真子圖 —— 且 (即 或 39。GG? 39。GG? 39。VV?39。EE? )。 生成子圖 —— 且 39。GG? 39。VV? 。 導(dǎo)出子圖 —— 非空 ，以 為頂點(diǎn)集， 39。VV? 39。V以兩端均在 中的邊的全體為邊集的 39。V G 的 子圖，稱 的導(dǎo)出子圖。 39。V—— 非空 39。EE? ，以 39。E 為邊集，以 中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的 39。E G 的子 圖，稱 的導(dǎo)出子圖。 39。E例 ( 1 ) ( 2 ) (3 )( 4 ) ( 5) ( 6 )上圖中， (1)－ (6)都是 (1)的子圖， 其中 (2)－ (6)為真子圖， (1)－ (5)為生成子圖。 補(bǔ)圖定義 。 設(shè) 為無(wú)向完全圖， 11,G V E?,G V E?， 22,G V E?為無(wú)向簡(jiǎn)單圖，其中 12EE ??， 12E E E?，則稱 1G 2G， 相對(duì)于 G 互為補(bǔ)圖， 記 12GG? 21GG?， 。 ( 1 ) ( 2 ) (3 )( 4 ) ( 5) ( 6 )如例 3中， 四、圖的同構(gòu)。 定義 ： 設(shè)兩個(gè)無(wú)向圖 1 1 1,G V E?， 2 2 2,G V E?， 若存在雙射函數(shù) 12: VV? ?，使得對(duì)于任意的 1( , )ije v v E??，當(dāng)且僅當(dāng) ? ?239。 ( ) , ( )ije v v E????并且 與 重?cái)?shù)相同，則稱 e 39。e 與 同構(gòu) ， 1G 2G記作 12GG≌。 例 ( 1 ) ( 2 ) ( 3 ) ( 4 )( 5) ( 6 ) ( 7 )1v2v3v4v5v5v1v2v3v4v6vecacaefbddb例 (1) 畫(huà)出 4個(gè)頂點(diǎn)， 3條邊的所有非同構(gòu) 的無(wú)向簡(jiǎn)單圖。 解： 只有如下 3個(gè)圖： (1 .1) (1 .2 ) ( )例 (2) 畫(huà)出 3個(gè)頂點(diǎn)， 2條邊的所有非同構(gòu) 的有向簡(jiǎn)單圖。 解： 只有如下 4個(gè)圖： 內(nèi)容： 圖的通路，回路，連通性，點(diǎn)割集，邊割集。 重點(diǎn)： 通路，回路，簡(jiǎn)單通路，回路， 初級(jí)通路，回路的定義， 圖的連通性的概念， 短程線，距離的概念。 第二節(jié) 通路，回路，圖的連通性 一、通路，回路。 通路 (回路 ) 中頂點(diǎn)和邊的交替序列 —— G0 1 1 2 llv e v e e v??，其中 1( , )i i ie v v??(無(wú)向圖 )， 或 1 ,i i ie v v??(有向圖 )， —— 始點(diǎn) ， 0v—— 終點(diǎn) ，稱 為 到 lv? 0v lv 的 通路 。當(dāng) 0 lvv?時(shí)， 為 回路 。 ?簡(jiǎn)單通路，簡(jiǎn)單回路。 簡(jiǎn)單通路 (跡 ) 簡(jiǎn)單回路 (閉跡 ) 復(fù)雜通路 (回路 ) 初級(jí)通路，初級(jí)回路。 初級(jí)通路 (路徑 ) 初級(jí)回路 (圈 ) 初級(jí)通路 (回路 ) 簡(jiǎn)單通路 (回路 )， ?但反之不真。 通路，回路 的長(zhǎng)度 —— 中邊的數(shù)目。 ? ?例 (1) 圖 (1)中，從 的通路有： 到 1v 6v1 1 1 2 5 5 7 6v e v e v e v??2 1 1 2 2 3 3 4 4 2 5 5 7 6v e v e v e v e v e v e v??3 1 1 2 5 5 6 4 4 2 5 5 7 6v e v e v e v e v e v e v??………… 長(zhǎng)度 3 長(zhǎng)度 6 長(zhǎng)度 6 初級(jí)通路 簡(jiǎn)單通路 復(fù)雜通路 (2) 1 2 4 4 3 3 2 2v e v e v e v??2 2 5 5 6 4 3 3 2 2v e v e v e v e v??3 2 4 4 3 3 2 2 5 5 6 4 3 3 2 2v e v e v e v e v e v e v e v??………… 長(zhǎng)度 3 長(zhǎng)度 4 長(zhǎng)度 7 圖 (2)中過(guò) )有： 的回路 (從 2v 2v到 2v初級(jí)回路 (圈 ) 初級(jí)回路 (圈 ) 復(fù)雜回路 圖中最短的回路。 如圖
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1