Graph Theory

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

see also WikiPedia:Graph_theory

잘 알려진 GraphTheory 문제들

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


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

  • 4색문제

  • TravelingSalesmanProblem

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

  • Partition problem

관련 책 추천

전산을 전공하는 학부생 중 GraphTheory에 관심있는 사람에게 책을 추천한다면 (대충 3-4학년 수준에 맞는 책들임) 다음과 같습니다. 그래프 이론을 하려면 이론적 배경도 튼튼하면 좋으니 함께 추천하죠.

  1. Introduction to Algorithms, Cormen, Leiserson, Rivert 저. 가장 널리 쓰이는 알고리즘 교재.
  2. Concrete Mathematics, Graham, DonaldKnuth, Patashnik저. 알고리즘의 기초인 이산수학을 제대로 이해하자면...
  3. Introduction to Algorithms, Uni Manber 저. 알고리즘을 디자인하는 방법을 익히고 싶다면...
  4. Graph Theory with Applications, Bondy, Murty 저. 그래프 이론의 Bible!
    절판되어 서점에서 구할 수는 없지만, [http]Bondy 교수님의 홈페이지에 책 전체를 scan한 pdf 파일을 올려놓았습니다.

질문

생물정보학의 각종 알고리즘들이 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 에 대한 얘기는 없는 것 같네요. 하하. 좋은 책은 샀는데, 공부는 언제 하나? ^^ --지상은

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




"; if (isset($options[timer])) print $menu.$banner."
".$options[timer]->Write()."
"; else print $menu.$banner."
".$timer; ?> # # ?>