매트로이드

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

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

정의[편집]

매트로이드 집합 와 그 부분집합들의 집합 로 구성된다. 여기서 의 원소들을 독립 집합(獨立集合, 영어: independent set)이라고 한다. 이 데이터는 다음 공리들을 만족시켜야 한다.[1]

  • (공집합의 독립성) 공집합은 독립 집합이다. 즉, 이다.
  • (독립성의 유전 영어: hereditary property) 독립 집합의 부분집합은 독립이다. 즉, 만약 라면 이다.
  • (추가성 영어: augmentation property) 만약 이며, 의 극대 원소이지만 의 극대 원소가 아니라면, 가 존재한다.
  • (극대 독립 집합의 존재) 만약 라면, 닫힌 구간 는 극대 원소를 갖는다.

만약 가 유한 집합이라면, 마지막 조건은 자동적으로 성립된다. 독립 집합이 아닌 집합을 종속 집합(영어: dependent set)이라고 한다.

매트로이드 에 대하여,

  • 만약 유한 집합이라면, 유한 매트로이드(영어: finite matroid)라고 한다.
  • 만약 임의의 에 대하여 의 모든 유한 부분 집합이 독립 집합인 경우 또한 독립 집합이라면, 유한형 매트로이드(영어: finitary matroid)라고 한다.[1]

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

매트로이드 회로(영어: circuit)는 의 최소 종속 집합이다. 즉, 모든 진부분집합이 독립 집합인 종속 집합이다.

부분 매트로이드[편집]

매트로이드 의 부분집합 위에서, 는 매트로이드를 이룬다. 이를 부분 매트로이드(영어: submatroid)라고 한다. 매트로이드의 부분집합 계수는 부분 매트로이드로서의 계수이다.

폐포[편집]

매트로이드 의 부분집합 폐포 (영어: closure) 는 다음과 같다.

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

쌍대 매트로이드[편집]

매트로이드 쌍대 매트로이드 는 다음과 같이 정의된다. 집합으로서, 이지만,

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

이 연산은 쌍대성을 가진다. 즉, 이다.

텃 다항식[편집]

매트로이드 텃 다항식(영어: Tutte polynomial)은 다음과 같은 2변수 다항식 이다.

여기서 는 매트로이드 의 계수이다.

[편집]

균등 매트로이드[편집]

균등 매트로이드(영어: uniform matroid) 는 다음과 같다.

  • 집합으로서, 개의 원소를 갖는다.
  • 의 독립 집합은 크기가 이하인 집합이다.

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

에 대한 유한 차원 벡터 공간 의 유한 부분 중복집합 를 생각하자. (임의로 순서를 잡으면, 이는 에 대한 행렬로 나타낼 수 있다.) 일차독립 부분 중복집합들의 집합이라고 하면, 는 매트로이드를 이룬다.

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

그래프 의 변들의 집합 이 주어지면, 들의 집합이라고 하자. 그렇다면 는 매트로이드를 이루며, 이를 순환 매트로이드(영어: cycle matroid) 라고 한다. 순환 매트로이드의 회로는 그래프의 순환들이다.

그래프에서, 접합(영어: bond) 는 제거하면 연결 성분의 수가 증가하는 변의 극소 집합이다. 의 접합을 회로로 갖는 매트로이드를 접합 매트로이드(영어: bond matroid) 라고 한다. 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.

작은 매트로이드의 수[편집]

크기가 인 서로 동형이 아닌 매트로이드의 수는 다음과 같다 ().

1, 2, 4, 8, 17, 38, 98, 306, 1724, 383172, … (OEIS의 수열 A55545)

이를 이라고 하면, 다음이 성립한다.[2]

크기가 인 서로 동형이 아닌 단순 매트로이드의 수는 다음과 같다 ().

1, 1, 1, 2, 4, 9, 26, 101, 950, 376467, … (OEIS의 수열 A2773)

역사[편집]

해슬러 휘트니가 1935년 도입하였다.[3] 1938년에 일본의 나카자와 다케오(일본어: 中澤 武雄 (なかざわ たけお))가 동일한 개념을 독립적으로 발견하였으나,[4][5][6][7] 크게 알려지지 못했다. 이후 윌리엄 토머스 텃이 매트로이드 이론을 발달시켰고, 텃 다항식과 같은 중요한 개념들을 발견하였다.

참고 문헌[편집]

  1. Bruhn, Henning; Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, Paul Wollan (2013년 6월 1일). “Axioms for infinite matroids”. 《Advances in Mathematics》 (영어) 239: 18–46. arXiv:1003.3919. Bibcode:2010arXiv1003.3919B. doi:10.1016/j.aim.2013.01.011. Zbl 1279.05013. 
  2. (영어). arXiv:1206.6270.  |제목=이(가) 없거나 비었음 (도움말)
  3. 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. JFM 61.0073.03. JSTOR 2371182. MR 1507091. Zbl 0012.00404. 
  4. Nakasawa, Takeo (1935). “Zur Axiomatik der linearen Abhängigkeit I”. 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 2: 235–255. JFM 61.1341.03. Zbl 0012.22001. 
  5. Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit II”. 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 3: 45–69. JFM 62.0649.01. Zbl 0013.31406. 
  6. Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit III”. 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 3: 123–136. JFM 62.1400.01. Zbl 0016.03704. 
  7. 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. 

바깥 고리[편집]