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

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

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

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

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

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

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

問題描述:給定一個賦權(quán)無向圖G=(V,E),每個頂點都有權(quán)值w(v).如果,且對任意(u,V)∈E有u∈U或v∈U,就稱U為圖G的一個頂點覆蓋.G的最小權(quán)頂點覆蓋是指G中所含頂點權(quán)之和最小的頂點覆蓋.

算法設(shè)計:對于給定的無向圖G,設(shè)計一個優(yōu)先隊列式分支限界法,計算G的最小權(quán)頂點覆蓋.

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

結(jié)果輸出:將計算的最小權(quán)頂點覆蓋的頂點權(quán)值和以及最優(yōu)解輸出到文件output.txt.文件的第1行是最小權(quán)頂點覆蓋頂點權(quán)之和;第2行是最優(yōu)解xi(1≤i≤n),xi=0表示頂點i不在最小權(quán)頂點覆蓋中,xi=1表示頂點i在最小權(quán)頂點覆蓋中.

設(shè)計算法以判斷給定的無向圖G中是否存在一條以網(wǎng)為起點的包含所有頂點的簡單路徑，若存在，返回TRUE，否則，返回FALSE(注：本算法中可以調(diào)用以下幾個函數(shù)：FIRSTADJ(G，V)——返回圖G中頂點V的第一個鄰接點的號碼，若不存在，則返回0；NEXTADJ(G，W)——返回圖G中頂點V的鄰接點中處于W之后的鄰接點的號碼，若不存在，則返回0；NODES(G)——返回圖G中的頂點數(shù))。【合肥工業(yè)大學(xué)1999五、5(8分)】

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

設(shè)G=<V，E>為一無向圖。若對于任意的，均有P(G-V₁)≤|V₁|，則G是哈密頓圖。以上結(jié)論成立嗎?為什么?

設(shè)無向圖G=(V，E)和G’=(V’，E’)，如果G’是G的生成樹，則下列說法中錯誤的是（ ）。

A．G’為G的子圖

B．G’為G的連通分量

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

D．G’是G的一個無環(huán)子圖

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

設(shè)無向圖G=(V，E)和G’=(V’，E’)，如果G’是G的生成樹，則下面說法中錯誤的是 ( )。

A．G’是G的子圖

B．G’是G的連通分量

C．G’是G的極小連通子圖且V=V’

D．G’是G的一個無環(huán)子圖

設(shè)有兩個無向圖G=V,E)，G=(礦，E’)，如果G是G的生成樹，則下列說法不正確的是( )。【北京交通大學(xué)2006一、5(2分)】

A．G是G的子圖

B．G是G的連通分量

C．G是G的無環(huán)子圖

D．G是G的極小連通子圖，且V"=V

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

A．G'為G的子圖

B．G'為G的連通分量

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

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