[其他] 離散一題組

看板Math作者 (俊偉)時間5年前 (2020/10/21 17:38), 編輯推噓0(0推 0噓 41→)
留言41則, 2人參與, 5年前最新討論串1/1
題目: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://www.ptt.cc/bbs/Math/M.1603273106.A.AAC.html
→
10/21 17:58, 5年前 , 1F
(a) { V finite set of N} is countable,
10/21 17:58, 1F
→
10/21 17:58, 5年前 , 2F
{G a subgraph of complete graph} is finite
10/21 17:58, 2F
→
10/21 17:58, 5年前 , 3F
countable union of countable set is countable
10/21 17:58, 3F
→
10/21 18:01, 5年前 , 4F
(b) 無窮可數 所以|V|=|N| 不是有限
10/21 18:01, 4F
→
10/21 18:06, 5年前 , 5F
(c) 將V分成兩個無窮子集 然後用Hint
10/21 18:06, 5F
→
10/21 18:25, 5年前 , 6F
(d)一樣將V分成兩個無窮子集 然後依此對每一個遞增
10/21 18:25, 6F
→
10/21 18:26, 5年前 , 7F
數列造一個特別的tree 並依hint得到uncountable的結
10/21 18:26, 7F
→
10/21 18:26, 5年前 , 8F
論
10/21 18:26, 8F
→
10/21 18:28, 5年前 , 9F
等等有事 抱歉 看其他大大能不能補上其他想法 或者
10/21 18:28, 9F
→
10/21 18:28, 5年前 , 10F
晚點我再補上細節 抱歉
10/21 18:28, 10F
→
10/22 00:47, 5年前 , 11F
b部分 如果|V|=|N|，我可以說{V countably infinite
10/22 00:47, 11F
→
10/22 00:47, 5年前 , 12F
set of N} is countable
10/22 00:47, 12F
→
10/22 00:50, 5年前 , 13F
我要如何判斷subgraphs呢? 可以說subgraphs Gi, i=
10/22 00:50, 13F
→
10/22 00:51, 5年前 , 14F
1,2,...,N 都是countable sets來推得countable嗎?
10/22 00:51, 14F
→
10/22 01:46, 5年前 , 15F
10/22 01:46, 15F
→
10/22 01:47, 5年前 , 16F
10/22 01:47, 16F
→
10/22 01:50, 5年前 , 17F
不太清楚你文中(a)部份的v[i],e[i]是什麼 冏
10/22 01:50, 17F
→
10/22 01:52, 5年前 , 18F
(b)部份是說 固定一個頂點集合V V是無窮可數的
10/22 01:52, 18F
→
10/22 01:53, 5年前 , 19F
則考慮所有的graph其頂點集合為V 所形成的集合
10/22 01:53, 19F
→
10/22 01:54, 5年前 , 20F
就vertex 1,2,3..., edge 1,2,3
10/22 01:54, 20F
→
10/22 01:56, 5年前 , 21F
我之前只是草草寫過想法 而沒有把符號定清楚 抱歉
10/22 01:56, 21F
→
10/22 01:57, 5年前 , 22F
edge 1,2,3是指?
10/22 01:57, 22F
→
10/22 01:58, 5年前 , 23F
第一個edge, 第二個edge...
10/22 01:58, 23F
→
10/22 02:05, 5年前 , 24F
終於看懂(c)的hint有多重要了..
10/22 02:05, 24F
→
10/22 02:10, 5年前 , 25F
可是第一個edge 第二個edge...不是整數呀
10/22 02:10, 25F
→
10/22 02:10, 5年前 , 26F
話說deg=2的重要性是確保N->N嗎?
10/22 02:10, 26F
→
10/22 02:45, 5年前 , 27F
先等一下 我(c)是錯的 之後再改 抱歉
10/22 02:45, 27F
→
10/22 02:49, 5年前 , 28F
不會，不急
10/22 02:49, 28F
→
10/22 06:55, 5年前 , 29F
10/22 06:55, 29F
→
10/22 06:58, 5年前 , 30F
degree=2 應該是讓我們將V的元素排成一直線 然後像
10/22 06:58, 30F
→
10/22 06:59, 5年前 , 31F
G_1一樣將相鄰的頂點連起來
10/22 06:59, 31F
→
10/23 15:37, 5年前 , 32F
話說我現在想到(b)的另一個解，不知道對不對
10/23 15:37, 32F
→
10/23 15:39, 5年前 , 33F
|V|=|N|-> |E|=C(|V|,2)=C(|N|,2)=power set of N
10/23 15:39, 33F
→
10/23 15:40, 5年前 , 34F
power set of natural numbers is uncountable
10/23 15:40, 34F
→
10/23 15:41, 5年前 , 35F
應該說the cardinality of P(N) is uncountable
10/23 15:41, 35F
→
10/23 15:58, 5年前 , 36F
不是很清楚C(|V|,2)是指什麼 不過如果你是想說對任
10/23 15:58, 36F
→
10/23 16:00, 5年前 , 37F
意i<j (i,j)有取與不取的選項的話 那cardinality的
10/23 16:00, 37F
→
10/23 16:00, 5年前 , 38F
確和P(N)一樣多
10/23 16:00, 38F
→
10/23 16:04, 5年前 , 39F
對，我是這樣想
10/23 16:04, 39F
→
10/23 20:41, 5年前 , 40F
不是很重要 不過你的符號可能要改一下 |E|是固定一
10/23 20:41, 40F
→
10/23 20:42, 5年前 , 41F
個圖的edge數 不過你想要的其實是所有可能圖的個數
10/23 20:42, 41F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1Va06Igi (Math)