꼭짓점 (그래프 이론)

수학에서, 구체적으로 그래프 이론에서 꼭짓점, 정점, 버텍스(vertex), 노드(node)는 그래프 구성에 필수적인 단위이다: 무향 그래프에는 꼭짓점의 집합과 간선의 집합(순서가 없는 꼭짓점의 쌍)으로 구성되는 한편 유향 그래프는 꼭짓점의 집합과 아크(arc)의 집합(순서가 있는 꼭짓점의 쌍)으로 구성된다. 그래프 다이어그램에서 꼭짓점은 일반적으로 레이블이 있는 원으로 표현되며 간선은 한 꼭짓점에서 다른 꼭짓점으로 확장하는 선이나 화살표로 표현된다.

6개의 꼭짓점과 7개의 간선이 있는 그래프. 여기에서 맨 왼쪽의 꼭짓점 숫자 6은 리프 버텍스(leaf vertex) 또는 펜던트 버텍스(pendant vertex)이다.

그래프 이론의 관점에서 꼭짓점은 기능이 없는 불가분의 객체로 취급되지만 그래프가 발생하는 상황에 따라 추가적인 구조를 갖고 있을 수 있다: 이를테면 시맨틱 네트워크는 꼭짓점이 개념이나 객체의 종류를 나타내는 그래프이다.

간선을 구성하는 2개의 꼭짓점은 이 간선의 종점(endpoint)이라고 이야기되며 간선은 꼭짓점에 대한 사건으로 언급된다. 그래프에 간선(v, w)이 포함되어 있다면 꼭짓점 w는 다른 꼭짓점에 인접(adjacent)하다고 이야기된다. 꼭짓점 v의 이웃은 그래프의 유도 부그래프이며 v에 인접한 모든 꼭짓점에 의해 형성된다.

같이 보기

각주

Gallo, Giorgio; Pallotino, Stefano (1988). “Shortest path algorithms”. 《Annals of Operations Research》 13 (1): 1–79. doi:10.1007/BF02288320.
Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
Chartrand, Gary (1985). 《Introductory graph theory》. New York: Dover. ISBN 0-486-24775-9.
Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). 《Graph theory, 1736-1936》. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
Harary, Frank (1969). 《Graph theory》. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
Harary, Frank; Palmer, Edgar M. (1973). 《Graphical enumeration》. New York, Academic Press. ISBN 0-12-324245-2.

외부 링크

Weisstein, Eric Wolfgang. “Graph Vertex”. 《Wolfram MathWorld》 (영어). Wolfram Research.