圖與網絡分析試題及答案

圖與網絡分析試題及答案一、填空題.圖的最基本要素是點、點與點之間構成的邊.在圖論中，通常用點表示，用邊或有向邊表示研究對象，以及研究對象之間具有特定

關系。.在圖論中，通常用點表示研究對象，用邊或有向邊表示研究對象之間具有某種特定的

關系。.在圖論中，圖是反映研究對象之間特定關系的一種工具。.任一樹中的邊數必定是它的點數減1。.最小樹問題就是在網絡圖中，找出若干條邊，連接所有結點，而且連接的總長度最小。.最小樹的算法關鍵是把最近的未及結點連接到那些已接結點上去。8.求最短路問題的計算方法是從0≤f∣≤cn開始逐步推算的，在推算過程中需要不斷標記平

衡和最短路線。 —二、單選題1、關于圖論中圖的概念，以下敘述(B)正確。A圖中的有向邊表示研究對象，結點表示銜接關系。B圖中的點表示研究對象，邊表示點

與點之間的關系。C圖中任意兩點之間必有邊。D圖的邊數必定等于點數減1。.關于樹的概念，以下敘述(B)正確。A樹中的點數等于邊數減1 B連通無圈的圖必定是樹 C含n個點的樹是唯一的D任一樹中，去掉一條邊仍為樹。.一個連通圖中的最小樹(B),其權(A)。A是唯一確定的 B可能不唯一 C可能不存在 D一定有多個。.關于最大流量問題，以下敘述(D)正確。A一個容量網絡的最大流是唯一確定的B達到最大流的方案是唯一的C當用標號法求最大

流時，可能得到不同的最大流方案D當最大流方案不唯一時，得到的最大流量亦可能不相

同。.圖論中的圖，以下敘述(C)不正確。A.圖論中點表示研究對象邊或有向邊表示研究對象之間的特定關系。B.圖論中的圖，

用點與點的相互位置，邊的長短曲直來表示研究對象的相互關系。C.圖論中的邊表示研究

對象，點表示研究對象之間的特定關系。 D.圖論中的圖，可以改變點與點的相互位置。只要不改變點與點的連接關系。.關于最小樹，以下敘述(B)正確。A.最小樹是一個網絡中連通所有點而邊數最少的圖B.最小樹是一個網絡中連通所有的

點，而權數最少的圖C.一個網絡中的最大權邊必不包含在其最小樹內D.一個網絡的最小

樹一般是不唯一的。.關于可行流，以下敘述(A)不正確。A.可行流的流量大于零而小、于容量限制條件B.在網絡的任一中間點，可行流滿足流人

量=流出量。C.各條有向邊上的流量均為零的流是一個可行流D.可行流的流量小于容量限

制條件而大于或等于零。三、多選題.關于圖論中圖的概念,以下敘述(123)正確。(1)圖中的邊可以是有向邊,也可以是無向邊(2)圖中的各條邊上可以標注權。(3)結點

數等于邊數的連通圖必含圈(4)結點數等于邊數的圖必連通。.關于樹的概念,以下敘述(123)正確。1)樹中的邊數等于點數減1(2)樹中再添一條邊后必含圈。(3)樹中刪去一條邊后必不連

通(4)樹中兩點之間的通路可能不唯一。.從連通圖中生成樹,以下敘述(134)正確。(1)任一連通圖必有支撐樹(2)任一連通圖生成的支撐樹必唯一(3)在支撐樹中再增加

一條邊后必含圈(4)任一連通圖生成的各個支撐樹其邊數必相同.在下圖中，(abcd)不是根據(a)生成的支撐樹。5.從賦權連通圖中生成最小樹,以下敘述(124)不正確。(1)任一連通圖生成的各個最小樹,其總長度必相等(2)任一連通圖生成的各個最小樹,

