33.jpg
55.jpg

KAIST부설 한국과학영재학교 온라인 과학매거진 코스모스

  • 블랙 페이스 북 아이콘
  • 블랙 인스 타 그램 아이콘

그래프이론, 세상을 바꾸다

고등교육과정에서 자취를 감추었던 그래프 이론. 그러나 일상에서는 알게 모르게 자주 접하고 있는 그 이론. 특히 사회 현상의 분석과 관련하여 그래프 이론이 자주 사용되는데, 이 그래프 이론이 무엇이고, 어떤 역할을 해줄 수 있는지, 조금 구체적으로 알아봅시다. 이 글에서는 그래프 이론에 대한 구체적인 내용보다는 그 활용 방식에 초점을 두고 있기에 기본적인 지식이 없어도 이해하는데 전혀 무리가 가지 않을 것입니다.


그래프, 그 기본적인 개념

우선 그래프 이론이 무엇인지 알아보려면 “그래프”라는 단어가 무엇인지 알아야할 것 같습니다. 물론, 여기서 말하는 그래프는 함수의 관계를 나타내는 그림을 의미하는 것이 아닌, 완전히 다른 개념을 말하는 것입니다. 그래프 이론에서 그래프는 점과 선으로 나타낸 도형이며, 이때, 점을 ‘꼭짓점’, 두 꼭짓점을 연결한 선을 ‘변’이라고 합니다. 만일 두 꼭짓점을 A, B라고 하고, 그 사이의 변이 하나뿐이라면 그 변을 AB 또는 BA라고 나타냅니다.


그래프 이론의 기초

또한, 길이와 위치에 상관 없이, 꼭짓점의 위치를 바꾸거나 변의 모양과 길이를 변형하여 두 그래프를 일치시킬 수 있을 때, 두 그래프를 서로 같다, 또는 동형이라고 합니다.


그래프 이론 상에서 서로 같은(동형의) 그래프 (G와 H는 서로 동형이다.)

경로라는 개념 역시 존재합니다. 경로는 그래프의 한 꼭짓점에서 이어진 변을 따라 다른 꼭짓점으로 연결하는 길을 의미라고 하며, 연결된 변의 개수가 n개라면, ‘길이가 n인 경로’라고 합니다. 또한, 선분 대신 화살표를 그리는 것 역시 가능한데, 화살표를 그리게 된다면, 화살표를 따라서만 이동이 가능해집니다. 양방향 통행이 아닌 단방향 통행이 되는 것이지요.


한붓그리기

그래프 이론의 가장 대표적인 예시로 한붓그리기를 들 수 있습니다. 한붓그리기란, 그래프의 모든 변을 단 한번씩만 통과하는 경로를 의미합니다. 한붓그리기의 대표적인 문제로 쾨니히스베르크의 다리가 있습니다. 이는 아래 그림과 같이 7개의 다리가 놓여있을 때, 7개의 다리를 한 번씩만 지나도록 모두 건널 수 있는지 알아보는 문제입니다.


쾨니히스베르크의 다리

다리 사이 사이에 꼭짓점을 두고, 다리를 지나도록 변을 그려보면 위에 나와있는 그림처럼 문제를 단순화할 수 있습니다. 결국, 두 개의 원뿔모양이 겹쳐진 형태에 대해 한붓그리기가 가능하느냐 라는 문제가 되는 것입니다.


답은 “불가능”하다 였습니다. 홀수점이 C, A, B로 3개이기에 불가능했던 것인데요, 오일러에 따르면, 연결된 변의 개수가 홀수인 꼭짓점이 0개 또는 2개인 그래프만이 한붓그리기가 가능하고, 한붓그리기가 가능하면 연결된 변의 개수가 홀수인 꼭짓점이 0개 또는 2개이어야하기 때문입니다. 더 구체적인 내용이 궁금하다면 인터넷에 검색해보면 좋을 것 같습니다.


다양한 그래프의 종류

앞에서 봤듯이, 그래프의 활용은 무궁무진합니다. 평면 지도에서도 그래프 이론을 활용할 수 있습니다. 지하철 노선도 역시 역이 점으로, 철길은 선으로 나타나 그래프의 형태를 띠고 있으며, 모든 지도는 4가지 색 만으로도 그 경계의 색이 다르도록 칠할 수 있다는 4색 정리에서도 그래프를 활용할 수 있습니다. 4색 문제의 경우, 최소 반례와 다섯 이웃 정리 등의 아이디어 역시 활용 가능하다. 4색 정리가 증명된 이후, 하트비거의 추측과 같은 더 확장된 연구가 계속되고 있습니다.


