📂그래프이론

그래프의 패밀리와 프로퍼티

빌드업

$n$ 개의 라벨링 된^labeled 버텍스의 집합 $V = [n] = \left\{ 1 ,\cdots , n \right\}$ 를 가진 심플 그래프를 생각해보자. 이 그래프의 에지는 서로 다른 두 버텍스를 고르는 경우의 수만큼 존재할 수 있고, 따라서 그 종류는 정확히 $\binom{n}{2}$ 다. 이것을 각각의 에지가 아닌 그래프 전체로 생각해보자면 $n$ 개의 버텍스가 픽스된 상황에서 $\binom{n}{2}$ 가지 각각의 에지가 존재하느냐(1) 존재하지 않느냐(0) 둘 중 하나로 구분할 수 있다. 따라서 버텍스가 $n$ 개인 모든 그래프의 집합은 다음과 같이 나타낼 수 있을 것이다. $$2^{\binom{n}{2}}$$ 물론 우리는 이 모든 그래프에 관심을 가지지 않기 때문에, 그 중에서 우리가 필요한 성질들을 가지는 그래프들을 따로 모아보고 싶다. 이를테면 버텍스 $n$ 개인 평면 그래프들만 모아놓은 집합 $P$ 와 오일러 그래프들만 모아놓은 집합 $O$ 가 있다고 한다면, 이들은 $2^{\binom{n}{2}}$ 의 부분집합으로써 정의되는 동시에, 그래프가 해당 부분집합에 속하면 그 성질을 가진다고 말할 수 있으므로 그들 자체를 성질^property이라 부르기에 충분하다. 가령 $G \in \left( P \cap O \right)$ 라면 그래프 $G$ 는 평면 그래프면서 오일러 그래프다. 달리 말하자면, 그래프 $G$ 는 평면이라는 성질과 오일러 그래프라는 성질을 가지는 것이다.

정의 ¹

1. $n$ 개의 라벨링 된 버텍스를 가진 그래프의 패밀리^family는 멱집합 표현을 써서 다음과 같이 나타낸다. $$2^{\binom{n}{2}}$$
2. 그래프 패밀리 $2^{\binom{n}{2}}$ 의 부분집합 $\mathscr{P} \subset 2^{\binom{n}{2}}$ 을 프로퍼티^property라 한다.
3. $n$ 개의 라벨링 된^labeled 버텍스와 $m$ 개의 에지를 가진 심플 그래프라는 프로퍼티 $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ 를 다음과 같이 정의한다. $$\mathscr{G}_{n,m} = \left\{ G \in 2^{\binom{n}{2}} : V(G) = [n] , \left| E(G) \right| = m \right\}$$
4. $G$ 에 하나의 에지 $e \notin E(G)$ 가 추가되어도 여전히 유지되는 프로퍼티를 단조 증가 프로퍼티라 한다. 다시 말해, 다음을 만족하는 $\mathscr{P}$ 를 단조 증가 프로퍼티라 한다. $$G \in \mathscr{P} \implies (G + e) \in \mathscr{P}$$ 반대로 하나의 에지 $e \in E(G)$ 가 빠져도 다음과 같이 여전히 유지되는 프로퍼티를 단조 감소 프로퍼티라 한다. $$G \in \mathscr{P} \implies (G - e) \in \mathscr{P}$$ 이들을 아울러 모노톤^monotone 프로퍼티라 한다.