Re: [其他] 用structural induction 證明
※ 引述《a606155123 (冷氣團團長)》之銘言：
: 各位大大有2題要請教
: 用structural induction方法來證
: 1.E=V-1(邊=點-1 跟tree的生成有關)
: 2.E=V+F-1 (邊=點+面-1)
: 謝謝大大回答!!_
先回答第一題好了:
Basis Step:
If there is only one node in the tree, E = 0, V = 1. => E = V - 1 (G1)
If there are two nodes, E = 1, V = 2. => E = V - 1 (G2)
If there are three nodes, E = 2, V = 3. => E = V - 1 (G3)
The following are the graphs above.
--------------------------------------------
| | | |
| | | |
| | | ● |
| | | \ |
| | | ● |
| ● | ●----● | / |
| | | ● |
| | | |
| (G1) | (G2) | (G3) |
|------------|---------------|-------------|
Suppose the statement is true for all tree with less and equal to n nodes,
n > 0.
Then, for a tree T = G(V,E) with n+1 nodes,
we can divide these tree into two trees by
removing an edge connecting two nodes x and y.
Let these two trees be T1 = G(V1,E1) containing x
and T2 = G(V2,E2) containing y.
Then V1 + V2 = V = n+1 and E = E1 + E2 + 1
By our construction, 1 ≦ V1 ≦ n, 1 ≦ V2 ≦ n.
Furthemore, by hypothesis, E1 = V1 - 1 and E2 = V2 - 1.
Therefore, E = E1 + E2 + 1
= (V1 - 1) + (V2 - 1) + 1
= V1 + V2 -1
= V - 1
= n
The statement is true.
By structural induction, we complete the proof.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.160.15
推
12/13 13:17, , 1F
12/13 13:17, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：