# Clique與獨立集

Clique內每對不同頂點相鄰，獨立集內每對不同頂點不相鄰；最大與極大不可混同。

mko-clique-and-independent-set · definition · v0.10.0



## 數學敘述

候選集合逐對核相鄰或不相鄰。單一大小r候選只給omega或alpha的下界；宣稱maximum須遍歷全部頂點子集合或另有全域上界。maximal只代表不能加入頂點，且clique大小只推出chi(G)>=omega(G)。





## 代表公式（精確 TeX）

omega(G)





## 成立條件


- 完整有限無loop簡單無向圖及無重複頂點子集。
- exact extrema題限定n<=9並遍歷全部2^n子集。





## 符號作用域


- omega — 最大clique大小
- alpha — 最大獨立集大小





## 直觀、定義與常見誤解

clique與independent set分別核全部不同頂點對。

maximal是局部不可擴張，maximum是全域最大基數。

clique給色數下界但不一般給等號。

把任一極大clique當最大clique，或由omega直接宣稱chi=omega。





## 已採用的推導導讀

[三頂點圖的全部clique與independent sets](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-clique-and-independent-set-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限簡單無向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-graph/) — 相鄰關係。
- [子集合](https://ocme.evemisslab.com/zh-Hant/mko/mko-subset/) — 候選頂點集合。





## 驗證界線

全域extremum證書限小型完整圖；不宣稱大型圖高效演算法。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入Ramsey bounds與perfect graphs。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/clique-and-independent-set.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-clique-and-independent-set/index.md)