매트로이드

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

조합론에서, 매트로이드(영어: 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 Ia\in\mathcal A가 존재한다.

독립 집합이 아닌 집합을 종속 집합(영어: dependent set)이라고 한다.

매트로이드 E기저(영어: basis)는 E의 최대 독립 집합이다. 즉, 만약 독립 집합 B의 모든 진포함집합이 종속 집합이라면, B는 기저를 이룬다. 매트로이드의 서로 다른 기저들의 크기는 서로 같으며, 기저의 크기를 매트로이드의 계수(영어: rank) r(E)라고 한다. |E|-r(E)를 매트로이드의 쌍대계수(영어: corank)라고 한다.

부분 매트로이드[편집]

매트로이드 (E,\mathcal I)의 부분집합 S\subset E 위에서, (S,\mathcal I\cap\mathcal P(S))는 매트로이드를 이룬다. 이를 E부분 매트로이드(영어: submatroid)라고 한다. 매트로이드의 부분집합 S계수는 부분 매트로이드로서의 계수이다.

폐포[편집]

매트로이드 (E,\mathcal I)의 부분집합 S폐포 (영어: closure) \operatorname{cl}(S)는 다음과 같다.

\operatorname{cl}(S)=\{e\in E\colon r(S)=r(S\cup\{x\})\}\supset S

즉, S의 폐포는 S에 추가해도 계수가 바뀌지 않는 모든 원소들을 추가한 S의 포함집합이다. \operatorname{cl}(S)=S인 집합 S평탄면(영어: flat 플랫[*])이라고 한다. 매트로이드 E 속에서, 계수가 |E|-1인 평탄면을 초평면(영어: hyperplane 하이퍼플레인[*])이라고 한다.

쌍대 매트로이드[편집]

매트로이드 (E,\mathcal I)쌍대 매트로이드 (E^*,\mathcal I^*)는 다음과 같이 정의된다. 집합으로서, E=E^*이지만,

\mathcal I^*=\{S\in\mathcal P(E)\colon\operatorname{cl}_{\mathcal I}(E\setminus S)=E\}

이다. 이에 따라, E의 기저는 항상 E^*의 기저의 여집합이다.

이 연산은 쌍대성을 가진다. 즉, E^{**}=E이다.

텃 다항식[편집]

매트로이드 (E,\mathcal I)텃 다항식(영어: Tutte polynomial)은 다음과 같은 2변수 다항식 T_E(x,y)이다.

T_E(x,y)=\sum_{S\subset E}(1-x)^{r(E)-r(S)}(y-1)^{|S|-r(S)}

여기서 r(E)는 매트로이드 E의 계수이다.

[편집]

균등 매트로이드[편집]

균등 매트로이드(영어: uniform matroid)는 모든 부분집합이 독립인 매트로이드이다. 즉, 유한집합 E에 대하여 (E,\mathcal P(E))의 꼴이다.

벡터공간의 부분집합의 매트로이드[편집]

k에 대한 벡터공간 V의 유한 부분중복집합 E\subset V를 생각하자. \mathcal I(E)\subset\mathcal P(E)E일차독립 부분중복집합들의 집합이라고 하면, (E,\mathcal I(E))는 매트로이드를 이룬다.

그래프의 매트로이드[편집]

무향 그래프 \Gamma의 변들의 집합 E(\Gamma)이 주어지면, \mathcal I(\Gamma)\subset\mathcal P(E(\Gamma))\Gamma들의 집합이라고 하자. 그렇다면 (E(\Gamma),\mathcal I(\Gamma))는 매트로이드를 이룬다.

역사[편집]

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

참고 문헌[편집]

  1. (영어) Whitney, Hassler (1935년). On the abstract properties of linear dependence. 《American Journal of Mathematics》 57 (3): 509–533. doi:10.2307/2371182. JSTOR 2371182. MR1507091. Zbl 0012.00404. JFM 61.0073.03.
  2. (독일어) Nakasawa, Takeo (1935년). Zur Axiomatik der linearen Abhängigkeit I. 《Science reports of the Tokyo Bunrika Daigaku A》 2: 235–255. Zbl 0012.22001. JFM 61.1341.03.
  3. (독일어) Nakasawa, Takeo (1936년). Zur Axiomatik der linearen Abhängigkeit II. 《Science reports of the Tokyo Bunrika Daigaku A》 3: 45–69. Zbl 0013.31406. JFM 62.0649.01.
  4. (독일어) Nakasawa, Takeo (1936년). Zur Axiomatik der linearen Abhängigkeit III. 《Science reports of the Tokyo Bunrika Daigaku A》 3: 123–136. Zbl 0016.03704. JFM 62.1400.01.
  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
  • (영어) Bryant, Victor, Hazel Perfect (1980년). 《Independence Theory in Combinatorics》. London and New York: Chapman and Hall. ISBN 0-412-22430-5
  • (영어) Crapo, Henry H., Gian-Carlo Rota (1970년). 《On the Foundations of Combinatorial Theory: Combinatorial Geometries》. Cambridge, Mass.: M.I.T. Press. MR0290980. ISBN 978-0-262-53016-3
  • (영어) Gordon, Gary, Jennifer McNulty (2012년 9월). 《Matroids: A geometric introduction》. Cambridge University Press. doi:10.1017/CBO9781139049443. ISBN 978-052176724-8
  • (영어) Oxley, James (1992년). 《Matroid Theory》. Oxford: Oxford University Press. MR1207587. Zbl 0784.05002. ISBN 0-19-853563-5
  • (영어) Recski, András (1989년). 《Matroid Theory and its Applications in Electric Network Theory and in Statics》. Berlin and Budapest: Springer-Verlag and Akademiai Kiado. MR1027839. ISBN 3-540-15285-7
  • (영어) Truemper, Klaus (1992년). 《Matroid Decomposition》. Boston: Academic Press. MR1170126. ISBN 0-12-701225-7
  • (영어) Tutte, W. T. (1965년). Lectures on matroids. 《Journal of Research of the National Bureau of Standards (U.S.A.) B》 69: 1–47.
  • (영어) Tutte, W.T. (1971년). 《Introduction to the theory of matroids》, Modern Analytic and Computational Methods in Science and Mathematics 37. New York: American Elsevier Publishing Company. Zbl 0231.05027
  • (영어) Welsh, D. J. A. (1976년). 《Matroid Theory》, London Mathematical Society Monographs 8. Academic Press. Zbl 0343.05002. ISBN 0-12-744050-X
  • (영어) Wilson, R. J. (1973년 5월). An Introduction to Matroid Theory. 《The American Mathematical Monthly》 80 (5): 500–525. doi:10.2307/2319608. JSTOR 2319608. Zbl 0275.05018.

바깥 고리[편집]