




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、節(jié)點的度數(shù)幻燈片 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請自行刪除,謝謝! 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請自行刪除,謝謝! 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請自行刪除,謝謝! 本課件PPT僅供大家學(xué)習(xí)使用 學(xué)習(xí)完請自行刪除,謝謝!節(jié)點的度數(shù)幻燈片 本課件PPT僅供大家學(xué)習(xí)使用 6.2 節(jié)點的度數(shù)第6章 圖論6.2 節(jié)點的度數(shù)第6章 圖論本講內(nèi)容無向圖節(jié)點的度數(shù)1有向圖節(jié)點的出度、入度和度數(shù)2握手定理3k-正則圖、最大(小)度、度數(shù)序列4本講內(nèi)容無向圖節(jié)點的度數(shù)1有向圖節(jié)點的出度、入度和度數(shù)2握手6.2 節(jié)點的度數(shù)從一個地方出發(fā)的橋的數(shù)目就是對應(yīng)節(jié)點的度數(shù).邊與節(jié)點的關(guān)聯(lián)次數(shù)?6.2
2、節(jié)點的度數(shù)從一個地方出發(fā)的橋的數(shù)目就是對應(yīng)節(jié)點的度數(shù)Def 設(shè)G = (V, E)是無向圖, v V, 稱與節(jié)點v關(guān)聯(lián)的所有邊的關(guān)聯(lián)次數(shù)之和為節(jié)點v的度數(shù)(degree),記為deg(v).一個環(huán)算2度?Def 設(shè)G = (V, E)是無向圖, v V, 稱Def 設(shè)G = (V, E)是有向圖, v V:deg+(v) = od(v); deg-(v) = id(v); deg (v) = od(v)+ id(v).一個環(huán)算2度?Def 設(shè)G = (V, E)是有向圖, v V:下面的定理是L. Euler在1736年證明的圖論中的第一定理, 常稱為“握手(?)定理.Theorem 6-1
3、在任何(n, m)圖G = (V, E)中, 其所有節(jié)點度數(shù)之和等于邊數(shù)m的2倍, 即下面的定理是L. Euler在1736年證明的圖論中的第一定Corollary 在任意圖G = (V, E)中, 度數(shù)為奇數(shù)的節(jié)點個數(shù)必為偶數(shù).Proof Corollary 在任意圖G = (V, E)中, 度數(shù)為由定理及其推論很容易知道,在任何一次聚會上, 所有人握手次數(shù)之和必為偶數(shù)并且握了奇數(shù)次手的人數(shù)必為偶數(shù).(環(huán)的解釋?)在任意有向圖中, 顯然有Theorem 6-2 在任意有向圖中, 所有節(jié)點的出度之和等于入度之和.由定理及其推論很容易知道,在任何一次聚會上, 所有人握手次數(shù)在任意圖中, 度數(shù)為0
4、的節(jié)點稱為孤立點(isolated vertex), 度數(shù)為1的節(jié)點稱為懸掛點(pendant vertex).在任意圖中, 度數(shù)為0的節(jié)點稱為孤立點(isolated v例6-1 證明: 對于任意n(n2)個人的組里, 必有兩個人有一樣個數(shù)的朋友.Proof 將組里的每個人看作節(jié)點, 兩個人是朋友當且僅當對應(yīng)的節(jié)點鄰接, 于是得到一個n階簡單無向圖G, 進而G中每節(jié)點的度數(shù)可能為0, 1, 2, , n - 1中一個. 例6-1 證明: 對于任意n(n2)個人的組里, 必有兩個當G中無孤立點時,于是每節(jié)點的度數(shù)可能為1, 2, , n - 1. 由于共有n個節(jié)點, 于是必有兩節(jié)點度數(shù)一樣.當
5、G中有孤立點時,這時每節(jié)點的度數(shù)只可能為0, 1, 2, , n - 2. 同樣由于共n有個節(jié)點, 因此必有兩節(jié)點度數(shù)一樣.當G中無孤立點時,于是每節(jié)點的度數(shù)可能為1, 2, , n假設(shè)一個Simple無向圖G的每節(jié)點度數(shù)均為k, 那么稱G為k-正那么圖(k-regular graph). 假設(shè)一個Simple無向圖G的每節(jié)點度數(shù)均為k, 那么稱G為例6-2 設(shè)無向圖G是一個3-正那么(n, m)圖, 且2n 3 = m, 求n和m各是多少? Hint 根據(jù)握手定理有:例6-2 設(shè)無向圖G是一個3-正那么(n, m)圖, Def 6-9任意圖G = (V, E):有向圖G = (V, E):例
6、子?Def 6-9對于無向圖G = (V, E), V = v1, v2, , vn,稱deg(v1), deg(v2), , deg(vn)為的度數(shù)序列. 對于有向圖, 還可以定義其出度序列和入度序列.例6-3 是否存在一個無向圖G, 其度數(shù)序列分別為(1) 7, 5, 4, 2, 2, 1.(2) 4, 4, 3, 3, 2, 2.(度數(shù)序列與節(jié)點排列 順序關(guān)系不大)對于無向圖G = (V, E), V = v1, v2, Solution (1)由于序列7, 5, 4, 2, 2, 1中, 奇數(shù)個數(shù)為奇數(shù). 根據(jù)握手定理的推論知, 不可能存在一個圖其度數(shù)序列為7, 5, 4, 2, 2,
7、 1.(2) 因為序列4, 4, 3, 3, 2, 2中, 奇數(shù)個數(shù)為偶數(shù), 可以得到一個無向圖(見圖7-11),其度數(shù)序列為4, 4, 3, 3, 2, 2.Solution (1)由于序列7, 5, 4, 2, 2,RemarkI. (G)節(jié)點相當Hub節(jié)點: 魯棒而脆弱.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è)無向圖節(jié)點的度數(shù)有向圖節(jié)點的出度、入度和度數(shù)握手定理k
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024游泳救生員職業(yè)試題及答案全解析
- 如何利用自我反思提升體育經(jīng)紀人考試能力 試題及答案
- 手工焊接與返修的技術(shù)培訓(xùn)
- 如何進行比賽記錄的試題及答案
- 模具設(shè)計師資格考試實例分析試題與答案
- 2023年公務(wù)員多省聯(lián)考《申論》題(重慶三卷)筆試試題試卷真題及答案解析
- 2025年公務(wù)員考試省考行測四川卷試題真題試卷答案解析
- 游泳救生員突發(fā)情況應(yīng)對試題及答案
- 2024年湖北省考公務(wù)員考試縣鄉(xiāng)崗結(jié)構(gòu)化面試真題試題試卷答案解析
- (高清版)DB50∕T 798-2017 渝小吃 牛肉焦包烹飪技術(shù)規(guī)范
- 30條人性潛規(guī)則大部分人一輩子都沒看明白
- 義務(wù)教育道德與法治課程標準試題(2022版)
- 軟件系統(tǒng)功能需求調(diào)研表信息系統(tǒng)項目需求調(diào)研表
- GB/T 3956-2008電纜的導(dǎo)體
- 美國史-教學(xué)講解課件
- 第六章-復(fù)合材料課件
- 民事訴訟法學(xué)課件第十四章
- 小學(xué)三年級音樂《馬蘭謠》課件
- 大學(xué)有機化學(xué)復(fù)習(xí)重點
- 國家開放大學(xué)《大學(xué)語文》形考任務(wù)1-5參考答案
- 汽車起重機基本結(jié)構(gòu)、工作原理課件
評論
0/150
提交評論