<commit_before>---
layout: post
title: poset and Dilworth theorem
excerpt: "從 偏序集 介紹到Dilworth定理"
modified: 2017-03-04
categories: articles

---

關鍵字：     
Dilworth theorem / partially ordered set / non-strict partial order / 偏序 / 非嚴格偏序 / 自反偏序  

這篇文章是為了把之前做的筆記整理成電子版本，順便幫助自己之後複習，還請多多指教！     


研讀較抽象的算法或概念，最害怕不知道能幹嘛，所以我在開頭這邊先給出一個題目以及簡述，才開始介紹什麼是偏序關係、偏序集以及Dilworth theorem，最後，再使用該定理來解決開頭的問題，以及給出其他例題，以下正文開始。    

##### 傳送門：[105學年度資訊學科能力決賽第五題-直昇機抓寶](http://nhspc.csie.ntnu.edu.tw/2016/ref_exam.php)   


> 題目簡述：    
>     
> 在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？    
>
> ***N ≤ 800,000*** 看這Ｎ這麼大，N 平方掃過去的做法可以先收一收了。    
> ```
> input          output
> 5              3
> 2 2   
> 1 1   
> 0 0   
> 2 2   
> 4 4   
> ``` 




已經知道偏序關係的同學可以跳過 ***偏序*** 這節，想直接看詳解請用力下拉。    

# 偏序  

