簡談圖論期末論文

《簡談圖論期末論文》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、簡談圖論期末論文簡談圖論期末論文導(dǎo)讀：最典型的兩種求解最短路徑算法分別是Dijkstra算法和Floyd算法，其中Dijkstra算法適用于計算指定頂點之間的最短路徑，而Floyd算法適用于計算一個圖或者X中所有頂點間的最短路徑。3.2最短路徑算法3.2.1Dijkstra算法Dijkstra算法又稱為標(biāo)號法，是1959年由荷蘭計算機(jī)科學(xué)家E.W.Dijkstra提出的關(guān)于最短路徑的搜索算法。該算法是圖論在重慶地鐵中的應(yīng)用1.引言圖論是數(shù)學(xué)的一個分支，并且是組合數(shù)學(xué)和應(yīng)用數(shù)學(xué)的一部分。它以圖做為研究對象，而圖是由若干節(jié)點和節(jié)點之間的邊所構(gòu)成的圖型。在圖論中，圖

2、往往是某個具體現(xiàn)實生活中問題的數(shù)學(xué)抽象，可以說，圖中的節(jié)點代表著生活中的某些特定事物，而節(jié)點之間的邊則代表著節(jié)點之間的特定聯(lián)系。圖論這門學(xué)科需要解決的就是如何利用數(shù)學(xué)知識去解決它們之間的關(guān)系。圖論最早起源于1736年著名的柯尼斯堡七橋問題[1]。這個問題的內(nèi)容是：在柯尼斯堡的普萊格爾河上有七座橋?qū)⒑又械膷u嶼與河岸連接起來。問題是要從這四塊陸地中任何一塊開始，通過每一座橋正好一次，最后再回到起始點。然而人們無數(shù)次的嘗試解決卻都沒有成功。直到1736年，歐拉解決了這個問題。他用抽像分析法將這個問題化為世界上第一個圖論問題：即把每一塊陸地用一個點來代替，將每一座橋用

3、聯(lián)接相應(yīng)的兩個點的一條邊來代替，從而得到了一個“圖”。最終，歐拉成功證明了這個問題是無解的，并且推廣了這個問題的意義，給出了對于一個給定的圖可以某種方式走遍的判定法則。這就是后來的歐拉通路、歐拉回路以及歐拉圖問題。于是，歐拉成為了圖論學(xué)的創(chuàng)始人。從那以后開始的幾百年間，圖論開始了飛速的發(fā)展。雖然圖論研究的是點和邊之間所構(gòu)成圖的問題，但其應(yīng)用領(lǐng)域還是十分廣闊的。圖論的應(yīng)用不僅僅局限于數(shù)學(xué)問題和計算機(jī)領(lǐng)域，它同時還涵蓋了交通管理、通信領(lǐng)域、社會學(xué)等諸多其他研究領(lǐng)域。而最短路徑問題是圖論應(yīng)用中的基本問題。最短路徑顧名思義就是在所有的路徑中找出一條距離最短的有效路徑。

4、實際上，這里所指的“距離”不僅僅是指地理意義上的距離，還可以引申到時間、費用、等其他度量單位上面。本文中，以重慶地鐵為研究對象，利用圖論知識解決在搭乘重慶地鐵時的最短路徑問題?？梢哉f，最短路徑問題再交通X絡(luò)結(jié)構(gòu)的分析以及交通路線的選擇中都有重要的應(yīng)用價值。此外，最短路徑問題一直是計算機(jī)科學(xué)、地理信息學(xué)、交通管理學(xué)等學(xué)科中一個研究的熱點問題。圖的著色是指對圖的每個節(jié)點指定一種顏色，使得相鄰的節(jié)點的顏色不相同。著色問題在實際中有很多的應(yīng)用，比如可以解決化學(xué)藥品的儲藏問題，電視頻道分配問題以及考試安排問題等。重慶市是一座擁有三千多年歷史并且舉世聞名的歷史文化名城,是

5、巴渝文化的發(fā)祥地。其坐落于長江與嘉陵江的交匯處，四面環(huán)山，并被美麗的江水所環(huán)抱。同時，重慶也是我國最大的直轄市。對于來這兒旅行的旅客或是剛來重慶上學(xué)的學(xué)生來說，如何在最短的時間內(nèi)以及最經(jīng)濟(jì)的方式瀏覽“山城”美景，品嘗“山城”著名的小吃、火鍋是一個十分重要的問題。事實表明，充分利用好重慶的地鐵交通系統(tǒng)可以在短時間內(nèi)游遍重慶的知名景點和風(fēng)景區(qū)，并且搭乘地鐵可以大大縮短旅行時間。通過對于《圖論及其應(yīng)用》這門課程的學(xué)習(xí)后，我們可以將這個問題轉(zhuǎn)化成為一個圖論中的數(shù)學(xué)問題來看待，于是，就可以利用在圖論中所學(xué)習(xí)和掌握的相關(guān)數(shù)學(xué)知識，對該問題進(jìn)行抽象成圖論中的最短路徑問題以得

6、到很好的解決。圖論中關(guān)于最短路徑問題的解決主要是依靠Dijkstra算法，F(xiàn)loyd算法以及Warshell算法等算法。所需要乘坐或者換成的地鐵站數(shù)即可看出是圖中每條邊的權(quán)重。本文研究的目的是為了通過圖論知識找出可以瀏覽“山城”景點的最短旅游路徑以及點著色問題。1圖論在重慶地鐵中的應(yīng)用2.圖論基本概念2.1圖的定義圖就是一個有序三元組G=<V(G)，E(G)，?(G)>，其中：（1）V(G)={v1，v2，?，vn}且V(G)≠?，則稱V(G)為頂點集，其元素叫做圖的頂點；（2）E(G)={e1，e2，?，en}，稱為邊集，其元素叫做圖的邊；（3）

7、?(G)；E→V×V是從邊集E到頂點集V的有序或者無序?qū)系挠吧?，稱為關(guān)聯(lián)函數(shù)。2.2無向圖和有向圖如果圖G中連接某兩個不同頂點間的邊是有方向的，則稱該邊為有向邊。有向邊用有序?qū)?lt;Vi,Vj>表示,其中Vi表示源點，Vj表示終點。如果圖G中所有邊都是有向邊，則稱圖G為有向圖。如果連接某兩個不同頂點間的邊是沒有方向的，則稱該邊為無向邊。無向邊用無序?qū)?Vi,Vj)表示。如果圖G中的所有邊都是無向邊，則稱圖G為無向圖。2.3關(guān)聯(lián)和度關(guān)聯(lián)指的是圖中頂點與邊之間的關(guān)系。設(shè)Vi和Vj是一條邊的兩個頂點，如果Vi≠Vj，則該邊關(guān)聯(lián)頂點一次；若Vi=Vj，即構(gòu)

8、成了環(huán)，關(guān)聯(lián)次數(shù)為2次。對于無向圖中，