Graph

용어

• 정점(Vertex, Node): 그래프의 노드
• 간선(Edge): 그래프의 노드를 연결하는 선
  • 방향 (화살표)
    • 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프
    • 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프
  • 값
    • 가중치(Weight): 간선에 부여된 값

정의

그래프(Graph)

그래프(graph) $G$는 정점(vertex)의 집합 $V$와 간선(edge)의 집합 $E$로 구성된다.

$$G\equiv (V,E)$$

• $\equiv$은 동등한 관계, 즉, 특정 개념을 정의할 때 많이 사용한다.
• $=$은 값이 같음을, $\equiv$은 해당 개념의 정의 우측과 같음을 의미한다. 해당 의미를 강조한다.

Vertex

$$V=\{v_1,v_2,\cdots ,v_n\}$$

Edge

$e\in E,v_1,v_2\in V$일 때, 간선 $e$는 다음과 같이 정의된다.

$$e=\{v_1,v_2\}$$

• $v_1,v_2$는 각각 간선 $e$의 끝점(Endpoint)이라 부른다.
• $v_1,v_2$는 서로 인접한다(adjacent), 이웃한다(neighbors)라고 한다.
• $e$는 $v_1$과 $v_2$를 붙어있다(incident), 연결한다(connected)라고 한다.

방향 그래프(Directed Graph)

• 위 그래프의 정의에서 $e$에 대한 정의를 아래와 같이 바꾼 것을 말한다.

$$e=(v_1,v_2)$$

• 이전에 간선의 정의가 집합이었다면, 이제는 순서쌍이다.
• $e$는 방향변(Directed Edge, arc)라 부른다.
• $v_1$은 시점(Start), $v_2$는 종점(End)이라 부른다.

다중 그래프(Multigraph)

두 정점 사이에 여러 간선이 존재할 수 있는 그래프

$$G\equiv (V,E,\varphi )$$

다중 그래프 $G$는 정점의 집합 $V$, 간선의 집합 $E$, 간선의 함수 $\varphi$로 구성된다.

$$\varphi :E\to S^2(V)$$ $$S^2(V)=\{u,v\}|u,v\in V$$

• 이전에는 $E$가 간선의 집합이었지만, 이제는 간선의 집합을 정의하는 함수 $\varphi$가 추가되었다.
• 대신 함수를 통해 이를 계산한다.
• $\varphi (e)$는, 간선과 이 간선이 가지는 끝점을 사상하는 함수이다.
• 공역 $S^2(V)$는 특정 집합내의 부분집합 중, 원소의 개수를 2개를 가지는 집합이다.
• 최종적으로 간선과 끝점의 관계는 아래와 같이 표현된다.

$$\varphi (e)=\{v_1,v_2\}$$

유향 다중 그래프(Directed Multigraph)

사상하는 함수의 공역이 원소개수가 2개인 집합족이 아닌, 순서쌍으로 정의하면 된다.

$$\varphi :E\to V^2$$ $$V\times V=\{(u,v)|u,v\in V\}$$

가중 그래프(Weighted Graph)

간선에 가중치가 부여된 그래프

$$G\equiv (V,E,W)$$ $$W:E\to \mathbb{R}$$

• 간선에 대응되는 값을 계산하는 함수가 추가되었다.

특수한 그래프

완전 그래프(Complete Graph)

• 모든 정점이 서로 인접한 그래프
• 꼭짓점이 $n$개인 경우 $K_n$이라고 표현한다.
• 고등학교때 배운 특정 다각형의 모든 대각을 이은 모양이라 생각하면 되겠다.
• $K_n$은 $n$개의 정점과 $\frac{n(n-1)}{2}$개의 간선을 가진다.

$$K_n\equiv (V,E)$$

사이클 그래프(Cycle Graph)

• 간선이 모두 하나의 사이클을 이루는 그래프
• 정점이 $n$개인 경우 $C_n$이라고 표현한다.
• $C_n$은 $n$개의 정점과 $n$개의 간선을 가진다.

$$E=\{v_1{v}_2,v_2{v}_3,\cdots ,v_{n-1}{v}_n,v_n{v}_1\}$$

트리(Tree)

• 사이클이 없는 연결 그래프
• $n$개의 정점을 가지는 트리는 $n-1$개의 간선을 가진다.