본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대57. 방향그래프의 경로 갯수 찾기
수학동아 2021.09.02 15:35 조회 424

방향그래프의 경로 갯수 찾기

정의진 아주대학교 수학과 (uijin@ajou.ac.kr)

September 2021

 

문제. 각각의 변이 방향을 가지고 있는 그래프를 방향그래프(direct graph)라고 부른다. 아래는 간단 한 두 방향그래프의 예이다. 한 꼭지점에서 출발해서 다른 꼭지점에 도착하는 변이 꼭 하나일 필요도 없고, 한 꼭지점에서 출발한 변이 자기 자신으로 도착할 수도 있음을 확인하자.

 

자연수 n에 대해, 방향그래프에서 나타나는 길이 n의 경로의 수 A_{n}이라고 하자. 예를 들어, 왼쪽 그래프에서는 가능한 모든 a, b의 조합이 그래프의 경로가 되므로 A_{n}=2^{^{n}}이 된다. 오른쪽 그래프에 서는 A_{1}=3, A_{2}=5, A_{3}=8, A_{4}=13이다. 사실 A_{n}n+3번째 피보나치 수와 같음을 확인할 수 있다.

 

 

이 때, A_{n}은 매우 빨리 커지는 수이므로, A_{n}이 커지는 속도를 다음과 같이 정의하면 더 다루기 쉬운 수가 된다.

 

 

위의 두 예제에서, G\lambda값은 1임을 바로 확인할 수 있다.

 

문제 1. F_{0}=F_{1}=1이고, n\geq 2일 때 F_{n}=F_{n-1}+F_{n-2}인 수열이라고 하자. 즉 F_{n}n번째 피보나치 수이다. 위 그래프 H에서, A_{n}=F_{n+3}임을 보여라.

 

문제 2. 자연수 k에 대해, \lambda =k가 되는 서로 다른 형태의 그래프가 존재하고, 그 수가 무한함을 증명하 여라.

 

문제 3. 위 그래프 H에 대해, \lambda =\frac{1+\sqrt{5}}{2} 임을 보여라. 문제 4. 임의의 방향그래프 G에 대해, \lambda값이 존재할까?

 

