作者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/cn.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