그래프

개요

그래프는 점(Vertex)과 이음선(Edge)으로 이루어진 수학적 구조이다. 이를 형식화하면 다음과 같이 표현할 수 있다.

• G = (V, E)
• V = {v₁, v₂, v₃, ... , v_n}
• E = {(v_i, v_j), ... }

즉, 그래프는 점 집합과 이음선 집합의 순서쌍이다. 이음선 집합의 이음선은 V²의 부분집합이다. V², 즉 V×V는 집합론에서 교차곱(Cross Product) 또는 데카르트곱(Cartesian Product)이라고 불리는 연산의 결과물이다. 위와 같이 집합론의 기호들을 사용하여 표현된 그래프는 비교적 쉽게 행렬 표기로 바꿀 수 있다. 예를 들어, v_i와 v_j가 서로 연결되어 있을 경우, 그래프를 나타내는 행렬 G의 원소 G[i][j]는 1이며, 연결되어 있지 않을 경우 0이다.

특수한 그래프

방향 있는 그래프(directed graph)와 가중치 있는 그래프(weighted graph)가 있다. (편집중)