圖論與路由

① 圖論中的鄰接與關聯兩術語的含義

鄰接是點與點或者邊與邊之間的關系。在無向圖中，如果兩個點之間內至少有一條邊相連，容則稱這兩個點是鄰接（adjacent）的。同樣，如果兩條邊有共同的頂點，則兩條邊也是鄰接的。

關聯是點與邊之間的關系。一個點如果是一條邊的頂點之一，則稱為該點與該邊關聯（incident）。

② 離散數學與圖論什麼關系，離散數學中的圖就是圖論嗎

圖論是離散數學研究的眾多對象之一。離散數學用「圖」的方法研究圖論，但圖論是一種理內論，其容他學科也有自己的研究方法（如數據結構也有圖論部分）。無論如何，各學科都保留了圖論的基本概念（有向與無向、點集、邊集、迴路、最短路徑等）與演算法理論（Dijkstra、最小生成樹、DFS等）

③ 聯圖的定義，關於圖論的。

圖G與H的聯圖是一個新的圖，一般記為GVH，表示在G與H的基礎上，再將G的每一個點與H的每一個點之間連接一條邊。嚴格定義看圖片。

④ 圖論的基本概念有哪些

1、有向圖和無向圖

有向圖，就是有方向的圖；所謂無向圖，就是沒有版方向的圖。

2、路徑和環權

我們把沒有經過重復的點的路徑就叫做簡單路徑。

環的定義是在路徑的定義的基礎上做了一定的拓展，首尾相接的路徑我們就把它叫做一個環。同樣我們也有簡單環，也就是除開首尾以外，剩下的部分不會經過重復的點的環就叫做簡單環。

3、極大獨立集

如果K是G的獨立集，且不是任何其他獨立集的真子集，就為極大獨立集。

4、極大團

如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團。

5、最大團

頂點最多的極大團，稱之為圖G的最大團。

6、獨立集

獨立集是指圖G=(V,E)中兩兩互不相鄰的頂點構成的集合。

⑤ 路由協議有哪些各有什麼作用

路由分為靜態路由和動態路由，其相應的路由表稱為靜態路由表和動態路由表。靜態路由表由網路管理員在系統安裝時根據網路的配置情況預先設定，網路結構發生變化後由網路管理員手工修改路由表。動態路由隨網路運行情況的變化而變化，路由器根據路由協議提供的功能自動計算數據傳輸的最佳路徑，由此得到動態路由表。

根據路由演算法，動態路由協議可分為距離向量路由協議（Distance Vector Routing Protocol）和鏈路狀態路由協議（Link State Routing Protocol）。距離向量路由協議基於Bellman-Ford演算法，主要有RIP、IGRP（IGRP為Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First，SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議（Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置選路策略時，具有明顯的缺點，目前已被BGP代替。

EIGRP是Cisco公司的私有協議，是一種混合協議，它既有距離向量路由協議的特點，同時又繼承了鏈路狀態路由協議的優點。各種路由協議各有特點，適合不同類型的網路。下面分別加以闡述。

2 靜態路由

靜態路由表在開始選擇路由之前就被網路管理員建立，並且只能由網路管理員更改，所以只適於網路傳輸狀態比較簡單的環境。靜態路由具有以下特點：

· 靜態路由無需進行路由交換，因此節省網路的帶寬、CPU的利用率和路由器的內存。

· 靜態路由具有更高的安全性。在使用靜態路由的網路中，所有要連到網路上的路由器都需在鄰接路由器上設置其相應的路由。因此，在某種程度上提高了網路的安全性。

· 有的情況下必須使用靜態路由，如DDR、使用NAT技術的網路環境。

靜態路由具有以下缺點：

· 管理者必須真正理解網路的拓撲並正確配置路由。

· 網路的擴展性能差。如果要在網路上增加一個網路，管理者必須在所有路由器上加一條路由。

· 配置煩瑣，特別是當需要跨越幾台路由器通信時，其路由配置更為復雜。

3 動態路由

動態路由協議分為距離向量路由協議和鏈路狀態路由協議

⑥ 研究圖論與網路最優化演算法這個方向有什麼用

研究這個演算法的最終目的肯定是降低演算法的時間復雜度以最快時間得到結果，也就是計算效率內的提容升，很多涉及到優化計算的軟體都需要這個演算法的支持，現在軟體的框架變成很簡單，但是核心的演算法是很重要的，如果說就業的話，面很窄，但是一般人也很少會這個，會的人又用得到，薪水應該會不錯

⑦ 什麼是路由啊 路由的組成 以及路由的演算法