4색 정리의 예시
현실 세계에서의 적용

우선, 그래프는 어떠한 복잡한 상황을 직관적으로 보이게 단순화시켜줍니다. 앞의 쾨니히스베르크의 다리 문제를 보면, 그래프 이론을 통해 문제의 단순화가 가능하다는 것을 느끼실 수 있으셨을 것입니다. 이처럼 상호관계를 직관적으로 표현해주는 그래프는 여러 복잡한 문제를 단순화시킬 수 있다는 단점이 있기에, 현실 세계의 여러 상황에서도 잘 적용되며 복잡한 문제들을 해결하는데 도움을 줍니다. 첫 번째로 볼 예시는 우체부 문제입니다. 우체부가 우편물을 모두 배달하기 위한 최적의 경로를 묻는 문제입니다. 이는 그래프의 모든 변을 통과하는 최단 거리의 닫힌 경로를 찾는 것으로 단순화시킬 수 있을 것입니다. 그러나, 그래프는 경로의 거리를 생각하지 않아 이동하는데 걸리는 시간을 알 수 없습니다. 그렇기에, 이러한 그래프에 시간, 거리적 요소를 고려시키려는 노력이 있었고, 그 결과가 가중 그래프입니다. 이는 각 변에 가중치를 부여하는데, 이를 이용한다면 여러 경로를 그래프로 효율적이게 표현할 수 있습니다.


가중 그래프의 예시. 적혀있는 숫자들이 거리를 나타낸 가중치이다.

이러한 가중 그래프는 화물 운송 경로에도 응용될 수 있습니다. 운송하는 화물의 양에는 한계치 Max flow만큼이 존재할 것이며, 운송 경로의 최소치 Min cut이 존재하게 됩니다. 이때, Min cut의 운송 한계치의 합과 Max flow의 값이 같다는 정리가 Max-flow Min-cut Theorem 이라고 합니다. 예시를 보면서 계산해보면 성립하는지 대략적으로 확인해볼 수 있을 것입니다.


짝을 지어주는 데에도 그래프 이론이 활용될 수 있습니다. 사이가 좋은 이성 친구들 사이를 변으로 연결하여 이를 찾을 수 있습니다. 이외에도 사회학에서 여러 사람들 사이의 관계를 그래프로 나타내어 해석하는 데에 가장 중요하게 사용됩니다. 특히 사회학은 복잡한 계를 주로 다루기에, 이러한 그래프 이론을 통해 데이터를 더 빠르고 효율적으로 처리할 수 있을 것입니다.


마무리

지금까지 그래프 이론이 무엇이며 어떤식으로 활용이 가능한지에 대해 다루어보았습니다. 깊이 있는 내용을 다루지는 않았기에, 읽는데에 큰 어려움은 없었을 것이라고 생각됩니다. 그러나, 그래프 이론을 더 자세히 알아보고 싶은 분들도 있을 것으로 생각되어, 어렵지는 않으나, 조금 더 자세히 알 수 있는 그래프 이론의 기초를 다룬 영상 링크를 아래와 같이 남깁니다.



이 기사를 통해 그래프 이론이 무엇인지, 어느정도 활용도가 있었는지 한 번 생각해볼 수 있는 기회가 되었으면 좋겠습니다.


 

정지훈 | Math & Computer Sci. | 지식더하기


참고자료

[1] 수학의 정석

[2] https://times.kaist.ac.kr

[3] https://terms.naver.com/

[4] https://www.ibs.re.kr/


첨부 이미지 출처

[1] aerocode.net

[2] https://velog.io/

[3] https://namu.wiki/

[4] https://kcjeong.cbu.ac.kr/

[5] https://luv-n-interest.tistory.com/


첨부 동영상 출처

[1] https://www.youtube.com/watch?v=GXM1-xHlbxc



ⓒ KAIST부설 한국과학영재학교 온라인 과학매거진 KOSMOS

조회수 280회댓글 0개

최근 게시물

전체 보기