정규매트로이드

Regular matroid

수학에서, 정규의 매트로이드는 모든 분야에 걸쳐 표현될 수 있는 매트로이드다.

정의

매트로이드는 유한 집합의 하위 집합으로 정의되어 특정 공리를 만족한다.그 가족의 세트는 "독립 세트"라고 불린다.매트로이드를 구성하는 방법 중 하나는 벡터 공간에서 유한한 벡터 집합을 선택하고, 벡터 공간에서 선형적으로 독립적일 때 매트로이드에서 독립할 벡터의 부분 집합을 정의하는 것이다.이런 식으로 구성된 집합의 모든 집단은 모종이지만, 모든 모종이 이런 식으로 구성될 수 있는 것은 아니며, 서로 다른 영역에 걸친 벡터 공간은 모종으로부터 구성될 수 있는 서로 다른 모종 집합으로 이어진다.

매트로이드 은(는) 모든 F 에 대해 을(를) F 위에 있는 벡터 시스템으로 나타낼 수 있을 때 정규적이다[1][2]

특성.

만약 매트로이드가 규칙적이면, 그 이중 매트로이드도,[1] 그리고 모든 미성년자도 그렇다.[3]일반 모종의 모든 직접 합은 규칙적으로 유지된다.[4]

모든 그래픽 매트로이드(그리고 모든 동그래픽 매트로이드)는 규칙적이다.[5]반대로, 모든 일반 매트로이드는 그래프에서 클릭섬 연산을 일반화하는 매트로이드 결합 연산을 사용하여 그래픽 매트로이드, 공동 그래픽 매트로이드 및 그래픽이 아닌 특정 10요소 매트로이드를 결합하여 구성할 수 있다.[6]

일반 매트로이드의 염기 수는 그래픽 매트로이드에 대한 Kirchhoff의 매트릭스 트리 정리를 일반화하면서 관련 매트릭스의 결정요인으로 계산할 수 있다.[7]

특성화

균일한 매트로이드 2 4점선)은 규칙적이지 않다: 2요소 유한장 GF(2)에서는 실현될 수 없으므로 다른 모든 분야에 걸쳐 실현될 수 있지만 바이너리 매트로드는 아니다.Pano 평면(점 3배 중 7배가 종속되는 3등급 매트로이드)과 그 이중도 역시 규칙적이지 않다: GF(2)를 통해, 특성 2의 모든 분야에서 실현될 수 있지만 그것 이외의 어떤 분야에서도 실현될 수 없다.투테(1958)가 보여주었듯이, 이 세 가지 예는 규칙적인 모계 이론의 기초가 된다: 모든 비정규직 모계들은 이 세 가지 중 적어도 하나를 미성년자로 가지고 있다.따라서 일반 매트로이드는 세 가지 금지된 U 파노 비행기 또는 그 이중 중 한 가지를 가지고 있지 않은 정확히 매트로이드가 된다.[8]

매트로이드(matroid)가 정규적인 경우, GF(2)와 GF(3)의 두 분야에 걸쳐 명확하게 실현 가능해야 한다.그 반대는 사실이다: 이 두 분야 모두에 걸쳐 실현 가능한 모든 매트로이드들은 규칙적이다.그 결과는 Rota의 추측에 의해 규합된 결과의 일부인 이들 분야에 걸쳐 실현 가능한 금지된 작은 성질의 모체에서 비롯된다.[9]

일반 매트로이드는 모든 정사각형 서브트리셔가 0, 1 또는 -1을 갖는 매트릭스인 완전히 단변성 매트릭스에서 정의할 수 있는 매트로이드다.매트로이드(matroid)를 실현하는 벡터는 행렬의 행으로 간주할 수 있다.이러한 이유로, 일반 매트로이드는 때때로 단모형 매트로이드라고도 불린다.[10]규칙적인 매트로이드와 단변성 매트릭스의 등가성, 그리고 금지된 미성년자에 의한 그들의 특성화는 원래 그가 투트 호모토피 정리를 이용하여 증명했던 W. T. Tutte의 깊은 결과물이다.[8]제라드(1989)는 후에 금지된 미성년자에 의한 비모형 행렬의 특성화에 대한 대안적이고 단순한 증거를 발표했다.[11]

알고리즘

독립적 신탁을 통해 매트로이드에 대한 접근 권한을 부여받아 매트로이드의 정규성 여부를 시험하기 위한 다항식 시간 알고리즘이 있다.[12]

참조

  1. ^ a b Fujishige, Satoru (2005), Submodular Functions and Optimization, Annals of Discrete Mathematics, Elsevier, p. 24, ISBN 9780444520869.
  2. ^ Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 209, ISBN 9780199202508.
  3. ^ 옥슬리(2006년), 페이지 112.
  4. ^ 옥슬리(2006년), 페이지 131.
  5. ^ Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards, 69B: 1–47, doi:10.6028/jres.069b.001, MR 0179781.
  6. ^ Seymour, P. D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, hdl:10338.dmlcz/101946, MR 0579077.
  7. ^ Maurer, Stephen B. (1976), "Matrix generalizations of some theorems on trees, cycles and cocycles in graphs", SIAM Journal on Applied Mathematics, 30 (1): 143–148, doi:10.1137/0130017, MR 0392635.
  8. ^ a b Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society, 88 (1): 144–174, doi:10.2307/1993244, JSTOR 1993244, MR 0101526.
  9. ^ Seymour, P. D. (1979), "Matroid representation over GF(3)", Journal of Combinatorial Theory, Series B, 26 (2): 159–173, doi:10.1016/0095-8956(79)90055-8, MR 0532586.
  10. ^ 옥슬리(2006년), 페이지 20.
  11. ^ Gerards, A. M. H. (1989), "A short proof of Tutte's characterization of totally unimodular matrices", Linear Algebra and Its Applications, 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8.
  12. ^ Truemper, K. (1982), "On the efficiency of representability tests for matroids", European Journal of Combinatorics, 3 (3): 275–291, doi:10.1016/s0195-6698(82)80039-5, MR 0679212.