1 離散數(shù)學(xué)作業(yè) 4 圖的矩陣表示及計(jì)算 作業(yè) 作業(yè)內(nèi)容 ： 1 已知圖 G 如下圖所示 （ 1） 試給出圖 G 的 集合 表示 ； （ 2） 求圖 G 的鄰接矩陣 A； （ 3） 利用 矩陣 A 及其冪，求出 從 結(jié)點(diǎn) v1 到 v5 長(zhǎng)度為 2 和 3 的路 的數(shù)目并寫(xiě)出這些路 解：（ 1） 設(shè) G=， V= v1， v2， v3， v4， v5， v6， E= (v1,v2)， (v1,v6)， (v2,v3)， (v2,v5)，(v2,v6)， (v3,v4)， (v3,v5)， (v4,v5) ， (v5,v6) (2) 圖 G 的 鄰接矩陣 A=010101010011110100011010110101100010(3) 從 結(jié)點(diǎn) v1到 v5長(zhǎng)度為 2 的路的數(shù)目 有 2 條，路為： v1v2v5， v1v6v5 從 結(jié)點(diǎn) v1到 v5長(zhǎng)度為 3 的路的數(shù)目 有 3 條，路為： v1v2 v3v5， v1 v2v6v5， v1 v6 v2v5 2 設(shè) G=， V= v1， v2， v3， v4， v5， E= (v1,v2)， (v1,v3)， (v2,v3)， (v2,v4)，(v3,v4)， (v3,v5)， (v4,v5) （ 1）試給出 G 的圖形表示； （ 2）寫(xiě)出其鄰接矩陣； （ 3）求出每個(gè)結(jié)點(diǎn)的度數(shù) ； （ 4）畫(huà)出其補(bǔ)圖的圖形 解： （ 1） G 的圖形表示如下： v1 v2 v3 v5 v4 v6 2 （ 2） G 的鄰接矩陣為：0110110100110110110100110（ 3） 每個(gè)結(jié)點(diǎn)的度數(shù)為： deg（ v1） =2， deg（ v2） =3， deg（ v3） =4， deg（ v4） =3， deg（ v5） =2， （ 4） 補(bǔ)圖的圖形為： 活動(dòng)說(shuō)明 ： 圖的矩陣表示及計(jì)算 的 內(nèi)容是 圖 論的應(yīng)用之一， 本次活動(dòng)是一次 運(yùn)用圖的矩陣 解決實(shí)際問(wèn)題的實(shí)踐，也是 學(xué)習(xí)過(guò)程中的 依次 形成性考核 本次活動(dòng) 共兩個(gè)題目， 第 1 題 共 45 分， 每小題 15； 第 2 題共 55 分，其中 第 1、 2、 4 小題各 15 分 ，第 3 小題各 10 分 活動(dòng) 要求 ： 1 學(xué)生 在 Word 下編輯完成作業(yè)， 文件命名為“作業(yè)次數(shù) +學(xué)號(hào)”（這是第 4v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 3 次作業(yè)，即可命名為：