運(yùn)籌學(xué)最大流試題及答案

一、單項(xiàng)選擇題（每題2分，共20分）1.最大流問(wèn)題是指在一個(gè)網(wǎng)絡(luò)中尋找（）的流。A.流量最大B.費(fèi)用最小C.時(shí)間最短D.路徑最多2.以下關(guān)于增廣鏈的說(shuō)法，正確的是（）。A.增廣鏈上所有弧的流量都為0B.增廣鏈上所有弧的流量都達(dá)到容量C.增廣鏈上存在前向弧流量未達(dá)到容量，后向弧流量不為0D.增廣鏈上不存在前向弧和后向弧3.最大流-最小割定理表明，網(wǎng)絡(luò)的最大流等于（）。A.最小割的容量B.最大割的容量C.所有割的容量之和D.所有弧的容量之和4.在尋找最大流的算法中，常用的是（）。A.單純形法B.匈牙利法C.福特-富爾克森算法D.狄克斯屈拉算法5.網(wǎng)絡(luò)中某條弧的容量是指（）。A.該弧上允許通過(guò)的最大流量B.該弧上的實(shí)際流量C.該弧上的初始流量D.該弧上的平均流量6.若網(wǎng)絡(luò)中不存在增廣鏈，則此時(shí)的流（）。A.一定是最大流B.一定不是最大流C.可能是最大流D.與最大流無(wú)關(guān)7.最大流問(wèn)題的目標(biāo)函數(shù)通常是（）。A.最大化流量B.最小化費(fèi)用C.最大化路徑數(shù)D.最小化時(shí)間8.在最大流問(wèn)題中，源點(diǎn)的凈流出量（）匯點(diǎn)的凈流入量。A.大于B.小于C.等于D.不確定9.當(dāng)一條弧的流量達(dá)到其容量時(shí)，該?。ǎ?。A.成為飽和弧B.成為非飽和弧C.不影響增廣鏈的尋找D.一定在增廣鏈上10.對(duì)于一個(gè)網(wǎng)絡(luò)，其割集是指（）。A.一組弧，去掉這些弧后網(wǎng)絡(luò)不連通B.一組頂點(diǎn)，去掉這些頂點(diǎn)后網(wǎng)絡(luò)不連通C.一組邊，去掉這些邊后網(wǎng)絡(luò)不連通D.一組路徑，去掉這些路徑后網(wǎng)絡(luò)不連通答案：1-5：ACACA；6-10：AACAA二、多項(xiàng)選擇題（每題2分，共20分）1.以下屬于最大流問(wèn)題特點(diǎn)的有（）。A.有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)B.弧有容量限制C.目標(biāo)是最大化從源點(diǎn)到匯點(diǎn)的流量D.可以有多個(gè)源點(diǎn)和匯點(diǎn)2.尋找增廣鏈的方法有（）。A.標(biāo)號(hào)法B.破圈法C.避圈法D.廣度優(yōu)先搜索法3.最大流-最小割定理的意義在于（）。A.為求解最大流問(wèn)題提供了理論依據(jù)B.建立了最大流和最小割之間的關(guān)系C.可以通過(guò)求最小割來(lái)得到最大流D.可以通過(guò)求最大流來(lái)得到最小割4.在最大流問(wèn)題中，流量需要滿足的條件有（）。A.非負(fù)性B.容量限制C.守恒性D.對(duì)稱性5.網(wǎng)絡(luò)的割集具有以下性質(zhì)（）。A.割集的容量是非負(fù)的B.不同割集的容量可能不同C.最小割的容量等于最大流D.割集可以為空集6.以下關(guān)于最大流算法的說(shuō)法正確的有（）。A.福特-富爾克森算法是一種經(jīng)典算法B.算法的終止條件是不存在增廣鏈C.算法每次迭代都能使流量增加D.算法的復(fù)雜度與網(wǎng)絡(luò)的規(guī)模無(wú)關(guān)7.最大流問(wèn)題在實(shí)際中的應(yīng)用包括（）。A.交通網(wǎng)絡(luò)中的車輛流量分配B.通信網(wǎng)絡(luò)中的數(shù)據(jù)傳輸C.供水網(wǎng)絡(luò)中的水量分配D.電力網(wǎng)絡(luò)中的電力輸送8.增廣鏈的特點(diǎn)包括（）。A.前向弧流量未達(dá)到容量B.后向弧流量不為0C.可以改變流量以增加總流量D.一定包含源點(diǎn)和匯點(diǎn)9.對(duì)于一個(gè)網(wǎng)絡(luò)，改變某些弧的容量可能會(huì)（）。A.改變最大流的值B.改變最小割的容量C.影響增廣鏈的尋找D.不影響網(wǎng)絡(luò)的連通性10.在最大流問(wèn)題中，以下哪些情況可能導(dǎo)致找不到增廣鏈（）。A.已經(jīng)達(dá)到最大流B.網(wǎng)絡(luò)結(jié)構(gòu)不合理C.流量分配已經(jīng)最優(yōu)D.弧的容量設(shè)置不合理答案：1.ABC；2.AD；3.ABCD；4.ABC；5.ABC；6.ABC；7.ABCD；8.ABC；9.ABCD；10.AC三、判斷題（每題2分，共20分）1.最大流問(wèn)題中，源點(diǎn)的流出量可以大于匯點(diǎn)的流入量。（）2.只要網(wǎng)絡(luò)中存在增廣鏈，就可以通過(guò)調(diào)整流量來(lái)增加總流量。（）3.最小割的容量一定小于最大流。（）4.最大流問(wèn)題的目標(biāo)是最小化從源點(diǎn)到匯點(diǎn)的流量。（）5.網(wǎng)絡(luò)中所有弧的流量都為0時(shí)，一定不是最大流。（）6.增廣鏈上的前向弧一定是非飽和弧，后向弧一定是飽和弧。（）7.改變網(wǎng)絡(luò)中某條弧的容量，一定會(huì)改變最大流的值。（）8.最大流-最小割定理表明，網(wǎng)絡(luò)的最大流和最小割是一一對(duì)應(yīng)的。（）9.在尋找最大流的過(guò)程中，每次找到的增廣鏈都是唯一的。（）10.若網(wǎng)絡(luò)中不存在割集，則該網(wǎng)絡(luò)不存在最大流問(wèn)題。（）答案：1.×；2.√；3.×；4.×；5.×；6.×；7.×；8.√；9.×；10.×四、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述最大流問(wèn)題的基本概念。最大流問(wèn)題是在一個(gè)有向網(wǎng)絡(luò)中，有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)，每條弧有容量限制，目標(biāo)是找出從源點(diǎn)到匯點(diǎn)的最大流量，同時(shí)滿足流量非負(fù)、容量限制和守恒性。2.什么是增廣鏈？它在最大流算法中有什么作用？增廣鏈?zhǔn)蔷W(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)的一條鏈，其上前向弧流量未達(dá)容量，后向弧流量不為0。作用是通過(guò)調(diào)整增廣鏈上的流量可增加總流量，直到找不到增廣鏈時(shí)得到最大流。3.簡(jiǎn)述最大流-最小割定理。該定理表明在一個(gè)網(wǎng)絡(luò)中，從源點(diǎn)到匯點(diǎn)的最大流等于最小割的容量。最小割是使網(wǎng)絡(luò)不連通的一組弧的容量之和最小的割集，此定理為求解最大流提供理論依據(jù)。4.簡(jiǎn)述福特-富爾克森算法的基本步驟。首先給源點(diǎn)標(biāo)號(hào)，開(kāi)始尋找增廣鏈；若找到，確定調(diào)整量并調(diào)整流量；若找不到，當(dāng)前流就是最大流。重復(fù)上述過(guò)程，直到找不到增廣鏈為止。五、討論題（每題5分，共20分）1.討論最大流問(wèn)題在交通網(wǎng)絡(luò)中的應(yīng)用及可能遇到的問(wèn)題。應(yīng)用：可用于優(yōu)化車輛流量分配，確定道路最大通行能力。問(wèn)題：實(shí)際交通情況復(fù)雜，如交通事故、道路施工等會(huì)改變弧容量；車輛行駛具有隨機(jī)性，難以準(zhǔn)確建模；還需考慮不同車型對(duì)流量的影響。2.當(dāng)網(wǎng)絡(luò)中存在多個(gè)源點(diǎn)和匯點(diǎn)時(shí)，如何將其轉(zhuǎn)化為單源單匯的最大流問(wèn)題？可添加一個(gè)虛擬源點(diǎn)和一個(gè)虛擬匯點(diǎn)。虛擬源點(diǎn)與各實(shí)際源點(diǎn)相連，弧容量設(shè)為無(wú)窮大；虛擬匯點(diǎn)與各實(shí)際匯點(diǎn)相連，弧容量也設(shè)為無(wú)窮大，這樣就轉(zhuǎn)化為單源單匯問(wèn)題。3.分析改變網(wǎng)絡(luò)中弧的容量對(duì)最大流和最小割的影響。若改變的弧在最小割集中，可能改變最小割容量，進(jìn)而改變最大流；若不在最小割