圖的基本概念(編輯修改稿)
2024-09-01 04:46 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 設(shè)所得圖為 G， 則 (G)＝ max{5,4,3,2,2}＝ 5， 這與定理 。 例 (3) (3,3,3,1) 可圖化，不可簡(jiǎn)單圖化。假設(shè)該序列可以簡(jiǎn)單圖化， 設(shè) G＝ V， E以該序列為度數(shù)列。 不妨設(shè) V＝ {v1,v2,v3,v4} 且 d(v1)＝ d(v2)＝ d(v3)＝ 3,d(v4)＝ 1， 由于 d(v4)＝ 1， 因而 v4只能與 v1， v2， v3之一相鄰， 于是 v1， v2， v3不可能都是 3度頂點(diǎn)，這是矛盾的， 因而 (3)中序列也不可簡(jiǎn)單圖化。 (4) (d1,d2,… dn)， d1d2… dn≥1 且 為偶數(shù)。 ??n1iid可圖化，不可簡(jiǎn)單圖化。 例 (5) (4,4,3,3,2,2) 可簡(jiǎn)單圖化。下圖中兩個(gè) 6階無(wú)向簡(jiǎn)單圖都以 (5)中序列為度數(shù)列。 完全圖 定義 設(shè) G為 n階無(wú)向簡(jiǎn)單圖，若 G中 每個(gè)頂點(diǎn)均與其余的 n1個(gè)頂點(diǎn)相鄰 ，則稱 G為 n階無(wú)向完全圖 ，簡(jiǎn)稱 n階完全圖 ，記做Kn(n≥1) 。 設(shè) D為 n階有向簡(jiǎn)單圖，若 D中每個(gè)頂點(diǎn)都鄰接到其余的 n1個(gè)頂點(diǎn)，又鄰接于其余的 n1個(gè)頂點(diǎn)，則稱 D是 n階有向完全圖 。 設(shè) D為 n階有向簡(jiǎn)單圖，若 D的基圖為 n階無(wú)向完全圖 Kn， 則稱 D是 n階競(jìng)賽圖 。 完全圖舉例 n階無(wú)向完全圖的邊數(shù)為： n(n1)/2 n階有向完全圖的邊數(shù)為： n(n1) n階競(jìng)賽圖的邊數(shù)為： n(n1)/2 K5 3階有向完全圖 4階競(jìng)賽圖 正則圖 定義 設(shè) G為 n階無(wú)向簡(jiǎn)單圖，若 v∈V(G) ， 均有 d(v)＝ k，則稱 G為 k正則圖 。 舉例 n階零圖是 0正則圖 n階無(wú)向完全圖是 (n1)正則圖 彼得森圖是 3正則圖 說(shuō)明 n階 k正則圖中，邊數(shù) m＝ kn/2。 當(dāng) k為奇數(shù)時(shí)， n必為偶數(shù)。 子圖 定義 設(shè) G＝ V,E， G?＝ V ?,E?為兩個(gè)圖 (同為無(wú)向圖或同為有向圖 )，若 V ??V且 E ??E， 則稱 G?是 G的 子圖 ， G為 G ?的 母圖 ，記作 G ??G。 若 V ??V或 E ??E， 則稱 G ?為 G的 真子圖 。 若 V ?＝ V， 則稱 G ?為 G的 生成子圖 。 設(shè) G＝ V,E為一圖， V1?V且 V1≠ ?， 稱以 V1為頂點(diǎn)集，以G中 兩個(gè)端點(diǎn)都在 V1中的邊 組成邊集 E1的圖為 G的 V1導(dǎo)出的子圖 ，記作 G[V1]。 設(shè) E1?E且 E1≠ ?， 稱以 E1為邊集，以 E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集 V1的圖 為 G的 E1導(dǎo)出的子圖 ，記作 G[E1]。 導(dǎo)出子圖舉例 在上圖中，設(shè) G為 (1)中圖所表示， 取 V1＝ {a,b,c}， 則 V1的導(dǎo)出子圖 G[V1]為 (2)中圖所示。 取 E1＝ {e1,e3}， 則 E1的導(dǎo)出子圖 G[E1]為 (3)中圖所示。 定義 定義 設(shè) G＝ V,E為 n階無(wú)向簡(jiǎn)單圖， 以 V為頂點(diǎn)集 ，以所有 使 G成為完全圖 Kn的添加邊組成的集合 為邊集的圖，稱為 G的 補(bǔ)圖 ，記作 G。 若圖 G≌ G， 則稱為 G是 自補(bǔ)圖 。 (1)為自補(bǔ)圖 (2)和 (3)互為補(bǔ)圖 定義 定義 設(shè) G＝ V,E為無(wú)向圖。 (1)設(shè) e∈ E， 用 Ge表示從 G中去掉邊 e， 稱為 刪除 e。 設(shè) E ??E， 用 GE ?表示從 G中刪除 E ?中所有的邊，稱為 刪除 E ?。 (2)設(shè) v∈ V， 用 Gv表示從 G中去掉 v及所關(guān)聯(lián)的一切邊，稱為 刪除頂點(diǎn) v。 設(shè) V ??V， 用 GV ?表示從 G中刪除 V ?中所有頂點(diǎn)，稱為 刪除 V ?。 (3)設(shè)邊 e＝ (u,v)∈ E， 用 G\e表示從 G中刪除 e后，將 e的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn) w(或用 u或 v充當(dāng) w)代替，使 w關(guān)聯(lián)除 e外 u,v關(guān)聯(lián)的所有邊，稱為 邊 e的收縮 。 (4)設(shè) u,v∈ V(u,v可能相鄰，也可能不相鄰 )， 用 G∪( u,v)(或G+(u,v))表示在 u,v之間加一條邊 (u,v)， 稱為 加新邊 。 說(shuō)明 在收縮邊和加新邊過(guò)程中可能產(chǎn)生環(huán)和平行邊。 通路與回路 定義 設(shè) G為無(wú)向標(biāo)定圖 ， G中頂點(diǎn)與邊的交替序列 Г＝vi0ej1vi1ej2vi2… ejivil稱為 vi0到 vil的 通路 ， 其中 ， vir1,vir為 ejr的 端點(diǎn)， r ＝ 1， 2， … ， l， vi0， vil分別稱為 Г的 始點(diǎn) 與 終點(diǎn) ， Г中邊的條數(shù)稱為它的 長(zhǎng)度 。 若 vi0＝ vil， 則稱通路為 回路 。 若 Г的 所有邊各異 ， 則稱 Г為 簡(jiǎn)單通路 ， 又若 vi0＝ vil， 則稱 Г為 簡(jiǎn)單回路 。 若 Г的所有 頂點(diǎn) (除 vi0與 vij可能相同外 )各異 ， 所有 邊也各異 ， 則稱 Г為 初級(jí)通路 或 路徑 ， 又若 vi0＝ vil， 則稱 Г為 初級(jí)回路 或 圈 。 將長(zhǎng)度為奇數(shù)的圈稱為 奇圈 ， 長(zhǎng)度為偶數(shù)的圈稱為 偶圈 。 關(guān)于通路與回路的說(shuō)明 ?在初級(jí)通路與初級(jí)回路的定義中，仍將初級(jí)回路看成初級(jí)通路 (路徑 )的特殊情況，只是在應(yīng)用中初級(jí)通路 (路徑 )都是始點(diǎn)與終點(diǎn)不相同的， 長(zhǎng)為 1的圈只能由環(huán)生成 ， 長(zhǎng)為 2的圈只能由平行邊生成 ，因而在 簡(jiǎn)單無(wú)向圖中，圈的長(zhǎng)度至少為 3。 ?若 Г 中有 邊重復(fù) 出現(xiàn)，則稱 Г 為 復(fù)雜通路 ， 又若 vi0＝ vil， 則稱 Г 為 復(fù)雜回路 。 ?在有向圖中 ，通路、回路及分類的定義與無(wú)向圖中非常相似，只是 要注意有向邊方向的一致性 。 ?在以上的定義中，將回路定義成通路的特殊情況，即 回路也是通路 ，又 初級(jí)通路 (回路 )是簡(jiǎn)單通路 (回路 )，但反之不真。 通路和回路的簡(jiǎn)單表示法 (1)只用邊的序列表示通路 (回路 )。定義 Г 可以表示成 ej1 ,ej2 ,… ,ejl。
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1