大二離散08圖論圖的基本概念

1、 圖 論主要內(nèi)容圖的基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算圖的子圖與補(bǔ)圖一個(gè)圖G是一個(gè)三重組，其中V(G)是一個(gè)非空的結(jié)點(diǎn)（頂點(diǎn)）集合， E(G)是邊的集合，G是從邊集E到結(jié)點(diǎn)偶對集合上的函數(shù)。 一個(gè)圖可以用一個(gè)圖形表示。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的基本概念G=V(G),E(G),GV(G)=a,b,c,d E(G)=e1,e2,e3,e4,e6,e7G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d), G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)。定義中的結(jié)點(diǎn)偶對可以是有序的，也可以是無序的。若邊

2、e所對應(yīng)的偶對(a,b)是有序的，即序偶，則稱e是有向邊。有向邊簡稱弧，a稱為弧e的始點(diǎn)，b稱為弧e的終點(diǎn)，統(tǒng)稱為e的端點(diǎn)。稱e是關(guān)聯(lián)于結(jié)點(diǎn)a和b的，結(jié)點(diǎn)a和b是鄰接的。若邊e所對應(yīng)的偶對(a,b)是無序的，則稱e是無向邊。無向邊簡稱棱，除無始點(diǎn)和終點(diǎn)概念外，其它與有向邊相同。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的基本概念每一條邊都是有向邊的圖稱為有向圖；每一條邊都是無向邊的圖稱為無向圖；如果在圖中一些邊是有向邊，而另一些邊是無向邊，則稱這個(gè)圖是混合圖。約定：表示有向邊，(a,b)表示無向邊，a,b既表示有向邊又表示無向邊。于是圖的三元組表達(dá)形式可以變?yōu)槎M形式G=，其中

3、E為偶對集合，隱含表示圖中的邊。把無向圖中每一條邊都看成兩條方向不同的有向邊，無向圖就成為有向圖；把有向圖中每條有向邊都看成無向邊，就成為無向圖。通常稱這個(gè)無向圖是該有向圖的底圖。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的基本概念在圖中，不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)。全由孤立結(jié)點(diǎn)構(gòu)成的圖稱為零圖。關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊稱為自回路，自回路的方向不定。在有向圖中，兩結(jié)點(diǎn)間（包括結(jié)點(diǎn)自身間）若同始點(diǎn)和同終點(diǎn)的邊多于一條，則這幾條邊稱為平行邊。在無向圖中，兩結(jié)點(diǎn)間（包括結(jié)點(diǎn)自身間）若多于一條邊，則這幾條邊稱為平行邊。兩結(jié)點(diǎn)a和b間互相平行的邊的條數(shù)稱為邊a,b的重?cái)?shù)。僅有一條邊時(shí)

4、，重?cái)?shù)為1，無邊時(shí)重?cái)?shù)為0。含有平行邊的圖稱為多重圖。非多重圖稱為線圖。無自回路的線圖稱為簡單圖。多重圖要用三元組形式表示，線圖則可以不用。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的基本概念賦權(quán)圖G是一個(gè)三重組或四重組，其中V是一個(gè)非空的結(jié)點(diǎn)集合， E是邊的集合，f是定義在V上的函數(shù)，g是定義在E上的函數(shù)。如左圖所示：V=a,b,c,E=e1,e2,e3,f(a)=3, f(b)=4, f(c)=5, g(e1)=6, g(e2)=7, g(e3)=8。3a5c4be16e38e27 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的基本概念在有向圖中，對于任何結(jié)點(diǎn)v，以

5、v為始點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引出次數(shù)（或出度），記為deg+(v);以v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn)v的引入次數(shù)（或入度），記為deg-(v)；結(jié)點(diǎn)v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的次數(shù)（或度數(shù)），記為deg(v)。在無向圖中，結(jié)點(diǎn)v的次數(shù)是與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù)，也記為deg(v)。孤立結(jié)點(diǎn)的次數(shù)為0。以后把具有n個(gè)結(jié)點(diǎn)和m條邊的圖簡稱為(n,m)圖。各結(jié)點(diǎn)的次數(shù)均相同的圖 稱為正則圖，各結(jié)點(diǎn)的次 數(shù)均為k時(shí)，稱為k正則 圖。右圖為彼得森圖。 圖 論頂點(diǎn)的度數(shù)圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖設(shè)G是一個(gè)(n,m)圖，它的結(jié)點(diǎn)集合為V=v1,v2,.,vn，則 圖 論圖基本概念

