대한수학회 59번
그래프와 연결 부분 그래프의 성질
문제 출제자 : 최수영 아주대학교 수학과 교수
이번에는 다시 그래프에 관한 문제를 다루려 한다. 다음은 예전 그래프를 다룰 때 소개했던 그래프에 대한 기본 이론이다. 이번 문제에도 중요한 개념이니 다시 한 번 복습하자.
① (유한)그래프는 유한한 점의 집합에 대해서 각 점의 쌍을 서로 변으로 연결한 것이다. 이때 어떤 두 점도 많아야 한 개의 변으로 연결되어 있고, 각 변은 항상 서로 다른 두 점을 잇는다면 이 그래프를 단순그래프라고 한다. 즉, 단순그래프 는 유한한 점의 집합
와 서로 다른 두 점의 쌍으로 이루어진 변의 집합
로 구성되어 있다. 가령 집합
와
로 구성된 그래프
는 다음 모양과 같은 그래프이다.
=
② 그래프가 연결되어 있다는 것은 그래프의 임의의 점의 쌍에 대해서 한 점에서 출발하여 변으로만 이동해서 다른 점으로 갈 수 있다는 뜻이다. 그래프 가 연결된 몇 개의 성분으로 나누어질 때, 각 성분을 그래프
의 연결성분이라 부르자.
③ 단순그래프 의 부분유도그래프
란
에 포함되는 점의 부분집합에 대하여 그 부분집합으로 구성되는 모든 변을 다 모은 것이다. 즉,
이고,
를 만족하는 그래프이다.
-------------------------------------------------------------------------------------------------------------------------------------
연결된 그래프 의 점의 집합을
라 하자. 각 점
에 대해서
를 점으로 가지면서
의 연결된 부분유도그래프의 개수를
라 정의하자. 이제
중에서 가장 작은 것을
라 부르자.
문제1-1.
완전그래프란 모든 점의 쌍을 변으로 가지는 그래프이다. 개의 점을 가지는 완전그래프
에 대하여
을 구하여라.
문제1-2.
자신이 알고 있는 그래프 에 대하여
를 구하는 공식을 만들어 보아라.
문제2.
만약 가 성립하면, 집합
로 유도되는 부분유도그래프는 연결임을 증명하여라.
문제3.
그래프 의 연결된 부분유도그래프의 개수를
라 하자. 다음 부등식을 증명하여라.
문제4-1.
이고 그래프
가 집합
로 유도되는 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.
문제4-2.
위 문제4-1은 다음처럼 확장될 수 있다. 이고 그래프
가 점
을 가지지 않는
의 연결된 부분유도그래프일 때, 다음 부등식이 성립함을 보여라.
(단, 는
의 점의 개수를 의미하고,
이다.)