매트로이드 - 위키백과, 우리 모두의 백과사전 매트로이드 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 조합론에서, 매트로이드 ( 영어 : matroid 메이트로이드 [ * ] ) 는 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이다. [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다. 목차 1 정의 1. 1 독립 집합을 통한 정의 1. 2 기저를 통한 정의 1. 3 회로를 통한 정의 1. 4 폐포를 통한 정의 1. 5 계수 함수를 통한 정의 1. 6 정의들 사이의 관계 2 종류 2. 1 유한성 2. 2 작은 회로의 부재 3 연산 3. 1 부분 매트로이드 3. 2 쌍대 매트로이드 3. 3 직합 3. 4 마이너 3. 5 안
합 E [UNK] V { [UNK] displaystyle E [UNK] subset V } 를 생각하자. ( 임의로 순서를 잡으면, 이는 K { [UNK] displaystyle K } 에 대한 행렬로 나타낼 수 있다. ) I ( E ) [UNK] P ( E ) { [UNK] displaystyle { [UNK] mathcal { I } } ( E ) [UNK] subset { [UNK] mathcal { P } } ( E ) } 가 E { [UNK] displaystyle E } 의 일차독립 부분 중복집합들의 집합이라고 하면, ( E, I ( E ) ( E ) ) { [UNK] displaystyle ( E, { [UNK] mathcal { I } } ( E ) ( E ) ) } 는 매트로이드를 이룬다. 이를 선형 매트로이드 ( 영어 : linear matroid ) 라고 한다. 그래프의 매트로이드 [ 편집 ] 이 부분의 본문은
playstyle ( E, { [UNK] mathcal { I } } ) } 를 유한 매트로이드 ( 有 限 matroid, 영어 : finite matroid ) 라고 한다. 만약 모든 회로가 유한 집합이라면 ( 즉, 임의의 A [UNK] E { [UNK] displaystyle A [UNK] subseteq E } 에 대하여, 만약 A { [UNK] displaystyle A } 의 모든 유한 부분 집합이 독립 집합인 경우 A { [UNK] displaystyle A } 또한 독립 집합이라면 ), ( E, I ) { [UNK] displaystyle ( E, { [UNK] mathcal { I } } ) } 를 유한형 매트로이드 ( 有 限 形 matroid, 영어 : finitary matroid ) 라고 한다. [ 7 ] : 18, [UNK] 0 만약 모든 회로와 쌍대 회로의 교집합이 유한 집합이라면, ( E, I
[ 22 ] : 263, [UNK] 6, Problem P531 데니스 [UNK] ( 영어 : Denis A. Higgs, 1932 ~ 2011 ) 는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 " B - 매트로이드 " ( 영어 : B - matroid ) 라는 개념이었다. [ 23 ] 이후 1978년에 제임스 옥슬리 ( 영어 : James G. Oxley ) 는 " B - 매트로이드 " 의 모임이 쌍대성을 가지며 매트로이드 마이너에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다. [ 24 ] 이후 2010년에 이 " B - 매트로이드 " 에 대한 여러 자연스러운 공리화들이 발견되었으며, [ 7 ] 이후 이 개념이 무한 매트로이드의 통상적인 정의로 굳어지게 되었다. 참고 문헌 [ 편집 ] ↑ Gordon, Gary ; McNult
영어 : linear matroid ) 라고 한다. 그래프의 매트로이드 [ 편집 ] 이 부분의 본문은 순환 매트로이드입니다. 모든 그래프에는 순환 매트로이드라는 유한형 매트로이드 및 그 쌍대 매트로이드인 접합 매트로이드가 대응된다. 작은 크기의 매트로이드 [ 편집 ] 공집합 위에는 유일한 매트로이드 구조가 존재하며, 이는 균등 매트로이드 Unif ( 0, 0 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 0, 0 ) } 이다. 이는 무변 그래프의 순환 매트로이드이자, 임의의 벡터 공간 속의 공집합으로부터 정의되는 선형 매트로이드이다. 크기 1 [ 편집 ] 크기 1의 매트로이드 동형류들은 다음 두 가지이다. Unif ( 1, 1 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 1, 1
18, [UNK] 0 만약 모든 회로와 쌍대 회로의 교집합이 유한 집합이라면, ( E, I ) { [UNK] displaystyle ( E, { [UNK] mathcal { I } } ) } 를 유순 매트로이드 ( [UNK] [UNK] matroid, 영어 : tame matroid ) 라고 한다. [ 7 ] : 28, [UNK] 2. 6 [ 8 ] : [UNK] 1 즉, 다음과 같은 함의 관계가 존재한다. 유한 매트로이드 [UNK] 유한형 매트로이드 [UNK] 유순 매트로이드 [UNK] 매트로이드 작은 회로의 부재 [ 편집 ] 크기 1의 회로는 고리 ( 영어 : loop ) 라고 하며, 크기 2의 회로는 평행변 ( 平 行 [UNK], 영어 : parallel lines ) 이라고 한다. ( 이러한 용어는 다중 그래프에 대응되는 순환 그래프에서 유래하였다. ) 모든 회로의 크기가 2 이상인 매트로이드를 단순 매트
계수 2 ) Unif ( 3, 1 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 3, 1 ) } ( 계수 1 ) Unif ( 2, 1 ) [UNK] Unif ( 1, 0 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 2, 1 ) [UNK] oplus [UNK] operatorname { Unif } ( 1, 0 ) } ( 계수 1 ) Unif ( 2, 0 ) [UNK] Unif ( 1, 1 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 2, 0 ) [UNK] oplus [UNK] operatorname { Unif } ( 1, 1 ) } ( 계수 1 ) Unif ( 3, 0 ) { [UNK] displaystyle [UNK] operatorname { Unif } ( 3, 0 ) } ( 계수 0 ) 이 가운데 단순 매트로이드인
ame { Pow } ( S ) ( S ) ) } 는 매트로이드를 이룬다. 이를 E { [UNK] displaystyle E } 의 부분 매트로이드 ( 영어 : submatroid ) 라고 한다. 매트로이드의 부분 집합 S { [UNK] displaystyle S } 의 계수는 부분 매트로이드로서의 계수이다. 쌍대 매트로이드 [ 편집 ] 매트로이드 ( E, I ) { [UNK] displaystyle ( E, { [UNK] mathcal { I } } ) } 의 쌍대 매트로이드 ( E [UNK], I [UNK] ) { [UNK] displaystyle ( E ^ { * }, { [UNK] mathcal { I } } ^ { * } ) } 는 다음과 같이 정의된다. 집합으로서, E = E [UNK] { [UNK] displaystyle E = E ^ { * } } 이지만, I [UNK] = { S [UNK] P ( E ) : cl I ( E [UNK] S
본문은 매트로이드 마이너입니다. 부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 매트로이드 마이너라고 한다. 이는 그래프 마이너의 일반화이다. 안둘레와 밖둘레 [ 편집 ] 이 부분의 본문은 안둘레입니다. 매트로이드의 안둘레는 가장 작은 회로의 크기이다. 마찬가지로, 매트로이드의 밖둘레는 회로들의 크기의 상한이다. 성질 [ 편집 ] 계수 [ 편집 ] 유한 매트로이드의 서로 다른 기저들의 크기는 서로 같다. 만약 일반화 연속체 가설이 참이라면, 모든 ( 유한 또는 무한 ) 매트로이드들의 서로 다른 기저들의 크기는 서로 같은 기수이다. [ 9 ] : 861, Theorem 2 이 경우, 기저의 크기를 매트로이드의 계수 ( [UNK] 數, 영어 : rank ) 라고 한다.
[UNK] log - { 2 } m - { n } [UNK] leq n - { [UNK] frac { 3 } { 2 } } [UNK] log - { 2 } n { [UNK] frac { 1 } { 2 } } [UNK] log - { 2 } { [UNK] frac { 2 } { [UNK] pi } } 1o ( 1 ) } 범주론적 성질 [ 편집 ] 임의의 두 유한 매트로이드 E { [UNK] displaystyle E }, E [UNK] { [UNK] displaystyle E'} 사이의 함수 f : E → E [UNK] { [UNK] displaystyle f [UNK] colon E [UNK] to E'} 에 대하여 다음 세 조건이 서로 동치이며, 이를 만족시키는 함수를 강사상 ( [UNK] [UNK] [UNK], 영어 : strong morphism ) 이라고 하자. 임의의 B [UNK] A [UNK] E { [UNK] displaystyle B [UNK] subseteq A [UNK] sub
조합론에서 매트로이드(영어: matroid 메이트로이드[*])는 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이다. 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다.