1.ignore
2.ignore
3.O(V2)

4.證明:
考慮一個(gè)頂點(diǎn)u,u屬于V
對(duì)BFS算法，當(dāng)執(zhí)行到u出隊(duì)時(shí)，有

for each v belongs to Adj[u]

            do if color[v] <- GRAY
                        d[v]<-   d[u]+1
                        n[v]<-    u
                        ENQUEUE(Q,v)（參考算導(dǎo)P325）
由此，對(duì)點(diǎn)u的鄰接鏈中的任意點(diǎn)v，如果v為白，則d[v]=d[u]+1。對(duì)u的鄰接鏈中任意一點(diǎn)均為如此，所以可知對(duì)v,v屬于u的鄰接點(diǎn),d[v]=d[u]+1，即d[v]的值與順序無關(guān)

電腦畫圖太麻煩，不畫了，大概說下

對(duì)22-3圖b
S的兩個(gè)鄰接點(diǎn)，r&&w,若r在s鄰接表的前面，w在后面，則必然r為s的左兒子，w為右兒子。反之則反

5.don't understand

6. 二分圖...先跳過 DDD

7.沒想出來復(fù)雜度合適的算法，看了別人思路...

考慮BFS出廣度優(yōu)先樹，然后DP求最大值.

if(x==leaf)
   D(x)=0;
else
   D(x)=max{ maxiD(x.childi)),maxij{(d(x).childi) + d(x).childj)} + 2}

8.