8-1. 그래프의 개념

그래프 ($G = (V, E)$)

공집합이 이닌 정점(vertex, node)의 집합 $V$와 서로 다른 정점의 쌍($v_i, v_j$)를 연결하는 변(edge)의 집합 $E$로 구성된 구조

• 정점 $v_i$와 $v_j$는 서로 인접(adjacent)한다 : 정점 $v_i$와. $v_j$를 연경하는 변이 존재한다.
• 변 $e_k$는 정점 $v_i$와 $v_j$에 근접(incident)한다 : 변 $e_k$는 정점 $v_i$와 $v_j$를 연결한다.

단순그래프

그래프 $G = (V, E)$에서 임의의 두 정점 사이에 오직 하나의 변이 있는 그래프

다중그래프

그래프 $G = (V, E)$에서 임의의 두 정점 사이에 두 개 이상의 변이 있는 그래프

방향그래프 ($G = <V,E>$)

그래프를 구성하는 정점 사이에 순서가 존재하여 화살표를 이용해 순서대로 정점을 연결하여 표현하는 그래프

가중치그래프

그래프 $G = (V, E)$를 구성하는 각 변에 가중치가 부여된 그래프

• $W[v_i, v_j]$ : 두 정점 $v_i$와 $v_j$에 근접하는 변에 부여된 가중치 표기

차수 (degree : $d(v)$)

정점 $v$에 근접하는 변의 개수

• 외차수(out-degree : $d_{out}(v)$) : 정점 v를 시작점으로 하는 화살표의 개수 / 진출 차수
• 내차수(in-degree : $d_{in}(v)$) : 정점 $v$를 끝점으로 하는 화살표의 개수 / 진입 차수

8-2. 그래프의 종류