第6章 圖與網(wǎng)絡(luò)圖

《第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個頂點，則

2、其邊數(shù)共（C）條。Am+nBm-nCm×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課

3、程排序問題B生產(chǎn)計劃問題C人力資源問題D選址問題13.求網(wǎng)絡(luò)圖中任意兩點之間的最短距離的方法是（C）A求最小部分樹B矩陣算法CDijkstra算法D破圈法14.下面（A）是矩陣算法求最短路問題A小學(xué)生選校址問題B課程排序問題C生產(chǎn)計劃問題D人力資源問題15.下面（A）是最大流問題。A橋梁問題B設(shè)施布局問題C生產(chǎn)計劃問題D以上都不是16.二、填空1.在圖論中，稱(無圈的)連通圖為樹。2.樹是無圈連通圖中邊數(shù)最多的，在樹圖上只要任意再加上一條邊，必定會出現(xiàn)（圈）。3.在圖中一般用點表示（研究的對象），

4、用邊表示這些（對象的聯(lián)系）。4.如果給圖中的點和邊賦以具體的含義和權(quán)數(shù)，把這樣的圖稱為（網(wǎng)絡(luò)圖）5..圖G可以定義為點和邊的集合，記作（G=[V,E]）6.在圖中，（鏈）是點可重復(fù)，邊不可重復(fù)的。7.在圖中，（路）是點與邊都不可以重復(fù)的。8.如果邊e的兩個端點相重，稱該邊為（環(huán)）9.對無環(huán)、無多重邊的圖稱為（簡單圖）10.與某一個點相關(guān)聯(lián)的邊的數(shù)目稱為點的（次）11.對起點與終點相重合的鏈稱為（圈）。12.若在一個圖中，如果每一對頂點之間至少存在一條鏈，稱這樣的圖為（連通圖）。13.若在一個圖中，

5、如果每一對頂點之間至少存在一條（鏈），稱這樣的圖為連通圖。14.一個簡單圖中若任意兩點之間均有邊相連，稱這樣的圖為（完全圖）。15.一個（簡單圖）中若任意兩點之間均有邊相連，稱這樣的圖為完全圖。16.對要研究的問題確定具體對象及這些對象間的性質(zhì)聯(lián)系，這就要對研究的問題建立（圖的模型）17.（樹）是無圈的連通圖。18.在樹圖中，稱次為1的點為（懸掛點）19..如果G1是G2的部分圖，又是樹圖，則稱G1是G2的（部分樹）20.樹枝總長最小的部分樹，稱為（最小支撐樹）。21.把圖的所有點分成V和兩個集合

6、，則兩個集合之間連線的最短邊一定包含在（最小部分樹）內(nèi)。22.(最短路問題)是指從給定的網(wǎng)絡(luò)圖中找出任意兩點之間距離最短（權(quán)值和最小）的一條路。23.矩陣算法中D（k）給出網(wǎng)絡(luò)中任意兩點直接到達，經(jīng)過一個、兩個、···，到（2k-1）個中間點時比較得到的最短距離。24.設(shè)網(wǎng)絡(luò)圖有p個點，則一般計算到不超過D（k），k的值按公式（），即計算結(jié)束。25.對圖中每條邊規(guī)定指向的圖稱為(有向圖)26.有向圖的邊稱為(弧)，記作(vi,vj)，27.弧(vi,vj)的最大通過能力，稱為該弧的(容量)，記為c

7、(vi,vj)，或簡記為cij。28.(流)是指加在網(wǎng)絡(luò)各條弧上的一組負載量，對加在弧(vi,vj)上的負載量記作f(vi,vj)，或簡記作fij29.（割）是指將容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使s→t的流中斷的一組弧的集合。30.（割的容量）是組成它的集合中各弧容量之和。31.如果在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在這條鏈上所有指向為s→t的?。ǚQ前向弧，記作μ+），存在f0(非零)，這樣的鏈稱（增廣鏈）。32.求網(wǎng)絡(luò)最大流

8、的方法是（標(biāo)號算法）33.34.求網(wǎng)絡(luò)的最大流，是指滿足（容量限制條件）和（中間點平衡）的條件下，使值達到最大。三、判斷1.圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴(yán)格注意。（不正確）2.在任一圖G中，當(dāng)點集V確定后，樹圖是G中邊數(shù)最少的連通圖。（正確）3.如圖中某點有若干個相鄰點，與其距離最遠的相鄰點為，則邊[i,j]必不包含在最小支撐樹內(nèi)。（正確）4.如圖中從至各點均有唯一的最短路，則連接至其他各點的最