低調(diào)而不簡(jiǎn)單的優(yōu)美句子：一心一意寫一個(gè)喜歡的故事

1、2022-5-71圖是一類相當(dāng)廣泛的實(shí)際問題的數(shù)學(xué)模型，有著極其豐富的內(nèi)容，是數(shù)據(jù)結(jié)構(gòu)等課程的先修內(nèi)容.學(xué)習(xí)時(shí)應(yīng)掌握好圖論的基本概念、基本方法、基本算法；善于把實(shí)際問題抽象為圖論的問題，然后用圖論的方法解決問題.http:/ 1.基本概念有:路,路的起點(diǎn),路的終點(diǎn),路的長(zhǎng)度,開路,閉路,簡(jiǎn)單路,回路,基本路,圈,連通,連通分支,連通圖,兩點(diǎn)間的距離,可達(dá),強(qiáng)連通圖,單向連通圖,弱連通圖,權(quán)圖,權(quán),迪克斯特拉算法等；2022-5-742.主要結(jié)論: 設(shè)G=(V,E)是圖，且|V|=n,若存在結(jié)點(diǎn)u到v的路，則必存在u到v的長(zhǎng)度不超過n-1的路. 3.算法:迪克斯特拉(Dijkstra)算法,迪克

2、斯特拉算法是圖論中最基本的算法,應(yīng)很好地掌握. 2022-5-75l本節(jié)主要考慮三種矩陣，即鄰接矩陣，可達(dá)矩陣與關(guān)聯(lián)矩陣.鄰接矩陣反映的是頂點(diǎn)與頂點(diǎn)之間的關(guān)系；可達(dá)矩陣反映了圖的聯(lián)通情況；關(guān)聯(lián)矩陣反映的是頂點(diǎn)與邊（?。┑年P(guān)系. 分有向圖與無向圖來討論.2022-5-76l在討論集合的二元關(guān)系時(shí)，我們就給出了關(guān)系的圖形表示，即關(guān)系圖.這里用圖論的方法給出關(guān)系圖的嚴(yán)格定義. l關(guān)系中的很多性質(zhì)可以在關(guān)系圖上反映出來 ,可以通過圖來研究關(guān)系,也可以通過關(guān)系來研究圖.2022-5-77l歐拉圖是一類非常著名的圖，之所以如此，不僅是因?yàn)闅W拉是圖論的創(chuàng)始人，更主要是歐拉圖具有對(duì)邊（?。┑摹氨闅v性”. 1.

3、概念有:歐拉路,歐拉圖,半歐拉路,半歐拉圖,割邊等；2022-5-782.結(jié)論有:(1)無向連通圖G是歐拉圖的充要條件是G中每個(gè)頂點(diǎn)的度均為偶數(shù)； (2)設(shè)G是無向連通圖，則G是半歐拉圖的充要條件是G恰含有兩個(gè)奇數(shù)度點(diǎn). 3.算法:在歐拉圖中找歐拉路的Fleury算法.2022-5-79l哈密爾頓圖是一類實(shí)際背景很強(qiáng)的圖論模型,與歐拉圖不同，哈密爾頓圖感興趣的是遍歷圖中的諸頂點(diǎn).1.主要概念:哈密爾頓路,半哈密爾頓圖,哈密爾頓回路,哈密爾頓圖,圖的閉包；2.主要結(jié)論:哈密頓圖的判定，至今也還沒有令人滿意地結(jié)果.下面的一些哈密頓圖的結(jié)果都只是充分條件或必要條件，而非充要條件. 2022-5-71

4、0(1)設(shè)G=(V,E)是哈密爾頓圖，則對(duì)V的任意非空子集S均有W(G-S) |S|,其中G-S表示在G中刪除S中的點(diǎn)以及以S為端點(diǎn)的邊后所構(gòu)成的圖；W(G-S)表示G-S的連通分支數(shù);(2)設(shè)G=(V,E)是n階無向簡(jiǎn)單圖，若對(duì)G中任意不相鄰的頂點(diǎn)u,v都有d(u)+d(v) n-1,則G存在哈密爾頓路，因此G是半哈密爾頓圖；(3)設(shè)G是n階簡(jiǎn)單圖，則是哈密爾頓圖當(dāng)且僅當(dāng)其閉包是哈密爾頓圖. 2022-5-711l二分圖也是一類實(shí)際背景很強(qiáng)的圖論模型,在1已給出了二分圖的定義,二分圖與圖的匹配有密切關(guān)系.1.基本概念:二分圖,匹配,最大匹配,飽和,非飽和,完美匹配,交錯(cuò)路,可擴(kuò)路,鄰集等;2.結(jié)論:(1)設(shè)G是無向簡(jiǎn)單圖,則G是二分圖的充要條件是它的所有回路的長(zhǎng)度為偶數(shù);2022-5-712(2)圖G的匹配M是最大匹配當(dāng)且僅當(dāng)G不含M的可擴(kuò)路;(3)設(shè)G=(V,E)為二分圖,頂點(diǎn)劃分為V= V1 V2 ,則G存在飽和V1的每個(gè)頂點(diǎn)匹配的充要條件是對(duì)任何S V1均有|N(S)|S|；3.算法：匈牙利算法，解決了二分圖的匹配問題。 2022-5-713l本章我們僅討論無向圖與有向圖、我們首先給出圖的一些基本概念和術(shù)語，比如，路、回路、連通性、鄰接矩陣、關(guān)聯(lián)矩陣等；給出了圖論