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

1、第六章圖與網(wǎng)絡(luò)圖一、選擇1.在圖中用V表示點，用E表示邊，如果有兩個圖G1=V1E1和圖G2=V2E2若有V1?V2E1E2，則稱G1是G2的一個（D）?A偶圖B部分圖C完全圖D子圖2.3.在樹圖中，頂點有個，邊有條，那么頂點和邊的數(shù)量關(guān)系是（B）veA、=B、＝1C、＝1veevve4.在圖中用V表示點，用E表示邊，如果有兩個圖G1=V1E1和圖G2=V2E2若有V1=V2E1E2，則稱G1是G2的一個（A）?A部分圖B子圖C二分圖5

2、.完全偶圖中V1含m個頂點，V2含有n個頂點，則其邊數(shù)共（C）條。AmnBmnCmnDmn6.任何樹中必存在次為（A）的點A1B2C3D47含有n個頂點的完全圖，其邊數(shù)有（B）條。AnBCn(n1)Dn1)1(21?nn8.具有n個頂點的樹的邊數(shù)恰好為（A）條。An1條Bn條CDn(n1))1(21?nn9.在網(wǎng)絡(luò)圖中st的最大流量（C）它的最小割集的容量。?A大于B小于C等于D無關(guān)10.構(gòu)成最大流問題的條件之一是（B）A、網(wǎng)絡(luò)有一個始

3、點B、網(wǎng)絡(luò)有一個始點和一個終點vsvsvtC、網(wǎng)絡(luò)有一個終點D無要求vt11.下圖中（C）是完全二分圖AB18.在樹圖中，稱次為1的點為（懸掛點）19..如果G1是G2的部分圖，又是樹圖，則稱G1是G2的（部分樹）20.樹枝總長最小的部分樹，稱為（最小支撐樹）。21.把圖的所有點分成V和兩個集合，則兩個集合之間連線的最短邊一定包含在（最小?V部分樹）內(nèi)。22.(最短路問題)是指從給定的網(wǎng)絡(luò)圖中找出任意兩點之間距離最短（權(quán)值和最小）的一條

4、路。23.矩陣算法中D（k）給出網(wǎng)絡(luò)中任意兩點直接到達，經(jīng)過一個、兩個、，到（2k1）個中間點時比較得到的最短距離。24.設(shè)網(wǎng)絡(luò)圖有p個點，則一般計算到不超過D（k），k的值按公式（），即計算結(jié)束。25.對圖中每條邊規(guī)定指向的圖稱為(有向圖)26.有向圖的邊稱為(弧)，記作(vivj)，27.弧(vivj)的最大通過能力，稱為該弧的(容量)，記為c(vivj)，或簡記為cij。28.(流)是指加在網(wǎng)絡(luò)各條弧上的一組負載量，對加在弧(vi

5、vj)上的負載量記作f(vivj)，或簡記作fij29.（割）是指將容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使s→t的流中斷的一組弧的集合。30.（割的容量）是組成它的集合中各弧容量之和。31.如果在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在這條鏈上所有指向為s→t的弧（稱前向弧，記作μ），存在f0(非零)，這樣的鏈稱（增廣鏈）。32.求網(wǎng)絡(luò)最大流的方法是（標(biāo)號算法）33.34.求網(wǎng)絡(luò)的最大流，是指滿足（容量限制條件）和（中間點平衡）的條件下，使值達