독립 시스템
Independence system결합 수학에서 독립 시스템 S는 쌍(V, I)이며, 여기서 V는 유한 집합이고 I는 다음과 같은 특성을 가진 V의 하위 집합(독립 집합 또는 실현 가능한 집합이라고 함)의 집합이다.
- 빈 집합은 독립적이다, 즉 ∅ ∈ I. (대안적으로 V의 적어도 한 부분집합은 독립적이다, 즉 ≠)
- 독립된 집합의 모든 부분 집합은 독립적이다. 즉, 각 Y x X에 대해 X → I → Y i I이 있다.이것을 세습재산, 즉 하방폐쇄라고 부르기도 한다.
독립체제의 또 다른 용어는 추상적으로 단순화된 복합체다.
다른 개념과의 관계
1. 쌍(V, I)은 V가 유한 집합이고 나는 V의 하위 집합의 집합체인 쌍(V, I)은 하이퍼그래프라고도 한다.이 용어를 사용할 때, 세트 V의 원소를 정점이라고 하고, 패밀리의 원소들을 나는 요정이라고 부른다.그래서 독립 시스템은 하향 폐쇄형 하이퍼그래프로 정의될 수 있다.
2.증강 속성 또는 교환 속성이라고 하는 추가 속성을 가진 독립체계는 매트로이드(matroid)를 산출한다.다음 표현은 용어 간의 관계를 요약한 것이다.
하이퍼그래프 ⊃ 독립-시스템s = 추상-심층-복합체 es 매트로이드.
참조
- Bondy, Adrian; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699.
.svg){kind=small}
