그래프 이론

in kr-dev •  3 years ago 

그래프 이론은 자연이나 사회 현상, 네트워크의 구조를 점과 선으로 단순화해 이해하고 분석하는 이론이다. 최근에는 그래프 이론을 다양한 분야에서 응용하면서 그 중요도가 높아지고 있다.

18세기경, 쾨니히스베르크라는 도시에는 강이 흐르고 있었다. 강에는 7개의 다리가 있었다. 과연 이 다리를 중복해서 건너는 일 없이 모두 한 번씩 건널 수 있을까. 한붓그리기 문제로 유명한 이 ‘쾨니히스베르크의 다리’에서 그래프 이론이 시작되었다.

▲ 쾨니히스베르크의 다리 = 육지와 다리가 정점, 간선에 대응된다 /이가영 기자

한붓그리기로 시작한 그래프 이론

오일러는 육지를 점, 다리를 선으로 대응시켜 문제를 단순화했다. 그래프 이론에서 점은 ‘정점(ver-tex)’, 정점을 연결하는 선을 ‘간선(edge)’이라고 한다. 정점과 간선을 건너뛰지 않고 움직이는 것을 ‘워크(walk)’라고 한다. 간선이 중복되지 않는 워크를 ‘트레일(trail)’, 모든 간선을 지나가는 트레일을 ‘오일러 트레일(Euler trail)’이라고 한다. 시작점과 도착점이 같은 워크를 ‘닫혀있다(closed)’라고 하며, 모든 간선을 ‘적어도’ 한 번씩 지나가는 닫힌 워크를 ‘투어(tour)’라고 한다. 모든 간선을 ‘정확히’ 한 번만 지나가는 투어는 ‘오일러 투어(Euler tour)’라고 한다. 결국, 어떤 그래프를 한붓그리기할 수 있는지는 오일러 트레일을 갖는 그래프인지 아닌지를 판별하는 문제로 귀결된다.

쾨니히스베르크의 다리를 단순화한 그래프는 오일러 트레일이 아니다. 이는 쾨니히스베르크 다리를 정확히 한 번씩만 건널 수 없다는 것을 의미한다. 그래프가 오일러 트레일을 가질 조건은 뜻밖에도 간단하다. 한 정점에 연결된 간선의 개수를 ‘차수(degree)’라고 하는데, 홀수 차수를 갖는 정점의 개수가 2개 이하인 그래프는 오일러 트레일을 갖는다. 모든 정점이 짝수 차수를 갖는다면 아무 점에서나 시작해도 오일러 투어를 그릴 수 있으며, 홀수 차수를 갖는 정점 2개면 그 점이 시작점이나 끝점이 되는 오일러 트레일을 그릴 수 있다. 쾨니히스베르크 다리의 그래프는 홀수 차수의 정점이 4개나 되므로 오일러 트레일을 갖지 않는다는 것을 알 수 있다.

알아보기 쉽게 단순화하다

지하철 노선도는 일반 지도와 달리 역들 사이의 거리 비율도, 역의 위치도 엉망이다. 그럼에도 ‘지도’라는 측면에서 이렇게 불합리한 지하철 노선도를 이용하는 이유는 무엇일까. 지하철 노선도를 보는 데는 지하철 역 간의 실제 거리, 역의 자세한 위치가 중요하지 않다. 1호선은 어느 역을 거치는지, 환승 역은 어디 있는지 등 역들이 서로 연결된 관계가 중요하다. 따라서 지하철 노선도는 이러한 역 사이의 관계를 명확히 드러내기 위해 거리 등의 부차적인 정보를 생략하고 간결한 그래프로 나타낸다.

그래프 이론과 우체부 문제

그래프는 이렇게 복잡한 대상이나 관계를 단순화해 보기 쉽게 만들기만 하는 것은 아니다. 그래프 이론은 어떤 문제에 대해 최적의 방법이나 효율적인 경로를 찾기 위해서도 사용된다.

