問(wèn)題描述:給定有向圖G=(V,E).設(shè)P是G的一個(gè)簡(jiǎn)單路(頂點(diǎn)不相交)的集合.如果V中每個(gè)頂點(diǎn)恰好在P的條路上,則稱P是G的一個(gè)路徑覆蓋.P中路徑可以從V的任何一個(gè)項(xiàng)點(diǎn)開始,長(zhǎng)度也是任意的,特別地,可以為0.G的最小路徑覆蓋是G的所含路徑條數(shù)最少的路徑覆蓋.

設(shè)計(jì)一個(gè)有效算法求一個(gè)有向無(wú)環(huán)圖G的最小路徑覆蓋.

[設(shè)V={1,2,...,n},如下構(gòu)造網(wǎng)絡(luò)G₁=(V1,E₁):

每條邊的容量均為1.求網(wǎng)絡(luò)G₁的(x₀,y₀)最大流.]

算法設(shè)計(jì):對(duì)于給定的有向無(wú)環(huán)圖G,找出G的一個(gè)最小路徑覆蓋.

數(shù)據(jù)輸入:由文件input.txt提供輸入數(shù)據(jù).文件第1行有2個(gè)正整數(shù)n和m.n是給定有向無(wú)環(huán)圖G的頂點(diǎn)數(shù),m是G的邊數(shù).接下來(lái)的m行,每行有2個(gè)正整數(shù)i和j,表示一條有向邊(i,j).

結(jié)果輸出:將最小路徑覆蓋輸出到文件output.txt.從第1行開始,每行輸出一條路徑.文件的最后一行是最少路徑數(shù).

問(wèn)題描述:給定一個(gè)無(wú)向圖G=(V.E),設(shè)是G的頂點(diǎn)集.對(duì)任意,若u∈U且v∈V-U,就稱(u,1)為關(guān)于頂點(diǎn)集U的條割邊.頂點(diǎn)集U的所有割邊構(gòu)成圖G的一個(gè)割.G的最大割是指G中所含邊數(shù)最多的割.

算法設(shè)計(jì):對(duì)于給定的無(wú)向圖G,設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法,計(jì)算G的最大割.

數(shù)據(jù)輸入:由文件input.txt給出輸入數(shù)據(jù).第1行有2個(gè)正整數(shù)n和m,表示給定的圖G有n個(gè)頂點(diǎn)和m條邊,頂點(diǎn)編號(hào)為1,2,...,n.接下來(lái)的m行中,每行有2個(gè)正整數(shù)u和y,表示圖G的一條邊(u,v).

結(jié)果輸出:將計(jì)算的最大割的邊數(shù)和頂點(diǎn)集U輸出到文件output.txt.文件的第1行是最大割的邊數(shù);第2行是表示頂點(diǎn)集U的向量x(1≤i≤n),x=0表示頂點(diǎn)i不在項(xiàng)點(diǎn)集U中,x=1表示頂點(diǎn)i在頂點(diǎn)集U中.

給定簡(jiǎn)單無(wú)向圖G=，且|V|=n，|E|>(1/2)(n-1)(n-2)，試證G是連通圖。試給出|V|=n，|E|=(1/2)(n-1)(n-2)的簡(jiǎn)單無(wú)向圖G=是不連通的例子。

給定簡(jiǎn)單無(wú)向圖G=證明：Δ(G)<|V|。

給定簡(jiǎn)單無(wú)向圖G=，且|V|=m，|E|=n。試證，若，則G是哈密爾頓圖。

給定無(wú)向圖G=，且對(duì)任意結(jié)點(diǎn)v∈V，有d(v)≥2。試證，G至少有一基本圈。

設(shè)G是一個(gè)用鄰接表表示的連通無(wú)向圖。對(duì)于G中某個(gè)頂點(diǎn)v，若從G中刪去頂點(diǎn)v及與頂點(diǎn)v相關(guān)聯(lián)的邊后，G變成由兩個(gè)或兩個(gè)以上非空連通分量所組成的圖，則稱v是原來(lái)圖G的一個(gè)關(guān)節(jié)頂點(diǎn)。如下圖中，只有頂點(diǎn)4和頂點(diǎn)6是關(guān)節(jié)頂點(diǎn)，而其他頂點(diǎn)都不是關(guān)節(jié)頂點(diǎn)。試敘述尋找圖G的所有關(guān)節(jié)頂點(diǎn)的算法，并用算法語(yǔ)言(Pascal或C)編寫一個(gè)實(shí)現(xiàn)你所給出的算法的程序?！緩?fù)旦大學(xué)1996八(20分)】

設(shè)有一個(gè)無(wú)向圖G=(V,E)和G'=(V',E')，如果G'是G的生成樹，則下面不正確的說(shuō)法是( )

A．G'為G的子圖

B．G'為G的連通分量

C．G'為G的極小連通子圖且V'=V

D．G'是G的一個(gè)無(wú)環(huán)子圖

已知帶權(quán)連通無(wú)向圖G=(V，E)，其中V：{v1，v2，v3，v4，v5，v6，v7)，E={(v1，v2)10，(v1，v3)2，(v3，v4)2，(v3，v6)11，(v2，v5)1，(v4，v5)4，(v4，v6)6，(v5，v7)7，(v6，v7)3}(注：頂點(diǎn)偶對(duì)括號(hào)外的數(shù)據(jù)表示邊上的權(quán)值)，從源點(diǎn)v1到頂點(diǎn)v7的最短路徑上經(jīng)過(guò)的頂點(diǎn)序列是（ ）。

A．v1，v2，v5，v7

B．v1，v3，v4，v6，v7

C．v1，v2，v3，v4，v5，v7

D．v1，v2，v5，v4，v6，v6

設(shè)有一個(gè)無(wú)向圖G=(V，E)和G′=(V′,E′)，如果G′為G的生成樹，則下面不正確的說(shuō)法是(40)。

A．G′為G的子圖

B．G′為G的極小連通子圖且V′=V

C．G′為G的一個(gè)無(wú)環(huán)子圖

D．G′為G的邊通分量