其邊數必相等。(3)任一連通圖中具有最小權的邊必包含在生成的最小樹上。(4)最小樹中可能包括連通圖中的最大權邊。6．從起點到終點的最短路線，以下敘述(123)不正確。1)從起點出發(fā)的最小權有向邊必含在最短路線中。(2)整個圖中權最小的有向邊必包含在最短路線中。(3)整個圖中權最大的有向邊可能含在最短路線中(4)從起點到終點的最短路線是唯一的。7．關于帶收發(fā)點的容量網絡中從發(fā)點到收點的一條增廣路，以下敘述(123)不正確。(1)增廣路上的有向邊的方向必須是從發(fā)點指向收點的(2)增廣路上的有向邊，必須都是不飽和邊(3)增廣路上不能有零流邊(4)增廣路上與發(fā)點到收點方向一致的有向邊不能是飽和邊，相反方向的有向邊不能是零流邊8?關于樹，以下敘述(ABCE)正確。A.樹是連通、無圈的圖B.任一樹，添加一條邊便含圈C.任一樹的邊數等于點數減1。D.任一樹的點數等于邊數減1E?任一樹，去掉一條邊便不連通。.關于最短路，以下敘述(ACDE)不正確。A從起點出發(fā)到終點的最短路是唯一的。B?從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的。C從起點出發(fā)的有向邊中的最小權邊，一定包含在起點到終點的最短路上D.從起點出發(fā)的有向邊中的最大權邊，一定不包含在起點到終點的最短路上。E?整個網絡的最大權邊的一定不包含在從起點到終點的最短路線上。.關于增廣路，以下敘述(BC)正確。A.增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向必一致。B.增廣路是一條從發(fā)點到收點的有向路，這條路上各條邊的方向可不一致。C增廣路上與發(fā)點到收點方向一致的邊必須是非飽和邊，方向相反的邊必須是流量大于零的邊。D.增廣路上與發(fā)點到收點方向一致的邊必須是流量小于容量的邊，方向相反的邊必須是流量等于零的邊。E?增廣路上與發(fā)點到收點方向一致的邊必須是流量為零的邊，方向相反的邊必須是流量大于零的邊。四、名詞解釋1、樹:在圖論中，具有連通和不含圈特點的圖稱為樹。2．權：在圖中，邊旁標注的數字稱為權。3．網絡：在圖論中，給邊或有向邊賦了權的圖稱為網絡4．最大流問題：最大流問題是指在網絡圖中，在單位時間內，從發(fā)點到收點的最大流量5．最大流問題中流量：最大流問題中流量是指單位時間的發(fā)點的流出量或收點的流入量。6．容量：最大流問題中，每條有向邊單位時間的最大通過能力稱為容量7．飽合邊：容量與流量相等的有向邊稱為飽合邊。8零流邊：流量為零的有向邊稱為零流邊9.生成樹：若樹T是無向圖G的生成樹，則稱T是G的生成樹。.。10根：有向圖G中可以到達圖中任一頂點的頂點U稱為G的根。11枝：樹中的邊稱為枝。12.平行邊：具有相同端點的邊叫平行邊。13根樹：若有向圖G有根u,且它的基本圖是一棵樹，則稱G為以u為根的根樹。四、計算題1．下圖是6個城市的交通圖，為將部分道路改造成高速公路，使各個城市均能通達，又要使高速公路的總長度最小，應如何做?最小的總長度是多少?2．對下面的兩個連通圖，試分別求出最小樹。3、第1題中的交通圖，求城市A到D沿公路走的最短路的路長及路徑。4．對下面兩圖，試分別求出從起點到終點的最短路線。6.下面網絡中，點①，②是油井，點⑥是原油脫水處理廠，點③、④、⑤是泵站，各管道的每小時最大通過能力（噸/小時）如有向邊上的標注。求從油井①、②每小時能輸送到脫曲1%Wl?jl?1色MFT'上，3,lAM.ι?}fi即

Λ?φA,√ιj?,∕(Jf產i?∕?,'j??.??iaFpE????f"小心=尸K沌名詞十一章1、需求：需求就是庫存的輸出。2、存貯費：一般是指每存貯單位物資單位時間所需花費的費用。3、缺貨損失費：一般指由于中斷供應影響生產造成的損失賠償費。4、訂貨批量Q：存貯系統(tǒng)根據需求，為補充某種物資的庫存而向供貨廠商一次訂貨或采購的數量。5、訂貨間隔期T：兩次訂貨的時間間隔可訂貨合同中規(guī)定的兩次進貨之間的時間間隔。6、記賬間隔期R：指庫存記賬制度中的間隔記賬制所規(guī)定的時間。十二章1、預測：是決策的基礎，它借助于經濟學、概率論與數理統(tǒng)計、現代管理科學、系統(tǒng)論和計算機科學等所提供的理論及方法，通過適當的模型技術，分析和預測研究對象的發(fā)展趨勢。十三章1、決策：凡是根據預定目標而采取某種行動方案所作出的選擇或決定就稱為決策。2、單純選優(yōu)決策：是指根據已掌握的數據，不需再加工計算，或僅進行方案指標值的簡單計算，通過比較便可以直接選出最優(yōu)方案的決策方法。3、模型選優(yōu)決策：是在決策對象的客觀狀態(tài)完全確定的條件下，建立一定的符合實際經濟狀況的數學模型，進而通過對模型的求解來選擇最優(yōu)方案的方法。4、非確定型決策：是一種在決策分析過程中，對決策方案付諸實施后可能遇到的客觀狀態(tài)，雖然能夠進行估計，但卻無法確定每一種客觀狀態(tài)出現的概率的決策。5、風險型決策：是一種在分析過程中，對方案付諸實施后可能遇到的客觀狀態(tài)，不僅在決策分析時能夠加以估計，而且對每一種狀態(tài)出現的概率大小也有所掌握。6、決策樹：就是對一個決策問題畫一張圖，用更容易了解的形式來表示有關信息。十四章1、排隊論：排隊論所討論的