Graph Theory

그래프이론(GraphTheory)이란 과학의 거의 모든 분야(자연과학이던, 인문사회과학이던)에서 필요로 하는 수학적 모델을 제공해주는 학문이다.
연구에서 다루는 주제는 대개 어떤 대상(object)의 집합과 그들 사이의 관계(relation)이다. GraphTheory는 대상-관계(object-relation) 구조에 관계된 복잡하게 얽힌 개념을 간결한 용어로 표현할 수 있도록 해 준다.
GraphTheory는 초보자들도 심심풀이로 풀어볼 수 있는 연습문제에서 수학의 달인이 도전하고 있는 미해결 문제까지 다양한 지적 도전으로 가득차 있다. GraphTheory 분야의 많은 흥미진진하고 주목하지 않을 수 없는 문제를 들여다보면 그 문제 자체는 이해하기 쉽지만, 그 답은 갈피를 잡을 수 없도록 어려운 경우가 많다.

-- 1992년에 GraphTheory의 미래에 관해 나온 논문집 Quo Vadis, Graph Theory?의 서문에서 발췌 번역

잘 알려진 GraphTheory 문제들 ¶

Königsberg의 다리 문제 - Königsberg의 일곱 개의 다리를 한 다리를 두 번 건너지 않으면서 모두 건널 수 있느냐?

[JPEG external image]

Note: 이 문제에 관해 Euler가 1736년에 쓴 글은 GraphTheory 분야의 첫 논문으로 알려져 있다.
4색문제
TravelingSalesmanProblem

세일즈맨이 n개의 서로 떨어져 있는 도시들을 한 번씩 방문하면서 세일즈를 해야 한다고 했을 때, 도시와 도시 사이를 어떻게 (어떤 도시를 먼저 방문하며, 그 다음에는 어떤 도시를 방문하는지의 문제) 돌아다녀야 최단시간이 걸리는가?
Steiner Tree Problem
Partition problem

[edit]

질문 ¶

생물정보학의 각종 알고리즘들이 GraphTheory에 바탕을 두고 있는것들을 많이 접해왔습니다. 일반적인 이산수학책 중반이후에 소개되는 GraphTheory만으로는 많이 부족한가요? 제가가진책은 Skvarcius/Robinson의 이산수학책입니다. --yong27

Bondy&Murty 책은 한번 쭉 읽어보셔야 합니다. 모든 다른 책이나 논문은 대개 이 책의 정의를 따르거든요. -- 까리용

까리용님과 김창준님의 추천으로 Concrete Mathematics 샀습니다. 다른 곳에는 없는 것 같고, 영풍문고에서 25,000원 주고 샀는데, 이게 지금 아마존에서는 $54.95 거든요. Print 된지는 오래된 것 같지만 어쨌든 Second Edition 맞아요. 아직 한권 남아 있으니... 관심 있는 분은 영풍문고로...

(2001.9.12 현재)

서문에 재미있는 내용이 많은데, Concrete Mathematics 의 "CONCRETE" 가 "CONtinuous" 와 "disCRETE" 의 blend 라는 말도 있고, 이 책은 저자들이 수학을 하는데 있어 가장 좋아하는 방법으로 접근한 일종의 manifesto 이고, 주제들이 저절로 확실해지고 생명을 얻어서 이 책은 거의 스스로 쓰여진 것처럼 보인다는 멋진 얘기도 있구요.

또한 이 책에서 처음으로 틀린 점을 발견한 사람에게는 $2.56 주겠다는 내용도 있습니다.

이건 DonaldKnuth 의 철학이랍니다. 하지만 큰 기대는 하지 마세요. 역시 훌륭하다고 평가받는 이산수학책인 Discrete Mathematics and It's Applications 에 보면 저자 Rosen 이 DonaldKnuth 의 책에서 오류를 발견하고 편지를 보냈는데, Rosen 의 편지 몇달전에 그 오류는 다른 사람에 의해서 보고되었다는 답장을 몇년 후에 받았답니다.

아쉬운 점은 여기는 GraphTheory 에 대한 얘기는 없는 것 같네요. 하하. 좋은 책은 샀는데, 공부는 언제 하나?

--지상은

고등학교땐 수학이 좋아 공부를 했고 그래서 대학에 가서 무작정 수학을 전공했지만 공부하는 중에는 정작 수학이란 학문의 진정한 매력을 몰랐던 것 같습니다. 대학강의중 그래프이론이 어떻게 적용되어 이용될 수 있는지를 알았다면 좀더 관심있고 재미있게 배웠을텐데...라는 아쉬움이 남습니다.
솔직히 그래프이론이 생각이 나지않습니다. @_@;
오일러의 다리문제에 관한 논문은 기학학에서 최초로 위상학적 성질을 연구한 논문으로 평가됐다고 합니다.
--하늘아이

수학분류, 컴퓨터분류

Graph Theory

잘 알려진 GraphTheory 문제들 ¶

관련 책 추천 ¶

질문 ¶