주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대19. 방향그래프의 꼭짓점 나누기

2018.07.01

같이 풀어볼까?

네이버밴드 구글플러스

이번 대한수학회 문제는 정의진 아주대 수학과 교수님께서 출제해 주셨습니다~. 새로운 방향그래프를 만드는 규칙을 숙지한 뒤 문제에 도전하세요!

 

각각의 변이 방향을 가지고 있을 때 그 그래프를 방향그래프(direct graph)라고 부른다. 편의상 임의의 꼭짓점에서 다른 꼭짓점으로 가는 경로가 있는 그래프만을 생각하기로 하자. 이러한 그래프를 강연결 그래프라고 한다. 

 

주어진 방향그래프 \LARGE G가 있을 때, 아래 순서대로 \LARGE G를 변형해 새로운 방향그래프 \LARGE H를 만드는 규칙을 생각하자.

 

(1) 그래프 \LARGE G의 꼭짓점 \LARGE I을 하나 택한다.

 

(2) \LARGE I에서 시작하는 변의 집합을 \LARGE E라 할 때, \LARGE E를 두 개의 공집합이 아닌 집합 \LARGE A\LARGE B로 나눈다. 따라서 \LARGE A\cup B=E이고 \LARGE A\cap B=\varnothing이다.

 

(3) 그래프에 새 꼭짓점 두 개를 그린다. \LARGE I_A와 \LARGE I_B라 하자.

 

(4) \LARGE A에 속한 변은 \LARGE I 대신 \LARGE I_A에서 출발하게 바꾸고, \LARGE B에 속한 변은 \LARGE I 대신  \LARGE I_B에서 출발하게 바꾼다.

 

(5) 그래프 \LARGE G에서 꼭짓점 \LARGE I에서 끝나는 모든 변에 대해서, 시작하는 꼭짓점은 같고 끝나는 꼭짓점은 각각  \LARGE I_A와  \LARGE I_B인 변을 하나씩 추가한다.


(6) 꼭짓점 \LARGE I와  \LARGE I에 연결된 모든 변을 지운다.

 

쉬운 이해를 위해 방향그래프의 일부분에서 어떤 일이 일어나는지를 살펴보면 다음과 같다. 아래 오른쪽 그림은 그래프  \LARGE G(왼쪽 그림)의 꼭짓점 \LARGE I에서 시작하는 변의 집합을  \LARGE A=\left \{ e,\, f \right \}, \, B=\left \{ g \right \}의 둘로 나눌 때 위의 규칙을 통해 새롭게 만들어진 그래프의 일부분이다.

 

 

새 규칙을 사용해서 만든 그래프 \LARGE H는 그래프 \LARGE G보다 꼭짓점이 하나 많음을 관찰할 수 있다. 또한 그래프 \LARGE G의 꼭짓점 \LARGE I에서 출발하는 변의 개수는 그래프 \LARGE H의 꼭짓점  \LARGE I_A와  \LARGE I_B에서 출발하는 변의 개수의 합임을 관찰할 수 있다.

 

그래프 \LARGE G의 꼭짓점 \LARGE I가 아닌 꼭짓점 \LARGE J에서 출발하는 변의 개수는 그래프 \LARGE H에서 그대로일 수도 있고 늘어날 수도 있는데, 늘어나는 경우에 그 수는 그래프 \LARGE G의 꼭짓점 \LARGE J에서 시작해 꼭짓점 \LARGE I에서 끝나는 변의 개수임을 확인할 수 있다.

 

문제 1~4에서는 방향그래프 \LARGE G에 규칙을 적용해 방향그래프 \LARGE H를 만들고, 위에서의 표기와 같이 그래프 \LARGE H는 꼭짓점 \LARGE I 대신  \LARGE I_A와  \LARGE I_B를 가진다고 하자.

 


문제 1.  그래프 \LARGE G의 각 꼭짓점에서 끝나는 변의 수들을 모아놓은 집합은 그래프 \LARGE H의 각 꼭짓점에서 끝나는 변의 수들을 모아놓은 집합과 같을까?

 

 