路由：路由（routing）是指分組從源到目的地時，決定端到端路徑的網路范圍的進程。路由工作在OSI參考模型第三層——網路層的數據包轉發設備。路由器通過轉發數據包來實現網路互連。雖然路由器可以支持多種協議（如TCP/IP、IPX/SPX、AppleTalk等協議），但是在我國絕大多數路由器運行TCP/IP協議。路由器通常連接兩個或多個由IP子網或點到點協議標識的邏輯埠，至少擁有1個物理埠。路由器根據收到數據包中的網路層地址以及路由器內部維護的路由表決定輸出埠以及下一跳地址，並且重寫鏈路層數據包頭實現轉發數據包。路由器通過動態維護路由表來反映當前的網路拓撲，並通過網路上其他路由器交換路由和鏈路信息來維護路由表。

路由器的組成：

1. RAM（隨機存儲器）

   功能：存放路由表；存放ARP告訴緩存；存放快速交換緩存；存放分組交換緩沖；存放解壓後的IOS；路由器加電後，存放running配置文件；

   特點：重啟或者斷電後，RAM中的內容丟失。

2. NVRAM（非易失性RAM）

   功能：存儲路由器的startup配置文件；存儲路由器的備份。

   特點：重啟或者斷電後內容不丟失。

3. FLASH（快速快閃記憶體）

   功能：存放IOS和微代碼。

   特點：重啟或者斷電後內容不丟失；可存放多個IOS版本（在容量許可的前提下）；允許軟體升級不需替換CPU中的晶元。

4. ROM(只讀存儲器)

   功能：存放POST診斷所需的指令；存放mini-ios；存放ROM監控模式的代碼。

   特點：ROM中的軟體升級需要更換CPU的晶元（還好這種情況比較少遇到)

5. CPU（中央處理器）

   衡量路由器性能的重要指標，負責路由計算，路由選擇等。

6. 背板：

   背板能力是一個重要參數，尤其在交換機中。

路由演算法：又名選路演算法，可以根據多個特性來加以區分。演算法的目的是找到一條從源路由器到目的路由器的「好」路徑（即具有最低費用的路徑[1]）。演算法設計者的特定目標影響了該路由協議的操作；具體來說存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；由於路由演算法使用多種度量標准（metric），從而影響到最佳路徑的計算。

演算法分類：主要有RIP、IGRP（IGRP為 Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First， SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳 遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議 （Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域 間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置 選路策略時，具有明顯的缺點，已被BGP代替。

⑧ 離散數學、組合數學、圖論的關系是什麼

圖論是組合數學的一個分支，而離散數學是專為計算機專業編的數學書，和組合數學有部分知識交叉。

離散數學（Discrete mathematics）是研究離散量的結構及其相互關系的數學學科，是現代數學的一個重要分支。離散的含義是指不同的連接在一起的元素，主要是研究基於離散量的結構和相互間的關系，其對象一般是有限個或可數個元素。

組合數學（Combinatorial mathematics），又稱為離散數學。廣義的組合數學就是離散數學，狹義的組合數學是離散數學除圖論、代數結構、數理邏輯等的部分。但這只是不同學者在叫法上的區別。總之，組合數學是一門研究離散對象的科學。

圖論〔Graph Theory〕是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。

(8)圖論與路由擴展閱讀：

一、離散數學學科內容

1、集合論部分：集合及其運算、二元關系與函數、自然數及自然數集、集合的基數。

2、圖論部分：圖的基本概念、歐拉圖與哈密頓圖、樹、圖的矩陣表示、平面圖、圖著色、支配集、覆蓋集、獨立集與匹配、帶權圖及其應用。

3、代數結構部分：代數系統的基本概念、半群與獨異點、群、環與域、格與布爾代數。

4、組合數學部分：組合存在性定理、基本的計數公式、組合計數方法、組合計數定理。

5、數理邏輯部分：命題邏輯、一階謂詞演算、消解原理。

二、圖論的起源

眾所周知，圖論起源於一個非常經典的問題——柯尼斯堡（Konigsberg）問題。

1738年，瑞典數學家歐拉( Leornhard Euler)解決了柯尼斯堡問題。由此圖論誕生。歐拉也成為圖論的創始人。

1859年，英國數學家漢密爾頓發明了一種游戲：用一個規則的實心十二面體，它的20個頂點標出世界著名的20個城市，要求游戲者找一條沿著各邊通過每個頂點剛好一次的閉迴路，即「繞行世界」。用圖論的語言來說，游戲的目的是在十二面體的圖中找出一個生成圈。

這個生成圈後來被稱為漢密爾頓迴路。這個問題後來就叫做漢密爾頓問題。由於運籌學、計算機科學和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。