그래프 이론

그래프는 점과 선을 연결하여 구성된 구조로, 점을 꼭지점(Vertex), 정점(Vertex), 또는 노드(Node)라 하며, 선을 변(Edge) 또는 간선(Edge)라 부른다. 그래프에는 여러 가지 유형이 있으며, 각각의 특성과 용도가 존재한다.

연결 그래프는 모든 정점 사이가 연결되어 있는 그래프로, 모든 정점의 경로가 존재하는 것이 특징이다. 반면, 고립 정점은 어떤 정점과도 연결되지 않은 정점을 말한다. 동형 그래프의 경우, 정점들이 어떻게 연결되어 있는지가 중요하기 때문에 정점의 위치가 그래프의 본질적인 차이를 만들지 않는다. 즉, 정점을 이동시키더라도 본질적으로 같은 그래프가 될 수 있다.

복잡한 그래프에서는 평행 변(Parallel Edge)이 포함될 수 있으며, 이는 정점 두 개가 두 개 이상의 변으로 연결된 경우를 뜻한다. 또한 양끝이 같은 변(Self-loop)은 하나의 정점에서 시작해서 같은 정점으로 끝나는 변이다. 유향 그래프(Directed Graph)는 각 변에 방향이 부여된 그래프이다. 유향 비순회 그래프(Directed Acyclic Graph; DAG)는 임의의 정점에서 출발하여 해당 정점으로 다시 돌아오는 경로가 없는 그래프를 의미한다.

가중 그래프(Weighted Graph)는 간선, 혹은 정점에 가중치가 부여된 그래프로, 가중치 정보가 추가된 유향 그래프의 한 종류이다. 이들은 네트워크라고도 하며, 신경망이나 베이즈 네트워크 등이 이에 해당한다. 가중 그래프는 상태 전이 다이어그램에서도 활용된다.

무향 그래프(Undirected Graph)는 변에 방향이 존재하지 않는 그래프로, 각 변이 쌍방향으로 해석된다. 그래프는 행렬로 표현될 수 있으며, 이는 인접 행렬(Adjacency matrix)과 근접 행렬(Incidence matrix)로 구분된다. 인접 행렬은 정점 사이의 관계를 나타내며, n개의 정점이 있을 때 nxn 행렬로 표현되고, 정점이 연결되어 있으면 1, 그렇지 않으면 0으로 표시된다. 근접 행렬은 정점과 변의 관계를 나타내며, n x m 행렬로써, 변이 연결되어 있으면 1로, 그렇지 않으면 0으로 표현한다. 변에 가중치가 있는 경우, 인접 행렬의 요소들은 0과 1 대신 가중치 값으로 구성할 수 있다. 그래프를 행렬로 표현하면 표 형식으로 변경이 용이하며, 표 형식의 값을 가중 그래프처럼 변환해 히트 맵으로 표현할 수도 있다. 이는 가중 그래프를 이용한 네트워크 분석에서 유용하다.

트리 구조 그래프는 여러 개의 정점이 있을 때 시작 정점에서 출발점으로 돌아오는 유일한 경로가 존재하는 그래프를 의미한다. 그러한 시작 정점이 막다른 정점인 경우 그 정점을 루트(Root)라 한다. 의사 결정 트리는 통계 모델 예측을 위한 조건 분기에 트리 구조를 사용하며, 탐색 트리는 상태를 나누는 수단으로 트리 구조를 활용하는 방식을 말한다.

그래프 이론과 트리 구조는 데이터 구조와 알고리즘의 기초를 이루며, 컴퓨터 과학 및 데이터 분석 및 인공지능 분야에서 아주 중요한 개념으로 자리 잡고 있다. 이를 통해 복잡한 데이터와 과정들을 시각적으로나 수학적으로 이해하는 데 큰 도움을 주고 있다.