본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대45. 완벽한 그래프
수학동아 2020.09.01 11:17

그래프 G의 꼭짓점으로 구성된 집합 W\subseteq V(G)에 대하여 W의 임의의 두 꼭짓점이 서로 연결되어있으면, WG의 ‘집단’이라 부르자. 그리고 가장 큰 집단의 크기를 G의 ‘집단수’라 정의하자. 예를 들어, 순환 그래프(cycle)의 집단수는 2이고, 꼭짓점이 n개인 완전 그래프의 집단수는 n이다. 그리고 아래 그림에서는 \left \{ a, b, c, d\right \}, \left \{ b, e \right \}, \left \{ a, c, f \right \}등이 그래프의 집단이고, 가장 큰 집단이 \left \{ a, b, c, d\right \}이므로 이 그래프의 집단수는 4다.

 

 

그래프 G의 채색(그래프 채색의 정의는 대한수학회 38호 참고)에서 G의 집단 W에 속하는 꼭짓점들은 서로 연결되어 있으므로 다른 색으로 칠해야 한다. 예를 들어 위의 그래프에서 집단 \left \{ a, b, c, d\right \}의 임의의 두 꼭짓점은 서로 연결돼 있으므로, a, b, c, d 모두 다른 색으로 칠해야 한다. 따라서 그래프의 채색수는 집단수보다 항상 크거나 같다. 그래프의 집단수와 채색수가 같을 때, 이 그래프를 ‘완벽하다’고 한다. 길이가 짝수인 순환 그래프와 완전 그래프가 완벽한 그래프의 예다. 

 

 

다음 문제들을 통해서 어떤 그래프가 완벽하고, 어떤 그래프가 그렇지 않은지 공부해보자.

 

 

문제1 그래프 G의 보수 그래프(\bar{G}로 표기한다)는 G와 같은 꼭짓점 집합을 갖고, 임의의 두 꼭짓점 u, v에 대해, uv\in E(\bar{G})일 필요충분조건이 uv\notin E(\bar{G})인 그래프다. 아래 그림에서 오른쪽 그래프는 왼쪽 그래프의 보수 그래프다. (또한, 왼쪽 그래프는 오른쪽 그래프의 보수 그래프다)

 

 

길이가 5이상이고, 홀수개의 꼭짓점을 갖는 순환 그래프는 완벽하지 않다. (채색수는 3이고 집단수는 2) 이러한 그래프의 보수 그래프도 완벽하지 않음을 보여라. 즉, 채색수와 집단수가 다르다는 것을 증명하라. (아래 그림에서 왼쪽 그래프는 길이가 5인 순환 그래프, 오른쪽 그래프는 길이가 5인 순환 그래프의 보수 그래프다.) 

 

 

문제2 이분 그래프가 완벽하다는 것은 쉽게 알 수 있다. 이분 그래프의 보수 그래프도 완벽함을 증명하라.

 

 

문제3 그래프 G의 변그래프는 L(G)로 표기하고, 다음 두 조건을 모두 만족하는 그래프다.   

 

조건 1) L(G)G의 변을 꼭짓점으로 갖는다. 즉, V(L(G))=E(G).  

 

조건 2) L(G)의 두 꼭짓점 e, f에 대하여, e f\in E(L(G))일 필요충분조건은 G에서 e와  f가 꼭짓점을 공유하는 것이다.   

 

아래 그림에서 오른쪽 그래프는 왼쪽 그래프의 변그래프다. 

 

 

이분 그래프의 변그래프는 완벽함을 보여라. 또한, 이분 그래프의 변그래프의 보수그래프도 완벽함을 보여라. (아래 그림에서 오른쪽 그래프는 왼쪽에 있는 이분 그래프의 변그래프이다)

 

 

 

문제4 p_4를 부분유도그래프로 갖지 않는 그래프가 완벽함을 보여라. 또한, 이러한 그래프의 보수그래프도 완벽함을 보여라. (p_4와 부분유도그래프의 정의는 대한수학회 12호 참고)

 

 

 

문제5 1, 2, \cdots , n의 순열 \mathbb{A}=(a_1, a_2, \cdots , a_n)에 대해, 그래프 G_\mathbb{A}를 다음과 같이 정의하자.   

 

