圖與網(wǎng)絡(luò)1(參考版)
2024-10-06 17:10本頁面
【正文】 用廣探法確定（奇數(shù)次）過河方案。 例 99： 一個人帶領(lǐng)一條狗、一只羊和一筐菜過河，河中有一條小船，只能乘一個人和一樣?xùn)|西，而如果人不在場時，狗要咬羊，羊要吃菜，設(shè)想一種過河方案。 二、 DFS和 BFS法 DFS（ Depth First Search） 深度優(yōu)先法或深探法。 如果 n=3k（ k正整數(shù)），假定先取者拿走 a根（ a=1或 2），則后者只要取走b 根，（滿足 a+b=3），使余下火柴為3（ k1）根，那么先取者必敗。 這樣從樹葉開始逐層向上，就可以算術(shù)出甲方勝負(fù)情況。 若甲方勝時得分 +1，乙方勝時甲方得分 1，無凝輪到甲方取時一定選擇能使他進(jìn)入得分 +1狀態(tài)。顯然，一旦最后出現(xiàn)方框（ 1或 2）狀態(tài)時乙方勝。為了便于理解，不妨假設(shè) n=7。 求最小樹的方法有 破圈法 和 避圈法 。 定義（最優(yōu)樹） 在賦權(quán)圖 G中，一棵生成樹所有樹柱上權(quán)的和，稱為生成樹的權(quán)。 一個子圖與生成樹的區(qū)別是：子圖與原圖相比少弧又少點，生成樹與原圖相比少弧不少點。 4 圖中邊數(shù)有 ne=p1（ p為頂點數(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 定義（生成樹） 如果圖 T是 G的一個生成子圖，而且 T又是一棵樹，則稱圖 T為一棵生成樹。 2 在圖中劃去一條邊，則圖不連通。如果一個無圈的圖中每一個分支都是樹，則稱圖為森林。 定義（連通圖） 如果圖中的任意兩點之間至少存在一條通路，則稱圖為連通圖，否則為不連通圖。 定義（鏈） 如果圖中的某些點、邊可以排列成點和邊的交錯序列，則稱此為一條鏈。 1 （ vi， vk） =ej Bij= 1 （ vk， vi） =ej 0 其他 v1 v2 v4 v3 e1 e2 e4 e3 e7 e5 e6 e1 e2 e3 e4 e5 e6 e7 v1 1 1 1 0 0 0 0 v2 0 0 1 1 1 0 0 v3 0 1 0 1 0 1 1 v4 1 0 0 0 1 1 1 對無向圖不存在 1 元素 。其中 ?表示兩點之間沒有 弧 連接 。 v1 v2 v3 v4 2 5 6 4 3 4 v1 v2 v3 v4 v1 0 2 5 6 v2 2 4 3 ? v3 5 3 0 4 v4 6 ? 4 0 其中 ?表示兩點之間不能連接 。 v1 v5 v4 v3 v2 也可以對有向圖 v1 v2 v3 v4 v5 v1 0 0 0 1 1 v2 1
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1