證明定理15.8.

定理15.8：設(shè)u,v為n階無向圖簡單圖G中兩個(gè)不相鄰的頂點(diǎn),且d(u)+d(v)≥n,則G為哈密頓圖GU(u,v)為哈密頓圖((u,v)是加的新邊.

設(shè)G=(V，E)為無向簡單圖，|V|=n，Δ(G)為圖G中結(jié)點(diǎn)的最大次數(shù)，請指出下面4個(gè)中哪個(gè)不等式是正確的．

  (1)Δ(G)＜n；  (2)Δ(G)≤n；

  (3)Δ(G)＞n；  (4)Δ(G)≥n．

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

算法設(shè)計(jì):對于給定的無向圖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.接下來的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中.

設(shè)G=<V，E>為無向簡單圖，|V|=n，△(G)為圖G中結(jié)點(diǎn)的最大次數(shù)，請指出下面4個(gè)中哪個(gè)不等式是正確的．

  (1)△(G)＜n；  (2)△(G)≤n；

  (3)△(G)＞n；  (4)△(G)≥n

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

下列各命題中。哪個(gè)是真命題? ()

A、若一個(gè)有向圖是強(qiáng)連通圖，則是有向歐拉圖。

B、n(n ≥1)階無向完全圖 Kn都是歐拉圖。

C、n(n ≥1)階有向完全圖都是有向歐拉圖。

D、二分圖G=〈V1, V2, E〉必不是歐拉圖。

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

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

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

數(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.第2行有n個(gè)正整數(shù)表示n個(gè)頂點(diǎn)的權(quán).接下來的m行中,每行有2個(gè)正整數(shù)u和v,表示圖G的一條邊(u,v).

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