第七章圖的基本概念(參考版)
2025-07-23 15:07本頁面
【正文】 同構(gòu) 設兩個無向圖 G1=V1,E1,G2=V2,E2,如果存在雙射函數(shù) ?： V1→V 2,使得對于任意的e=(vi,vj)∈ E1當且僅當 e’=( ? (vi), ? (vj))∈ E2,并且 e與 e’的重數(shù)相同 ,則稱G1與 G2是 同構(gòu) 的 ,記作 G1≌ G2. 有向圖的同構(gòu) (1)≌(2), 頂點之間的對應關系為 a?v1,b ? v2,c ?v3,d ? v4,e ? v5. 兩圖同構(gòu) ?頂點個數(shù)相同 邊的條數(shù)相同 度數(shù)相同的結(jié)點數(shù)相同 (a)≌(b) ≌ (c).(a)所示圖稱為彼德森圖 . 例 (1)畫出 4個頂點 3條邊的所有可能非同構(gòu)的無向簡單圖； (2)畫出 3個頂點 2條邊的所有可能非同構(gòu)的有向簡單圖 . ，返回目錄 。 G’是結(jié)點集 {v1， v2， v4，v5， v6}的導出子圖。?E,則稱 G 39。 最大度和最小度 對于圖 G＝ V,E,記 Δ(G)＝ max{d(v)｜v∈ V}, ? (G)＝ min{d(v)｜v∈ V},分別稱為 G的最大度 和 最小度 . 若 D＝ 〈 V,E〉 是有向圖 ,除了 Δ(D), ?(D)外 ,還有 最大出度 、 最大入度 、 最小出度 、 最小入度 ,分別定義為 基本定理 (握手定理 ) 設圖 G＝ V,E為無向圖或有向圖 ,V＝{v1,v2,...,vn},|E|=m(m為邊數(shù) ),則 推論 任何圖 (無
黨政相關相關推薦
鄂ICP備17016276號-1