순환 매트로이드

매트로이드 이론에서 순환 매트로이드(循環matroid, )는 그래프로부터 정의될 수 있는 매트로이드이다. 순환 매트로이드의 회로는 그래프 순환이다. 순환 매트로이드의 쌍대 매트로이드는 접합 매트로이드(接合matroid, )라고 한다.

정의 
(유한 또는 무한) 그래프 가 주어졌다고 하자. 그렇다면, 그 변들의 집합 위에는 다음과 같은 두 매트로이드 구조를 줄 수 있다.

순환 매트로이드 
가 의 숲들의 집합이라고 하자.

그렇다면 는 매트로이드를 이루며, 이를 의 순환 매트로이드() 라고 한다. 순환 매트로이드의 회로는 그래프의 순환들이다.

접합 매트로이드 
그래프 의 절단(絶斷, ) 는 제거하면 연결 성분의 수가 증가하는 변의 집합이다. 즉, 다음 세 조건들을 모두 만족시키는 두 꼭짓점 가 존재하여야 한다.
 이다.
 와  사이의 모든 (유한) 경로가 하나 이상 존재한다. 즉, 와 는 같은 연결 성분에 속한다.
 와  사이의 모든 (유한) 경로들은 에 속하는 변을 적어도 하나 이상 포함한다.

그래프 의 접합(接合, ) 는 절단의 집합의 (부분 집합 관계에 대한) 극소 원소이다. 즉, 다음 두 조건을 만족시켜야 한다.
 는 절단이다.
 임의의 에 대하여, 는 절단이 아니다.
의 접합들의 집합을

라고 하자.

의 접합을 회로로 갖는 매트로이드

를 의 접합 매트로이드라고 한다. 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.

성질

그래프 성질과의 관계 
그래프의 성질과 순환 매트로이드 · 접합 매트로이드의 성질들은 다음과 같이 대응된다.

특히, 순환 매트로이드와 접합 매트로이드의 매트로이드 마이너는 둘 다 그래프 마이너와 대응한다.

유한성 
순환 매트로이드는 항상 유한형 매트로이드이다. 즉, 그 모든 회로들은 항상 유한 집합이다. 반면, 무한 그래프의 접합 매트로이드는 일반적으로 유한형 매트로이드가 아니다. (물론, 유한 그래프의 접합 매트로이드는 유한 매트로이드이다.)

예 
무변 그래프의 경우, 그 순환 그래프와 접합 그래프 둘 다 크기 0의 유일한 매트로이드이다.

숲 그래프 의 경우, 그 순환 매트로이드는 모든 집합이 독립 집합인 균등 매트로이드 이며, 그 접합 매트로이드는 공집합만이 독립 집합인 균등 매트로이드 이다.

순환 그래프 의 경우, 그 순환 매트로이드는 균등 매트로이드 이다. 즉, 전체 집합을 제외한 모든 부분 집합이 독립 집합이다. 반대로, 그 접합 매트로이드는 균등 매트로이드 이다.

참고 문헌

외부 링크 
 
 

그래프 이론
매트로이드 이론
평면 그래프