基本介紹
劃分擬陣是一種組合構形，它是由在有限集E={e，e，…，e}上的劃分π導出的擬陣M。
若劃分π把E分割為劃分塊B，B，…，B，並相應地設定非負整數d，d，…，d，則E的子集I為劃分擬陣的獨立集，若且唯若對於i=1，2，…，m，均有|I∩B|≤d。
例如對於有向圖G=(V，A)，A的子集I為這樣一類集合：I中沒有兩條邊同指向一個節點，以這樣的I為獨立集可得一划分擬陣，相應地，J為A的這樣一類集合：J中沒有兩條邊始於同一節點，以這樣的J為獨立集可得另一划分擬陣 。
舉例說明
例1 設E是一個有限集，∏是E的一個劃分，即∏={E₁，E₂，…E}為E的不相交子集的集合，並且覆蓋E。E的一個子集I稱為是獨立的(I∈ F)，若且唯若I中任何兩個元素不在∏的同一個集合里，即對一切j=1，2，…，p，|I∩E|≤1。則M=(E， F)為一個擬陣，並稱其為劃分擬陣 。
劃分擬陣
劃分擬陣
劃分擬陣要證明M是一個擬陣，只要證明它有明確定義的秩函式即可。令J(A)={j≤p：E∩A≠∅)，讀者容易驗證，r(A)=|J(A)|是滿足要求的秩函式。事實上，對於E的任一個子集A，我們可構造A的極大獨立子集如下：對於使E∩A≠∅的每一個E，我們在E中選取A的一個元素，那么所選取的元素集合，就是A的一個極大獨立集。例如，若E={e，…，e}，∏=，那么在M中的秩為3，A的極大獨立集為，A的支撐
劃分擬陣對每一個j，集合E中任意兩個元素就構成M的一個圈。因此，{e，e}和{e，e}都是M的圈。
例2 給定一個有向圖(V，A)，對每一孤a∈A有一個權w(a)≥0。希望找出A的一個最大權的子集B，使得B中任何兩條弧都沒有公共的終點。這是關於子集系統(A， B)的一個組合最佳化問題，其中A的一個子集B∈ B，若且唯若B中任何兩條弧都沒有公共的終點。這一問題看起來很象無向圖的匹配同題，但是它比匹配問題容易得多。例如在圖1中，選取進入v的弧時，只要挑選一個最大權的即可。因為選取進入一個點的任何一條弧，對於選取進入其它點的弧沒有影響，故greedy算法能得到該問題的最優解。
劃分擬陣例2中的子集系統，是劃分擬陣的另一個例子。在圖1上的有向圖D中，設B是D中弧的一個集合，若B中任何兩條弧都不指向同一個節點，則稱B為獨立集。這就等價於把D的弧進行劃分，使得指向同一節點v的弧之集合定義為E。在這個例子中，下述定義的∏為D的弧集的一個劃分：
劃分擬陣因此，這個系統是一個劃分擬陣M(並稱其為有向圖D的入孤劃分擬陣)，從而greedy算法能求例2的解是十分自然的了 。
