图论应用与心得
圖論是離散數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖可以用來(lái)表現(xiàn)多種類(lèi)型的結(jié)構(gòu)或系統(tǒng)，地圖、社交網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)聯(lián)通、迷宮游戲等多種結(jié)構(gòu)及系統(tǒng)都可以用圖來(lái)表示。樹(shù)是圖論中應(yīng)用最為廣泛的一類(lèi)圖。在理論上，由于樹(shù)的簡(jiǎn)單結(jié)構(gòu)，常常是圖論理論研究的“試驗(yàn)田”。在實(shí)際問(wèn)題中，許多實(shí)際問(wèn)題的圖論模型就是樹(shù)。
以圖作為模型，來(lái)表示真實(shí)世界之間的關(guān)系，那么可以表示什么樣的關(guān)系呢？從表面上看，這種形式好像很簡(jiǎn)單，也很枯燥，但是它的內(nèi)涵卻很豐富，如下：
最典型的莫過(guò)于交通運(yùn)輸，它可以使用圖來(lái)表達(dá)，如：每個(gè)頂點(diǎn)可以是一個(gè)城市，每條邊可以是城市之間的道路再擴(kuò)展一下，每個(gè)頂點(diǎn)可以是一個(gè)航站樓，每條邊可以是相應(yīng)的航線，每個(gè)頂點(diǎn)可以是港口，每條邊可以是相應(yīng)的海運(yùn)線甚至更宏觀的，每個(gè)頂點(diǎn)可以是一個(gè)星球，每條邊可以是星球之間宇宙飛船飛行的航線，亦或更微觀的，每個(gè)頂點(diǎn)可以是城市中的一座樓，每條邊可以是樓和樓之間的街道。如上，都是可以的，這是對(duì)于圖來(lái)說(shuō)，最直觀的一種表示方式，但是，其實(shí)很多更抽象的數(shù)據(jù)關(guān)系，也可以用圖來(lái)表示。
?（2）社交網(wǎng)絡(luò)
對(duì)于社交網(wǎng)絡(luò)來(lái)說(shuō)，每個(gè)頂點(diǎn)可以表示一個(gè)人，每條邊可以表示
人與人之間的關(guān)系。這種關(guān)系可以是像 FaceBook 這種好友的關(guān)
系，也可以是像 Twitter 這種關(guān)注的關(guān)系。
?每個(gè)頂點(diǎn)可以表示一部電影，每條邊可以表示兩部電影之間的相似程度
（?4）互聯(lián)網(wǎng)
互聯(lián)網(wǎng)，也可以用圖來(lái)表示，每個(gè)頂點(diǎn)可以表示一個(gè)域名，每條邊可以表示域名之間的跳轉(zhuǎn)或 每個(gè)頂點(diǎn)可以表示一個(gè)頁(yè)面，每條邊可以表示頁(yè)面之間的連接
?（5）工作安排
在工作中的工作安排，也可以用圖來(lái)表示，每個(gè)頂點(diǎn)可以是一個(gè)工作內(nèi)容，每條邊可以是兩個(gè)工作內(nèi)容之間的相關(guān)程度，或 先后執(zhí)行的優(yōu)先級(jí)順序。
?（6）腦區(qū)活動(dòng)
像腦區(qū)活動(dòng)的研究這樣更復(fù)雜、更專(zhuān)業(yè)的領(lǐng)域，也經(jīng)常用到圖，每個(gè)頂點(diǎn)可以是一個(gè)腦區(qū)，每條邊可以是腦區(qū)之間信息的傳遞。
?
（7）程序狀態(tài)執(zhí)行
在計(jì)算機(jī)程序中，程序狀態(tài)的執(zhí)行，也可以用圖來(lái)表示，每個(gè)頂點(diǎn)可以表示一個(gè)程序狀態(tài)，每條邊可以表示從一種狀態(tài)執(zhí)行到另外一種狀態(tài)。對(duì)于這種情況，最典型的一個(gè)應(yīng)用就是自動(dòng)機(jī)，包括制作專(zhuān)業(yè)的編譯器，甚至是做一個(gè)游戲，都可能要設(shè)計(jì)一個(gè)自動(dòng)機(jī)。在這種情況下，或多或少都會(huì)使用圖論建模的方法。
?
?
總結(jié)
