圖與網(wǎng)絡(luò)分析試題及答案

圖與網(wǎng)絡(luò)分析試題及答案一、填空題.圖的最基本要素是點(diǎn)、點(diǎn)與點(diǎn)之間構(gòu)成的邊.在圖論中，通常用點(diǎn)表示，用邊或有向邊表示研究對(duì)象，以及研究對(duì)象之間具有特定

關(guān)系。.在圖論中，通常用點(diǎn)表示研究對(duì)象，用邊或有向邊表示研究對(duì)象之間具有某種特定的

關(guān)系。.在圖論中，圖是反映研究對(duì)象之間特定關(guān)系的一種工具。.任一樹(shù)中的邊數(shù)必定是它的點(diǎn)數(shù)減1。.最小樹(shù)問(wèn)題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點(diǎn)，而且連接的總長(zhǎng)度最小。.最小樹(shù)的算法關(guān)鍵是把最近的未及結(jié)點(diǎn)連接到那些已接結(jié)點(diǎn)上去。8.求最短路問(wèn)題的計(jì)算方法是從0≤f∣≤cn開(kāi)始逐步推算的，在推算過(guò)程中需要不斷標(biāo)記平

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

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

流時(shí)，可能得到不同的最大流方案D當(dāng)最大流方案不唯一時(shí)，得到的最大流量亦可能不相

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

用點(diǎn)與點(diǎn)的相互位置，邊的長(zhǎng)短曲直來(lái)表示研究對(duì)象的相互關(guān)系。C.圖論中的邊表示研究

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

點(diǎn)，而權(quán)數(shù)最少的圖C.一個(gè)網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹(shù)內(nèi)D.一個(gè)網(wǎng)絡(luò)的最小

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

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

制條件而大于或等于零。三、多選題.關(guān)于圖論中圖的概念,以下敘述(123)正確。(1)圖中的邊可以是有向邊,也可以是無(wú)向邊(2)圖中的各條邊上可以標(biāo)注權(quán)。(3)結(jié)點(diǎn)

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

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

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

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

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