作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散一題組
時間Wed Oct 21 17:38:22 2020
題目:
https://imgur.com/a/cbSlBwA
看到題組有點傻眼
教授把graph theory和countability結合
嘗試做了(a)也不知道方向對不對
(a)
Consider (|V|, |E|, v[i], e[i])
where 1<=i<=|V| and 1<=j<=|E|
∵|V|, |E|, v[i], e[i] ∈ N
∴(|V|, |E|, v[i], e[i]) ∈ NxNxNxN
∵NxNxNxN is countable and
there is a bijection between NxNxNxN and N
∴the set of all finite graphs is countable
(b)不知道理解有沒有問題
fixed, countably infinite set of vertices
我可以說|V|=n∈ N 嗎?
那|E|最多也只有C(|V|,2)個
那我可以回到part(a)的證法
(c)如果我(b)的理解是對的
那(c)不就是(b)的一種特例?
(d)完全沒想法
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.144.194 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1603273106.A.AAC.html
1F：→ hwanger : (a) { V finite set of N} is countable, 10/21 17:58
2F：→ hwanger : {G a subgraph of complete graph} is finite 10/21 17:58
3F：→ hwanger : countable union of countable set is countable 10/21 17:58
4F：→ hwanger : (b) 無窮可數 所以|V|=|N| 不是有限 10/21 18:01
5F：→ hwanger : (c) 將V分成兩個無窮子集 然後用Hint 10/21 18:06
6F：→ hwanger : (d)一樣將V分成兩個無窮子集 然後依此對每一個遞增 10/21 18:25
7F：→ hwanger : 數列造一個特別的tree 並依hint得到uncountable的結 10/21 18:26
8F：→ hwanger : 論 10/21 18:26
9F：→ hwanger : 等等有事 抱歉 看其他大大能不能補上其他想法 或者 10/21 18:28
10F：→ hwanger : 晚點我再補上細節 抱歉 10/21 18:28
11F：→ LiquidTLO : b部分 如果|V|=|N|，我可以說{V countably infinite 10/22 00:47
12F：→ LiquidTLO : set of N} is countable 10/22 00:47
13F：→ LiquidTLO : 我要如何判斷subgraphs呢? 可以說subgraphs Gi, i= 10/22 00:50
14F：→ LiquidTLO : 1,2,...,N 都是countable sets來推得countable嗎? 10/22 00:51
17F：→ hwanger : 不太清楚你文中(a)部份的v[i],e[i]是什麼 冏 10/22 01:50
18F：→ hwanger : (b)部份是說 固定一個頂點集合V V是無窮可數的 10/22 01:52
19F：→ hwanger : 則考慮所有的graph其頂點集合為V 所形成的集合 10/22 01:53
20F：→ LiquidTLO : 就vertex 1,2,3..., edge 1,2,3 10/22 01:54
21F：→ hwanger : 我之前只是草草寫過想法 而沒有把符號定清楚 抱歉 10/22 01:56
22F：→ hwanger : edge 1,2,3是指? 10/22 01:57
23F：→ LiquidTLO : 第一個edge, 第二個edge... 10/22 01:58
24F：→ LiquidTLO : 終於看懂(c)的hint有多重要了.. 10/22 02:05
25F：→ hwanger : 可是第一個edge 第二個edge...不是整數呀 10/22 02:10
26F：→ LiquidTLO : 話說deg=2的重要性是確保N->N嗎? 10/22 02:10
27F：→ hwanger : 先等一下 我(c)是錯的 之後再改 抱歉 10/22 02:45
28F：→ LiquidTLO : 不會，不急 10/22 02:49
30F：→ hwanger : degree=2 應該是讓我們將V的元素排成一直線 然後像 10/22 06:58
31F：→ hwanger : G_1一樣將相鄰的頂點連起來 10/22 06:59
32F：→ LiquidTLO : 話說我現在想到(b)的另一個解，不知道對不對 10/23 15:37
33F：→ LiquidTLO : |V|=|N|-> |E|=C(|V|,2)=C(|N|,2)=power set of N 10/23 15:39
34F：→ LiquidTLO : power set of natural numbers is uncountable 10/23 15:40
35F：→ LiquidTLO : 應該說the cardinality of P(N) is uncountable 10/23 15:41
36F：→ hwanger : 不是很清楚C(|V|,2)是指什麼 不過如果你是想說對任 10/23 15:58
37F：→ hwanger : 意i<j (i,j)有取與不取的選項的話 那cardinality的 10/23 16:00
38F：→ hwanger : 確和P(N)一樣多 10/23 16:00
39F：→ LiquidTLO : 對，我是這樣想 10/23 16:04
40F：→ hwanger : 不是很重要 不過你的符號可能要改一下 |E|是固定一 10/23 20:41
41F：→ hwanger : 個圖的edge數 不過你想要的其實是所有可能圖的個數 10/23 20:42