질문 5. 임의의 꼭지점에서 다른 꼭지점으로 가는 경로가 있는 그래프 G를 생각하자. (이러한 그래프를 ‘강연결’ 그래프라고 한다.) 부분그래프 H가 있을 때 (단, H\neq G이다.) 이때 G\lambda값과 H\lambda값이 항상 다를까? 같을 수도 있을까?

 

  •  
    RedoC Lv.3 2021.09.02 23:05 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      RedoC Lv.3 2021.09.02 23:09 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      김미래_기자 Lv.6 2021.09.03 12:59

      안녕하세요. RedoC님!

       

      김다인 멘토가 잘 풀었다는 피드백을 주셨어요!

       

      교수님께 최종 확인 후 해결 딱지를 드리겠습니다!

      좋아요1
  •  
    RedoC Lv.3 2021.09.05 14:59
    확인요청중

    문제 2 풀이입니다.

    다음을 만족하는 그래프를 '특수' 그래프라 명명하자:

    - 방향그래프의 형태를 띈다.

    - 모든 노드에 대해 그 노드에서 시작해 자신 포함 임의의 노드에 도착하는 엣지의 개수가 일정하다.

    즉 그래프 G는 '특수' 그래프이지만, 그래프 H는 '특수' 그래프가 아니다.

     

    각 노드에서 시작하는 엣지의 개수가 2^e개이고, 노드의 개수가 p개인 임의의 '특수' 그래프 G를 생각하자. 이 그래프 G에 대한 A_n은 다음과 같다.

    A_n = (2^e)^n \cdot p

    이를 이용하면 '특수' 그래프 G의 \lambda를 구할 수 있다.

    \begin{align*} \lambda &= \lim_{n \to \infty} \frac{\log_2 (2^e)^n + \log_2 p}{n} \\ &= \lim_{n \to \infty} \left ( \log_2 (2^e) \right ) + \lim_{n \to \infty} \frac{\log_2 p}{n} \\ &= \lim_{n \to \infty} e = e \end{align*}

    즉, '특수' 그래프 G의 경우 \lambda가 노드의 개수와 관계 없이 결정되며 이는 각 노드에서 시작하는 엣지의 개수가 같으면 노드의 개수와 상관 없이 같은 \lambda을 가진다는 것을 의미한다.

    이제 이 사실을 문제에 확장시키면, 각 노드에서 시작하는 엣지의 개수가 2^k개인 모든 '특수' 그래프가 \lambda = k를 만족한다는 것을 알 수 있으며 \lambda = k를 만족하는 '특수' 그래프들은 무한하기 때문에 자연수 k에 대하여 \lambda = k를 만족시키는 그래프는 무한하다는 것을 도출해낼 수 있다. ♦

    문제가 등록된지 조금 시간이 흘렀기 때문에, 그리고 이번에는 저도 제 답에 확신이 서질 않아서 공개 댓글로 올립니다.
    오류나 궁금한 점 있으시면 언제든지 남겨주세요. 감사합니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      RedoC Lv.3 2021.09.09 21:28 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      김미래_기자 Lv.6 2021.09.10 09:26

      김다인 멘토께서 잘 풀었다고 답변 남겨주셨습니다~. 

       

      두번째 문제도 교수님께 확인 후에 일괄적으로 알려드릴게요!

       

      김미래 드림.

      좋아요0
  •  
    RedoC Lv.3 2021.09.10 19:07

    문제 1 풀이입니다.

    I에서 시작하는 경로 중 길이가 k인 경로의 개수를 \small I_k, J에서 시작하는 경로 중 길이가 k인 경로의 개수를 J_k로 두자. 이때 A_n = I_n + J_n이다.

    이때 그래프의 노드 I에서 시작하는 경로 중 길이가 k인 경로의 마지막 원소를 K-Level로 두는 트리를 생각하자. 이때 트리는 [Figure 1]과 같은 모습을 띌 것이다. 이 트리에서 K-Level의 I, J 노드의 개수를 P_k = \begin{bmatrix} i\\ j \end{bmatrix} (i: 노드 I의 개수, j: 노드 J의 개수, P_0 = \begin{bmatrix} 1\\ 0 \end{bmatrix})의 형태를 띄는 행렬로 나타내자. 이때 I에서는 경로가 J로만 확장될 수 있고, J에서는 I와 J로 경로가 확장될 수 있다는 것에 의해 P_{k+1} = \begin{bmatrix} j\\ i+j \end{bmatrix}가 되며 또한 P_{k+2} = \begin{bmatrix} i+j\\ i+2j \end{bmatrix}가 성립한다. 이때, P_{k+2} = P_{k+1} + P_{k}이며 P_k의 원소합 Q_k = F_{k+1}이다. 또한 정의에 의거, I_k = Q_k이며 J부터 시작되는 경로 중 길이가 k인 경로의 마지막 원소가 K+1 Level에 존재하게 되므로 J_k = Q_{k+1}가 성립한다. 최종적으로, A_n = I_n + J_n = Q_n + Q_{n+1} = F_{n+1} + F_{n+2} = F_{n+3}로 정리된다. ♦

    [Figure 1]

     

    문제에 대한 참여도가 저조한 듯 하여 (현재 비밀댓글로 올려진) 문제 1 풀이를 공유해보려고 합니다.

    여러분들의 많은 참여 부탁드려요 :)

    댓글 작성하기 좋아요0 댓글수0
  •  
    구머 Lv.5 2021.09.19 12:15

    3번    log_2 \frac {1+\sqrt{5} } {2}이어야 할 것 같습니다

    댓글 작성하기 좋아요1 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911