《節(jié)點(diǎn)的度數(shù)》幻燈片課件

1、節(jié)點(diǎn)的度數(shù)幻燈片 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請(qǐng)自行刪除，謝謝！ 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請(qǐng)自行刪除，謝謝！ 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請(qǐng)自行刪除，謝謝！ 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請(qǐng)自行刪除，謝謝！節(jié)點(diǎn)的度數(shù)幻燈片 本課件PPT僅供大家學(xué)習(xí)使用 6.2 節(jié)點(diǎn)的度數(shù)第6章 圖論6.2 節(jié)點(diǎn)的度數(shù)第6章 圖論本講內(nèi)容無(wú)向圖節(jié)點(diǎn)的度數(shù)1有向圖節(jié)點(diǎn)的出度、入度和度數(shù)2握手定理3k-正則圖、最大(小)度、度數(shù)序列4本講內(nèi)容無(wú)向圖節(jié)點(diǎn)的度數(shù)1有向圖節(jié)點(diǎn)的出度、入度和度數(shù)2握手6.2 節(jié)點(diǎn)的度數(shù)從一個(gè)地方出發(fā)的橋的數(shù)目就是對(duì)應(yīng)節(jié)點(diǎn)的度數(shù).邊與節(jié)點(diǎn)的關(guān)聯(lián)次數(shù)?6.2

2、節(jié)點(diǎn)的度數(shù)從一個(gè)地方出發(fā)的橋的數(shù)目就是對(duì)應(yīng)節(jié)點(diǎn)的度數(shù)Def 設(shè)G = (V, E)是無(wú)向圖, v V, 稱與節(jié)點(diǎn)v關(guān)聯(lián)的所有邊的關(guān)聯(lián)次數(shù)之和為節(jié)點(diǎn)v的度數(shù)(degree),記為deg(v).一個(gè)環(huán)算2度?Def 設(shè)G = (V, E)是無(wú)向圖, v V, 稱Def 設(shè)G = (V, E)是有向圖, v V:deg+(v) = od(v); deg-(v) = id(v); deg (v) = od(v)+ id(v).一個(gè)環(huán)算2度?Def 設(shè)G = (V, E)是有向圖, v V:下面的定理是L. Euler在1736年證明的圖論中的第一定理, 常稱為“握手(?)定理.Theorem 6-1

3、在任何(n, m)圖G = (V, E)中, 其所有節(jié)點(diǎn)度數(shù)之和等于邊數(shù)m的2倍, 即下面的定理是L. Euler在1736年證明的圖論中的第一定Corollary 在任意圖G = (V, E)中, 度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必為偶數(shù).Proof Corollary 在任意圖G = (V, E)中, 度數(shù)為由定理及其推論很容易知道,在任何一次聚會(huì)上, 所有人握手次數(shù)之和必為偶數(shù)并且握了奇數(shù)次手的人數(shù)必為偶數(shù).(環(huán)的解釋?)在任意有向圖中, 顯然有Theorem 6-2 在任意有向圖中, 所有節(jié)點(diǎn)的出度之和等于入度之和.由定理及其推論很容易知道,在任何一次聚會(huì)上, 所有人握手次數(shù)在任意圖中, 度數(shù)為0

4、的節(jié)點(diǎn)稱為孤立點(diǎn)(isolated vertex), 度數(shù)為1的節(jié)點(diǎn)稱為懸掛點(diǎn)(pendant vertex).在任意圖中, 度數(shù)為0的節(jié)點(diǎn)稱為孤立點(diǎn)(isolated v例6-1 證明: 對(duì)于任意n(n2)個(gè)人的組里, 必有兩個(gè)人有一樣個(gè)數(shù)的朋友.Proof 將組里的每個(gè)人看作節(jié)點(diǎn), 兩個(gè)人是朋友當(dāng)且僅當(dāng)對(duì)應(yīng)的節(jié)點(diǎn)鄰接, 于是得到一個(gè)n階簡(jiǎn)單無(wú)向圖G, 進(jìn)而G中每節(jié)點(diǎn)的度數(shù)可能為0, 1, 2, , n - 1中一個(gè). 例6-1 證明: 對(duì)于任意n(n2)個(gè)人的組里, 必有兩個(gè)當(dāng)G中無(wú)孤立點(diǎn)時(shí),于是每節(jié)點(diǎn)的度數(shù)可能為1, 2, , n - 1. 由于共有n個(gè)節(jié)點(diǎn), 于是必有兩節(jié)點(diǎn)度數(shù)一樣.當(dāng)

5、G中有孤立點(diǎn)時(shí),這時(shí)每節(jié)點(diǎn)的度數(shù)只可能為0, 1, 2, , n - 2. 同樣由于共n有個(gè)節(jié)點(diǎn), 因此必有兩節(jié)點(diǎn)度數(shù)一樣.當(dāng)G中無(wú)孤立點(diǎn)時(shí),于是每節(jié)點(diǎn)的度數(shù)可能為1, 2, , n假設(shè)一個(gè)Simple無(wú)向圖G的每節(jié)點(diǎn)度數(shù)均為k, 那么稱G為k-正那么圖(k-regular graph). 假設(shè)一個(gè)Simple無(wú)向圖G的每節(jié)點(diǎn)度數(shù)均為k, 那么稱G為例6-2 設(shè)無(wú)向圖G是一個(gè)3-正那么(n, m)圖, 且2n 3 = m, 求n和m各是多少? Hint 根據(jù)握手定理有:例6-2 設(shè)無(wú)向圖G是一個(gè)3-正那么(n, m)圖, Def 6-9任意圖G = (V, E):有向圖G = (V, E):例

6、子?Def 6-9對(duì)于無(wú)向圖G = (V, E), V = v1, v2, , vn,稱deg(v1), deg(v2), , deg(vn)為的度數(shù)序列. 對(duì)于有向圖, 還可以定義其出度序列和入度序列.例6-3 是否存在一個(gè)無(wú)向圖G, 其度數(shù)序列分別為(1) 7, 5, 4, 2, 2, 1.(2) 4, 4, 3, 3, 2, 2.(度數(shù)序列與節(jié)點(diǎn)排列 順序關(guān)系不大)對(duì)于無(wú)向圖G = (V, E), V = v1, v2, Solution (1)由于序列7, 5, 4, 2, 2, 1中, 奇數(shù)個(gè)數(shù)為奇數(shù). 根據(jù)握手定理的推論知, 不可能存在一個(gè)圖其度數(shù)序列為7, 5, 4, 2, 2,

7、 1.(2) 因?yàn)樾蛄?, 4, 3, 3, 2, 2中, 奇數(shù)個(gè)數(shù)為偶數(shù), 可以得到一個(gè)無(wú)向圖(見圖7-11),其度數(shù)序列為4, 4, 3, 3, 2, 2.Solution (1)由于序列7, 5, 4, 2, 2,RemarkI. (G)節(jié)點(diǎn)相當(dāng)Hub節(jié)點(diǎn): 魯棒而脆弱.R.Albert, H.Jeong, A.L.Barabasi.The Internets Achilles heel: Error and attack tolerance of complex networks.Nature , 2000, 406: 378-382.RemarkII.度數(shù)序列分布.A.L.Barabasi , R.Albert et al.Power-law distribution of the World Wide Web.Science , 2000, 287: 130-131.II.度數(shù)序列分布.小結(jié)與作業(yè)無(wú)向圖節(jié)點(diǎn)的度數(shù)有向圖節(jié)點(diǎn)的出度、入度和度數(shù)握手定理k