매트로이드: 두 판 사이의 차이

내용 삭제됨 내용 추가됨

인라인

2014년 1월 3일 (금) 13:58 판

조합론에서, 매트로이드(영어: matroid)는 선형독립성을 공리화한 조합론적인 대상이다.

정의

매트로이드 $(E,{\mathcal {I}})$ 는 유한집합 $E$ 와 그 부분집합들의 집합 ${\mathcal {I}}\subset {\mathcal {P}}(E)$ 로 구성된다. 여기서 ${\mathcal {I}}$ 의 원소들을 독립집합(영어: independent set)이라고 한다. 이 데이터는 다음 공리들을 만족시켜야 한다.

(공집합의 독립성) $\varnothing \in {\mathcal {I}}$ .
(독립성의 유전 영어: hereditary property) 독립집합의 부분집합은 독립이다. 즉, 만약 $A\in {\mathcal {I}}$ 라면 ${\mathcal {P}}(A)\subset {\mathcal {I}}$ 이다.
(추가성 영어: augmentation property) 만약 $A,B\in {\mathcal {I}}$ 이고 $|A|>|B|$ 라면, $B\cup \{a\}\in {\mathcal {I}}$ 인 $a\in {\mathcal {A}}$ 가 존재한다.

역사

해슬러 휘트니가 1935년 도입하였다.^[1] 1938년에 일본의 나카사와 다케오(中澤武雄)가 동일한 개념을 독립적으로 발견하였으나,^[2]^[3]^[4]^[5] 크게 알려지지 못했다.

참고 문헌

↑ Whitney, Hassler (1935). “On the abstract properties of linear dependence”. 《American Journal of Mathematics》 (The Johns Hopkins University Press) 57 (3): 509–533. doi:10.2307/2371182. JSTOR 2371182. MR 1507091.
↑ Nakasawa, Takeo (1935). “Zur Axiomatik der linearen Abhängigkeit I”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 2: 235–255.
↑ Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit II”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 3: 45–69.
↑ Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit III”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 3: 123–136.
↑ Nishimura, Hirokazu; Susumu Kuroda. 《A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory》. Springer. doi:10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9.

바깥 고리

Weisstein, Eric Wolfgang. “Matroid”. 《Wolfram MathWorld》 (영어). Wolfram Research.
“Matroid”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.

[1] Whitney, Hassler (1935). “On the abstract properties of linear dependence”. 《American Journal of Mathematics》 (The Johns Hopkins University Press) 57 (3): 509–533. doi:10.2307/2371182. JSTOR 2371182. MR 1507091.

[2] Nakasawa, Takeo (1935). “Zur Axiomatik der linearen Abhängigkeit I”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 2: 235–255.

[3] Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit II”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 3: 45–69.

[4] Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit III”. 《Science reports of the Tokyo Bunrika Daigaku A》 (東京文理科大学) 3: 123–136.

[5] Nishimura, Hirokazu; Susumu Kuroda. 《A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory》. Springer. doi:10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9.

[1]

[2]

[3]

[4]

[5]