6、頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖頂點(diǎn)的度數(shù)在圖中，次數(shù)為奇數(shù)的結(jié)點(diǎn)必有偶數(shù)個(gè)。證明：設(shè)V1和V2分別是圖G中奇數(shù)次數(shù)和偶數(shù)次數(shù)結(jié)點(diǎn)的集合，則有 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖頂點(diǎn)的度數(shù)設(shè)G=和G=是兩個(gè)圖，若存在從V到V的雙射函數(shù)f，使對任意a,bV，a,bE，當(dāng)且僅當(dāng)f(a),f(b)E，并且a,b和f(a),f(b)有相同的重?cái)?shù)，則稱G和G是同構(gòu)的。兩個(gè)圖的各結(jié)點(diǎn)之間，如果存在一一對應(yīng)關(guān)系，而且這種對應(yīng)關(guān)系保持了各結(jié)點(diǎn)間的鄰接關(guān)系（有向圖還保持邊的方向）和邊的重?cái)?shù)，則這兩個(gè)圖是同構(gòu)的。即同構(gòu)圖除了頂點(diǎn)和邊的名稱不同外，實(shí)際上就是一個(gè)圖形。 圖 論圖基本概念頂點(diǎn)的度

7、數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的同構(gòu)4321acdb同構(gòu) 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的同構(gòu)632154321654K3,3圖 圖 論圖的同構(gòu)圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖兩圖同構(gòu)的必要條件：結(jié)點(diǎn)數(shù)相同邊數(shù)相同度數(shù)相同的結(jié)點(diǎn)數(shù)相等不同構(gòu) 圖 論圖的同構(gòu)圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖設(shè)圖G1=和圖G2=。G1與G2的并：定義為圖G3=，其中V3V1V2，E3E1E2，記為G3G1G2。G1與G2的交：定義為圖G3=，其中V3V1V2，E3E1E2，記為G3G1G2。G1與G2的差：定義為圖G3=，其中E3E1E2， V3(V1V2)E3中

8、邊所關(guān)聯(lián)的頂點(diǎn)，記為G3G1G2。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算G1與G2的環(huán)和：定義為圖G3=， G3(G1G2)(G1G2)，記為G3G1G2。此外還有以下兩種操作： 刪去圖G的一條邊； 刪去圖G的一個(gè)結(jié)點(diǎn)v：即刪去結(jié)點(diǎn)v和與v關(guān)聯(lián)的 所有邊。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算acbdG2e4e1e5acbG1e2e1e3acbdG1G2e2e4e1e3e5 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算acbG1G2e1acbdG2e4e1e5acbG1e2e1e3acbG1G2e2e3 圖 論圖基本概念頂點(diǎn)的度數(shù)

9、圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算acbdG1G2e2e4e1e3e5acbG1G2e1acbdG1G2e2e4e3e5 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算acbG1e2e1e3acb刪去邊e2e1e3ab刪去結(jié)點(diǎn)ce1 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的運(yùn)算設(shè)圖G=和圖G=。如果V V和E E，則稱G是G的子圖。如果V V和E E而GG，則稱G是G的真子圖。如果VV和E E，則稱G為G的生成子圖。以E為邊集，以E中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集，并保持它們的關(guān)聯(lián)關(guān)系，得到G，則稱G為由邊集E導(dǎo)出的子圖。以V為頂點(diǎn)集，以V中關(guān)聯(lián)的邊的全體為邊集，并保持它們的關(guān)聯(lián)關(guān)系，得到G，此時(shí)稱G為由結(jié)點(diǎn)集V導(dǎo)出的子圖。 圖 論圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖圖的子圖與補(bǔ)圖真子圖abeacbde生成子圖acbde圖Gabde由V=a,b,d,e導(dǎo)出的子圖 圖 論圖的子圖與補(bǔ)圖由E=a,b,b,c,c,d導(dǎo)出的子圖acbd圖基本概念頂點(diǎn)的度數(shù)圖的同構(gòu)圖的運(yùn)算子圖與補(bǔ)圖在n個(gè)結(jié)點(diǎn)的有向圖G中，如果EVV，則稱G為有向完全圖；在n個(gè)結(jié)點(diǎn)的無向圖G中，如果任何兩個(gè)不同結(jié)點(diǎn)間都恰好有一條邊，則稱G為無向完全圖，記為Kn。設(shè)線圖G有n個(gè)頂點(diǎn)，線圖H也