그래프 용어

G : 그래프
V : 정점(vertex)
E : 간선(edge), 연결선. 정점을 연결하는 선. V x V의 부분집합.
G = (V,E)
V(G) = 그래프 G를 구성하는 정점들의 집합.
E(G) = 그래프 G를 구성하는 연결선들의 집합.

무방향 그래프(undirected graph)
쌍방통행이 가능한 그래프.
즉, 방향성이 없는 선이다. 고로 (v1, v2) = (v2, v1)

방향 그래프(directed graph)
일방통햄만이 가능한 그래프
즉, 방향성이 있는 선. 고로 (v1, v2) ≠ (v2, v1)
방향 그래프에서 정점의 쌍은 <v1, v2>로 표시한다. 이 때 v1을 꼬리(tail)이라 한고 v2를 머리(head)라 한다.

제한 사항>
1. 자기 자신을 향하는 연결선은 없다.(no self loop)
2. 중복된 연결선은 허용하지 않느다. (no multigraph)

관련 용어>
 
완전그래프(complete graph)
그래프에서 연결선의 수가 최대인 그래프. 즉, 모든 정점이 인접한 그래프.
ex>정점이 3개이면 간선의 최대 갯수는 3개. 이런식으로.. 
무방향그래프, n개의 정점 -> 최대 연결선의 수 = n(n-1) / 2
방향그래프, n개의 정점 -> 최대  연결선의 수 = n(n-1)

인접(adjacent)
그래프 G에서 정점 a, b에 대하여  연결선(a, b)가 있으면 정점 a는 정점 b에 인접한다고 한다.

교차, 부속(incident)
그래프 G에서 정점 a, b에 대하여  연결선(a, b)가 있으면 간선 (a, b)는 정점 a와 정점 b에 부속한다고 한다.

경로(path)
그래프 G에서 정 a에서 b까지 이르는 정점들의 순서. 경로상의 연결선의 수를 경로의 길이(length)라 한다.
경로는 다양할 수 있다.

단순경로(simple path)
경로상의 정점들 중 첫번째와 마지막 정점을 제외한 정점들이 서로 다를 때의 경로.
ex> 경로 ABC는 단순경로이지만 경로 ABCBCBC는 단순경로라 할 수 없다.

사이클(cycle)
처음 정점과 마직막 정점이 같은 단순경로이다.
ex> 경로 ABCDA는 사이클

차수(degree)
그래프 G(V,E)에서 한 정점에 교차된 연결선들의 수.
ex> (a,b), (a,c), (a,d) 3개의 연결선이 있으면 이 3개의 연결선들은 a에 교차한다. 고로 a의 차수는 3이다.

진입차수(InDegree)
방향성 그래프에서 한 정점으로 들어오는 연결선의 갯수. 즉, 어떤 정점을 머리(head)로 하는 연결선의 갯수이다.

진출차수(OutDegree)
방향성 그래프에서 한 정점에서 나가는 연결선의 갯수. 즉, 어떤 정점을 꼬리(tail)로 하는 연결선의 갯수이다.

연결(connected)
무방향 그래프에서 임의의 두 정점 a, b 사이에 경로가 존재하면 두 정점 a, b는 연결되 있다.

서브 그래프(subgraph)
그래프 G와 G'가 있을 때  G'의 모든 정점과 연결선들이 G에 포함 될 때  G'를 G의 서브그래프라 한다.

연결요소,연결성분(connected component)
한 그래프내에서 최대로 연결되어 있는 서브 그래프를 연결요소라한다.
즉, 한 그래프내에서 뭉텅이들을 연결성분,요소라 한다. 

연결그래프(connected garph) <-> 단절그래프(disconnected graph)
그래프 G에 속하는 모든 정점들이 연결되어 있어서 임의의 두 정점에 대한 경로가 존재할 때, 이 그래프를 연결그래프라 한다. 
반대로 정점들이 연결되 있지 않으면 단절그래프.

강력 연결 그래프(strongly connected graph)
모든 정점들의 자신을 제외한 다른 정점들에게서부터 방향성을 가진 연결선을 주고 받는 그래프.
즉, 그래프 G의 정점의 갯수가 n일 때 임의의 정점의 진입차수와 진출차수는 n-1이 되겠다.