圖的基本概念

1 圖

1.1 圖的定義

定義1： 一個(gè)無(wú)向圖G是一個(gè)有序的二元組<V,E>，其中
（1）V是一個(gè)非空有窮集，稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)。
（2）E是無(wú)序積V&V的有窮多重子集，稱(chēng)為邊集，其元素稱(chēng)為無(wú)向邊，簡(jiǎn)稱(chēng)邊。

定義2： 一個(gè)有向圖D是一個(gè)有序的二元組<V,E>，其中
（1）V是一個(gè)非空有窮集，稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)。
（2）E是笛卡爾積VXV的有窮多重子集，稱(chēng)為邊集，其元素稱(chēng)為有向邊，簡(jiǎn)稱(chēng)邊。

在圖G中,

• 如果每條邊都是有向邊, 該圖稱(chēng)為有向圖(Directed Graph)
• 若每條邊都是無(wú)向邊, 該圖G稱(chēng)為無(wú)向圖(Undirected Graph)
• 如果有些邊是有向邊, 另一些邊是無(wú)向邊, 圖G稱(chēng)為混合圖(Mixed Graph)

定義3：
（1）無(wú)向圖和有向圖統(tǒng)稱(chēng)為圖，但有時(shí)把無(wú)向圖簡(jiǎn)稱(chēng)為圖，統(tǒng)常用G表示無(wú)向圖，D表示有向圖。
（2）頂點(diǎn)數(shù)稱(chēng)作圖的階，n個(gè)頂點(diǎn)的圖稱(chēng)為n階圖。
（3）一條邊也沒(méi)有的圖稱(chēng)為零圖，n階零圖記作$N_n$,一階零圖$N_1$稱(chēng)為平凡圖(平凡圖只有一個(gè)頂點(diǎn)，沒(méi)有邊)。
（4）將有向圖的各條有向邊改成無(wú)向邊后所得到的無(wú)向圖稱(chēng)為這個(gè)有向圖的基圖。
（5）設(shè)G=<V,E>為無(wú)向圖，$e_k=(v_i,v_j)$∈E，稱(chēng)$v_i,v_j$為$e_k$的端點(diǎn)，$e_k$與$v_i,v_j$關(guān)聯(lián)。

• 若$v_i\ne v_j$,則稱(chēng)$e_k$與$v_i,v_j$的關(guān)聯(lián)次數(shù)是1。
• 若$v_i=v_j$,則稱(chēng)$e_k$與$v_i,v_j$的關(guān)聯(lián)次數(shù)是2，并稱(chēng)$e_k$為環(huán)。
• 如果頂點(diǎn)$v_i,v_j$不與邊$e_k$關(guān)聯(lián)，則稱(chēng)$e_k$與$v_i,v_j$的關(guān)聯(lián)次數(shù)是0。
• 若兩個(gè)頂點(diǎn)$v_i與v_j$之間有一條邊連接，則稱(chēng)這兩個(gè)頂點(diǎn)相鄰，若兩條邊至少有一個(gè)公共端點(diǎn)，則稱(chēng)這兩條邊相鄰。

（6）圖(無(wú)向的或有向的)中沒(méi)有邊關(guān)聯(lián)的頂點(diǎn)稱(chēng)為孤立點(diǎn)。
（7）在無(wú)向圖中，如果關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊多于一條，則稱(chēng)這些邊為平行邊，平行邊的條數(shù)稱(chēng)為重?cái)?shù)。（平行邊的條數(shù)是n-1）在有向圖中，如果關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊多于1條，并且這些邊的始點(diǎn)終點(diǎn)相同(它們的方向相同)，則稱(chēng)這些邊為平行邊，含平行邊的圖稱(chēng)為多重圖，即不含平行邊也不含環(huán)的圖稱(chēng)為簡(jiǎn)單圖。

（8）設(shè)G=<V,E>為無(wú)向圖，$?v$∈V，稱(chēng)$v$作為邊的端點(diǎn)的次數(shù)為$v$的度數(shù)，簡(jiǎn)稱(chēng)度，記作$d(v)$。設(shè)D=<V,E>為有向圖，$?v$∈V，稱(chēng)$v$作為邊的始點(diǎn)的次數(shù)為$v$的出度，記作$d^{+}(v)$,稱(chēng)$v$作為邊的終點(diǎn)的次數(shù)為$v$的入度，記作$d^{?}(v)$，稱(chēng)$d^{+}(v)$+$d^{?}(v)$為$v$的度數(shù)，記作$d(v)$。

1.2 握手定理

定理1：在任何無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。
? ? ?在任何有向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍；所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和，都等于邊數(shù)。

$\sum _{v\in V}d(v)=2m,（其中d(v)是度數(shù)之和，m是邊數(shù)）$

定理2：任何圖中(無(wú)向圖或有向圖)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)（要滿足握手定律，偶數(shù)個(gè)奇度頂點(diǎn)的和為偶數(shù)，滿足2倍關(guān)系）。
定理3：設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則$△(G)?n?1$。（$△(G)$代表最大度數(shù)，n代表頂點(diǎn)數(shù)(階數(shù))，一個(gè)圖的最大度數(shù)一定小于等于頂點(diǎn)數(shù)減一）。

1.3 圖的同構(gòu)

定義：設(shè)G=(V, E),G′=(V′, E′)同為無(wú)向圖或有向圖, 若存在雙射??: V→V′, 使得:

• 對(duì)無(wú)向圖, (??, ??)∈E?(??(??), ??(??))∈E′
• 對(duì)有向圖, <??, ??>∈E?<??(??), ??(??)>∈E′
  且對(duì)應(yīng)邊重?cái)?shù)相同, 則稱(chēng)G與G′是同構(gòu)(Isomorphic)的, 記為G?G′。

注意：由同構(gòu)的定義可知, 不僅結(jié)點(diǎn)之間要具有一一對(duì)應(yīng)關(guān)系, 而且要求這種對(duì)應(yīng)關(guān)系保持結(jié)點(diǎn)間的鄰接關(guān)系。對(duì)于有向圖的同構(gòu)還要求保持邊的方向。

1.4 補(bǔ)圖

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-537253.html

到了這里，關(guān)于離散數(shù)學(xué)-圖論-圖的基本概念（11）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！