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

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

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

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

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

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