版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、圖論圖的基本概念教師:孫繼榮電話:87768609Email:1圖論圖的基本概念教學要求理解圖的概念:結(jié)點、邊、有向圖,無向圖、圖的同構(gòu)、簡單圖、完全圖、結(jié)點的度數(shù)、子圖、邊的重數(shù)和平行邊等理解握手定理了解通路與回路概念:通路(簡單通路、初級通路和復雜通路),回路(簡單回路、初級回路和復雜回路) ,會求通路和回路的長度了解無向圖的連通性,會求無向圖的連通分支。了解點割集、割點、邊割集、割邊、點連通度、邊連通度等概念了解有向圖的強連通強性;會判別其類型了解(有向圖、無向圖)關(guān)聯(lián)矩陣、(無向圖)相鄰矩陣和(有向圖)鄰接矩陣的概念,掌握構(gòu)造方法及其應(yīng)用。知道帶權(quán)圖、最短通路概念,知道關(guān)鍵路徑概念 2
2、圖論圖的基本概念學習內(nèi)容: 圖的概念 (圖的表示,有向圖、無向圖、度、同構(gòu)) 圖的矩陣表示 (鄰接矩陣,關(guān)聯(lián)矩陣) 3圖論圖的基本概念本章重點圖的概念握手定理通路回路圖的矩陣表示. 4圖論圖的基本概念圖的基本概念圖是指某些具體的事物以及這些事物之間的聯(lián)系圖是一個有序?qū)?,V是結(jié)點集,E是邊集,當V,E有限時,稱為有限圖;否則稱無限圖. 無向邊, 與無序結(jié)點(v,u)相關(guān)聯(lián)的邊有向邊,與有序結(jié)點相關(guān)聯(lián)的邊.無向圖,每條邊都是無向邊的圖,記作G; 每條邊都是有向邊的圖,記作D.混合圖,既有有向邊,也有無向邊的圖. 5圖論圖的基本概念圖的基本概念平凡圖,僅有一個結(jié)點的圖;零圖(空圖):邊集為空集的圖,
3、即僅有結(jié)點的圖. 自回路(環(huán)),關(guān)聯(lián)于同一個結(jié)點的邊. 無向平行邊,聯(lián)結(jié)相同兩個結(jié)點的多于1條的無向邊;有向平行邊,聯(lián)結(jié)兩個結(jié)點之間的多于1條且方向相同的有向邊. 簡單圖,不含平行邊和自回路的圖. 6圖論圖的基本概念圖的基本概念在無向圖G中,與結(jié)點v(V)關(guān)聯(lián)的邊數(shù),即為結(jié)點度數(shù)deg(v)或d(v).;有向圖G中,以結(jié)點v為始點的變的條數(shù)為該點的出度,記作deg+(v);以結(jié)點v為終點的邊為該點的入度,記作deg(v);結(jié)點v的出度和入度之和為度數(shù). 最大度數(shù),(G)maxd(v)vV; 最小度數(shù),(G)=mind(v)vV7圖論圖的基本概念1圖的基本概念有n個結(jié)點的且每對結(jié)點都有邊相連無向
4、簡單圖,無向完全圖Kn. 此時有 ;有n個結(jié)點的且每對結(jié)點之間都有兩條方向相反的邊相關(guān)連的有向簡單圖為有向完全圖,.此時有設(shè)G, V,E的子集V,E構(gòu)成的圖G=是圖G的子圖;若GG且GG,(VV或EE),G是G的真子圖.生成子圖,設(shè)圖G, 若EE, 則圖是的生成子圖. 即結(jié)點與原圖G相同的子圖,為生成子圖. 8圖論圖的基本概念圖的基本概念補圖 G=,設(shè)G, 以V為結(jié)點集,以使G成為完全圖所添加的邊為邊集E的圖,就是圖G的補圖G ,即是完全圖, 其中EE.圖的同構(gòu),設(shè)G1=和G2=, 存在雙射f:V1V2,(vi,vj)E1, 當且僅當 (f(vi),f(vj)E2,且(vi,vj)與 (f(v
5、i),f(vj)的重數(shù)相同. 則G1G2.同構(gòu)充分條件:建立兩個圖的對應(yīng)關(guān)系,這個關(guān)系是雙射函數(shù). 同構(gòu)必要條件:結(jié)點數(shù)相同;邊數(shù)相同;度數(shù)相同的結(jié)點個數(shù)相同. 9圖論圖的基本概念圖的基本概念握手定理:結(jié)點度數(shù)之和為邊數(shù)的兩倍 設(shè)G=,有在有向圖圖D中,奇數(shù)度結(jié)點的個數(shù)為偶數(shù)個. 如果一個圖中只有兩個奇數(shù)度節(jié)點,則這兩個節(jié)點相連通。10圖論圖的基本概念通路、回路、圖的連通性 通路與通路的長度,設(shè)圖G,Vv0,v1,vn,E=e1,e2,em,結(jié)點與邊的交替序列v0e1v1e2vi-1eivi,成為結(jié)點v0到結(jié)點vi的通路. v0,vi是通路的起點和終點. 通路中邊的數(shù)目就是通路的長度. 回路,
6、起點和終點重合的通路. 簡單通路(回路):邊不重復的通路(回路). 初級通路(回路):結(jié)點不重復的通路(回路). 復雜通路(回路):邊有重復的通路(回路). 11圖論圖的基本概念通路、回路、圖的連通性定理:若圖中具有n各結(jié)點,從結(jié)點vi多幅奧結(jié)點vj存在一條通路,則從vi到vj存在一條不多于n1條邊的通路推論:在一個具有n個結(jié)點的圖中,如果存在結(jié)點vi到vj的一條通路,則必存在一條從vi到vj的不多于n1條邊的初級通路定理:在一個具有n個結(jié)點的圖中,如果存在結(jié)點vi到自身的回路,則從vi到自身存在不多于n條邊的回路。推論:在一個具有n個結(jié)點的圖中,如果存在結(jié)點vi到自身的簡單回路,則從vi到自
7、身存在不多于n條邊的初級回路。12圖論圖的基本概念通路、回路、圖的連通性連通與連通圖,無向圖G中,結(jié)點u,v存在通路,那么u,v是連通的,G中任意結(jié)點u,v都是連通的,G是連通圖. 連通分支,設(shè)G,V的連通等價類V1,V2,,Vm,子圖G(V1),G(V2),G(Vm)成為連通分支,P(G)表示圖G連通分支的個數(shù). 13圖論圖的基本概念通路、回路、圖的連通性點割集與割點,設(shè)無向圖G,存在結(jié)點集VV,使得P(GV)P(G),而對任意VV,都有P(GV)P(G),V稱為圖G的點割集. 若V是單元集,Vv,v叫做割點. 邊割集與割邊,設(shè)無向圖G,存在邊集EE,使得P(GV)P(G),而對任意EE,都
8、有P(GE)P(G),E稱為圖G的邊割集. 若E是單元集,Ee,e叫做割邊(橋). 14圖論圖的基本概念通路、回路、圖的連通性點連通度:最小的點割集的點數(shù)目邊連通度:最小的邊割集的邊數(shù)目定理5:15圖論圖的基本概念通路、回路、圖的連通性單側(cè)通路,有向圖中,任意一對結(jié)點之間至少有一個結(jié)點可達另一結(jié)點. 強連通,在有向圖中任何一對結(jié)點都相互可達. 弱連通,略去有向圖D各邊的方向成為無向連通圖,稱D是弱連通圖. 由定義可知:強連通 單側(cè)連通 弱連通. 16圖論圖的基本概念通路、回路、圖的連通性定理:一個有向圖是強連通的充分必要條件是G中有一個回路,它至少經(jīng)過每個結(jié)點一次的。強分圖:既有強連通性的最大
9、子圖單側(cè)分圖:既有單側(cè)連通性的最大子圖弱分圖:既有弱連通性的最大子圖定理:在有向圖D中,它的每個結(jié)點位于且僅位于一個強分圖中17圖論圖的基本概念圖的矩陣表示 (無向圖)關(guān)聯(lián)矩陣設(shè)G=, 關(guān)聯(lián)矩陣M(G)= ,其中mij=vi與ej的關(guān)聯(lián)次數(shù)(行為結(jié)點,列為邊) 性質(zhì):列元素和為2行元素和為結(jié)點的度數(shù)若行元素和為0,則對應(yīng)的結(jié)點為孤立點全部元素之和為G的總度數(shù)平行邊對應(yīng)的兩列完全相同18圖論圖的基本概念圖的矩陣表示(無向圖)相鄰矩陣:設(shè)G, ,相鄰矩陣 A(G)= ,其中aij =vi與vj相關(guān)聯(lián)的邊的條數(shù)(行、列均為結(jié)點) 性質(zhì):A(G)是對稱矩陣對角線上的元素表示該結(jié)點處環(huán)的個數(shù) ,若vi是
10、孤立結(jié)點,則19圖論圖的基本概念圖的矩陣表示(無環(huán)有向圖)關(guān)聯(lián)矩陣:設(shè)D=, 關(guān)聯(lián)矩陣M(D)= , (行為結(jié)點,列為邊),其中20圖論圖的基本概念圖的矩陣表示(無環(huán)有向圖)關(guān)聯(lián)矩陣: ,列元素和為0每行元素絕對值之和等于對應(yīng)點的度數(shù),其中1的個數(shù)為對應(yīng)點的出度,1的個數(shù)為對應(yīng)電的入度所有元素的和為0,1的個數(shù)等于1的個數(shù),都等于邊數(shù)m21圖論圖的基本概念圖的矩陣表示(有向圖)鄰接矩陣:設(shè)D,相鄰矩陣 A(D)= ,其中aij =vi鄰接到vj的邊的條數(shù)(行、列均為結(jié)點)所有元素之和為D中長度為1的通路 有向圖的鄰接矩陣不一定對稱22圖論圖的基本概念圖的矩陣表示由有向圖D的鄰接矩陣推斷從ai到aj 的長度為l的通路的數(shù)目:Al(D)由有向圖D的鄰接矩陣推斷D的可達矩陣P(D) P(D)= ,其中 P(D) A1(D) A2(D) An(D)將其中大于0的元素都改為1,再將主對角線上的元素改為1。23圖論圖的基本概念最短路徑和關(guān)鍵路徑帶權(quán)圖:G,其中W
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 云南警官學院《柳琴戲藝術(shù)概論》2023-2024學年第一學期期末試卷
- 配電設(shè)施運行安全與事故預防制度
- 餐廳業(yè)績月度總結(jié)模板
- 業(yè)務(wù)操作-房地產(chǎn)經(jīng)紀人《業(yè)務(wù)操作》真題匯編3
- 全球旅游業(yè)年度總結(jié)模板
- 三育人先進個人主要事跡
- 二零二五年飯店員工勞動合同及員工培訓經(jīng)費保障合同2篇
- 人教版三年級數(shù)學下冊第四單元兩位數(shù)乘兩位數(shù)綜合卷(含答案)
- 二零二五版小學教師崗位績效評價與激勵機制合同3篇
- 煙臺南山學院《工程管理專業(yè)概論》2023-2024學年第一學期期末試卷
- 居家辦公培訓課件
- (規(guī)劃設(shè)計)家具產(chǎn)業(yè)園項目可行性研究報告
- 2024中國誠通控股集團限公司總部招聘11人易考易錯模擬試題(共500題)試卷后附參考答案
- 2025初級會計理論考試100題及解析
- 2024屆高考英語詞匯3500左右
- 績效管理數(shù)字化轉(zhuǎn)型
- 2025年山東省高考數(shù)學模擬試卷(附答案解析)
- 部編人教版小學4四年級《道德與法治》下冊全冊教案
- 《BIM土建算量與云計價》完整課件
- 新客戶建檔協(xié)議書范文范本
- 心房顫動診斷和治療中國指南(2023) 解讀
評論
0/150
提交評論