資源描述:
《第6章 圖與網(wǎng)絡(luò)圖》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第六章圖與網(wǎng)絡(luò)圖一、選擇1.在圖中用V表示點,用E表示邊,如果有兩個圖G1={V1,E1}和圖G2={V2,E2},若有V1V2,E1E2,則稱G1是G2的一個(D)A偶圖B部分圖C完全圖D子圖2.3.在樹圖中,頂點有個,邊有條,那么頂點和邊的數(shù)量關(guān)系是(B)A、=B、=-1C、=-14.在圖中用V表示點,用E表示邊,如果有兩個圖G1={V1,E1}和圖G2={V2,E2},若有V1=V2,E1E2,則稱G1是G2的一個(A)A部分圖B子圖C二分圖5.完全偶圖中V1含m個頂點,V2含有n個頂點,則其邊數(shù)共(C)條。Am+nBm-nCm×
2、nDm÷n6.任何樹中必存在次為(A)的點A1B2C3D47.含有n個頂點的完全圖,其邊數(shù)有(B)條。AnBCn(n-1)Dn-18.具有n個頂點的樹的邊數(shù)恰好為(A)條。An-1條Bn條CDn(n-1)9.在網(wǎng)絡(luò)圖中st的最大流量(C)它的最小割集的容量。A大于B小于C等于D無關(guān)10.構(gòu)成最大流問題的條件之一是(B)A、網(wǎng)絡(luò)有一個始點B、網(wǎng)絡(luò)有一個始點和一個終點C、網(wǎng)絡(luò)有一個終點D無要求11.下圖中(C)是完全二分圖ABCD12.下面(D)是最短路問題A課程排序問題B生產(chǎn)計劃問題C人力資源問題D選址問題13.求網(wǎng)絡(luò)圖中任意兩點之間的最
3、短距離的方法是(C)A求最小部分樹B矩陣算法CDijkstra算法D破圈法14.下面(A)是矩陣算法求最短路問題A小學生選校址問題B課程排序問題C生產(chǎn)計劃問題D人力資源問題15.下面(A)是最大流問題。A橋梁問題B設(shè)施布局問題C生產(chǎn)計劃問題D以上都不是16.二、填空1.在圖論中,稱(無圈的)連通圖為樹。2.樹是無圈連通圖中邊數(shù)最多的,在樹圖上只要任意再加上一條邊,必定會出現(xiàn)(圈)。3.在圖中一般用點表示(研究的對象),用邊表示這些(對象的聯(lián)系)。4.如果給圖中的點和邊賦以具體的含義和權(quán)數(shù),把這樣的圖稱為(網(wǎng)絡(luò)圖)5..圖G可以定義為點和
4、邊的集合,記作(G=[V,E])6.在圖中,(鏈)是點可重復,邊不可重復的。7.在圖中,(路)是點與邊都不可以重復的。8.如果邊e的兩個端點相重,稱該邊為(環(huán))9.對無環(huán)、無多重邊的圖稱為(簡單圖)10.與某一個點相關(guān)聯(lián)的邊的數(shù)目稱為點的(次)11.對起點與終點相重合的鏈稱為(圈)。12.若在一個圖中,如果每一對頂點之間至少存在一條鏈,稱這樣的圖為(連通圖)。13.若在一個圖中,如果每一對頂點之間至少存在一條(鏈),稱這樣的圖為連通圖。14.一個簡單圖中若任意兩點之間均有邊相連,稱這樣的圖為(完全圖)。15.一個(簡單圖)中若任意兩點之
5、間均有邊相連,稱這樣的圖為完全圖。16.對要研究的問題確定具體對象及這些對象間的性質(zhì)聯(lián)系,這就要對研究的問題建立(圖的模型)17.(樹)是無圈的連通圖。18.在樹圖中,稱次為1的點為(懸掛點)19..如果G1是G2的部分圖,又是樹圖,則稱G1是G2的(部分樹)20.樹枝總長最小的部分樹,稱為(最小支撐樹)。21.把圖的所有點分成V和兩個集合,則兩個集合之間連線的最短邊一定包含在(最小部分樹)內(nèi)。22.(最短路問題)是指從給定的網(wǎng)絡(luò)圖中找出任意兩點之間距離最短(權(quán)值和最?。┑囊粭l路。23.矩陣算法中D(k)給出網(wǎng)絡(luò)中任意兩點直接到達,經(jīng)過
6、一個、兩個、···,到(2k-1)個中間點時比較得到的最短距離。24.設(shè)網(wǎng)絡(luò)圖有p個點,則一般計算到不超過D(k),k的值按公式(),即計算結(jié)束。25.對圖中每條邊規(guī)定指向的圖稱為(有向圖)26.有向圖的邊稱為(弧),記作(vi,vj),27.弧(vi,vj)的最大通過能力,稱為該弧的(容量),記為c(vi,vj),或簡記為cij。28.(流)是指加在網(wǎng)絡(luò)各條弧上的一組負載量,對加在弧(vi,vj)上的負載量記作f(vi,vj),或簡記作fij29.(割)是指將容量網(wǎng)絡(luò)中的發(fā)點和收點分割開,并使s→t的流中斷的一組弧的集合。30.(割的
7、容量)是組成它的集合中各弧容量之和。31.如果在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈,在這條鏈上所有指向為s→t的?。ǚQ前向弧,記作μ+),存在f0(非零),這樣的鏈稱(增廣鏈)。32.求網(wǎng)絡(luò)最大流的方法是(標號算法)33.34.求網(wǎng)絡(luò)的最大流,是指滿足(容量限制條件)和(中間點平衡)的條件下,使值達到最大。三、判斷1.圖論中的圖不僅反映了研究對象之間的關(guān)系,而且是真實圖形的寫照,因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴格注意。(不正確)2.在任一圖G中,當
8、點集V確定后,樹圖是G中邊數(shù)最少的連通圖。(正確)3.如圖中某點有若干個相鄰點,與其距離最遠的相鄰點為,則邊[i,j]必不包含在最小支撐樹內(nèi)。(正確)4.如圖中從至各點均有唯一的最短路,則連接至其他各點的最