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

Junior Polymath

주니어 폴리매스 문제 보기

문제

[코딩 수학] 코딩으로 '그래프 이론' 정복하기

2019.04.04

같이 풀어볼까?

네이버밴드 구글플러스

코딩 수학 4번째 시간입니다. 다들 코딩을 이용해 수학 문제를 효율적으로 풀고 계신가요? 간단한 수학 문제는 손으로도 풀고 코딩으로도 풀 수 있지만, 실생활 문제나 어렵고 복잡한 함수가 포함된 수학 문제는 손으로 풀기 어려운 경우가 많아요. 코딩을 활용하면 쉽게 해결할 수 있으니 열심히 익히고 활용해 보자고요!

코딩 명령어를 익힌 뒤엔 해당 코딩 명령어로 풀 수 있는 수학 문제를 찾아 댓글로 달고 친구들과 토론해 보세요.





한붓그리기에서 시작된 ‘그래프 이론’


이번에 코딩으로 정복해 볼 수학 개념은 ‘그래프 이론’입니다. 대부분 그래프를 통계 자료를 보기 좋게 나타낸 그림으로 알고 있을 텐데요, 여기서 그래프는 꼭짓점과 이들을 연결하는 변으로 이뤄진 그림을 뜻해요. 그래프 이론은 이런 그래프의 성질을 연구하는 분야로, 변의 길이나 꼭짓점의 위치보다는 어떻게 연결됐는지에 주목합니다.


여러 수학 분야와 컴퓨터 및 네트워크와 관련된 분야에서 쓰이는 그래프 이론은 1736년 독일에서 주로 활동한 스위스 수학자 레온하르트 오일러(Leonhard Euler)에 의해 시작됐습니다. 독일 쾨니히스베르크의 프레겔 강에는 7개의 다리가 있었는데, 사람들은 이 다리들을 한 번씩만 건너서 처음 위치로 돌아올 수 있는 지 궁금했습니다. 오일러는 다리로 이어진 지점을 꼭짓점으로, 다리를 변으로 나타낸 뒤 어떤 점에서 출발해도 변을 한 번씩만 지나서 원래 점으로 돌아오는 게 불가능하다는 사실을 밝혀냈죠.






오일러가 했던 것처럼 어떤 그래프의 한 점에서 출발해 모든 변을 한 번씩만 지나 원래 점으로 돌아올 수 있는지 따지는 문제를 한붓그리기 문제라고 합니다. 그래프 이론에서는 한붓그리기가 가능한 그래프를 오일러 경로(Euler path)를 갖는 그래프라고 하죠.

그래프가 오일러 경로를 가지려면 주어진 그래프가 연결 그래프이면서 추가로 모든 꼭짓점의 차수(Degree)가 짝수거나 또는 꼭짓점 중 두 개만 차수가 홀수여야 합니다. 여기서 차수는 꼭짓점에 연결된 변의 개수입니다.

한붓그리기 문제에서 모든 꼭짓점의 차수가 짝수면 어떤 꼭짓점에서 시작해도 한붓그리기를 할 수 있고, 차수가 홀수인 점이 2개일 때는 두 점 중 한 꼭짓점에서 시작해 나머지 한 꼭짓점에서 끝나도록 그리면 됩니다.

자 이제, 코딩을 통해 다양한 그래프를 그려보고 한붓그리기가 가능한지 알아보도록 할까요?




.

.

.



코 딩 타 임



그래프 이론과 관련된 코딩 명령어를 이용해 그래프를 그려보고 한붓그리기가 가능한지 탐구해보자.




1단계 따라하기

꼭짓점과 변이 모두 3개인 삼각형 모양의 그래프를 그리고 G라고 이름붙이자. 꼭짓점 a와 연결시키고 싶은 꼭짓점을 :[와 ] 사이에 쉼표로 구분해 모두 적는다. G.degree()를 적으면 모든 꼭짓점의 차수가 번호 순서대로 나타난다.




2단계 나아가기

사각형과 사각형이 붙은 집 모양 그래프를 그리고 꼭짓점의 차수를 계산해 한붓그리기가 가능한지 확인해보자.




3단계 활용하기

비슷하게 쾨니히스베르크의 다리 문제를 코딩으로 해결해보자. 코딩 명령어를 이용해 다양한 형태의 그래프들을 그려보고 한붓그리기가 가능한지 알아보자.





-끝-


댓글 3

  • 아인수타인 2019.04.10 00:49:50

    앗, 한붓그리긴 아니지만 매스펀에 제가 냈던 문제 중 비슷한 원리 이용한 문제가 있네요. 여기 링크 겁니다.

    좋아요1 댓글수0
  • MENEC 2019.04.24 17:04:33

    너무 멋있고, 재밌네요. ㅎㅎ 그래프 이론 공부해보고싶어요!

    좋아요0 댓글수0
  • je 2019.04.24 17:13:23

    핸드폰에서도 잘 나와서 너무 신기해요!!ㅎㅎ 이렇게 수학문제를 재밌게 풀어볼 수 있어서 너무 좋네요~ 앞으로도 많이 만들어주세요!

    좋아요0 댓글수0