우체부가 어떤 구역의 모든 집에 우편물을 배달해야 한다면, 최적의 경로는 어떻게 찾아야 할까. 모든 집에 우편물을 배달하려면 (집은 길옆에 늘어서 있으므로) 그 구역의 모든 길을 통과해야 한다. ‘중국 우체부 문제(Chinese Postman`s Problem)’라고도 이름 붙여진 이 문제는 결국, 그래프의 모든 간선을 적어도 한 번 통과하는 최단 거리의 닫힌 워크를 찾는 문제다.

가중 그래프로 최적의 경로 찾을 수 있어

하지만 이 문제를 풀기 위해서는 연결 관계만 드러난 그래프로는 부족하다. 각 길을 통과하는 데 걸리는 시간을 알 수 없으므로, 각 길의 거리정보가 필요하다. 이렇게 각 간선에 값을 부여한 그래프를 ‘가중 그래프(weighted graph)’라고 한다. 각 간선에 부여된 가중치를 알면 적절한 알고리즘을 이용해 최적의 경로를 찾아낼 수 있다.

최적의 경로를 찾는 문제는 이 외에도 다양하다. 부산에서 서울까지 운전한다고 생각해 보자. 어느 길로 가는 것이 최단 거리일까? 교차점과 출발점, 도착점 등을 정점으로 놓고 사이의 도로를 간선으로 표시하면 복잡한 도로망도 하나의 그래프로 표현할 수 있다.

운송로의 취약점 드러내

운송로의 취약점 드러내

이번엔 최대한 많은 화물을 부산에서 서울로 운송한다고 생각해 보자. 부산에서 서울로 향하는 운송로를 그래프로 표현할 때, 각 간선에 운송할 수 있는 한계치를 설정하면 부산에서 서울로 운송하는 화물의 전체 양은 한계가 존재할 수밖에 없다. 이 값이 이 그래프의 ‘Max flow’ 값이다. 흥미로운 사실은, 서울과 부산 사이의 운송 경로를 마비시키기 위해 끊어야 하는 최소한의 운송로를 ‘Min cut’이라고 할 때, ‘Min cut’의 운송 한계치의 합과 ‘Max flow’의 값이 같다는 점이다. 이를 ‘Max-flow Min-cut Theorem’이라고 하는데 적국의 보급로를 최소한으로 끊어 최대한의 타격을 주기 위한 연구 과정에서 도출되었다. 이 정리는 일견 당연한데, 최대한 많은 양의 화물을 운송하려면 필연적으로 운송 한계치가 작은 곳에서 ‘병목 현상(bottle neck)’이 일어날 수밖에 없기 때문이다. 이때 병목 현상이 일어나는 운송로를 끊으면 타격이 큰 것은 당연하다.

이번엔 최대한 많은 화물을 부산에서 서울로 운송한다고 생각해 보자. 부산에서 서울로 향하는 운송로를 그래프로 표현할 때, 각 간선에 운송할 수 있는 한계치를 설정하면 부산에서 서울로 운송하는 화물의 전체 양은 한계가 존재할 수밖에 없다. 이 값이 이 그래프의 ‘Max flow’ 값이다. 흥미로운 사실은, 서울과 부산 사이의 운송 경로를 마비시키기 위해 끊어야 하는 최소한의 운송로를 ‘Min cut’이라고 할 때, ‘Min cut’의 운송 한계치의 합과 ‘Max flow’의 값이 같다는 점이다. 이를 ‘Max-flow Min-cut Theorem’이라고 하는데 적국의 보급로를 최소한으로 끊어 최대한의 타격을 주기 위한 연구 과정에서 도출되었다. 이 정리는 일견 당연한데, 최대한 많은 양의 화물을 운송하려면 필연적으로 운송 한계치가 작은 곳에서 ‘병목 현상(bottle neck)’이 일어날 수밖에 없기 때문이다. 이때 병목 현상이 일어나는 운송로를 끊으면 타격이 큰 것은 당연하다.

▲ ‘Max-flow Min-cut Theorem’ = 큰 글자는 간선에 허용되는 최대 흐름이고, 작은 글자는 최대한 많은 양이 흐를 때 각 간선의 흐름이다. 노란 영역을 기준으로 자르면 보라색 간선의 흐름이 최대치이고, 이 간선을 자르면 최소한의 비용으로 흐름을 차단할 수 있다 /이가영 기자

좋은 짝을 찾아주는 그래프 이론

짝을 지우는 데도 그래프 이론은 중요한 역할을 한다. 학교에서 남학생과 여학생의 수가 같고, 남학생 한 명과 여학생 한 명을 짝으로 정해주는 상황을 가정해 보자. 각 학생을 정점으로 바꾸고, 사이가 좋은 이성 친구들끼리 간선을 이어주면 이 문제는 그래프 문제가 된다. 목표는 최대한 사이가 좋은 친구들끼리 짝을 맺어주는 것이므로, 그래프 상에서는 간선들의 집합 중 같은 정점에서 만나지 않는 최대한 많은 간선을 포함하는 부분집합을 찾는 문제로 바뀐다. 영국의 수학자 필립 홀은 ‘홀의 결혼정리’를 증명해 남학생과 여학생을 사이좋은 친구끼리 짝지어줄 수 있는 조건을 찾았다.

이러한 짝 지우기 문제도 다양한 분야에 응용되고 있다. 학생을 학교에 배정할 때나, 효율적으로 신장 이식을 할 수 있도록 하는 알고리즘에도 짝 지우기 문제에 관한 그래프 이론이 적용되고 있다.

짝을 지우는 데도 그래프 이론은 중요한 역할을 한다. 학교에서 남학생과 여학생의 수가 같고, 남학생 한 명과 여학생 한 명을 짝으로 정해주는 상황을 가정해 보자. 각 학생을 정점으로 바꾸고, 사이가 좋은 이성 친구들끼리 간선을 이어주면 이 문제는 그래프 문제가 된다. 목표는 최대한 사이가 좋은 친구들끼리 짝을 맺어주는 것이므로, 그래프 상에서는 간선들의 집합 중 같은 정점에서 만나지 않는 최대한 많은 간선을 포함하는 부분집합을 찾는 문제로 바뀐다. 영국의 수학자 필립 홀은 ‘홀의 결혼정리’를 증명해 남학생과 여학생을 사이좋은 친구끼리 짝지어줄 수 있는 조건을 찾았다.

이러한 짝 지우기 문제도 다양한 분야에 응용되고 있다. 학생을 학교에 배정할 때나, 효율적으로 신장 이식을 할 수 있도록 하는 알고리즘에도 짝 지우기 문제에 관한 그래프 이론이 적용되고 있다.

다양한 응용 분야와 연구

그래프 이론은 비단 수학뿐만 아니라 다양한 분야에서 응용, 연구되고 있다. 전산학에서는 데이터 구조에서 그래프 이론을 중요하게 다루고 있다. 큰 용량의 데이터를 빠르고 효율적으로 다루기 위해서다. 사회학은 초기에 사람들 사이의 관계를 기술하고 해석하기 위해 그래프 이론을 사용했다. 최근에는 집단에서 계층이나 역할의 분화를 설명하는 등, 통계적인 모델을 이용해 관계의 영향력이 특정한 결과에 영향을 주는지 측정하는 데도 이용하고 있다. 우리 학교 문화과학기술대학원 소셜 컴퓨팅 연구실은 SNS를 분석해 기존의 작은 네트워크에서 나타나는 사회학적 메커니즘이 큰 네트워크에서도 적용되는지를 연구하고 있다. 물리학과 정하웅 교수는 그래프 이론과 관련이 깊은 ‘복잡계 네트워크 과학’ 분야를 연구하고 있다.

수리과학과에서는 엄상일 교수가 그래프 구조이론(Structural graph theory)분야의 문제를 다루고 있다. 엄 교수는 “그래프 이론은 다른 수학 분야에 비해 젊은 분야이기 때문에, 최신 연구 결과에 빨리 다가가서 흥미로운 연구를 할 수 있다”라며 “국내에 전공자가 많지 않은 분야라 많은 기회가 있을 것이다”라고 말했다.

출 처 https://times.kaist.ac.kr/news/articleView.html?idxno=1526

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

[광고] STEEM 개발자 커뮤니티에 참여 하시면, 다양한 혜택을 받을 수 있습니다.