##atorname { Pow } ( E ) }. 그 원소를 기저 ( 基, 영어 : basis ) 라고 하며, 기저의 부분 집합을 독립 집합이라고 한다. 이는 다음 조건들을 만족시켜야 한다. [ 7 ] : 1. 2 B { displaystyle { mathcal { B } } neq varnothing } ( 추가성 ) 임의의 B, B B { displaystyle B, B'in { mathcal { B } } } 및 x B B { displaystyle x in B setminus B'} 에 대하여, 다음 조건을 만족시키는 x B B { displaystyle x'in B'setminus B } 가 항상 존재한다. ( B { x } ) { x } B { displaystyle ( B setminus { x } ) cup { x'} in { mathcal { B } } } ( 국소적 극대 독립 집합의 존재 ) 임의의 부분 집합 E E { displaystyle E'subseteq E } 및 기저 B B { displaystyle B in {
##akasawa, Takeo ( 1936 ). " Zur Axiomatik der linearen Ⅱ ". 《 Science reports of the Tokyo Bunrika Daigaku A 》 ( 독일어 ) ( 東 京 文 理 大 ) 3 : 45 - 69. JFM 62. 0649. 01. Zbl 0013. 31406. ↑ Nakasawa, Takeo ( 1936 ). " Zur Axiomatik der linearen Ⅲ ". 《 Science reports of the Tokyo Bunrika Daigaku A 》 ( 독일어 ) ( 東 京 文 理 大 ) 3 : 123 - 136. JFM 62. 1400. 01. Zbl 0016. 03704. ↑ Nishimura, Hirokazu ; Kuroda, Susumu ( 2009 ). 《 A lost mathematician, Takeo Nakasawa : the forgotten father of matroid theory 》 ( 영어 ). Springer - Verlag. ISBN 978 - 3 - 7643 - 8572 - 9. Zbl 1163. 01001. doi : 10. 1007 / 978 - 3 - 7643 - 8573 - 6. ↑
{ frac { 1 } { 2 } } log - { 2 } { frac { 2 } { pi } } 1o ( 1 ) } 범주론적 성질 [ 편집 ] 임의의 두 유한 매트로이드 E { displaystyle E }, E { displaystyle E'} 사이의 함수 f : E → E { displaystyle f colon E to E'} 에 대하여 다음 세 조건이 서로 동치이며, 이를 만족시키는 함수를 강사상 (, 영어 : strong morphism ) 이라고 하자. 임의의 B A E { displaystyle B subseteq A subseteq E } 에 대하여, rank ( f ( A ) ( A ) | f ( B ) ) rank ( A | B ) { displaystyle operatorname { rank } ( f ( A ) ( A ) | f ( B ) ) leq operatorname { rank } ( A | B ) } 이다. 임의의 A E { displaystyle A subseteq E } 에 대하여, cl ( f ( A ) ( A ) ) = f ( cl ( A ) ( A ) ) { displays
{ x } I } { displaystyle operatorname { cl } ( S ) = S cup { x in E colon exists I in { mathcal { I } } colon I cup { x } not in { mathcal { I } } } } 매트로이드 ( E, I ) { displaystyle ( E, { mathcal { I } } ) } 의 부분 집합 S { displaystyle S } 의 폐포 cl ( S ) { displaystyle operatorname { cl } ( S ) } 는 마찬가지로 상대 계수 함수로부터 다음과 같이 정의된다. cl ( S ) = max { S E : rank ( S | S ) = 0 } { displaystyle operatorname { cl } ( S ) = max { S'subseteq E colon operatorname { rank } ( S'| S ) = 0 } } ( 이러한 최대 원소가 항상 유일하게 존재함을 보일 수 있다. ) 매트로이드 ( E, I ) { displaystyle ( E, { mathcal { I } } ) } 의 상대 계수
##bl 1163. 01001. doi : 10. 1007 / 978 - 3 - 7643 - 8573 - 6. ↑ Tutte, William Thomas ( 1965 ). " Lectures on matroids ". 《 Journal of Research of the National Bureau of Standards ( U. S. A. ) B 》 ( 영어 ) 69 : 1 - 47. Zbl 0151. 33801. doi : 10. 6028 / jres. 069b. 001. ↑ Crapo, Henry Howland ; Rota, Gian - Carlo ( 1970 ). 《 On the Foundations of Combinatorial Theory Ⅱ. Combinatorial geometries 》 ( 영어 ). Massachusetts Institute of Technology Press. ISBN 978 - 0 - 262 - 53016 - 3. MR 0290980. ↑ Tutte, William Thomas ( 1971 ). 《 Introduction to the theory of matroids 》. Modern Analytic and Computational Methods in Science and Mathematics ( 영어 ) 37. Elsevier. Zbl 0231. 05027. ↑ Rado, Richard ( 1966 ). " Abstract linear dependence "
Applied Categorical Structures 》 ( 영어 ) 25. Bibcode : 2015arXiv151201390H. ISSN 0927 - 2852. arXiv : 1512. 01390. doi : 10. 1007 / s10485 - 017 - 9490 - 2. ↑ Whitney, Hassler ( 1935 ). " On the abstract properties of linear dependence ". 《 American Journal of Mathematics 》 ( 영어 ) 57 ( 3 ) : 509 - 533. JFM 61. 0073. 03. JSTOR 2371182. MR 1507091. Zbl 0012. 00404. doi : 10. 2307 / 2371182. ↑ Nakasawa, Takeo ( 1935 ). " Zur Axiomatik der linearen Ⅰ ". 《 Science reports of the Tokyo Bunrika Daigaku A 》 ( 독일어 ) ( 東 京 文 理 大 ) 2 : 235 - 255. JFM 61. 1341. 03. Zbl 0012. 22001. ↑ Nakasawa, Takeo ( 1936 ). " Zur Axiomatik der linearen Ⅱ ".
" 임의의 매트로이드에서, 기저들의 크기는 같다 " 라는 명제는 ZFC와 독립적이다. [ 10 ] : 4, Corollary 17 작은 매트로이드의 수 [ 편집 ] 작은 크기의 매트로이드의 동형류의 수 및 고리 없는 매트로이드의 동형류의 수 및 단순 매트로이드의 동형류의 수는 다음과 같다. [ 11 ] : 5, Table 1, Table 2 크기 매트로이드 동형류의 수 ( OEIS의 수열 A55545 ) 고리 없는 매트로이드 동형류의 수 ( OEIS의 수열 A58718 ) 단순 매트로이드 동형류의 수 ( OEIS의 수열 A2773 ) 주어진 집합 위의 매트로이드 구조의 수 ( OEIS의 수열 A58673 ) 주어진 집합 위의 고리 없는 매트로이드 구조의 수 ( OEIS의 수열 A58712 ) 주어진 집합 위의 단순 매트로이드 구조의 수 ( OEIS의 수열 A58721 ) 0 1 1 1 1 1 0 1 2 1 1 2 1 0 2 4 2 1 5 2 1 3 8 4 2 16 6 2 4 17 9 4 68 27 7 5 38 21 9 406 165 49 6 98 60 26 3807 2135 733 7 306 208 101 75164 55129 29760 8 1724 1418 950 10607540
##on T subseteq S } subseteq operatorname { Pow } ( E ) ^ { 2 } } 는 E { displaystyle E } 속의, 길이 2의 사슬들의 집합이다. 이 데이터는 다음 조건들을 만족시켜야 한다. [ 7 ] : 1. 5 임의의 ( A, B ) Pair ( E ) { displaystyle ( A, B ) in operatorname { Pair } ( E ) } 에 대하여, rank ( A | B ) | A B | { displaystyle operatorname { rank } ( A | B ) leq | A setminus B | } 임의의 A, B E { displaystyle A, B subseteq E } 에 대하여, rank ( A | A B ) rank ( A B | B ) { displaystyle operatorname { rank } ( A | A cap B ) geq operatorname { rank } ( A cup B | B ) } ( 유한 사슬에 대한 분해 ) 임의의 C B A E { displaystyle C subseteq B
##집합 모든 집합 기저 공집합 전체 집합 E { displaystyle E } 종속 집합 공집합이 아닌 집합 ( 없음 ) 회로 한원소 집합 ( 없음 ) 폐포 연산 전체 집합 값의 상수 함수 항등 함수 닫힌집합 전체 집합 E { displaystyle E } 모든 집합 상대 계수 함수 0 값의 상수 함수 차집합의 크기 이와 같은 두 종류의 매트로이드의 직합으로 표현될 수 있는 매트로이드를 이산 매트로이드 ( matroid, 영어 : discrete matroid ) 라고 한다. 보다 일반적으로, 임의의 집합 E { displaystyle E } 및 자연수 0 k { displaystyle 0 leq k } 에 대하여, 균등 매트로이드 ( matroid, 영어 : uniform matroid ) Unif ( E, k ) { displaystyle operatorname { Unif } ( E, k ) } 는 E { displaystyle E } 위의 다음과 같은 매트로이드이다. I = { S E : | S | k } { displaystyle { mathcal { I } } = { S subseteq E colon | S | leq k } } B = { S E
##playstyle E } 가 유한 집합이라면, ( E, I ) { displaystyle ( E, { mathcal { I } } ) } 를 유한 매트로이드 ( 有 限 matroid, 영어 : finite matroid ) 라고 한다. 만약 모든 회로가 유한 집합이라면 ( 즉, 임의의 A E { displaystyle A subseteq E } 에 대하여, 만약 A { displaystyle A } 의 모든 유한 부분 집합이 독립 집합인 경우 A { displaystyle A } 또한 독립 집합이라면 ), ( E, I ) { displaystyle ( E, { mathcal { I } } ) } 를 유한형 매트로이드 ( 有 限 形 matroid, 영어 : finitary matroid ) 라고 한다. [ 7 ] : 18, 0 만약 모든 회로와 쌍대 회로의 교집합이 유한 집합이라면, ( E, I ) { displaystyle ( E, { mathcal { I } } ) } 를 유순 매트로이드 ( matroid, 영어 : tame matroid ) 라고 한다. [ 7 ] : 28, 2. 6 [ 8 ] : 1 즉, 다음과 같은 함의 관계가 존재한다. 유한 매트로이드
조합론에서 매트로이드(영어: matroid 메이트로이드[*])는 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이다. 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다.