매트로이드 이론에서 순환 매트로이드(循環matroid, 영어: cycle matroid)는 그래프로부터 정의될 수 있는 매트로이드이다. 순환 매트로이드의 회로는 그래프 순환이다. 순환 매트로이드의 쌍대 매트로이드는 접합 매트로이드(接合matroid, 영어: bond matroid)라고 한다.
정의
(유한 또는 무한) 그래프 가 주어졌다고 하자. 그렇다면, 그 변들의 집합 위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.
순환 매트로이드
가 의 숲들의 집합이라고 하자.
그렇다면 는 매트로이드를 이루며, 이를 의 순환 매트로이드(영어: cycle matroid) 라고 한다.[1]:§2.2 순환 매트로이드의 회로는 그래프의 순환들이다.
접합 매트로이드
그래프 의 절단(絶斷, 영어: cut) 는 제거하면 연결 성분의 수가 증가하는 변의 집합이다. 즉, 다음 세 조건들을 모두 만족시키는 두 꼭짓점 가 존재하여야 한다.
- 이다.
- 와 사이의 모든 (유한) 경로가 하나 이상 존재한다. 즉, 와 는 같은 연결 성분에 속한다.
- 와 사이의 모든 (유한) 경로들은 에 속하는 변을 적어도 하나 이상 포함한다.
그래프 의 접합(接合, 영어: bond) 는 절단의 집합의 (부분 집합 관계에 대한) 극소 원소이다. 즉, 다음 두 조건을 만족시켜야 한다.
- 는 절단이다.
- 임의의 에 대하여, 는 절단이 아니다.
의 접합들의 집합을
라고 하자.
의 접합을 회로로 갖는 매트로이드
를 의 접합 매트로이드라고 한다.[1]:§2.2 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.
성질
그래프 성질과의 관계
그래프의 성질과 순환 매트로이드 · 접합 매트로이드의 성질들은 다음과 같이 대응된다.
특히, 순환 매트로이드와 접합 매트로이드의 매트로이드 마이너는 둘 다 그래프 마이너와 대응한다.
유한성
순환 매트로이드는 항상 유한형 매트로이드이다.[1]:§2.2 즉, 그 모든 회로들은 항상 유한 집합이다. 반면, 무한 그래프의 접합 매트로이드는 일반적으로 유한형 매트로이드가 아니다. (물론, 유한 그래프의 접합 매트로이드는 유한 매트로이드이다.)
예
무변 그래프의 경우, 그 순환 그래프와 접합 그래프 둘 다 크기 0의 유일한 매트로이드이다.
숲 그래프 의 경우, 그 순환 매트로이드는 모든 집합이 독립 집합인 균등 매트로이드 이며, 그 접합 매트로이드는 공집합만이 독립 집합인 균등 매트로이드 이다.
순환 그래프 의 경우, 그 순환 매트로이드는 균등 매트로이드 이다. 즉, 전체 집합을 제외한 모든 부분 집합이 독립 집합이다. 반대로, 그 접합 매트로이드는 균등 매트로이드 이다.
각주
외부 링크