圖的基本概念與握手定理

圖的基本概念與握手定理1第一頁，共二十二頁，2022年，8月28日一、圖的概念二、圖的類型三、結(jié)點(diǎn)的度數(shù)四、握手定理五、同構(gòu)概念六、鄰接矩陣主要內(nèi)容2第二頁，共二十二頁，2022年，8月28日圖論研究圖的邏輯結(jié)構(gòu)與性質(zhì).引言

圖論最早起源于一些數(shù)字游戲的難題研究．圖論的最早論文是1736年瑞士數(shù)學(xué)家歐拉（LeonhardEuler）所寫，從而使歐拉成為圖論的創(chuàng)始人。

圖論是組合數(shù)學(xué)的一個(gè)分支，研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。計(jì)算機(jī)的迅速發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。3第三頁，共二十二頁，2022年，8月28日引言哥尼斯堡七橋問題

當(dāng)時(shí)哥尼斯堡（Konigsberg）城（現(xiàn)名加里寧格勒,屬俄羅斯）的居民有郊游的習(xí)慣，在城郊的普雷格爾（Pregel）河畔，河中有兩個(gè)小島，七座橋?qū)蓚€(gè)小島和河岸連接起來，如圖所示，問一個(gè)人能否從任一小島出發(fā)不重復(fù)地走遍七座小橋？

4第四頁，共二十二頁，2022年，8月28日1852年畢業(yè)于倫敦大學(xué)的弗南西斯·格思里發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色?！边@個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？四色問題5第五頁，共二十二頁，2022年，8月28日Hamilton問題

1856年，英國數(shù)學(xué)家Hamilton設(shè)計(jì)了一個(gè)名為周游世界的游戲：他用一個(gè)正十二面體的二十個(gè)端點(diǎn)表示世界上的二十座大城市（見圖），提出的問題是要求游戲者找一條沿著十二面體的棱通過每個(gè)端點(diǎn)恰好一次的行走路線。此路線稱為：哈密爾頓回路，而此圖稱為：哈密爾頓圖。6第六頁，共二十二頁，2022年，8月28日圖G=<V,E>,其中(1)V

為頂點(diǎn)集，其元素稱為結(jié)點(diǎn)（頂點(diǎn)）--用來表示事物(2)E為VV的多重集。其元素稱為邊--表示事物間的二元關(guān)系(一)圖的定義:一、圖的概念7第七頁，共二十二頁，2022年，8月28日(二)結(jié)點(diǎn)與邊的關(guān)系:

①結(jié)點(diǎn)與邊(不)相

關(guān)聯(lián)：②結(jié)點(diǎn)與結(jié)點(diǎn),邊與邊(不)相鄰接一、圖的概念(三)特殊點(diǎn)孤立點(diǎn):不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)懸掛點(diǎn):

只與一條邊相關(guān)聯(lián)的結(jié)點(diǎn)(四)特殊的邊:環(huán):

