【文章內(nèi)容簡介】 V且 V1≠ ?， 稱以 V1為頂點集，以G中 兩個端點都在 V1中的邊 組成邊集 E1的圖為 G的 V1導(dǎo)出的子圖 ，記作 G[V1]。設(shè) E1?E且 E1≠ ?， 稱以 E1為邊集，以 E1中邊關(guān)聯(liá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)中圖所示。例 (1) 畫出 4階 3條邊的所有非同構(gòu)的無向 簡單圖 。由 握手定理 可知，所畫的無向簡單圖各頂點度數(shù)之和為 2 3＝ 6，最大度小于或等于 3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將 6分成 4個非負(fù)整數(shù)，每個整數(shù)均大于或等于 0且小于或等于 3，并且 奇數(shù)的個數(shù)為偶數(shù) 。將這樣的整數(shù)列排出來只有下面三種情況：(1) 2， 2， 1， 1(2) 3， 1， 1， 1(3) 2， 2， 2， 0 將每種度數(shù)列所有非同構(gòu)的圖都畫出來即得所要求的全部非同構(gòu)的圖。 對于給定的正整數(shù) n和 m(m≤ n(n1)/2)，構(gòu)造出所有非同構(gòu)的 n階 m條邊的所有非同構(gòu)的無向 (有向 )簡單圖，這是目前還沒有解決的難題。 例 (2) 畫出 3階 2條邊的所有非同構(gòu)的有向簡單圖。由握手定理可知，所畫有向簡單圖各頂點度數(shù)之和為 4，最大出度和最大入度均小于或等于 2。 度數(shù)列及入度出度列為1,2,1 入度列為 0,1,1 或 0,2,0 或 1,0,1出度列為 1,1,0 或 1,0,1 或 0,2,02,2,0 入度列為 1,1,0出度列為 1,1,0定義 定義 設(shè) G＝ V,E為 n階無向簡單圖， 以 V為頂點集 ，以所有 使 G成為完全圖 Kn的添加邊組成的集合 為邊集的圖，稱為 G的 補(bǔ)圖 ，記作 G。若圖 G≌ G， 則稱為 G是 自補(bǔ)圖 。(1)為自補(bǔ)圖(2)和 (3)互為補(bǔ)圖定義 定義 設(shè) G＝ V,E為無向圖。(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)的一切邊，稱為 刪除頂點 v。設(shè) V ??V， 用 GV ?表示從 G中刪除 V ?中所有頂點，稱為 刪除 V ?。(3)設(shè)邊 e＝ (u,v)∈ E， 用 G\e表示從 G中刪除 e后，將 e的兩個端點u,v用一個新的頂點 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)， 稱為 加新邊 。說明 在收縮邊和加新邊過程中可能產(chǎn)生 環(huán) 和 平行邊 。舉例G G－ e5 G－ {e1, e4}G－ v5 G－ {v4, v5} G\e5 通路與回路定義 設(shè) G為無向標(biāo)定圖， G中頂點與邊的交替序列 Г＝vi0ej1vi1ej2vi2… ejivil稱為 vi0到 vil的 通路 ，其中， vir1,vir為 ejr的 端點， r ＝ 1， 2， … ， l， vi0， vil分別稱為 Г的 始點 與 終點 ， Г中邊的條數(shù)稱為它的 長度 。若 vi0＝ vil，則稱通路為 回路 。若 Г的 所有邊各異 ，則稱 Г為 簡單通路 ，又若 vi0＝ vil，則稱 Г為 簡單回路 。若 Г的所有 頂點 (除 vi0與 vij可能相同外 )各異 ，所有 邊也各異 ，則稱 Г為 初級通路 或 路徑 ，又若 vi0＝ vil，則稱 Г為 初級回路 或 圈 。將長度為奇數(shù)的圈稱為 奇圈 ，長度為偶數(shù)的圈稱為 偶圈 。 關(guān)于通路與回路的說明q 在初級通路與初級回路的定義中，仍將初級回路看成初級通路 (路徑 )的特殊情況，只是在應(yīng)用中初級通路 (路徑 )都是始點與終點不相同的， 長為 1的圈只能由環(huán)生成 ， 長為 2的圈只能由平行邊生成 ，因而在 簡單無向圖中，圈的長度至少為 3。q 若 Г 中有 邊重復(fù) 出現(xiàn)，則稱 Г 為 復(fù)雜通路 ，又若 vi0＝ vil， 則稱 Г 為 復(fù)雜回路 。 q 在有向圖中 ，通路、回路及分類的定義與無向圖中非常相似，只是 要注意有向邊方向的一致性 。 q 在以上的定義中，將回路定義成通路的特殊情況，即 回路也是通路 ，又 初級通路 (回路 )是簡單通路 (回路 )，但反之不真。通路和回路的簡單表示法q 只用邊的序列表示通路 (回路 )。定義 Г 可以表示成 ej1 ,ej2 ,… , ejl。q 在簡單圖中也可以只用頂點序列表示通路 (回路 )。定義中的 Г 也可以表示成 vi0 ,vi2 ,… , vil。q 為了寫出非標(biāo)定圖中的通路 (回路 )，可以先將非標(biāo)定圖標(biāo)成標(biāo)定圖，再寫出通路與回路。q 在非簡單標(biāo)定圖中，當(dāng)只用頂點序列表示不出某些通路 (回路 )時，可在頂點序列中加入一些邊 (這些邊是平行邊或環(huán) )，可稱這種表示法為 混合表示法 。 定理 定理 在 n階圖 G中，若從頂點 vi到 vj（ vi≠ vj） 存在通路，則從vi到 vj存在長度小于或等于 n1的通路。 證明 設(shè) Г＝ v0e1v1e2… elvl(v0＝ vi ,vl＝ vj)為 G中一條長度為 l的通路，若 l≤ n1， 則 Г滿足要求，否則必有 l+1n， 即 Г上的頂點數(shù)大于 G中的頂點數(shù)，于是必存在 k,s,0≤ ks≤ l， 使得 vs＝ vk,即在 Г上存在 vs到自身的回路 Csk,在 Г上刪除 Csk上的一切邊及除 vs外的一切頂點，得 Г?＝ v0e1v1e2… vkes+1 … elvl ,Г?仍為 vi到 vj的通路，且長度至少比 Г 減少 1。若 Г?還不滿足要求，則重復(fù)上述過程，由于 G是有限圖，經(jīng)過有限步后，必得到 vi到 vj長度小于或等于 n1的通路。 定理 推論 在 n階圖 G中，若從頂點 vi到 vj（ vi≠ vj） 存在通路，則 vi到 vj一定存在長度小于或等于 n1的初級通路（路徑）。 定理 在一個 n階圖 G中，若存在 vi 到自身的回路，則一定存在 vi 到自身長度小于或等于 n的回路。 推論 在一個 n階圖 G中，若存在 vi 到自身的簡單回路，則一定存在 vi 到自身長度小于或等于 n的初級回路。例 例 無向完全圖 Kn(n≥ 3)中有幾種非同構(gòu)的圈？解答 長度相同的圈都是同構(gòu)的，因而只有長度不同的圈才是非同構(gòu)的，易知 Kn(n≥3) 中含長度為 3， 4， … ， n的圈，所以 Kn(n≥3) 中有 n2種非同構(gòu)的圈。 例 例 無向完全圖 K3的頂點依次標(biāo)定為 a,b,c。 在定義意義下 K3中有多少個不同的圈？解答 在同構(gòu)意義下， K3中只有一個長度為 3的圈。但在定義意義下，不同起點 (終點 )的圈是不同的，頂點間排列順序不同的圈也看成是不同的，因而 K3中有 6個不同的長為 3的圈： abca ， acba ， bacb ， bcab ， cabc ， cbac如果只考慮起點 (終點 )的差異，而不考慮順時針逆時針的差異，應(yīng)有 3種不同的圈，當(dāng)然它們都是同構(gòu)的，畫出圖來只有一個。 圖的連通性q 無向圖的連通性q 無向圖中頂點之間的短程線及距離q 無向圖的連通程度：點割集、割點、邊割集、割邊、連通度q 有向圖的連通性及判別方法q 擴(kuò)大路徑法與極