發表新討論
#40621: 作法


qerpzzea@gmail.com (賽希爾 cecill(陳宥穎))

學校 : 高雄市立中正高級中學
編號 : 169400
來源 : [114.40.35.5]
最後登入時間 ：
2024-07-19 09:54:49
g598. 4. 真假子圖 -- 2021年11月APCS | From: [114.40.34.172] | 發表日期 : 2024-06-01 19:54

用染色法判定

如果不能成功著色則代表有矛盾

 

本題重點

不能只有染兩種顏色

例如 範例1

0 1 0 2 1 3 2 3 4 5
只能確定
0 1 2 3之間的關係 和4 5之間的關係
不能確定這兩個子圖之間的關係
所以可以這樣染色
0 1 2 3(染1~2)
4 5(染3~4)
 
ZeroJudge Forum