용어사전

[ 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 (이분): 어떤 그래프가 bipartite라는 것은 그것의 각 변이 한 끝점은 U에 다른 끝점은 V에 갖도록 그것의 꼭지점들의 집합이 원소를 공유하지 않는 두 개의 집합 U와 V로 이분될 수 있다는 것을 의미한다. bipartite graph를 이분그래프라 부르고 (U, V)를 그것의 bipartition(이분 분할)이라 부른다. 이분 그래프가 complete bipartite graph (완전 이분 그래프)라는 것은 그것의 이분 분할이 (U,V)일 때, U의 각 꼭지점들이 V의 모든 꼭지점들과 이웃하고 있음을 의미한다. U가 m개의 원소를 V가 n개의 원소를 가지고 있는 완전 이분 그래프를 K_m,n으로 표시한다. K_3,3는 옆의 그림과 같다. [참조: complete graph 및 cut vertices].
chromatic number (착색수): 그래프의 착색수란 그것의 꼭지점들을 서로 인접(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개의 꼭지점을 가지는 완전 그래프는 K_n으로 나타낸다. 꼭지점의 수가 1, 2, 3, 4, 5개인 완전 그래프들은 다음과 같다:
component (성분): [참조: connected (연결된)].
connected (연결된): 어떤 그래프가 연결되어 있다는 것은 어떤 두 개의 꼭지점도 그것들을 양끝점으로 하는 경로(path)가 존재함을 의미한다. 연결되어 있지 않은 그래프는 두 개 이상의 연결된 성분(component) 또는 서로 공통 부분이 없는 두 개 이상의 연결된 부분그래프(subgraph)로 나뉘어 있다. 예를 들어 옆의 그래프는 3개의 연결된 성분들로 이루어져 있다.
cut vertex (절단점): 어떤 그래프의 절단점이란 그것이 그 그래프로부터 제거되었을 때 (꼭지점이 그래프에서 제거된다는 것은 꼭지점과 그것에 입사하는(incident) 변들을 지운다는 것을 의미) 생기는 그래프의 성분(component)의 수가 원래보다 적어도 하나 더 늘어나게 되는 꼭지점을 말한다. [참조: connected (연결된)].
cycle (회로): 회로는 시작점과 종착점 외에는 어떤 꼭지점도 반복되지 않는 닫혀진 트레일(closed trail)을 의미한다.
degree (차수): 그래프에서 꼭지점의 차수란 그 꼭지점을 끝점으로 가지는 변의 수를 의미한다. 이 때 고리(loop)는 두 번 세어 준다. valence라고도 한다. 예를 들어, 이 그래프에서는 모든 꼭지점들이 차수를 3으로 갖는다. 유향그래프(digraph) 에서는 차수의 개념이 내차수(in-degree)와 외차수(out-degree) 로 나뉘어 진다. (각 꼭지점의 내차수와 외차수를 모두 더하면 그 유향그래프의 방향을 무시하여 생기는 그래프의 각 꼭지점의 차수와 같다.)
digraph (유향그래프): 유향그래프란 그것의 각 변이 방향을 갖고 있는 그래프를 의미한다. 좀 더 정확히 정의하면 유향그래프란 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)의 개수를 말한다. [참조: digraph와 degree]
initial vertex (시작점): [참조: digraph]
isolated (분리된): 차수 (degree)가 0인 꼭지점, 즉 변의 끝도 아닌 꼭지점을 분리되었다고 한다.
Kuratowski's Theorem (정리): 그래프가 평면그래프가 아니라는 것과 그것이 K_3,3 또는 K₅와 동상인(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, 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)라 한다. 예를 들면, K₄는 평면 그래프이다.
pseudograph (가그래프): 쉽게 이야기하면 가그래프는 다중변이나 고리를 가지고 있는 그래프이다. 정확하게 정의하면 가 그래프는 꼭지점들의 집합인 V와 변들의 집합인 E, 그리고 E에서 집합 { {u,v} | u,v in V } 으로의 함수 f로 이루어져 있다. 여기에서 함수 f는 변의 양끝점을 제시한다. [참고: graph 및 multigraph]
terminal vertex (도착점): [참고: digraph]
trail(트레일): 변이 중복되지 않는 워크(walk)를 말한다. [참고: walk]
undirected edge: 보통의 graph를 말한다.
valence (차수): [참고: degree]
vertex (꼭지점): [참고: graph].
walk (워크): 꼭지점과 변이 교대로 나타나는 열이면서, 각 변의 앞과 뒤에 위치한 꼭지점을 그 변의 양끝점으로 갖는 열을 말한다.