용어사전

[ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ]


adjacent (인접)
두 개의 꼭지점들이 이웃하고 있다는 것은 그것들이 변으로 연결되어있다는 것을 의미한다. 두 개의 변들이 이웃하고 있다는 것은 그것들이 한 끝점을 공유하고 있다는 것을 의미한다.

arc (유향변)
방향이 있는 변을 말한다. [참조: graph].

articulation point (절단점)
[참조: cut vertices].

bipartite (이분) [graph]
어떤 그래프가 bipartite라는 것은 그것의 각 변이 한 끝점은 U에 다른 끝점은 V에 갖도록 그것의 꼭지점들의 집합이 원소를 공유하지 않는 두 개의 집합 U와 V로 이분될 수 있다는 것을 의미한다. bipartite graph를 이분그래프라 부르고 (U, V)를 그것의 bipartition(이분 분할)이라 부른다. 이분 그래프가 complete bipartite graph (완전 이분 그래프)라는 것은 그것의 이분 분할이 (U,V)일 때, U의 각 꼭지점들이 V의 모든 꼭지점들과 이웃하고 있음을 의미한다. U가 m개의 원소를 V가 n개의 원소를 가지고 있는 완전 이분 그래프를 Km,n으로 표시한다. K3,3는 옆의 그림과 같다. [참조: complete graphcut vertices].

chromatic number (착색수) [graph]
그래프의 착색수란 그것의 꼭지점들을 서로 인접(adjacent)하는 것들은 다른 색을 갖도록 칠할 때 필요한 색의 수 중 최소값을 의미한다. 예를 들어 옆의 그래프의 착색수는 3이다.
   지도에 대하여서도 이 착색수의 개념이 도입될 수 있는데, 지도를 그릴 때 국경을 접하고 있는 나라는 다른 색을 칠하도록 하는chromatic number (착색수) 데 필요한 최소색깔수를 의미한다. [참조: Four Color Theorem]

circuit (회로)
회로란 닫힌 path (경로)이다. (따라서 loop (고리) 란 길이가 1인 회로이다).

closed (닫혀진)

closed walk (닫혀진 워크)
닫혀진 워크란 시작점과 종착점이 같은 워크(walk)를 말한다. 닫혀진 트레일(closed trail)이란 시작점과 종착점이 같은 트레일(trail)을 말한다. [참조: walk 및 trail].

complete graph (완전그래프)
어떤 두 꼭지점도 이웃하는 단순 그래프(simple graph)를 완전그래프라 하며, n개의 꼭지점을 가지는 완전 그래프는 Kn으로 나타낸다. 꼭지점의 수가 1, 2, 3, 4, 5개인 완전 그래프들은 다음과 같다: [1 2 3 4 5]

component (성분)
[참조: connected (연결된)].

connected (연결된)
어떤 그래프가 연결되어 있다는 것은 어떤 두 개의 꼭지점도 그것들을 양끝점으로 하는 경로(path)가 존재함을 의미한다. 연결되어 있지 않은 그래프는 두 개 이상의 연결된 성분(component) 또는 서로 공통 부분이 없는 두 개 이상의 연결된 부분그래프(subgraph)로 나뉘어 있다. 예를 들어 옆의 그래프는 3개의 연결된 성분들로 이루어져 있다.

cut vertex (절단점)
어떤 그래프의 절단점이란 그것이 그 그래프로부터 제거되었을 때 (꼭지점이 그래프에서 제거된다는 것은 꼭지점과 그것에 입사하는(incident) 변들을 지운다는 것을 의미) 생기는 그래프의 성분(component)의 수가 원래보다 적어도 하나 더 늘어나게 되는 꼭지점을 말한다. [참조: connected (연결된)].

cycle (회로)
회로는 시작점과 종착점 외에는 어떤 꼭지점도 반복되지 않는 닫혀진 트레일(closed trail)을 의미한다.

degree (차수) [graph]
그래프에서 꼭지점의 차수란 그 꼭지점을 끝점으로 가지는 변의 수를 의미한다. 이 때 고리(loop)는 두 번 세어 준다. valence라고도 한다. 예를 들어, 이 그래프에서는 모든 꼭지점들이 차수를 3으로 갖는다. 유향그래프(digraph) 에서는 차수의 개념이 내차수(in-degree)외차수(out-degree) 로 나뉘어 진다. (각 꼭지점의 내차수와 외차수를 모두 더하면 그 유향그래프의 방향을 무시하여 생기는 그래프의 각 꼭지점의 차수와 같다.)

digraph (유향그래프) [GRAPH]
유향그래프란 그것의 각 변이 방향을 갖고 있는 그래프를 의미한다. 좀 더 정확히 정의하면 유향그래프란 V라는 유한 집합과 원소들이 V의 원소들로 이루어진 순서쌍들인 집합 A로 이루어진 순서쌍 (V,A)를 의미한다. V의 원소들을 꼭지점(vertex)이라 부르고 A의 원소들을 유향변(arc)이라고 부른다. 유향변 (a,b)이 주어졌을 때 a를 그 유향변의 시작점(initial vertex), b를 종착점(terminal vertex)이라고 부른다.

directed graph (유향그래프)
[참조: digraph]

