離散數(shù)學(xué)耿素云第5版-資料下載頁(yè)
2025-01-16 20:25本頁(yè)面
【正文】 度數(shù)列相同 (不計(jì)度數(shù)的順序 ) ③ 對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同 ， 等等 若破壞必要條件 ， 則兩圖不同構(gòu) 至今沒(méi)有找到判斷兩個(gè)圖同構(gòu)的多項(xiàng)式時(shí)間算法 23 完全圖 n階無(wú)向完全圖 Kn: 每個(gè)頂點(diǎn)都與其余頂點(diǎn)相鄰的 n階無(wú)向簡(jiǎn)單圖 . 簡(jiǎn)單性質(zhì) : 邊數(shù) m=n(n1)/2, ?=?=n1 n階有向完全圖 : 每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的 n階有向簡(jiǎn)單圖 . 簡(jiǎn)單性質(zhì) : 邊數(shù) m=n(n1), ?=?=2(n1), ?+=?+=?=?=n1 K5 3階有向完全圖 24 子圖 定義 設(shè) G=V,E, G ?=V ?,E ?是兩個(gè)圖 (1) 若 V ??V且 E ??E, 則稱(chēng) G ?為 G的 子圖 , G為 G ?的 母圖 , 記作 G ??G (2) 若 G ??G 且 V ?=V， 則稱(chēng) G ?為 G的 生成子圖 (3) 若 V ??V 或 E ??E， 稱(chēng) G ?為 G的 真子圖 (4) 設(shè) V ??V 且 V ???, 以 V ?為頂點(diǎn)集 , 以?xún)啥它c(diǎn)都在 V ?中的所有邊為邊集的 G的子圖稱(chēng)作 V ?的導(dǎo) 出子圖 ， 記作 G[V ?] (5) 設(shè) E ??E且 E ???, 以 E ?為邊集 , 以 E ?中邊關(guān)聯(lián)的 所有頂點(diǎn)為頂點(diǎn)集的 G的子圖稱(chēng)作 E ?的導(dǎo)出子 圖 , 記作 G[E ?] 25 生成子圖實(shí)例 K4的所有非同構(gòu)的生成子圖 導(dǎo)出子圖實(shí)例 26 G D G[{v1,v2}] G[{e1,e3,e4}] D[{e1,e3}] D[{v1,v2}] 27 補(bǔ)圖 GG定義 設(shè) G=V,E為 n階無(wú)向簡(jiǎn)單圖 ， 以 V為頂點(diǎn)集 ,所有使 G成為完全圖 Kn的添加邊組成的集合為邊集的圖 ， 稱(chēng)為 G的 補(bǔ)圖 ， 記作 . 若 G? , 則稱(chēng) G是 自補(bǔ)圖 . 例 對(duì) K4的所有非同構(gòu)子圖 , 指出互為補(bǔ)圖的每一對(duì)子圖 , 并指出哪些是自補(bǔ)圖 .
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1