이진매트로이드

매트로이드 이론에서 이항 매트로이드는 유한장 GF(2)에 걸쳐 나타낼 수 있는 매트로이드다.^[1]즉, 이형성까지, 그들은 원소가 a(0,1)-매트릭스의 열이고 해당 열이 GF(2)에서 선형적으로 독립된 경우에만 요소 집합이 독립된 매트로이드들이다.

대체 특성화

매트로이드 $M{\displaystyle }$ ${\displaystyle M}$은(는) 다음과 같은 경우에만 이진수임$$

• 대칭(0,1)-매트릭스에서 정의한 매트로이드다.^[2]
• 매트로이드 회로의 $모든$ S ${\$에 대해 $S{\displaystyle \mathcal{}}$ ${\$에서 회로의 대칭적 차이를 회로의 분리 결합으로 나타낼 수 있다$$.^[3][4]
• 매트로이드의 모든 회로 쌍에 대해 대칭 차이는 다른 회로를 포함한다.^[4]
• 모든 $쌍$에 대해${\displaystyle ,}$ $C{\displaystyle }$ ${\displaystyle C}$이(가) $M$의 회로이고$$ $D{\displaystyle }$ ${\$$displaystyle M$ ${\displaystyle D}$ ${\displaystyle D}$의 이중 매트로이드 회로인$$ D$$ $displaystyle C\cap$ D$}$은 짝수다$$.^[4][5]
• For every pair ${\displaystyle B,C}$ where ${\displaystyle B}$ is a basis of ${\displaystyle M}$ and ${\displaystyle C}$ is a circuit of ${\displaystyle M}$, ${\displaystyle C}$ is the symmetric difference of the fundamental circuits induced in ${\displaystyle B}$ by the elements of ${\displaystyle C}$${\displaystyle \setminus }$ B ${\displaystyle C\setminus$ B$\}.$^[4][5]
• $M{\displaystyle }$ ${\displaystyle M}$의 matroid 부차 없음은 4점선인$$균일한 matroid $U{\displaystyle }$ $4$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$ U${}_{4}^{2}}$이다.^[6][7][8]
• 매트로이드와 연관된 기하학적 격자에서는 높이 2의 모든 간격은 최대 5개의 원소를 가진다.^[8]

관련매트로이드

모든 일반 매트로이드와 모든 그래픽 매트로드는 이항이다.^[5]이항 매트로이드는 파노 평면(비정규격 이항 매트로이드 7개 요소)을 포함하지 않거나 마이너로서 이중을 포함하지 않는 경우에만 정규 분포를 따른다.^[9], 만약 그것의 미성년자 .[10]K5{\displaystyle K_{5}의 그래픽 matroid}도 K3의 이중, 3{\displaystyle K_{3,3}}을 포함하지 못하는 이진 matroid 그래픽이다 만약 이진 matroid의 모든 회로 이상한 기수고, 서로에게서 나서 그것의 회로야 한다 모두 해체되다;이 경우, 그것으로 표시할 수도 있다.월e 선인장 그래프의 그래픽 매트로이드.^[5]

추가 속성

$M{\displaystyle }$ ${\displaystyle M}$이(가) 바이너리 매트로이드인 경우 이중 매트로이드인 경우 $M{\displaystyle }$ ${\displaystyle M}$의 모든 마이너도 마찬가지$.$^[5] 또한 바이너리 매트로이드의 직접 합은 이진이다.

하라리와 웨일스(1969)는 초당적 매트로이드를 모든 회로가 고른 카디널리티를 갖는 매트로이드로 정의하고, 오일러리 매트로이드는 소자를 분리형 회로로 분할할 수 있는 매트로이드로 정의한다.그래픽 매트로이드 등급 내에서 이 두 속성은 각각 초당 그래프와 오일러 그래프(모든 정점이 짝수도를 갖는 불필요하게 연결된 그래프)의 매트로이드를 설명한다.평면 그래프(따라서 평면 그래프의 그래픽 매트로이드에도 해당)의 경우 이 두 가지 속성은 이중이다. 평면 그래프 또는 그 매트로드는 이중성이며 이중성이 오일러인 경우에만 양분적이다.2진수 매트로이드도 마찬가지다.그러나 이러한 이중성이 분해되는 비이진성 매트로이드가 존재한다.^[5][11]

주어진 matroid가 2진수인지 여부를 테스트하는 알고리즘은 독립성 oracle을 통해 matroid에 액세스할 수 있는 경우 기하급수적인 수의 오라클 쿼리를 수행해야 하므로 다항식 시간을 사용할 수 없다.^[12]

참조