圖的代數(shù)表示及其特征

1、圖的代數(shù)表示及其特征An 中元素的含義中元素的含義: n的途徑數(shù)的途徑數(shù)A22111131011211011 A32431424334211310 1v2v3v4v1e2e4e5eA0110101111000100 推論：若推論：若A為簡單圖為簡單圖G 的鄰接矩陣，則的鄰接矩陣，則 1）A2 中對角線上元素為頂點的度；中對角線上元素為頂點的度； 2） A3中對角線上元素為含該頂點的中對角線上元素為含該頂點的 三角形數(shù)目的兩倍。三角形數(shù)目的兩倍。思考？思考？ 如何從如何從 An中尋找任意兩點間的距中尋找任意兩點間的距離？離？推廣的鄰接矩陣（復(fù)合圖）推廣的鄰接矩陣（復(fù)合圖）無環(huán)圖無環(huán)圖1v2v3v

2、4v1e2e3e4e5eA0210201111000100 對稱矩陣對稱矩陣每一行、每一行、列之和列之和為該頂為該頂點的度點的度An 中元素的含義中元素的含義 邊數(shù)為邊數(shù)為n的途徑數(shù)的途徑數(shù)A25122162022212011 A3414611447667421620 1v2v3v4v1e2e3e4e5eA0210201111000100 推論：若推論：若A為簡單圖為簡單圖G 的鄰接矩陣，則的鄰接矩陣，則 1）A2 中對角線上元素為頂點的度；中對角線上元素為頂點的度； 2） A3中對角線上元素為含該頂點的中對角線上元素為含該頂點的 三角形數(shù)目的兩倍。三角形數(shù)目的兩倍。思考？思考？ 如何從如何從

3、 An中尋找任意兩點間的距中尋找任意兩點間的距離？離？思考？思考？ 上述結(jié)論對無環(huán)圖成立嗎？上述結(jié)論對無環(huán)圖成立嗎？推廣的鄰接矩陣（復(fù)合圖）續(xù)。推廣的鄰接矩陣（復(fù)合圖）續(xù)。有環(huán)圖有環(huán)圖1v2v3v4v1e2e3e4e5eA0210201111100100 對稱矩陣對稱矩陣每一行、每一行、列之和列之和不一定不一定為該頂為該頂點的度點的度6eA0210201111100100 1v2v3v4v1e2e3e4e5e6eAn 中元素的含義中元素的含義 邊數(shù)為邊數(shù)為n的途徑數(shù)的途徑數(shù)A25132163033312011 A351591155106910931630 鄰接矩陣的進(jìn)一步推廣有向圖鄰接矩陣的進(jìn)

4、一步推廣有向圖1v2v3v4v1e2e3e4e5e6eA0100101110100000 每一行每一行之和為之和為該頂點該頂點的出度的出度每一列之和每一列之和為該頂點的為該頂點的入度入度An 中元素的含義中元素的含義 邊數(shù)為邊數(shù)為n的途徑數(shù)的途徑數(shù)1v2v3v4v1e2e3e4e5e6eA0100101110100000 A21011111011100000 A31110212121210000 推論：若推論：若A為簡單圖為簡單圖G 的鄰接矩陣，則的鄰接矩陣，則 1）A2 中對角線上元素為頂點的度；中對角線上元素為頂點的度； 2） A3中對角線上元素為含該頂點的中對角線上元素為含該頂點的 三角

5、形數(shù)目的兩倍。三角形數(shù)目的兩倍。思考？思考？ 如何從如何從 An中尋找任意兩點間的距中尋找任意兩點間的距離？離？思考？思考？ 上述結(jié)論對有向圖成立嗎？上述結(jié)論對有向圖成立嗎？ 無向無向 有向圖有向圖1v2v3v4v1e2e3e4e5e6eA0210201111100100 1v2v4vA0210201111200100 無向無向 有向圖有向圖1v2v3v4v1e2e3e4e5e6eA25132163033312011 A25142164044612011 1v2v4vA0210201111100100 思考？思考？ 鄰接矩陣鄰接矩陣A所對應(yīng)的圖所對應(yīng)的圖G是什么？是什么？12345123411100011101001200000eeeeevvBvv 每一列之和每一列之和為為2關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 點與邊的關(guān)系點與邊的關(guān)系1v2v3v4v1e2e3e4e5e定理：具有定理：具有n個頂點的連通圖的關(guān)聯(lián)矩陣的個頂點的