圖與網(wǎng)絡(luò)（1）(文件)
【正文】 1 1 0 0 v3 0 1 0 1 0 1 1 v4 1 0 0 0 1 1 1 對(duì)無(wú)向圖不存在 1 元素 。 定義（連通圖） 如果圖中的任意兩點(diǎn)之間至少存在一條通路，則稱圖為連通圖，否則為不連通圖。 2 在圖中劃去一條邊，則圖不連通。 一個(gè)子圖與生成樹(shù)的區(qū)別是：子圖與原圖相比少弧又少點(diǎn)，生成樹(shù)與原圖相比少弧不少點(diǎn)。 求最小樹(shù)的方法有 破圈法 和 避圈法 。顯然，一旦最后出現(xiàn)方框（ 1或 2）狀態(tài)時(shí)乙方勝。 這樣從樹(shù)葉開(kāi)始逐層向上，就可以算術(shù)出甲方勝負(fù)情況。 二、 DFS和 BFS法 DFS（ Depth First Search） 深度優(yōu)先法或深探法。用廣探法確定（奇數(shù)次）過(guò)河方案。 例 99： 一個(gè)人帶領(lǐng)一條狗、一只羊和一筐菜過(guò)河，河中有一條小船，只能乘一個(gè)人和一樣?xùn)|西，而如果人不在場(chǎng)時(shí)，狗要咬羊，羊要吃菜，設(shè)想一種過(guò)河方案。 如果 n=3k（ k正整數(shù)），假定先取者拿走 a根（ a=1或 2），則后者只要取走b 根，（滿足 a+b=3），使余下火柴為3（ k1）根，那么先取者必?cái) ? 若甲方勝時(shí)得分 +1，乙方勝時(shí)甲方得分 1，無(wú)凝輪到甲方取時(shí)一定選擇能使他進(jìn)入得分 +1狀態(tài)。為了便于理解，不妨假設(shè) n=7。 定義（最優(yōu)樹(shù)） 在賦權(quán)圖 G中，一棵生成樹(shù)所有樹(shù)柱上權(quán)的和，稱為生成樹(shù)的權(quán)。 4 圖中邊數(shù)有 ne=p1（ p為頂點(diǎn)數(shù)） a b c f e d h g 例 96 b f e d b f d g b c e d a b c h a f d g 定義（生成樹(shù)） 如果圖 T是 G的一個(gè)生成子圖，而且 T又是一棵樹(shù)，則稱圖 T為一棵生成樹(shù)。如果一個(gè)無(wú)圈的圖中每一個(gè)分支都是樹(shù)，則稱圖為森林。 定義（鏈） 如果圖中的某些點(diǎn)、邊可以排列成點(diǎn)和邊的交錯(cuò)序列，則稱此為一條鏈。其中 ?表示兩點(diǎn)之間沒(méi)有 弧 連接 。 v1 v5 v4 v3 v2 也可以對(duì)有向圖 v1 v2 v3 v4 v5 v1 0 0 0 1 1 v2 1 0 0 1 0 v3 0 1 1 0 0 v4 0 1 1 0 1 v5 1 0 0 1 0 二、邊長(zhǎng)鄰接矩陣 在圖的各邊上一個(gè)數(shù)量指標(biāo)，具體表示這條邊的權(quán)（距離，單價(jià)，通過(guò)能力等） —— 賦權(quán)圖或網(wǎng)絡(luò)。 定義（圈）如一條鏈中起點(diǎn)和終點(diǎn)重合，則稱此為一條圈。 如果 V1? V， E1 ? E則稱 G1為 G的子圖； 如果 G1=（ V1， E1， ?1）是 G=（ V， E， ?） 子圖，并且 V1= V，則稱 G1為 G的生成子圖； 如果 V1? V， E1 是 E中所有端點(diǎn)屬于 V1的邊組成的集合， 則稱G1是 G的關(guān)于 V1的導(dǎo)出子圖； 如果 G1=（ V1， E1， ?1）是 G=（ V， E， ?） 子圖，并且 V1= V，則稱 G1為 G的生成子圖。 定理 92：在任意一個(gè)圖中，奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。 V， E，
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1