1.概念題,比較麻煩,幾個(gè)概念以前數(shù)據(jù)結(jié)構(gòu)課沒接觸過
2.
沒掃描儀...用手畫不如殺了我得了...
用文字大概說明吧
按DFS定義,順序是
q 4 8 10 9 3 6 7 2 5
數(shù)字含義是按圖上字母順序編號(hào),比如q應(yīng)該編為1號(hào),t應(yīng)該編為4號(hào)
然后對(duì)邊來說
q->w為正向邊(注:以下F表正向邊,B表反向邊,C表交叉邊,T表樹邊)
w->s,y->q,z->x為B
r->y,u->y為C
其它為T
3.比較簡(jiǎn)單
(u(v(y(xx)y)v)u)(w(zz)w)
4.證明:
(1)由定理22.8
u是v的祖先,所以d[u]<d[v]<f[v]<f[u]成立時(shí),(u,v)必然為樹邊或者前向邊
反之,若(u,v)是樹邊或前向邊,則
d[u]<d[v]<f[v]<f[u]顯然成立(不清楚的話畫畫P333的圖b)
(2)沒等號(hào)的情況跟上題類似,有等號(hào)的情況沒想通...
(3)
因?yàn)閐[v]<f[v]<d[u]<f[u]
由此畫出括號(hào)圖,顯然為交叉邊...(好像有點(diǎn)勉強(qiáng)...)
OR
由d[v]<f[v]<d[u]<f[u]不滿足(1)(2)中條件,所以不能為反向,樹邊或前向邊,由此應(yīng)為交叉邊...(好像更勉強(qiáng)...求達(dá)人)
5.
6.代碼題PASS掉
7. 郁悶了我,寫一半maxthon掛掉...郁悶

從v搜.再搜P
8.沒想出來
9.P334頁有講
if color[v]==WHITE
then (u,v)= T
if color[v]==GRAY
then (u,v)=B
if color[v]==BLACK
then (u,v)=C
10.
即使有入邊也有出邊,當(dāng)u被探查以后已經(jīng)被標(biāo)為GRAY||BLACK,不會(huì)繼續(xù)加入另一棵樹
11.我實(shí)在寫不出來數(shù)學(xué)的嚴(yán)格證明...當(dāng)面講應(yīng)該能講清楚...唉,數(shù)學(xué)差了害死人啊
12.看見星號(hào)直接跳過,過段時(shí)間來看