第1章 圖和子圖

《第1章 圖和子圖》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、圖論及其應(yīng)用1圖的基本概念2樹3連通度4遍歷問題5匹配6著色問題7平面圖8有向圖9網(wǎng)絡(luò)10NP-完全問題第一章圖的基本概念1.1圖的概念1.2同構(gòu)1.3圖的矩陣和頂點(diǎn)的度1.4子圖1.5路和連通性1.6圈1.7最短路問題1.1圖的概念K?nigsberg七橋問題電網(wǎng)絡(luò)四色猜想圖G=(V(G),E(G))，其中V(G)={}V---頂點(diǎn)集，---頂點(diǎn)數(shù)E(G)={}E---邊集，ε---邊數(shù)例如，下圖中，V={a,b,…,f},E={k,p,q,ae,af,…,ce,cf}defG=(V,E)pqabck注意，右圖僅僅是圖G的一個幾何實(shí)現(xiàn)（geometri

2、crealization,代表representation），它們有無窮多個，隨頂點(diǎn)位置及邊的形狀而不同。真正的圖G是上面所給出式子，它與頂點(diǎn)的位置、邊的形狀等無關(guān)。不過今后對圖G及其幾何實(shí)現(xiàn)將經(jīng)常不加以區(qū)別。defG=(V,E)pqabck稱邊ad與頂點(diǎn)a(及d)相關(guān)聯(lián)(incident)。也稱頂點(diǎn)b(及f)與邊bf相關(guān)聯(lián)。稱頂點(diǎn)a與e相鄰(adjacent)。也稱有公共端點(diǎn)的一些邊，例如p與af彼此相鄰。稱一條邊的兩個頂點(diǎn)為它的兩個端點(diǎn)環(huán)（loop，selfloop）：如邊k，它的兩個端點(diǎn)相同。棱（link）：如邊ae，它的兩個端點(diǎn)不相同。重邊：如邊

3、p及邊q。簡單圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個頂點(diǎn)的圖。注意：任何一圖都有V??。記號：（?,?）defG=(V,E)pqabck例題1.1若G為簡單圖，則。1.2若一群人中，凡相識的兩人都無公共朋友，凡不相識的兩人都恰有兩個公共朋友，則每人的朋友數(shù)相等。1.2同構(gòu)例如在下圖中，稱圖G恒等于圖H(記為G=H)?VG)=V(H),E(G)=E(H)。ayzxwbcdeG=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)xwbcdeayzH=(V,E)圖G同構(gòu)于圖F（記為GF）?V(G)與V(F),E(G)與E(F)

4、之間各存在一一映射，及且這二映射保持關(guān)聯(lián)關(guān)系，即：ayzxwbcdeG=(V,E)xwbcdeayzH=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)注兩個圖同構(gòu)是指”它們有相同的結(jié)構(gòu)”，僅在頂點(diǎn)及邊的標(biāo)號上或兩個圖的畫法上有所不同而已。往往將同構(gòu)慨念引伸到非標(biāo)號圖中，以表達(dá)兩個圖在結(jié)構(gòu)上是否相同。注判定兩個圖是否同構(gòu)是個未解決的困難問題（openproblem）。ayzxwbcdeG=(V,E)xwbcdeayzH=(V,E)x’d’w’a’b’c’y’e’z’F=(V’,E’)完全圖(completegraph)Kn空圖（empty

5、g.）?E=?。V’(?V)為獨(dú)立集?V’中任二頂點(diǎn)都互不相鄰。二部圖（偶圖，bipartiteg.）G=(X,Y;E)?存在V(G)的一個2-劃分(X,Y)（即V(G)=X∪Y，且X∩Y=?），使X與Y都是獨(dú)立集。K1K2K3K4K5完全二部圖Km,n?二部圖G=(X,Y;E)，其中X和Y之間的每對頂點(diǎn)都相鄰，且?X?=m,?Y?=n。類似地可定義，完全三部圖（例如，Km,n,p），完全n-部圖等。二部圖K3,3K1,5K2,2,2例。用標(biāo)號法判定二部圖。用紅藍(lán)兩種顏色進(jìn)行頂點(diǎn)標(biāo)號如下：任取一頂點(diǎn)v標(biāo)以紅色。再將v的所有相鄰頂點(diǎn)都標(biāo)以蘭色。這時稱v為已

6、掃描頂點(diǎn)。若尚存在一已標(biāo)號未掃描頂點(diǎn)u，將它的所有相鄰頂點(diǎn)，（若不出現(xiàn)矛盾）都標(biāo)以（其相異色）紅色，并稱u為已掃描頂點(diǎn)。如此繼續(xù)下去，直到或者所有頂點(diǎn)都已標(biāo)號，從而該圖為一二部圖；或者在標(biāo)號過程中出現(xiàn)矛盾，該圖為非二部圖。習(xí)題1.2.1G?H??(G)=?(H),?(G)=?(H)。并證明其逆命題不成立。1..2.2證明下面兩個圖不同構(gòu)：1.2.3證明下面圖1與圖2是同構(gòu)的；而圖1與圖3是不同構(gòu)的：1.2.4證明兩個簡單圖G和H同構(gòu)?存在一一映射f:V(G)?V(H)，使得uv?E(G)當(dāng)且僅當(dāng)f(u)f(v)?E(H)。圖1圖2圖31.2.5證明：(a

7、).?(Km,n)=mn;(b).對簡單二部圖有???2/4.1.2.6記Tm,n為這樣的一個完全m-部圖：其頂點(diǎn)數(shù)為n，每個部分的頂點(diǎn)數(shù)為[n/m]或{n/m}個。證明：(a).?(Tm,n)=其中k=[n/m].(b)*.對任意的n頂點(diǎn)完全m-部圖G，一定有?(G)??(Tm,n)，且僅當(dāng)G?Tm,n時等式才成立。1.2.7所謂k-方體是這樣的圖：其頂點(diǎn)是由0與1組成的有序k-元組，其二頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們恰有一個坐標(biāo)不同。證明k-方體有2k個頂點(diǎn)，k*2k-1條邊，且是一偶圖。1.2.8簡單圖G的補(bǔ)圖Gc是指和G有相同頂點(diǎn)集V的一個簡單圖，在Gc中

8、兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們在G中不相鄰。(a).畫出Kcn和Kcm,n。(b).如