我們先假設Ａ是個集合（例：整數集合），定義一個二元關係Ｐ（例：≤，左右各需要一個運算元稱為二元），如果Ｐ滿足：    
1. reflexivity (自反性)    
2. antisymmetry (反對稱性）   
3. transitivity（傳遞性）   

***則我們說，Ｐ為Ａ的一個偏序關係***    
（本文的偏序，皆是以非嚴格偏序、自反偏序來說明）    

#### reflexivity 自反性
> ***∀a ∈ A , （a,a） ∈ P***    

（a,a）∈ P 是指（a,a）滿足Ｐ關係。   

舉個例子：    
1. Ａ是 整數集合    
2. ａ是 整數集合中的任意一個元素，其實就是整數的意思啦    
3. Ｐ是 小於等於關係 （≤）    

則（a,a）∈Ｐ，因為 ａ≤ａ 成立    

再舉個例子：    
1. ａ是 正整數    
2. Ｐ是 整除    

則（a,a）∈Ｐ，因為 ａ整除ａ 成立

我們總結一下偏序關係中，自反性的意思如下：    
*若Ｐ為Ａ的一個偏序關係，則對於所有Ａ內的元素ａ，（a,a）都 **必須** 滿足Ｐ關係。*    

補充：∀ 是指對於所有集合內的元素，英文為for all    

#### antisymmetry 反對稱性    
> ***∀a ∈ A , ∀b ∈ A，if (a,b)∈P and (b,a)∈P，then a=b***    

（a,b）∈Ｐ內的ａ與ｂ不可對調，除非他們相等。    

繼續用剛剛的例子：    
1. ａ,ｂ是 整數    
2. Ｐ是 小於等於    

（a,b）∈Ｐ → ａ≤ｂ    
（b,a）∈Ｐ → ｂ≤ａ   

很明顯了吧！？，除非ａ＝ｂ否則不成立。    
值得一提的是，if(a,b)∈P 千萬別誤會成是任意(a,b)都∈Ｐ！   

#### transitivity 傳遞性    
> ***∀a ∈ A , ∀b ∈ A , ∀c ∈ A，if (a,b)∈P and (b,c)∈P，then (a,c)∈P***    

用反對稱性的代換一下，大概就懂這個意思了吧ＸＤ

#### 小整理    
> 對於集合Ａ，某二元關係Ｐ如果滿足自反性、反對稱性、傳遞性，則Ｐ為集合Ａ的一個偏序關係。    

太拗口？？    
反正拿整數以及小於等於來思考一下就好啦，運算兩邊可相同、兩邊不可任意交換、可推導（ａ≤ｂ,ｂ≤ｃ→ａ≤ｃ）！    


# 偏序集、可比、鏈    

終於講完偏序關係，這裡當作大家都已經理解了(?)，我們來繼續定義一些東西    

首先是偏序集合，再來是可比不可比，最後解釋鏈與反鏈。    

#### 偏序集合 poset

偏序集 ＝ 偏序集合 ＝ partially ordered set = poset    

偏序集 ＝ 集合 ＋ 集合的一個偏序關係 ＝（Ａ, Ｐ）    

舉個例子，剛剛我們用來講解偏序關係的小於等於以及整數集合，可以表示為（𝚭, ≤）。     

#### 可比 comparable    

在偏序集內任意兩元素ａ,ｂ，滿足（a,b）∈Ｐ或（b,a）∈Ｐ，則稱ａ,ｂ可比（comparable）， ***否則不可比*** （incomparable）    

舉個例子：    
poset（ 𝚭, 整除 ）內，元素２,４可比，元素３,４不可比，因為滿足（2,4）∈Ｐ，２整除４成立；而３整除４ 或 ４整除３ 都不成立，所以３,４不可比。    


再舉個例子：   
（𝚭, ≤）內任兩元素可比，思考看看吧！   

（對Tree不熟先去惡補一下 或跳往chain）  
  
再舉個比較另類的例子（Ａ,Ｐ）    

1. Ａ集合 = 有根（序）樹上的所有節點    
2. Ｐ關係 = ａ在以ｂ為根的子樹內    

（請自行驗證Ｐ為Ａ的偏序關係）   

則對於樹上任一點ｖ，ｖ與所有祖先及子樹成員可比，與所有祖先的子樹（不包括ｖ所在的子樹）成員不可比。    


#### 鏈 chain

我比較常聽到人家唸chain，而不稱鏈，所以這邊我們都使用 chain 來稱呼～    

chain：若集合內任兩元素可比，稱為 chain。    
antichain：若集合內任兩元素不可比，稱為 antichain。    

延續可比不可比所舉的例子來說明 chain / antichain    

- （𝚭, 整除）    
chain：｛１,２,４,８｝antichain：｛３,４,５｝    
- （Ａ,Ｐ）    
chain：｛ｖ以及所有祖先 ｝ antichain：｛ｖ的子節點 ｝    

# Dilworth theory

有了以上各種定義，我們可以在上面堆出一個定理    

##### In any finite poset, the minimum number of chains cover equals the maximum size of an antichain    

太抽象的東西看英文比較好理解ＸＤ，有看沒有懂的請繼續往下走   

定理所說的是，令（Ｓ,Ｐ）是一個偏序集且Ｓ是有限集合（正整數集合不是個有限集合），minimum chains cover 會等同於最大 antichain 的 size    

minimun chains cover：把所有集合內元素 都涵蓋在內所需要最少的 chain 的數量。或者也可以這麼理解，集合最少會被切割成幾個 chain ，無法再更少。     

如果要將偏序集分割成最少的 chain ，則 chain 的數量會與集合內最大（元素最多）的 antichain 大小相等。    

一句話，***最大反鏈等於最小鏈覆蓋***   
當然，最大鏈等於最小反鏈覆蓋也是成立的。    

到這裡我們已經把精華解釋完畢，至於這個定理是如何成立的，建議自行先推導看看。    

key point : 集合要切成 chains 需把不可比的分開。    

另外，雖然本文說的是自反偏序集（非嚴格偏序集），但此定理只要是偏序集都適用，需要是有限集合。    
--- 

還記得開頭的題目嗎？    

> 在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？    

先觀察題目，簡單地發現一些特點：    
1. 一進入區間立刻往上走才是最佳解，所以通過區間的位置一定是某個經過的區間左界，當然也可能是目前這層的區間左界    
2. 上方的區間右界如果在目前位置的左方則不可能經過該區間   

###### 看起來很正常的兩點就是關鍵，如果下方出現無法理解的邏輯請回來複習這兩點

第一點保證了我們在紀錄最佳路徑時，只需透過經過的左界來維護即可。    

具體來說每次要經過區間時，如果該區間左界在目前位置的左邊則不予理會（等於往上走就剛好在一個區間內），否則更新目前位置為該區間左界（等於往上又往右走才經過該區間）。  <commit_msg>fix syntax error<commit_after>---
layout: post
title: poset and Dilworth theorem
excerpt: "從 偏序集 介紹到Dilworth定理"
modified: 2017-03-04
categories: articles

---

關鍵字：     
Dilworth theorem / partially ordered set / non-strict partial order / 偏序 / 非嚴格偏序 / 自反偏序  

這篇文章是為了把之前做的筆記整理成電子版本，順便幫助自己之後複習，還請多多指教！     


研讀較抽象的算法或概念，最害怕不知道能幹嘛，所以我在開頭這邊先給出一個題目以及簡述，才開始介紹什麼是偏序關係、偏序集以及Dilworth theorem，最後，再使用該定理來解決開頭的問題，以及給出其他例題，以下正文開始。    

##### 傳送門：[105學年度資訊學科能力決賽第五題-直昇機抓寶](http://nhspc.csie.ntnu.edu.tw/2016/ref_exam.php)   


> 題目簡述：    
>     
> 在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？    
>
> ***N ≤ 800,000*** 看這Ｎ這麼大，N 平方掃過去的做法可以先收一收了。    
> ```
> input          output
> 5              3
> 2 2   
> 1 1   
> 0 0   
> 2 2   
> 4 4   
> ``` 




已經知道偏序關係的同學可以跳過 ***偏序*** 這節，想直接看詳解請用力下拉。    

# 偏序  

我們先假設Ａ是個集合（例：整數集合），定義一個二元關係Ｐ（例：≤，左右各需要一個運算元稱為二元），如果Ｐ滿足：    
1. reflexivity (自反性)    
2. antisymmetry (反對稱性）   
3. transitivity（傳遞性）   

***則我們說，Ｐ為Ａ的一個偏序關係***    
（本文的偏序，皆是以非嚴格偏序、自反偏序來說明）    

#### reflexivity 自反性
> ***∀a ∈ A , （a,a） ∈ P***    

（a,a）∈ P 是指（a,a）滿足Ｐ關係。   

舉個例子：    
1. Ａ是 整數集合    
2. ａ是 整數集合中的任意一個元素，其實就是整數的意思啦    
3. Ｐ是 小於等於關係 （≤）    

則（a,a）∈Ｐ，因為 ａ≤ａ 成立    

再舉個例子：    
1. ａ是 正整數    
2. Ｐ是 整除    

則（a,a）∈Ｐ，因為 ａ整除ａ 成立

我們總結一下偏序關係中，自反性的意思如下：    
*若Ｐ為Ａ的一個偏序關係，則對於所有Ａ內的元素ａ，（a,a）都 **必須** 滿足Ｐ關係。*    

補充：∀ 是指對於所有集合內的元素，英文為for all    

#### antisymmetry 反對稱性    
> ***∀a ∈ A , ∀b ∈ A，if (a,b)∈P and (b,a)∈P，then a=b***    

（a,b）∈Ｐ內的ａ與ｂ不可對調，除非他們相等。    

繼續用剛剛的例子：    
1. ａ,ｂ是 整數    
2. Ｐ是 小於等於    

（a,b）∈Ｐ → ａ≤ｂ    
（b,a）∈Ｐ → ｂ≤ａ   

很明顯了吧！？，除非ａ＝ｂ否則不成立。    
值得一提的是，if(a,b)∈P 千萬別誤會成是任意(a,b)都∈Ｐ！   

#### transitivity 傳遞性    
> ***∀a ∈ A , ∀b ∈ A , ∀c ∈ A，if (a,b)∈P and (b,c)∈P，then (a,c)∈P***    

用反對稱性的代換一下，大概就懂這個意思了吧ＸＤ

#### 小整理    
> 對於集合Ａ，某二元關係Ｐ如果滿足自反性、反對稱性、傳遞性，則Ｐ為集合Ａ的一個偏序關係。    

太拗口？？    
反正拿整數以及小於等於來思考一下就好啦，運算兩邊可相同、兩邊不可任意交換、可推導（ａ≤ｂ,ｂ≤ｃ→ａ≤ｃ）！    


# 偏序集、可比、鏈    

終於講完偏序關係，這裡當作大家都已經理解了(?)，我們來繼續定義一些東西    

首先是偏序集合，再來是可比不可比，最後解釋鏈與反鏈。    

#### 偏序集合 poset

偏序集 ＝ 偏序集合 ＝ partially ordered set = poset    

偏序集 ＝ 集合 ＋ 集合的一個偏序關係 ＝（Ａ, Ｐ）    

舉個例子，剛剛我們用來講解偏序關係的小於等於以及整數集合，可以表示為（𝚭, ≤）。     

#### 可比 comparable    

在偏序集內任意兩元素ａ,ｂ，滿足（a,b）∈Ｐ或（b,a）∈Ｐ，則稱ａ,ｂ可比（comparable）， ***否則不可比*** （incomparable）    

舉個例子：    
poset（ 𝚭, 整除 ）內，元素２,４可比，元素３,４不可比，因為滿足（2,4）∈Ｐ，２整除４成立；而３整除４ 或 ４整除３ 都不成立，所以３,４不可比。    


再舉個例子：   
（𝚭, ≤）內任兩元素可比，思考看看吧！   

（對Tree不熟先去惡補一下 或跳往chain）  
  
再舉個比較另類的例子（Ａ,Ｐ）    

1. Ａ集合 = 有根（序）樹上的所有節點    
2. Ｐ關係 = ａ在以ｂ為根的子樹內    

（請自行驗證Ｐ為Ａ的偏序關係）   

則對於樹上任一點ｖ，ｖ與所有祖先及子樹成員可比，與所有祖先的子樹（不包括ｖ所在的子樹）成員不可比。    


#### 鏈 chain

我比較常聽到人家唸chain，而不稱鏈，所以這邊我們都使用 chain 來稱呼～    

chain：若集合內任兩元素可比，稱為 chain。    
antichain：若集合內任兩元素不可比，稱為 antichain。    

延續可比不可比所舉的例子來說明 chain / antichain    

- （𝚭, 整除）    
chain：｛１,２,４,８｝antichain：｛３,４,５｝    
- （Ａ,Ｐ）    
chain：｛ｖ以及所有祖先 ｝ antichain：｛ｖ的子節點 ｝    

# Dilworth theory

有了以上各種定義，我們可以在上面堆出一個定理    

##### In any finite poset, the minimum number of chains cover equals the maximum size of an antichain    

太抽象的東西看英文比較好理解ＸＤ，有看沒有懂的請繼續往下走   

定理所說的是，令（Ｓ,Ｐ）是一個偏序集且Ｓ是有限集合（正整數集合不是個有限集合），minimum chains cover 會等同於最大 antichain 的 size    

minimun chains cover：把所有集合內元素 都涵蓋在內所需要最少的 chain 的數量。或者也可以這麼理解，集合最少會被切割成幾個 chain ，無法再更少。     

如果要將偏序集分割成最少的 chain ，則 chain 的數量會與集合內最大（元素最多）的 antichain 大小相等。    

一句話，***最大反鏈等於最小鏈覆蓋***   
當然，最大鏈等於最小反鏈覆蓋也是成立的。    

到這裡我們已經把精華解釋完畢，至於這個定理是如何成立的，建議自行先推導看看。    

key point : 集合要切成 chains 需把不可比的分開。    

另外，雖然本文說的是自反偏序集，但此定理偏序集都適用，只需要是有限集合。    

--- 

還記得開頭的題目嗎？    

> 在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？    

先觀察題目，簡單地發現一些特點：    
1. 一進入區間立刻往上走才是最佳解，所以通過區間的位置一定是某個經過的區間左界，當然也可能是目前這層的區間左界    
2. 上方的區間右界如果在目前位置的左方則不可能經過該區間   

###### 看起來很正常的兩點就是關鍵，如果下方出現無法理解的邏輯請回來複習這兩點

第一點保證了我們在紀錄最佳路徑時，只需透過經過的左界來維護即可。    

具體來說每次要經過區間時，如果該區間左界在目前位置的左邊則不予理會（等於往上走就剛好在一個區間內），否則更新目前位置為該區間左界（等於往上又往右走才經過該區間）。  
{'fraction_non_alphanumeric': 0.14088181581007045, 'fraction_numerical': 0.017740673102008872, 'mean_word_length': 3.5313238770685578, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2745426', 'n_tokens_mistral': 6842, 'n_tokens_neox': 7318, 'n_words': 570}