作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
标题[理工] 104 台大电机丙 选择第16题
时间Sun Dec 13 18:17:28 2020
https://i.imgur.com/k5164Bu.jpg
16题
目前确定的是A选项是错的，蝴蝶结
B选项直接上网查是对的，八面体是8个三角型组成的那个
证明方式：假设largest clique=4，随便选四个点中其中一个点V1，会有一个对角不是ad
jacent
C错，跟A一样的图形加方向
D不确定到底该不该选
题目描述的很笼统
没有给指数限制，那有边有点就一定能够满足题目叙述，但感觉不是要考这个...
E的话不太会证，尤其是不确定若是1个点的clique的情况怎麽讨论
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.139.127.136 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607854653.A.91E.html
1F：→ chengweihsu: (D) DAG任两点间至多一条path,所以#path应当正比於# 12/16 13:32
2F：→ chengweihsu: node，非指数增长 12/16 13:32
3F：→ chengweihsu: (E) 设G之minimum clique partition 为 12/16 13:32
4F：→ chengweihsu: P = {C_1,...,C_k},其中 |C_i|<=|C_ j|, for all 12/16 13:32
5F：→ chengweihsu: 1 <= i < j <= k,因为G上的每个node至多连出e条边， 12/16 13:32
6F：→ chengweihsu: 所以该node与其连接的e个node， 12/16 13:32
7F：→ chengweihsu: 共e+1个点，最大只会形成K_(e+1)。 12/16 13:32
8F：→ chengweihsu: n=|V|=|C_1 U ... U C_k|<=|C_1|+...+|C_k| 12/16 13:32
9F：→ chengweihsu: <=k|C_k|=k(e+1) 12/16 13:32
10F：→ chengweihsu: => k >= n/(e+1) 12/16 13:32