Graph

 

그래프란 두 개의 유한 집합, 즉 정점 (vertex) 들의 집합 과 간선 (edge) 들의 집합 으로 이루어지는 구조를 말한다. 여기서 각 간선은 집합 V 에 있는 정점들의 쌍이며, 예를 들어, 간선

    

는 정점 로부터 정점 로의 간선이 된다. 이 경우 간선 를 기준으로 했을 때는 진출 간선 (outgoing edge) 이라 하며, 를 기준으로 했을 때는 진입 간선 (incoming edge) 이라 한다. 이와 같은 구조는 각 간선에 방향 (예를 들어, 로부터 로) 을 지정하므로 유향 그래프 (directed graph, digraph) 라 한다. 그래프를 구성하는 요소, 즉 정점이나 간선에 라벨 (label) 을 지정할 수 있으며, 이러한 그래프를 라벨 그래프 (labeled graph) 라 한다. 이러한 라벨은 특별한 이름이나 또는 다른 정보일 수도 있다.

그래프는 다이어그램으로 편리하게 도식화할 수 있다. 여기서 정점은 원으로, 그리고 간선은 두 정점들을 잇는 화살로 표현된다. 예를 들어, 정점들의 집합이 이고 간선들의 집합이 인 그래프는 다음 그림과 같이 그려질 수 있다. ....... (Peter Linz 2001)

 

Term :

그래프 이론 (Graph Theory)

Site :

그래프이론 용어사전 : 서울대

Wikipedia : Graph (Mathematics)

그래프의 개요 : 전북대 박순철 교수님 동영상

Paper :

그래프 관련 용어 (Graph Notation) : Nils J.Nilsson

그래프와 트리 : Peter Linz 

경로와 사이클 (Paths and Cycles) : Richard Johnsonbaugh