폴리매스

대한수학회 59번

그래프와 연결 부분 그래프의 성질

문제 출제자 : 최수영 아주대학교 수학과 교수

이번에는 다시 그래프에 관한 문제를 다루려 한다. 다음은 예전 그래프를 다룰 때 소개했던 그래프에 대한 기본 이론이다. 이번 문제에도 중요한 개념이니 다시 한 번 복습하자.

① (유한)그래프는 유한한 점의 집합에 대해서 각 점의 쌍을 서로 변으로 연결한 것이다. 이때 어떤 두 점도 많아야 한 개의 변으로 연결되어 있고, 각 변은 항상 서로 다른 두 점을 잇는다면 이 그래프를 단순그래프라고 한다. 즉, 단순그래프 는 유한한 점의 집합 와 서로 다른 두 점의 쌍으로 이루어진 변의 집합 로 구성되어 있다. 가령 집합 와 로 구성된 그래프  는 다음 모양과 같은 그래프이다.

 = 

② 그래프가 연결되어 있다는 것은 그래프의 임의의 점의 쌍에 대해서 한 점에서 출발하여 변으로만 이동해서 다른 점으로 갈 수 있다는 뜻이다. 그래프 가 연결된 몇 개의 성분으로 나누어질 때, 각 성분을 그래프 의 연결성분이라 부르자.

③ 단순그래프 의 부분유도그래프 란 에 포함되는 점의 부분집합에 대하여 그 부분집합으로 구성되는 모든 변을 다 모은 것이다. 즉, 이고, 를 만족하는 그래프이다.

-------------------------------------------------------------------------------------------------------------------------------------

연결된 그래프 의 점의 집합을 라 하자. 각 점 에 대해서 를 점으로 가지면서 의 연결된 부분유도그래프의 개수를 라 정의하자. 이제  중에서 가장 작은 것을 라 부르자.

문제1-1.

완전그래프란 모든 점의 쌍을 변으로 가지는 그래프이다. 개의 점을 가지는 완전그래프 에 대하여 을 구하여라.

문제1-2.

자신이 알고 있는 그래프 에 대하여 를 구하는 공식을 만들어 보아라.

문제2.

만약 가 성립하면, 집합 로 유도되는 부분유도그래프는 연결임을 증명하여라.

문제3.

그래프 의 연결된 부분유도그래프의 개수를 라 하자. 다음 부등식을 증명하여라.

문제4-1.

이고 그래프 가 집합 로 유도되는 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.

문제4-2.

위 문제4-1은 다음처럼 확장될 수 있다. 이고 그래프 가 점 을 가지지 않는 의 연결된 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.

(단, 는 의 점의 개수를 의미하고, 이다.)