一條邊若與兩個(gè)相同的結(jié)點(diǎn)相關(guān)聯(lián)則稱為環(huán)。多重邊(平行邊）:與兩個(gè)結(jié)點(diǎn)相關(guān)聯(lián)的邊若多于一條，則稱這些邊為多重邊。8第八頁，共二十二頁，2022年，8月28日有向圖與無向圖:簡單圖與多重圖:簡單圖--不含環(huán)與多重邊；多重圖--含多重邊有權(quán)圖與無權(quán)圖:b.按邊的種類分類：有限圖與無限圖：V與E為有限集合的圖叫有限圖，否則叫無限圖。(n,m)圖：有n個(gè)結(jié)點(diǎn)與m條邊的圖。

零圖:即(n,0)圖;平凡圖:即(1,0)圖。完全圖:任意兩個(gè)結(jié)點(diǎn)都相鄰接的圖。K-正則圖:每個(gè)結(jié)點(diǎn)都與K條邊相關(guān)聯(lián)。c.按結(jié)點(diǎn)集與邊集的“階”分類a按邊的方向分類二、圖的類型9第九頁，共二十二頁，2022年，8月28日注意：完全圖是

n-1

正則圖完全圖的每個(gè)結(jié)點(diǎn)都與其它n-1個(gè)結(jié)點(diǎn)相鄰接,即與n-1條邊相關(guān)聯(lián),所以是n-1正則圖,反之正則圖不一定是完全圖。1.完全圖：2.正則圖：

是3正則圖完全圖,不是完全圖二、圖的類型10第十頁，共二十二頁，2022年，8月28日子圖：

設(shè)G=<V,E>,G`=<V`,E`>為兩個(gè)圖，滿足V`V且E`E，則稱G`為G的子圖，G為G`的母圖，記作G`G。(1)G`為G的真子圖：若G`G且V`V或E`E。

(2)G`為G的生成子圖：若G`G且V`=V。(3)V1導(dǎo)出的導(dǎo)出子圖：頂點(diǎn)集≠V1V,邊集為兩端點(diǎn)均在V1中的全體邊構(gòu)成的子圖。(4)E1導(dǎo)出的導(dǎo)出子圖：≠E1E,以E1中邊關(guān)聯(lián)的頂點(diǎn)的全體為頂點(diǎn)集的G的子圖。二、圖的類型11第十一頁，共二十二頁，2022年，8月28日abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母圖真子圖V'V或E'E生成子圖G'G且V'=V導(dǎo)出子圖V'V或E'E二、圖的類型12第十二頁，共二十二頁，2022年，8月28日補(bǔ)圖

設(shè)G=〈V,E〉,對于G1=〈V,E1〉若有G2=〈V,E∪E1〉是完全圖,且E∩E1=Φ,則稱G1是G的補(bǔ)圖。

圖G圖G1圖G2二、圖的類型13第十三頁，共二十二頁，2022年，8月28日

在無向圖G中，與v相鄰的頂點(diǎn)的數(shù)目稱為v的次或度/degree。記為deg(v)或d(v)。在有向圖G中，以v為終點(diǎn)的邊的條數(shù)稱為v的入次或入度/in-degree。記為deg–(v)或d–(v)。以v為起點(diǎn)的邊的條數(shù)稱為v的出次或出度/out-degree。記為deg+(v)或d+(v)。三、結(jié)點(diǎn)的度數(shù)14第十四頁，共二十二頁，2022年，8月28日在無向圖G中,令

△(G)=max{d(v)|v∈V(G)}(G)=min{d(v)|v∈V(G)}

稱△(G)和(G)分別為G的最大度和最小度。在有向圖D中,類似定義△(D)、(G)。另外,令

△+(G)=max{d+(v)|v∈V(D)}

+(G)=min{d+(v)|v∈V(D)}△-(G)=max{d-(v)|v∈V(D)}

-(G)=min{d-(v)|v∈V(D)}分別為D的最大出度、最小出度、最大入度、最小入度。簡記作△、、△+、+、△-、-。三、結(jié)點(diǎn)的度數(shù)15第十五頁，共二十二頁，2022年，8月28日定理1

設(shè)G=<V,E>為任意無向圖，V={v1,v2,…,vn},|E|=m,則四、握手定理定理2

設(shè)D=<V,E>為任意有向圖，V={v1,v2,…,vn},|E|=m,則

證G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m條邊共提供2m度.16第十六頁，共二十二頁，2022年，8月28日握手定理推論及應(yīng)用推論任何圖(無向或有向)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).例1

無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問G的階數(shù)n為幾？解設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn)v1,v2,…,vx，則

d(vi)2，i=1,2,…,x，于是

3224+2x得x4,階數(shù)n4+4+3=11.17第十七頁，共二十二頁，2022年，8月28日五、圖的同構(gòu)定義設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個(gè)圖(有向或無向圖)，（1）若存在雙射函數(shù)f:V1V2,對于vi,vjV1,(vi,vj)E1當(dāng)且僅當(dāng)(f(vi),f(vj))E2

（<vi,vj>E1當(dāng)且僅當(dāng)<f(vi),f(vj)>E2)（2）(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重?cái)?shù)相同。則稱G1與G2是同構(gòu)的，記作G1G2.18第十八頁，共二十二頁，2022年，8月28日圖同構(gòu)的必要條件圖之間的同構(gòu)關(guān)系是等價(jià)關(guān)系.同構(gòu)的必要條件：①邊數(shù)相同，頂點(diǎn)數(shù)相同;②度數(shù)列相同;③度數(shù)相同的結(jié)點(diǎn)數(shù)目相同19第十九頁，共二十二頁，2022年，8月28日圖同構(gòu)的實(shí)例

(1)(2)(3)(4)圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu).20第二十頁，共二十二頁，2022年，8月28日六、圖的表示——鄰接矩陣21第二十一