edge (변)
[참조: graph]

Four Color Theorem (4색 문제)
모든 planar (평면) graph 의 chromatics number (착색수) 가 4이하라고 주장하는 문제이다.

graph
쉽게 이야기하면 변(edge)이라고 불리는 것들에 의하여 연결된 꼭지점들의 유한 집합이다. 좀 더 정확히 정의하면, 단순 그래프(simple graph)란 V라는 꼭지점의 집합과 V의 서로 다른 두 원소로 이루어진 집합들의 집합 E로 이루어진 순서쌍 (V,E)를 의미한다.
   모든 그래프가 다 단순 그래프는 아니다. 때때로 두 개의 꼭지점들이 여러 개의 변들(multiple edges)로 연결될 수도 있고, 한 꼭지점이 자기 자신과 고리(loop)라는 변에 의하여 연결될 수도 있다. 경우에 따라서 그래프를 multigraph (멀티그래프)로 단순 그래프를 그래프(graph)로 부를 때도 있다. 그래프의 각 변에 방향을 줄 수 있는데 이렇게 하여 생긴 그래프를 유향그래프(digraph 또는 directed graph)라고 부른다.

in-degree (내차수)
어떤 꼭지점 v의 내차수란 v를 종착점으로 가지는 유향변(arc)의 개수를 말한다. [참조: digraphdegree]

initial vertex (시작점)
[참조: digraph]

isolated (분리된)
차수 (degree)가 0인 꼭지점, 즉 변의 끝도 아닌 꼭지점을 분리되었다고 한다.

Kuratowski's Theorem (정리)
그래프가 평면그래프가 아니라는 것과 그것이 K3,3 또는 K5와 동상인(homeomorphic) 부분그래프를 포함하는 것은 서로 동치이다.

length (길이)
[참조: 경로(path)의 길이 path].

loop (고리)
고리란 양끝점이 같은 변을 의미한다. [참조: degree(차수)에 대한 설명중 고리를 3개 가진 그래프에 대한 예를 보시오].

multigraph (멀티그래프)
쉽게 이야기하면 멀티그래프는 두 개의 꼭지점사이에 여러개의 변이 있는 그래프를 의미한다. 좀더 정확하게 정의하면, 멀티그래프는 V라고 하는 꼭지점들의 집합과 변들의 집합인 E, 그리고 E로부터 V에 있는 꼭지점들의 순서쌍의 집합({{u,v}|u,v in V; uv })으로의 함수 f로 이루어져 있다. 여기에서 함수 f는 변의 양끝점을 제시한다. 만약, 두 개의 변 r과 s의 함수값이 같다면, 즉 f(r)=f(s)이면, 우리는 r과 s는 평행하다라고 하거나 multiple edges라고 한다. [참조: graph와 pseudograph]

multiple edge (다중변)
[참조: multigraph (다중그래프)]

node (노드)
vertex (꼭지점)과 깉은 말이다. [참조: graph]

out-degree (외차수)
어떤 꼭지점v의 외차수란 시작점을 v로 하는 유향변(arc)의 개수를 말한다. [참조: digraph (유향그래프) 와

parallel edge (평행변)
[참조: multigraph]. [path]

path, walk, trail, cycle (한국 고교 교과서에서는 경로=trail 로 정의한다)
 
A trail is a special type of walk, which is stricter in the transition of edges than a walk. A trail is allowed to traverse only once for each edge. However, a trail is still allowed to traverse multiple times for the same vertex.
 
A path is a walk with no repeated vertexes, which is stricter than a trail to disallow an edge or a vertex to be traversed multiple times.
 
A walk is closed if the initial vertex is also the terminal vertex. A cycle is a closed trail with at least one edge and with no repeated vertices except that the initial vertex is the terminal vertex. A path in general is not closed; its origin and terminus are different.
 
A cycle of length k is called a k-cycle. If k is even, the cycle is called even cycle; otherwise, the cycle is called odd cycle.  [참조: walk]

pendant (펜던트)
degree (차수)가 1인 꼭지점을 펜던트 꼭지점이라 한다.

planar (평면)
어떤 그래프를 평면 위에 꼭지점에서만 교차하도록 그릴 수 있으면 평면 그래프(planar graph)라 한다. 예를 들면, K4는 평면 그래프이다.

pseudograph (가그래프)
쉽게 이야기하면 가그래프는 다중변이나 고리를 가지고 있는 그래프이다. 정확하게 정의하면 가 그래프는 꼭지점들의 집합인 V와 변들의 집합인 E, 그리고 E에서 집합 { {u,v} | u,v in V } 으로의 함수 f로 이루어져 있다. 여기에서 함수 f는 변의 양끝점을 제시한다. [참고: graphmultigraph]

terminal vertex (도착점)
[참고: digraph]

trail(트레일)
변이 중복되지 않는 워크(walk)를 말한다. [참고: walk]

undirected edge
보통의 graph를 말한다.

valence (차수)
[참고: degree]

vertex (꼭지점)
[참고: graph].

walk (워크)
꼭지점과 변이 교대로 나타나는 열이면서, 각 변의 앞과 뒤에 위치한 꼭지점을 그 변의 양끝점으로 갖는 열을 말한다.