ComputerScience에서 DataStructure의 하나인 [Graph]에 관한 이론들.

어떤 대상(object, node)들과 그들 사이의 관계(relationship, edge)에 관한 이론. [Bioinformatics]의 많은 문제들이 실제 GraphTheory문제인경우가 많다.

알려진 GraphTheory문제들

• TravelingSalesmanProblem

• AntiSymmetricLongestPathProblem

• ShortestPathProblem

• EulerPathProblem

• HamiltonianPathProblem

관련자료

• IntroductionToAlgorithms

• GraphTheoryWithApplications

• ReinhardDiestelGraphTheory

• [http://bioinfo.sarang.net/moin/wiki/upload/GraphTheoryII.pdf GraphTheory]

• [http://home.hanmir.com/~johnsonj/etc/Python%20Patterns%20-%20Implementing%20Graphs.htm 파이썬으로구현]

  • 여기서 구현한 내용은 recursive 함수를 사용해서 shortest path를 구하는 건데요, 그렇게 하면 노드가 많아질 경우 stack overflow되서 제대로 동작하지 못할 것 같습니다. 대략 어느정도 recursive가 불려질 경우 에러가 발생할지는 모르겠지만.. DynamicProgramming으로 path 구하는 방법을 바꿔야 하지 않을까 합니다. --[destine], 2004-03-21

SeeAlso GraphTheory