그래프 번호매김

수학의 그래프 이론 분야에서, 그래프 라벨링(영어: graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다.

공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 라벨링(영어: vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(영어: vertex-labeled graph)라고 부른다. 유사하게, 모서리 라벨링(영어: edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(영어: edge-labeled graph)라고 부른다.

모서리 라벨이 순서 집합(예,실수)의 원소라면, 이 그래프는 가중 그래프(영어: weighted graph)라고 부른다.

이것을 특정하지 않고 쓸 경우에는, 라벨 그래프(영어: labeled graph)는 일반적으로 모든 라벨이 다른 꼭짓점 라벨 그래프를 가리킨다. 그런 그래프는 동일하게 연속하는 정수 {1, …, |V|}로 라벨링 할 수 있으며, 이 때 |V|는 그래프의 꼭짓점의 갯수이다. 많은 적용에서, 모서리나 꼭짓점은 정의역과 관련이 있는 의미있는 라벨을 붙인다. 예를 들어, 모서리에 인접한 꼭짓점 사이를 이동할 때 드는 "비용"을 나타내는 가중치를 부여할 수 있다.

위의 정의에서 그래프는 유한 무향 단순 그래프로 이해된다. 하지만, 라벨링의 표기는 모든 그래프의 확장과 일반화에서 적용될 수 있다. 예를 들어, 오토마타 이론과 형식 언어 이론에서 이것은 라벨 다중 그래프로 보는 것이 편리하다. 즉, 꼭짓점 쌍은 일부 라벨이 붙은 모서리로 연결될 수 있다.

참고 문헌

• Rosa, A. (1967). 《On certain valuations of the vertices of a graph》. Theory of Graphs, Int. Symp. Rome July 1966. Gordon and Breach. 349–355쪽. Zbl 0193.53204. 
• Guy, Richard K. (2004). 《Unsolved problems in number theory》 3판. Springer-Verlag. C13. ISBN 0-387-20860-7. Zbl 1058.11001.