매트로이드의 기초
Basis of a matroid수학에서 매트로이드의 기본은 매트로이드의 최대 독립 집합, 즉 다른 독립 집합에 포함되지 않는 독립 집합이다.
예
예를 들어, 다음과 같은 독립된 세트를 사용하여 지면 세트 R2(이차원 유클리드 평면의 벡터) 위에 있는 매트로이드(matroid)를 고려하십시오.
두 개의 베이스를 가지고 있는데, 그 베이스는 {(0,1)}, {0,3},(2,0)이다.이것들은 포함시 최대치인 유일한 독립형 세트들이다.
이 기반은 다음과 같은 몇 가지 전문화된 종류의 매트로이드에 특화된 이름을 가지고 있다.[1]
- 독립된 집합이 숲인 그래픽 매트로이드에서는 그 기초를 그래프의 스패닝 포리스트라고 부른다.
- 독립 집합이 주어진 초당적 그래프에서 일치의 끝점인 횡단 매트로이드에서, 베이스를 횡단이라고 한다.
- 독립된 집합이 주어진 벡터 공간에서 선형적으로 독립된 벡터 집합인 선형 매트로이드에서는 베이스를 벡터 공간의 베이스라고 부른다.따라서, 매트로이드의 기본 개념은 선형 대수로부터 기본 개념을 일반화한다.
- 독립된 세트가 모두 최대 k(일부 정수 k)에서 카디널리티로 설정된 경우, 베이스는 카디널리티 정확히 k로 설정된 모든 세트다.
- 요소들이 범주로 분할되고 독립된 집합이 각 범주 c의 최대 kc 요소를 포함하는 파티션 매트로이드에서, 베이스는 모두 범주 c의 정확히 k 요소를c 포함하는 집합이다.
- 지반 집합 E의 모든 하위 집합이 독립적인 자유 매트로이드에서, 고유한 근거는 E이다.
특성.
교환
모든 매트로이드는 두 개의 고유한 A 및 에 대해 다음 속성을 만족한다[2][3]
- Basis-exchange property: if , then there exists an element such that is a basis.
- Symmetric basis-exchange property: if , then there exists an element such that both and are bases. 브루알디는[4] 그것이 사실상 염기교환 재산과 동등하다는 것을 보여주었다.
- Multiple symmetric basis-exchange property: if , then there exists a subset such that both and are bases.브라이레츠키, 그린, 우달 등은 (독립적으로) 사실상 염기교환 재산에 해당한다는 것을 보여주었다.
- 바이어시브 베이시스 교환 특성:There is a bijection from to , such that for every , is a basis.브루알디는[4] 그것이 기본 교환 재산과 맞먹는다는 것을 보여주었다.
- 파티션 기준 교환 속성:For each partition of into m parts, there exists a partition of into m parts, such that for every ( i ) B 가 기본이다.[5]
그러나 대칭적이고 비주사적인 기본 교환 특성은 모든 매트로이드에 의해 충족되지 않는다. 즉, 기본 주문 가능한 매트로이드에 의해서만 충족된다.
일반적으로 대칭 기준 교환 속성에서 b A{\B\이(가) 고유할 필요는 없다.일반 매트로이드는 한 교환 특성을 가지고 있는데, 이는 A B 의 경우 해당 b가 고유하다는 것을 의미한다[6]
카디널리티
의 멤버가 다른 멤버의 적절한 하위 집합이 될 수 없다는 것은 기본 교환 속성에서 따온 것이다.
또한 주어진 모형의 모든 염기들은 동일한 카디널리티를 가진다.선형 매트로이드에서는 모든 베이스의 카디널리티를 벡터 공간의 치수라고 부른다.
닐 화이트의 추측
모든 모종이 다음과 같은 성질을 만족한다고 추측된다.[2]모든 정수 t ≥ 1에 대해, 만약 B와 B'가 동일한 멀티셋 유니언을 가진 베이스의 두 t-t-tule이라면, B를 B'로 변환하는 대칭 교환의 순서가 있다.
특성화
매트로이드의 기초는 매트로이드의 특성을 완전히 나타낸다. 집합은 기준의 부분 집합인 경우에만 독립적이다.Moreover, one may define a matroid to be a pair , where is the ground-set and is a collection of subsets of , called "bases", with the following properties:[7][8]
- (B1) 베이스가 하나 이상 있음 - 이 (가) 비어 있지 않음;
- (B2) If and are distinct bases, and , then there exists an element such that is a basis (this is the basis-exchange재산의
(B2)는 A와 B의 어떤 두 베이스가 주어진다면, 우리는 단일 원소의 일련의 교환에 의해 A를 B로 변형시킬 수 있다는 것을 암시한다.특히 이는 모든 베이스가 같은 카디널리티를 가져야 한다는 것을 암시한다.
이중성
If is a finite matroid, we can define the orthogonal or dual matroid by calling a set a basis in if and only if its complement is in ( 이 실로 매트로이드임을 확인할 수 있다.이 정의는 ( 의 이중은(E {\ {B}}) , 임을 즉시 암시한다[9]: 32 [10]
이중성을 이용하여 재산(B2)을 다음과 같이 대체할 수 있음을 증명할 수 있다.
(B2*) If and are distinct bases, and , then there exists an element such that is a basis.
회로
기초에 대한 이중 개념은 회로다.매트로이드의 회로는 최소 종속 집합, 즉 적절한 하위 집합이 모두 독립적인 종속 집합이다.이 용어는 그래픽 매트로이드의 회로가 해당 그래프의 사이클이기 때문에 발생한다.
one may define a matroid to be a pair , where is the ground-set and is a collection of subsets of , called "circuits", with the following properties:[8]
- (C1) 빈 세트는 회로가 아니다.
- (C2) 회로의 서브셋은 회로가 아니다.
- (C3) C와1 C가2 회로이고 x가 교차로에 있는 요소라면 C {x 는 회로를 포함한다.
Another property of circuits is that, if a set is independent, and the set is dependent (i.e., adding the element makes it dependent), then contains a unique circuit , 그리고 을(를) 포함하고 있다이 회로를 w.r.t.{\ J의 기본 회로라고 한다 독립 벡터 J 에 벡터 를 추가하면 의 원소들의 고유한 선형 조합이 있다는 선형 대수학 사실과 유사하다. 과 (와) 같은 {\ J[10]
참고 항목
- Matroid polytope - Rn(여기서 n은 matroid에 있는 원소의 수)의 폴리토프로서, 정점은 matroid의 기저부의 지시 벡터다.
참조
- ^ Ardila, Federico (2007). "Matroids, lecture 3". youtube. Archived from the original on 2020-02-14.
- ^ a b Bonin, Joseph E.; Savitsky, Thomas J. (2016-01-01). "An infinite family of excluded minors for strong base-orderability". Linear Algebra and Its Applications. 488: 396–429. arXiv:1507.05521. doi:10.1016/j.laa.2015.09.055. ISSN 0024-3795. S2CID 119161534. Lay summary (PDF).
{{cite journal}}
:Cite는 사용되지 않는 매개 변수를 사용한다.lay-url=
(도움말) - ^ https://www.youtube.com/watch?v=pipoFmeDWIs
- ^ a b Brualdi, Richard A. (1969-08-01). "Comments on bases in dependence structures". Bulletin of the Australian Mathematical Society. 1 (2): 161–167. doi:10.1017/S000497270004140X. ISSN 1755-1633.
- ^ Greene, Curtis; Magnanti, Thomas L. (1975-11-01). "Some Abstract Pivot Algorithms". SIAM Journal on Applied Mathematics. 29 (3): 530–539. doi:10.1137/0129045. hdl:1721.1/5113. ISSN 0036-1399.
- ^ McGuinness, Sean (2014-07-01). "A base exchange property for regular matroids". Journal of Combinatorial Theory, Series B. 107: 42–77. doi:10.1016/j.jctb.2014.02.004. ISSN 0095-8956.
- ^ Welsh, D. J. A. (1976), Matroid Theory, L.M.S. Monographs, vol. 8, Academic Press, ISBN 978-0-12-744050-7, Zbl 0343.05002. 섹션 1.2, "매트로이드에 대한 축계", 페이지 7–9.
- ^ a b Federico, Ardila (2012). "Matroids: Lecture 6". Youtube.
- ^ White, Neil, ed. (1986), Theory of Matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl 0579.00001
- ^ a b Ardila, Federico (2012). "Matroids lecture 7". Youtube.