문제 2. 그래프 \LARGE G에 규칙을 적용해 그래프 \LARGE H를 만들었다고 하자. 임의의 자연수 \LARGE n에 대해 그래프 \LARGE G와 그래프 \LARGE H의 길이 \LARGE n 사이클의 수가 같음을 보여라.

 

 


문제 3.  그래프 \LARGE G에 규칙을 적용해 그래프 \LARGE H를 만들었다고 하자. 자연수 \LARGE n에 대해 그래프 \LARGE G와 그래프 \LARGE H의 길이 \LARGE n의 경로의 수를 각각 \LARGE g_n, \LARGE h_n이라 할 때 다음을 보여라.

 

\LARGE \lim_{n \to \infty } \frac{g_n}{h_n}=1

 

 


문제 4. 방향그래프 \LARGE G의 꼭짓점의 개수가 \LARGE n이고, 꼭짓점을 각각 \LARGE v_1, \, v_2, \, v_3, \cdots , \, v_n이라 해 보자. 각각의 자연수 순서쌍 \LARGE 1\leq i, \, j\leq n에 대해 \LARGE A_i_j를 꼭짓점 \LARGE i에서 시작해서 \LARGE j 로 끝나는 변의 수라고 정의하면, 다음과 같이 \LARGE n\times n 행렬 \LARGE A(G)를 만들 수 있다.

 

\LARGE A(G)=\left [ A_i_j \right ]_1_{\leq i, \, j\leq n} =\begin{bmatrix} A_1_1& A_1_2 & \cdots & A_1_n \\ A_2_1& A_2_2 & \cdots & A_2_n\\ \vdots & \vdots & \ddots &\vdots \\ A_n_1 & A_n_2 & \cdots & A_n_n \end{bmatrix}

 

방향그래프 \LARGE H에 대해서도 행렬 \LARGE A(H)를 위처럼 만들자. 다음 조건을 만족하는 행렬 \LARGE D\LARGE E가 존재함을 보여라.


(1) \LARGE D\LARGE 0\LARGE 1로만 이뤄진 행렬이고, 각 행은 최소한 한 개의 \LARGE 1을 포함하고, 각 열은 딱 한 개의 \LARGE 1만을 가진다.

 

(2) \LARGE E는 모든 원소가 음이 아닌 정수로 이뤄진 행렬이다.

 

(3) \LARGE A(G)=DE 이고 \LARGE A(H)=ED이다.

 

 


문제 5. 방향그래프 \LARGE G에서 문제 4처럼 \LARGE A_i_j를 정의했다고 하자. 음이 아닌 정수 \LARGE v_1, \, v_2, \, v_3, \cdots , \, v_n이 존재해서 모든 \LARGE i=1, 2, \cdots , n에 대해 다음을 만족한다고 하자.

 

\LARGE A_i_1v_1+A_i_2v_2+\cdots +A_i_nv_n\geq nv_i


이때 방향그래프 \LARGE G에 규칙을 유한 번 적용해 각각의 꼭짓점마다 출발하는 변의 수가 \LARGE n이상이 되게 하는 방향그래프 \LARGE H를 만들 수 있음을 보이시오.
 

