【正文】 圖 。 對(duì)于有向圖而言 ， 結(jié)點(diǎn)間的可達(dá)性不再是等價(jià)關(guān)系 ， 它僅僅是自反的和傳遞的 。于是 ， 對(duì)于分離圖 G， ?(G)=0；對(duì)于存在割點(diǎn)的連通圖 G， ?(G)=1。 在圖的研究中 ， 常常需要考慮刪去與增加結(jié)點(diǎn) 、結(jié)點(diǎn)集 、 邊和邊集 （ 或弧集 ） 的問(wèn)題 。 定理 在一個(gè)圖中 ， 若從結(jié)點(diǎn) vi到結(jié)點(diǎn) vj存在一條鏈 (或路 )， 則必有一條從 vi到 vj的基本鏈 (或基本路 )。 定義 給定無(wú)向圖 (或有向圖 )G=V， E。 一般說(shuō)來(lái) ， 證明兩個(gè)圖是同構(gòu)的并非是輕而易舉的事情 ， 往往需要花些氣力 。 在圖的定義中 ， 強(qiáng)調(diào)的是結(jié)點(diǎn)集 、 邊集以及邊與結(jié)點(diǎn)的關(guān)聯(lián)關(guān)系 ， 既沒(méi)有涉及到聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)的邊的長(zhǎng)度 、 形狀和位置 ， 也沒(méi)有給出結(jié)點(diǎn)的位置或者規(guī)定任何次序 。 (2) 如果 V2?V1， E2?E1且 E2≠E1， 則稱 G2為 G1的真子圖 ， 記為 G2?G1。 若 v點(diǎn)有環(huán) ， 規(guī)定該點(diǎn)度因環(huán)而增加 2。 定義 在無(wú)向圖 G=V， E中 ， 如果 V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接 ， 即 (?vi)(?vj)(vi， vj∈ V→ 〔 vi， vj〕 ∈ E) 則該圖稱為無(wú)向完全圖 ， 記作 K|V|。關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊或弧稱為鄰接邊或弧。第十六章 圖的概念與表示 圖的基本概念 鏈 (或路 )與圈 (或回路 ) 圖的矩陣表示 退出 圖的基本概念 什么是圖 ?可用一句話概括 ， 即：圖是用點(diǎn)和線來(lái)刻劃離散事物集合中的每對(duì)事物間以某種方式相聯(lián)系的數(shù)學(xué)模型 。 若結(jié)點(diǎn) vi與 vj由一條邊 (或弧 )e所聯(lián)結(jié)，則稱結(jié)點(diǎn) vi和 vj是邊 (或弧 )e的端結(jié)點(diǎn)；同時(shí)也稱結(jié)點(diǎn)vi與 vj是鄰接結(jié)點(diǎn)，記作 vi adj vj；否則為非鄰接結(jié)點(diǎn)，記作 vi nadj vj；也說(shuō)邊 (或弧 )e關(guān)聯(lián) vi與 vj或說(shuō)結(jié)點(diǎn) vi與 vj關(guān)聯(lián)邊 (或弧 )e。 加權(quán)圖在實(shí)際中有許多應(yīng)用 ， 如在輸油管系統(tǒng)圖中權(quán)表示單位時(shí)間流經(jīng)管中的石油數(shù)量；在城市街道中 ，權(quán)表示表示通行車輛密度；在航空交通圖中 ， 權(quán)表示兩城市的距離等等 。 對(duì)于無(wú)向圖 G=V， E， 結(jié)點(diǎn) v∈ V的度數(shù)等于聯(lián)結(jié)它的邊數(shù) ， 也記為 d(v)。 定義 給定無(wú)向圖 G1=V1， E1和 G2=V2，E2， 于是 (1) 如果 V2?V1和 E2?E1， 則稱 G2為 G1的子圖 ， 記為 G2?G1。 顯然 ， G與 互為補(bǔ)圖 。對(duì)于有向圖的同構(gòu)還要求保持邊的方向 。 例如圖 (a)與 (b) 圖 返回 返回 圖 鏈 (或路 )與圈 (或回路 ) 在無(wú)向圖 (或有向圖 )的研究中 ， 常?？紤]從一個(gè)結(jié)點(diǎn)出發(fā) ， 沿著一些邊 (或弧 )連續(xù)移動(dòng)而達(dá)到另一個(gè)指定結(jié)點(diǎn) ， 這種依次由結(jié)點(diǎn)和邊 (或弧 )組成的序列 ， 便形成了鏈 (或路 )的概念 。 可以看出，對(duì)于簡(jiǎn)單圖來(lái)說(shuō)，鏈 (或路 )和圈 (或回路 )能夠僅用結(jié)點(diǎn)序列表示之。 定義 若圖 G只有一個(gè)連通分圖，則稱 G是連通圖；否則，稱圖 G為非連通圖或分離圖。 對(duì)于連通的非平凡圖 G， 稱 ?(G)= {|S||S是 G的分離結(jié)點(diǎn)集 }為圖 G的結(jié)點(diǎn)連通度 ， 它表明產(chǎn)生不連通圖而需要?jiǎng)h去結(jié)點(diǎn)的最少數(shù)目 。 定理 連通無(wú)向圖 G中的一條邊 e是割邊 ?e不包含在圖的任何基本圈中 。 令 G是簡(jiǎn)單有向圖 ， 對(duì)于某種性質(zhì)而言 ， 若 G中再?zèng)]有其它包含子圖 G1的真子圖具有這種性質(zhì) ， 則稱 G1是G的關(guān)于該性質(zhì)的極大子圖 。 距離滿足下列性質(zhì)： du， v≥0 du， u=0 du， v+dv， w≥du， w 如果 u不可達(dá) v，則 du， v=+∞。如程序 A控制著資源 r1，請(qǐng)求資源 r2；但程序 B控制著資源r2，請(qǐng)求資源 r1。把每個(gè)資源 ri看作圖中一個(gè)結(jié)點(diǎn)，其中 i=1， 2， … ， n。 一個(gè)簡(jiǎn)單圖 G=V， E由 V中每?jī)蓚€(gè)結(jié)點(diǎn)間的鄰接關(guān)系唯一地確定，這種關(guān)系可以用一個(gè)矩陣給出，而矩陣形式與圖中結(jié)點(diǎn)的編序有密切關(guān)系，這是用矩陣表示圖值得注意的一點(diǎn)。若第 i行第 j列上的元素 alij便是 G中從第i個(gè)結(jié)點(diǎn) vi到第 j個(gè)結(jié)點(diǎn) vj長(zhǎng)度為 l的鏈（或路）的數(shù)目。 顯然鄰接矩陣是一個(gè)布爾矩陣 ， 同樣可達(dá)矩陣也是布爾矩陣 。,m； j=1,2,∪ Rk (k≤n) 于是，關(guān)系 R1和 R2的關(guān)系矩陣分別為 A1和A2，則關(guān)系 R1∪ R2的關(guān)系矩陣為 A1?A2。?A(n)=P 可見，關(guān)系 E的傳遞閉包 E+的關(guān)系矩陣 A+與可達(dá)矩陣相同。,n作 pij?pij?pkj (5) i?i+1，若 i≤n則轉(zhuǎn) (4) (6) k?k+1，若 k≤n則轉(zhuǎn)到 (3)，否則停止。,pn}是程序 P中的過(guò)程集合 ，做有向圖 G=VP,E， 其中 pi?VP， i=1,2, 已知加權(quán)的簡(jiǎn)單圖 G=V,E，定義一個(gè)矩陣 W=(wij)，其中： w, w是邊 [vi,vj]（或弧 vi,vj） ?E 的權(quán) wij= 0， vi與 vj不相鄰 則稱 W為圖 G的權(quán)矩陣 {