V(G_\mathbb{A})=(1, 2, \cdots , n)이고, 임의의 1\leq i<j\leq n에 대해, a_ia_j\in E(G_\mathbb{A})일 필요충분조건은 a_i> a_j이다.  

 

아래 그림은 \mathbb{A}=(2, 4, 1, 5, 3)으로 주어졌을 때, 그래프 G_\mathbb{A}를 나타낸 것이다. 임의의 순열 \mathbb{A}에 대해, G_\mathbb{A}가 완벽함을 보이고, G_\mathbb{A}의 보수 그래프도 완벽함을 보여라. 

 

 

 

위의 예제들에 나온 완벽한 그래프의 보수 그래프는 모두 완벽하다는 것을 알 수 있다. 5번까지 모두 해결했다면, 임의의 완벽한 그래프의 보수 그래프가 완벽한 그래프인지 생각해보자!  

  •  
    전자기역학 Lv.8 2020.09.08 00:39 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      전자기역학 Lv.8 2020.09.08 00:43

      이 문제에서 가장 쉽다고 세상에 알려진 1번의 풀이 선점권을 고인물분들이 양보하여 올렸습니다

      좋아요1
  •  
    리프 Lv.6 2020.09.08 01:06 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      리프 Lv.6 2020.09.08 01:07

      오류가 있는 풀이입니다. 수정 후 새로운 풀이를 올리겠습니다.

      좋아요0
  •  
    수학꿀잼 Lv.2 2020.09.08 12:50 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      리프 Lv.6 2020.09.08 13:45 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    리프 Lv.6 2020.09.08 12:51 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      리프 Lv.6 2020.09.08 12:52

      3번 앞부분 풀이입니다. (이분그래프의 변그래프에 대한 증명)

      수학꿀잼님이 3번 뒷부분 풀이를 완성하셨다고 하셔서 비댓이랑 확인요청했습니다.

      좋아요0
    •  
      수학꿀잼 Lv.2 2020.09.08 12:52 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      리프 Lv.6 2020.09.08 13:02

      ㅋㅋㅋㅋ 굳

      좋아요0
  •  
    수학꿀잼 Lv.2 2020.09.08 13:03 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      수학꿀잼 Lv.2 2020.09.08 13:04

      5번 날로 먹은것 같네요 ㅜㅡㅜ

      좋아요0
    •  
      리프 Lv.6 2020.09.08 13:10

      미르스키랑 딜워스 몰라서 이해를 못하겠네요 ㅠ 전 3번 나머지 절반 시도하겠습니다

      좋아요0
    •  
      수학꿀잼 Lv.2 2020.09.08 13:11

      아, 반전 그래프에서 딜워스의 정리까지 갈 필요도 없겠군요. 비교 불가능할 조건이 a_i<a_j라서 대칭적이니까요.

      그러면, 이제 미르스키 정리의 증명을 작성하겠습니다. x-)y, y-)z이면 x-)z이지요?(POSET의 정의이기도 합니다) 그러면, 부등호처럼 서로 다르면 정렬 가능하겠죠?

      이때, 다음과 같은 구조를 chain이라 부릅시다. a,b,c,d,...에 대해 임의의 두 원소가 -)으로 비교 가능할 때에요. 그리고, 임의의 2개가 비교 불가능한 것을 antichain이라 부릅시다

      이때, 집합 S를 antichain들로 분할하기 위해서 최대 크기의 chain 보다 같거나 많은 집합의 수가 필요합니다. 등호가 성립한다는 내용이 미르스키 정리이지요

      다음과 같은 함수 f를 생각합시다. S의 원소 x에 대해, x가 최대 원소인 chain의 최대 길이를 생각해 봅시다

      그러면, 그 길이로 가능한 값은, 1,2,... 최대 길이 chain의 길이 입니다.

      그리고, f를 취한 값이 같은 원소들을 모두 한 집합에 묶습니다. 이들이 antichain인 것은 자명하죠?

      좋아요0
  •  
    수학꿀잼 Lv.2 2020.09.08 15:40 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      수학꿀잼 Lv.2 2020.09.08 15:41

      아 실수했네요 ㅠㅠ 풀이 수정해서 올리겠습니다

      좋아요0
  •  
    수학꿀잼 Lv.2 2020.09.08 16:18 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    수학꿀잼 Lv.2 2020.09.08 19:54 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      수학꿀잼 Lv.2 2020.09.09 14:19

      기자님, 혹시나 이 풀이를 보신다면 제거해 주시면 감사하겠습니다. 지속적으로 오류가 발견되서 새로 썼어요 이것과 위의 두개 총 연속한 풀이 3개 전부 다요

      좋아요0
  •  
    수학꿀잼 Lv.2 2020.09.09 14:18 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    리프 Lv.6 2020.09.23 17:30
    확인요청중

    수정된 2번 풀이입니다.

     

    풀이) 주어진 이분그래프 G=(A, B)에 대해, G의 최대독립집합을 I라 하자.

    다음과 같은 점 집합들을 정의하자.

    A\cap I=V_1B\cap I=V_2A-I=V_3B-I=V_4

     

    이제, 다음을 만족하는 그래프 H_1을 잡자.

    V(H_1)=V_2\cup V_3

    \left \{ v_i, v_j \right \}\in E(H_1)\Leftrightarrow \left \{ v_i, v_j \right \}\in E(G) \wedge \left \{ v_i, v_j \right \}\subset V(H_1)

     

    이때, 그래프 H_1상에 V_3를 덮는 매칭이 존재함을 보이자.

    귀류법으로, 어떤 집합 \phi \neq S\subset V_3가 존재하여, \left | S \right |>\left | N(S) \right |라 가정하자.

    이때, V_1, V_2-N(S), S는 정의에 의해 각각 독립집합이다.

    또한, V_1\cup S\subset A이므로 V_1과 S 사이에는 선분이 존재하지 않고, V_1\cup (V_2-N(S))\subset I이므로 V_1과 V_2-N(S) 사이에도 선분이 없다.

    그리고 N(S)의 정의에 의해 V_2-N(S)와 S 사이에도 선분이 존재하지 않으므로, V_1\cup (V_2-N(S))\cup S가 독립집합임을 알 수 있다.

    이때, \left | V_1\cup (V_2-N(S))\cup S \right |=\left | V_1 \right |+\left | V_2 \right |+\left | S \right |-\left | N(S) \right |>\left | V_1 \right |+\left | V_2 \right |=\left | I \right |이므로 I가 최대독립집합이라는 조건에 모순이다.

    따라서, 임의의 집합 \phi \neq S\subset V_3에 대해, \left | S \right |\leq\left | N(S) \right |이고, 결혼 정리에 의해 V_3를 덮는 매칭이 존재한다.

    이러한 매칭을 이루는 선분 집합을 E_1이라 하자.

     

    한편, 다음과 같은 그래프 H_2를 정의하자.

    V(H_2)=V_1\cup V_4

    \left \{ v_i, v_j \right \}\in E(H_2)\Leftrightarrow \left \{ v_i, v_j \right \}\in E(G) \wedge \left \{ v_i, v_j \right \}\subset V(H_2)

    앞에서 했던 것과 동일한 논리에 의해, 그래프 H_2 상에는 V_4를 덮는 매칭이 존재한다.

    이러한 매칭을 이루는 선분 집합을 E_2라 하자.

     

    이제, G의 보수그래프 \bar{G}에 대해, 채색수가 집단수와 같음을 보이자.

    채색수는 집단수보다 항상 크거나 같으므로, \bar{G}의 집단수를 n이라 했을 때 n개의 색으로 점들을 칠하는 것이 가능함을 보이면 충분하다.

    다음과 같은 방법으로 각 점을 색칠하자.

     

    1. 집합 I의 원소들을 서로 다른 색(1번 색부터 n번 색까지)으로 칠한다.

    2. v\in V_3 \cup V_4인 점 v에 대해, 어떤 점 v{}'\in V_1 \cup V_2(=I)가 존재하여 \left \{ v, v{}' \right \}\in E_1\cup E_2를 만족한다고 할 때, 점 v를 점 v'과 같은 색으로 칠한다.

     

    매칭의 정의에 의해, 단계 2까지 하면 모든 점이 채색의 조건을 만족하도록 칠해짐을 알 수 있다.

     

    따라서, 임의의 이분그래프의 보수그래프는 완벽하다.

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911