수학의 그래프 이론 분야에서 그래프 번호매김(영어: graph labeling)은 전통적으로 정수로 표현되는 라벨(label)을 그래프의 꼭짓점(vertex)이나 모서리(edge), 또는 둘 모두에 할당하는 것을 말한다. 공식적으로 그래프 $G = (V, E)$가 주어졌을 때, 꼭짓점 번호매김(vertex labeling)은 $V$에서 라벨의 집합으로 가는 함수이며, 이 함수가 정의된 그래프는 꼭짓점-라벨 그래프(vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(edge labeling)은 $E$에서 라벨의 집합으로 가는 함수이며, 이 경우 그래프는 모서리-라벨 그래프(edge-labeled graph)라고 부른다. 모서리 라벨이 순서 집합(예: 실수)의 원소라면 이 그래프는 가중 그래프(weighted graph)라고 부른다.
별도의 조건 없이 사용될 경우, 라벨 그래프(labeled graph)는 일반적으로 모든 라벨이 서로 다른 꼭짓점 라벨 그래프를 가리킨다. 이러한 그래프는 연속하는 정수 ${1, \dots, |V|}$로 번호매김할 수 있으며, 여기서 $|V|$는 그래프의 꼭짓점 개수이다. 많은 응용에서 모서리나 꼭짓점은 정의역과 관련된 의미 있는 라벨을 가지며, 예를 들어 모서리에 인접한 꼭짓점 사이를 이동할 때 드는 비용을 나타내는 가중치를 부여할 수 있다.
역사
대부분의 그래프 번호매김 연구는 1967년에 발표된 알렉스 로사(Alex Rosa)의 논문에 기원을 두고 있다. 로사는 세 종류의 번호매김을 규정했고, 각각 α-, β-, ρ-번호매김이라고 이름 붙였다. β-번호매김은 이후 솔로몬 W. 골롬(Solomon W. Golomb)에 의해 'graceful'이라는 이름이 다시 붙여졌으며, 이 이름이 현재 더 널리 알려져 있다.
Graceful 번호매김
그래프의 꼭짓점을 0에서 그래프의 크기 $|E|$까지 번호 매겼을 때, 이 번호가 모서리에 1부터 $|E|$까지의 번호매김을 유도하면 graceful하다고 한다. 구체적으로, 모든 모서리 $e$에 대해, $e$의 번호는 $e$에 연결된 두 꼭짓점 번호의 차이의 절댓값으로 정의된다. 즉, 그래프 $G = (V, E)$에서 꼭짓점 집합에서 ${0, 1, \dots, |E|}$로 가는 단사함수가 존재하여, 각 모서리의 양 끝 꼭짓점 번호의 차가 ${1, \dots, |E|}$의 전단사 함수를 이룰 때 graceful 그래프라고 한다.
로사는 크기가 1 또는 2 (mod 4)인 모든 오일러 그래프는 graceful이 아니라는 것을 증명했다. 특정 그래프족이 graceful인지 아닌지는 그래프 이론에서 광범위하게 연구되는 영역이다. 그래프 번호매김 분야의 가장 중요한 미증명 추측으로는 Ringel–Kotzig 추측, 즉 모든 트리(tree)가 graceful이라는 가설이 있다. 이 가설은 경로 그래프, 애벌레 트리(caterpillar tree) 및 다른 많은 무한한 트리 그래프족에 대해서는 증명되었으나, 일반적인 경우는 아직 미해결 상태이다.
