[理工] [DS] 樹跟子樹的關係式

[dunkjames (Firefighter)]

再補充一個問題  補圖要怎麼看
為何右邊是左邊的補圖
定義上來說 不是要滿足G(V,E)=G(V,E')  其中E'= (V*V-E)

如果帶進去 不就是 E'=4*4-4=12 所以補圖應該要有12個邊
我怎麼想都覺得我錯了 但是不知道WHY

http://ppt.cc/BCVk

假如說

I is a subtree of J,
and J is a subtree of K,
then I is a subtree of K.

對嗎?

這題有爭議性的樣子? 好像會因為在不同條件下有所差異(?)
不過我直觀地認為是正確的

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.13.101
※ 編輯: dunkjames       來自: 192.192.13.101       (02/16 20:26)
推 bbhands:|E(G')| = n(n-1)-|E(G)|，不是n^2-|E(G)|，沒有self-loop
→ bbhands:以上為simple graph的情況
→ dunkjames:所以說 4(4-1)-|4|=8 ?!
→ dunkjames:可是他只有一條邊...
推 bbhands:你是在講你附的連結嗎？右邊並不是左邊的補圖
→ bbhands:V(G)=V(G')且E(G)∪E(G')=E(K_n) 這樣才是互為complement
→ bbhands:其中的∪為disjoint union