離散數(shù)學第6章圖的基本概念(編輯修改稿)
2025-02-12 20:35 本頁面
【文章內容簡介】 ： 性質。 定理 3： 階圖中，若從頂點 niv jv到 存在 通路 ()ijvv?，則從 iv jv到 存在長度小于等于 在一個 的通路。 1n?推論： 階圖中，若從頂點 niv jv到 存在 通路 ()ijvv?，則從 iv jv到 存在長度小于等于 在一個 的初級通路。 1n?定理 4： 階圖中，若 n iv 到自身存在回路， 則從 到自身存在長度小于等于 iv n的回路。 在一個 推論： 階圖中，若 niv到自身存在一個 簡單回路，則從 到自身存在長度小于等于 iv n的初級回路。 在一個 由以上定理可知，在 階圖中， n任何一條初級通路的長度 任何一條初級回路的長度 1n??n?二、圖的連通性。 連通，可達。 無向圖中，從 到 存在通路，稱 iv jv到 iv jv是 連通的 (雙向 )。 有向圖中，從 到 存在通路，稱 iv jv可達 iv jv(注意方向 ) 。 短程線，距離。 短程線 —— 連通或可達的兩點間長度最短的 通路。 距離 —— 短程線的長度， 記 ,ijd V V( , )ijd V V無向圖 有向圖 若 之間無通路 (或不可達 )，規(guī)定 ,ijvv? ?( , ) ,i j i jd v v d v v? ? ? ?距離 滿足： ,ijd v v(1) ， 時，等號成立。 ,0ijdvv ? ijvv?(2) , , ,i j j k i kd v v d v v d v v??若是無向圖，還具有對稱性， ( , ) ( , )i j j id v v d v v?。 無向圖的連通。 為連通圖 —— 是平凡圖，或 都是連通的。 G G G 中任兩點 為非連通圖 —— G 中至少有兩點不連通。 G設 是一個無向圖， 是 G R G 中頂點之間的連通 關系，則 是 等價關系 。 R設 將 劃分成 個等價類： R ()VG ( 1)kk ?12, , , kV V V，由它們導出的子圖 ? ? ? ?12,G V G V? ?, kGV 稱為 的 連通分支 ，其個數(shù)記為 G ()pG有向圖的連通。 —— 中任一對頂點都互相可達 D(雙向 ) —— 中任一對頂點至少一 向可達 D—— 略去 中有向邊的方向后 得到的無向圖連通 D連通 強連通 單向連通 弱連通 強連通 單向連通 弱連通 ? ?例 強連通 單向連通 單向連通 弱連通 非連通圖 三、點割集，邊割集。 設無向圖 是連通圖 ， 若有頂點集 ， 使 刪除 （ 將 中頂點及其關聯(lián)的邊都刪除 ） 后 ， 所得子圖 是不連通的或是平凡圖；而刪除 中的任何真子集 后 ， 所得子圖是連通的 ， 則稱 是 的 點割集 ． 若點割集中只有一個頂點 ， 則稱該點為 割點 ． VV ?39。 G39。V 39。VG? 設無向圖 是連通圖 ， 若有邊集 ， 使 刪除 （ 將 中的邊從 中全部刪除 ） 后 ， 所得子圖 是不連通的或是平凡圖；而刪除 中的任何真子集 后 ， 所得子圖 是連通的 ， 則稱 是 的 邊割集 ． 若邊割集中只有一條邊 ， 則稱該邊為 割邊或 橋 ． ??? EVG ,39。V39。V 39。39。V39。39。VG? 39。V G??? EVG , EE ?39。 G39。E 39。E G 39。EG?39。E 39。39。E 39。39。EG?39。E G內容： 關聯(lián)矩陣，鄰接矩陣，可達矩陣。 重點： 有向圖，無向圖的關聯(lián)矩陣， 有向圖的鄰接矩陣。 了解： 有向圖的可達矩陣。 第三節(jié) 圖的矩陣表示 一、無向圖的關聯(lián)矩陣。 設無向圖 ,G V E? ? ?12, , , nV v v v?， ， ? ?12, , , mE e e e? ， 的關聯(lián)矩陣 G( ) ( )ij n mM G m ?? ， 0112 2 ( )ijij i ji j j ivem v ev e e v??? ???與 不關聯(lián)其中 與 關聯(lián) 次與 關聯(lián) 次 即 是以 為端點的環(huán)例 無向圖 (下圖所示 )，求 G ()MG 。 1v2v3v4v1e2e 3e4e5e1 1 1 0 00 1 1 1 0()1 0 0 1 20 0 0 0 0MG?????????????解： 性質 。 12nijim???(1) 1()mij ijm d v???(2) (3) 1 1 1 1 12 ( )m n n m ni j i j ij i i j im m m d v? ? ? ? ????? ? ? ? ?握手定理 (4) 10mijjm???，當且僅當 為孤立點。 iv(5) 若第 列與第 列相同，則說明 j k 與 je ke為平行邊。 二、有向圖的關聯(lián)矩陣。
環(huán)評公示相關推薦
鄂ICP備17016276號-1