第7章圖與網(wǎng)絡(luò)分析練習(xí)題及答案

1、第七章 圖與網(wǎng)絡(luò)分析一、單項選擇題1關(guān)于可行流，以下敘述不正確的是（ ）A.可行流的流量大于零而小于容量限制條件 B在網(wǎng)絡(luò)的任一中間點，可行流滿足流人量=流出量C各條有向邊上的流量均為零的流是一個可行流 D可行流的流量小于或等于容量限制條件而大于或等于零2關(guān)于最小樹，以下敘述（ ）正確。A.最小樹是一個網(wǎng)絡(luò)中連通所有點而邊數(shù)最少的圖 B最小樹是一個網(wǎng)絡(luò)中連通所有的點，而權(quán)數(shù)最少的圖C一個網(wǎng)絡(luò)中的最大權(quán)邊必不包含在其最小樹內(nèi) D一個網(wǎng)絡(luò)的最小樹一般是唯一的。3最小樹的算法關(guān)鍵是把最近的某些結(jié)點連接到那些已接結(jié)點上去，前者所指結(jié)點是（ ）A. 邊緣結(jié)點 B.未接結(jié)點 C.已接結(jié)點 D.最重要結(jié)點4

2、.最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接所有結(jié)點，而且（ ）A.連接的總長度最大 B.連接的總長度最小 C.連接的總長度為0 D.計算總長度5最小樹問題就是在網(wǎng)絡(luò)圖中，找出若干條邊，連接（ ）A.相鄰結(jié)點 B.頭尾結(jié)點 C.部分結(jié)點 D.所有結(jié)點6任一樹中的邊數(shù)和它的點數(shù)之間的關(guān)系是（ ）A.邊數(shù)等于點數(shù)減1 B.邊數(shù)等于點數(shù)加1 C.點數(shù)等于邊數(shù)減1 D.點數(shù)等于邊數(shù)加17最大流問題中，對于一個可行流，ViVj有向邊上的流量fij必須滿足的條件之一是（ ）A.0fijcij B.0fijcij C. 0fijcij D. 0fijcij8.一個連通圖中的最小樹可能不唯一，其權(quán)（ ）A.

3、是唯一確定的 B.可能不唯一 C.可能不存在 D.一定有多個二、多項選擇題1.關(guān)于圖論中圖的概念，以下敘述正確的的（ ） A.圖中的邊可以是有向邊，也可以是無向邊 B.圖中的各條邊上可以標(biāo)注權(quán) C.結(jié)點數(shù)等于邊數(shù)的連通圖必含圈 D.結(jié)點數(shù)等于邊數(shù)的圖必連通 E.圖中的邊只能是有向邊2.關(guān)于最短路，以下敘述不正確的有（ ） A. 從起點出發(fā)到終點的最短路不一定是唯一的，但其最短路線的長度是確定的B從起點出發(fā)到終點的最短路是唯一的C從起點出發(fā)的有向邊中的最小權(quán)邊，一定包含在起點到終點的最短路上 D從起點出發(fā)的有向邊中的最大權(quán)邊，一定不包含在起點到終點的最短路上E整個網(wǎng)絡(luò)的最大權(quán)邊的一定不包含在從起

4、點到終點的最短路線上3.關(guān)于增廣鏈，以下敘述正確的有（ ） A增廣鏈?zhǔn)且粭l從發(fā)點到收點的有向路，這條路上各條邊的方向必一致 B增廣鏈?zhǔn)且粭l從發(fā)點到收點的有向路，這條路上各條邊的方向可不一致 C增廣鏈上與發(fā)收點方向一致的邊必是非飽和邊，方向相反的邊必是流量大于零的邊 D增廣鏈上與發(fā)收點方向一致的邊必是流量小于容量的邊，方向相反的邊必是流量等于零的邊 E增廣鏈上與發(fā)收點方向一致的邊必是流量為零的邊，方向相反邊必是流量大于零的邊4.在下圖中，根據(jù)（a） 生成的支撐樹有（ ） 三 、應(yīng)用題1.下圖是6個城市的交通圖，為將部分道路改造成高速公路，使各個城市均能通達(dá)，又要使高速公路的總長度最小，應(yīng)如何做?最小的總長度是多少? 2對下面的連通圖，試求出最小樹。 3用標(biāo)號法求下圖所示的最大流問題，弧上數(shù)字為容量和初始可行流量。45 參考答案一、單項選擇題1