Graphs

어제 졸려서 못다한 정리 이어서 하기~
이산수학에서 중점적으로 다뤄야 할 건 우리가 흔히 아는 그래프, 트리같은 것의 수학적 정의를 숙지하는 것이다.


Graph
undirected graph, 즉 ugraph는 edge가 2개 element의 쌍을 가지는 vertex의 subset인 경우를 말한다.
음. 즉 엣지가 set의 성질을 따르기 때문에 순서는 상관없다는 것을 의미한다.

directed graph, 즉 digraph는 일반적으로 정의하는 그래프 같은 것으로써 엣지는 버텍스 간의 카티션 곱의 서브셋이다. 즉 버텍스간의 릴레이션이다.
수학적으로 표현하면,
E⊆V×V 이다. 

그리고 어떠한 Graph가 다이그래프일때, path는 vertices의 sequence로 정의되며 각각의 인접한 버텍스들 간에는 edge가 있어야 한다. 출발지점과 도착지점이 같으면서 길이가 1 이상인 path를 cycle이라고 한다.
그리고 두개의 버텍스 사이에 path가 있으면 두 버텍스는 연결되었다(connected)고 말하며 이것 또한 릴레이션으로 생각할 수 있다.  (ex> u connected v)

또한 어떠한 edge (u,v)가 있을때 버텍스 u와 v는 인접하다(adjacent)고 말한다.
그리고 어떠한 vertex에 연결된 edge의 수를 해당 vertex의 degree라고 말하며 deg(A)와 같이 표현한다.
 
특수한 그래프로써, 모든 버텍스간에 엣지가 연결되어 있는 그래프를 완전 그래프, 즉 complete graph라고 말하며
Kn으로 표현한다.

새로운 정의로써 Euler path와 Hamilton path가 나온다.
오일러 패쓰는 모든 엣지를 다 지나가는 패쓰를 의미한다. 어렸을 때 한붓그리기 라고 했던가..
그 때 그렸던 길이 오일러 패쓰라고 보면 될 것이다. 오일러 패쓰는 각각의 버텍스의 degree가 짝수이며 단 두개의 버텍스만 홀수 degree를 가진다. 생각해보면 당연하게 받아들일 수 있다. 왜냐하면 들어오면 나가야 되기 때문이다. 그리고 시작지점과 끝나는 지점은 당연스럽게도 홀수 degree가 된다.
그리고 해밀턴 패쓰는 각각의 버텍스를 한번씩만 들르는 패쓰를 의미한다.

각각의 엣지에 cost를 가지는 그래프를 weighted graph라고 하는데 이 경우 shortest path problem이 등장한다.
어떠한 출발 vertex에서 목표 vertex로 가는 path를 찾되 최소 cost를 가지는 path를 찾는 문제이다.
이 문제는 실제 응용도 많이 될 것이라고 예측할 수 있다. 실제로도 기본적인 최단거리 계산은 그래프 개념을 적용한다.
그렇다면 이 문제의 해결법이 필요하다.
그것이 바로 그 이름도 유명한 Dijkstra's algorithm이다. 한글로 다익스트라 알고리즘이다.
Formal하게 정의하자면 길어질 것 같아서 간단히 정리하면
시작지점부터 시작해서 완성된 버텍스의 집합을 가지며 인접 버텍스에서 최소 cost를 가지는 것을 계속 추가해 나간다.
그 버텍스의집합이 모든 버텍스를 가지게 되면 알고리즘은 종료한다.
그리고 그 과정중에 그 집합에 추가하는 버텍스의 코스트와 인접한 버텍스와 그 버텍스간의 코스트를 합한 것이 
기존에 가지고 있던 코스트보다 더 작을 경우 코스트를 업데이트한다.
풀어서 쓰니까 더 어려워 보인다-_-... 나중에 시간내서 따로 잘 정리해 봐야겠다.
여튼! 이 알고리즘은 Computer Network에서 라우팅 테이블을 만드는 Link state algorithm으로도 사용된다.


Tree
트리를 그래프의 개념으로 정의할 수도 있다. 누군가는 트리의 정의를 물었을 때 상대의 대답으로 수준을 판별할 수 있다고 했다. 믿거나 말거나..ㅎㅎ

Tree는 acyclic connected graph이다. 즉 사이클이 없는 연결된 그래프이다. 구지 추가하자면 undirected graph이다.
트리는 여러가지 성질을 가지지만 트리만 따로 챕터가 있기 때문에 그건 그 단원 공부할때 정리해야겠다.