圖與網(wǎng)絡(luò)1-wenkub.com
2024-10-02 17:10 本頁面
【正文】 解： 用 m、 a、 b、 c表示人、狗、羊和菜。如果 n不等于 3k，則先取者取 a根，使 na=3k，那么先取者必勝。同理輪到乙方取時一定選擇能使甲方進入得分 1狀態(tài)。 7 5 4 4 3 3 1 2 2 2 1 1 2 6 5 1 2 2 2 3 4 1 2 3 3 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 1 +1 +1 +1 1 1 1 1 1 1 1 1 1 在樹形圖中，圓圈中數(shù)字 7表示輪到甲方取時還有 7根，方框中數(shù)字 6表示表示輪到乙方取時還有 6根，依次類推。具有最小權(quán)的生成樹，稱為最優(yōu)樹（或最小樹）。對于分離圖，則稱為生成森林。 樹的性質(zhì)： 1 在圖中任意兩點之間必有一條而且只有一條通路。 定義（圈） 如一條鏈中起點和終點重合，則稱此為一條圈。 v1 v5 v4 v3 v2 1 4 2 3 2 2 6 1 2 v1 v2 v3 v4 v5 v1 0 1 ? ? 2 v2 ? 0 2 ? 4 v3 ? 2 0 1 ? v4 ? 3 2 0 6 v5 ? ? ? ? 0 4 關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣 B揭示了圖 G的頂點和邊之間的關(guān)聯(lián)關(guān)系，它是一個nxm矩陣。 無向網(wǎng)絡(luò)；有向網(wǎng)絡(luò)；混合網(wǎng)絡(luò)；邊權(quán)網(wǎng)絡(luò)；點權(quán)網(wǎng)絡(luò)； 以邊長代替鄰接矩陣中的元素得到邊長鄰接矩陣。 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 有向圖 v1 v5 v4 v2 e1 e7 e6 e3 v1 v5 v4 v2 e1 e7 e6 e3 圈 二、圖的矩陣表示 一個圖非常直觀，但是不容易計算，特別不容易在計算機上進行計算，一個有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長鄰接矩陣、弧長矩陣和關(guān)聯(lián)矩陣。 v1 v5 v4 v2 v3 e1 e8 e7 e6 e5 e4 e3 e2 v1 v5 v4 v2 e1 e5 e3 （ a）的子圖 v1 v5 v4 v2 v3 e8 e6 e5 e2 （ a）的生成子圖 v1 v5 v2 e1 e6 e5 （ a）的導出子圖 定義（簡單圖）如果圖中任意兩個頂點之間至多有一條邊，則稱為簡單圖，否則稱為多重圖。 注意：一個圖的形狀并不唯一。 說明： （ 1） V非空，即沒有頂點的圖不討論； （ 2） E無非空條件，即允許沒有邊； （ 3）條件（ 2）是指點只在邊的端點 處相交； （ 4）任一條邊必須與一對頂點關(guān)聯(lián)， 反之不然。 A F E D C B A F E D C B A F E D C B 圖的基本概念 圖論是專門研究圖的理論的一門數(shù)學分支，主要研究點和線之間的 幾何關(guān)系。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 假定第三次就座方案是 （ 1， 4， 7， 3， 6， 2， 5， 1） ，那么第
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1