댓글 16

  • 미래탐정 2018.07.01 15:56:19

    문제 1. 같음이 자명하다.  그래프 G의 임의의 꼭짓점 I에서 끝나는 변의 수를 k라 하자. 그래프 H에서 IA에서 끝나는 변의 수가 k개, IB에서 끝나는 변의 수가 k개로 집합의 변화는 없다.

    (길이n 사이클의 수가 그래프에서 n번 이동했을 때 제자리로 돌아오는 경우의 수인가요?? 맞다고 하고 2번 풀었습니다. )

    문제 2. 그래프 G에서 I를 거치지 않는 길이 n 사이클의 수는 그래프 H에서 IA또는 IB를 거치지 않는 길이 n 사이클의 수와 같고  

    그래프 G에서 I를 거치는 길이 n 사이클의 수는 그래프 G에서 I에서 시작하여 갈 수 있었던 곳으로 가려면 그래프 H에서는 목적지에 따라 IA나 IB 둘중에 하나로 이원화되기 때문에 역시 길이 n 사이클의 수는 유지됩니다.

    좋아요0 댓글수5
    • 김우현 기자 2018.07.05 15:22:56

      주정훈 멘토가 검토한 결과 1, 2번 풀이 모두 정답! 정의진 교수님의 최종 확인을 기다려주세요!laugh

      좋아요0
    • 아인수타인 2018.09.23 16:52:42

      음... 언제 끝나나요? 일주일 있음 3달 되는데.

      좋아요0
    • 여백 패르마 2018.09.23 19:21:27

      맞았다고 할 수 있는 것같은데요?

      좋아요0
    • 김우현 기자 2018.09.27 10:10:25

      아앗, 죄송합니다! 최종 검토를 향해 달려가겠습니다!!!!crying

      좋아요0
    • 김우현 기자 2018.10.04 02:52:36

      오래 기다렸어요! 미래탐정 친구의 1, 2번 문제 풀이가 모두 정답으로 최종 확인됐습니다. 한 문제 이상 더 풀리면 '부분해결 딱지'를 붙이도록 할게요~smiley

      좋아요0
  • 여백 패르마 2018.07.01 19:16:01

    3번: g_n을 h_n에 대한 식으로 나타내야 한다. 

    1. G에서의 경로가 I를 지나지 않을 때

    이때는 G, H의 경로의 개수가 같다.  G, H의 차이점은 I가 I_A, I_B로 됬다는 것이다. 그런데, 경로가 I를 지나지 않는다면 I_A, I_B를 지나지도 않을 것이다. 즉, G, H모두에서 경로가 같을 것이다. 그러므로 경로의 개수도 같을 것이다. ><

    2. G에서의 경로가 I를 지날 때

    이때는 G, H의 경로의 개수가 같을 것이다. H의 경로가 I_A, I_B를 지나기 전에는 경로가 G와 같을 것이다. 그리고, I_A에 끝나는 변의 개수는 1번 미래탐정님의 말과 같이 어떤 상수 k이다. \left | A \right |=x라고 하자. 그러면 I_A를 지나는 경로의 개수는 kx이다. 또, I_B에 끝나는 변의 개수는 I_A때와 같은 상수 k이다. \left | B \right |=y라고 하자. 그러면, I_B를 지나는 경로의 개수는 ky이다. 즉, H에서의 경로의 개수는 kx+ky=k(x+y)개이다. G에서의 경로의 개수는 I를 지나기 전의 경로의 개수\times I를 지난 후의 경로의 개수이다. 그런데, I를 지나기 전 경로의 개수는 H의 경로때와 같기 때문에 신경을 쓸 필요가 없다. 즉, I를 지난 후의 경로의 개수만 생각하자. I에서 시작하는 변의 개수는 (x+y) 이다. 그리고, I에서 끝나는 변의 개수는 k 이다. 즉, G의 경로의 개수는 k(x+y)이다. 결론적으로, G,H의 경로의 개수가 같다. ><

    3. G에서의 경로가 I에서 끝날때

    이떄는 H의 경로가 G의 경로보다 어떤 상수 k만큼 개수가 더 많다. 그 이유는 I에 끝나는 변의 개수는 k개이고, I_A, I_B에 끝나는 변의 개수는 전체적으로 2k개이며, I를 지나기 전의 경로의 개수는 G,H모두 같기 때문이다. ><

    즉, g_n=h_n-k이다. 단, k는 상수이다. \lim_{n\rightarrow \infty }\frac{h_n-k}{h_n}=\lim_{n\rightarrow \infty }1-\frac{k}{h_n}이다. n\rightarrow \infty이면 꼭짓점의 개수도 무한대로 다가간다. 즉, h_n\rightarrow \infty이다. \lim_{n\rightarrow \infty }1-\frac{k}{h_n}=\lim_{n\rightarrow \infty }1-\lim_{n\rightarrow \infty }\frac{k}{h_n}=1-0=1이다. 즉, 증명이 끝났다. 

                                                                                                                                                                                                                                                                                                  Q.E.D

     

    좋아요0 댓글수3
    • 구머 2018.07.02 11:31:01

      그래프를 잘 조절하면 k->무한 이 됩니다. 이에 대한 추가적인 설명이 필요할 듯 합니다(예를 들면,h_n이 k보다 압도적으로 크거나.. )

      좋아요0
    • 모두다같이 2018.07.09 13:36:53

      세 유형의 n길이 경로( I를 지나는 경로, I를 지나지 않는 경로, I에서 시작하는 경로 )수가

      그래프G에서나 그래프H에서나 동일하단 점을 이해했어요.

      그래프 G에서 각 유형의 길이 n 경로 수를 g_{(1)n}, g_{(2)n}, g_{(3)n}

      그래프 H에서 각 유형의 길이 n 경로 수를 h_{(1)n}, h_{(2)n}, h_{(3)n}

      로 나타내면 g_{(1)n} = h_{(1)n}, g_{(2)n} = h_{(2)n}, g_{(3)n} = h_{(3)n}

      I에서 끝나는 n 길이 경로에 대해

      각 그래프 G,H에서 이 유형의 길이 n 경로 수를 g_{(4)n}, h_{(4)n}

      경로가 끝나는 점에 대해

      그래프 G에서는 I점 하나, 그래프 H에서는 I_{a}, I_{b} 점 2개 이므로

      h_{(4)n} = 2g_{(4)n}

      g_{n} = g_{(1)n} + g_{(2)n} + g_{(3)n} + g_{(4)n}

      h_{n} = h_{(1)n} + h_{(2)n} + h_{(3)n} + h_{(4)n}

      \frac{g_{n}}{h_{n}} = \frac{g_{(1)n}+g_{(2)n}+g_{(3)n}+g_{(4)n}}{h_{(1)n}+h_{(2)n}+h_{(3)n}+h_{(4)n}} = \frac{g_{(1)n}+g_{(2)n}+g_{(3)n}+g_{(4)n}}{g_{(1)n}+g_{(2)n}+g_{(3)n}+2g_{(4)n}} = 1 - \frac{g_{(4)n}}{g_{(1)n}+g_{(2)n}+g_{(3)n}+2g_{(4)n}} = 1 - \frac{1}{\frac{g_{(1)n}+g_{(2)n}+g_{(3)n}}{g_{(4)n}}+2}

      여기서 이대로

      \lim_{n \to \infty }\frac{g_{(1)n}+g_{(2)n}+g_{(3)n}}{g_{(4)n}} = \infty

      를  알아봐야 할까요?

      좋아요0
    • 여백 패르마 2018.07.27 11:28:17

      네, 맞는 것 같습니다. 그리고 마지막 식을 다시 정리하면 \lim_{n\rightarrow \infty }\frac{g_n}{g_{(4)n}}=\infty임을 증명해야 한다는 명제가 나오게 됩니다. 

      좋아요0
  • 여백 패르마 2018.10.07 20:24:41

    /resources/comment/2018/10/de29a32276afd6cf7d7b4bec8fe9f84f.hwp

    좋아요0 댓글수5
    • 여백 패르마 2018.10.07 20:24:55

      풀이입니다. 

      좋아요0
    • Kid Milli 2018.10.07 20:40:40

      뒤에서 2번째 문장에 (무한/무한) x 무한=무한 

      을 증명해주세요

      좋아요0
    • 수학장 2018.10.08 21:10:20

      \lim_{n\rightarrow \infty }\frac{(n+1)(n+2)}{n^2+3n+1}=\infty * \frac{\infty}{\infty}=1인데요?

      좋아요0
    • 아인수타인 2018.10.10 15:17:04

      무한*(무한/무한)이 왜 1이죠? 제가 알기론 무한을 무한으로 나누면 그 어떤 수든 될 수 있다고 알고 있는데요.(0 제외) 그러니까 거기에 무한을 곱하면 무한 맞는 거 같은데요?

      좋아요0
    • 여백 패르마 2018.10.14 20:27:07

      다시 수정했습니다. (/resources/comment/2018/10/de29a32276afd6cf7d7b4bec8fe9f84f.hwp)

      좋아요0