그래프 번호매김
수학의 그래프 이론 분야에서, 그래프 번호매김(영어: graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다.[1]
공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 번호매김(영어: vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(영어: vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(영어: edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(영어: edge-labeled graph)라고 부른다.
모서리 라벨이 순서 집합(예, 실수)의 원소라면, 이 그래프는 가중 그래프(영어: weighted graph)라고 부른다.
이것을 특정하지 않고 쓸 경우에는, 라벨 그래프(영어: labeled graph)는 일반적으로 모든 라벨이 다른 꼭짓점 라벨 그래프를 가리킨다. 그런 그래프는 동일하게 연속하는 정수 {1, …, |V|}로 번호매김 할 수 있으며, 이 때 |V|는 그래프의 꼭짓점의 개수이다.[1] 많은 적용에서, 모서리나 꼭짓점은 정의역과 관련이 있는 의미있는 라벨을 붙인다. 예를 들어, 모서리에 인접한 꼭짓점 사이를 이동할 때 드는 "비용"을 나타내는 가중치를 부여할 수 있다.[2]
위의 정의에서 그래프는 유한 무향 단순 그래프로 이해된다. 하지만, 번호매김의 표기는 모든 그래프의 확장과 일반화에서 적용될 수 있다. 예를 들어, 오토마타 이론과 형식 언어 이론에서 이것은 라벨 다중 그래프로 보는 것이 편리하다. 즉, 꼭짓점 쌍은 일부 라벨이 붙은 모서리로 연결될 수 있다.[3]
역사
[편집]대부분의 그래프 번호매김은 1967년에 발표된 알렉스 로사(Alex Rosa)의 논문의 번호매김에 기원을 두고 있다.[4] 로사는 세 종류의 번호매김을 규정했고, 각각 α-, β-, and ρ-번호매김이라고 이름 붙였다.[5] β-번호매김은 나중에 솔로몬 W. 골롬에 의해 graceful이라는 이름이 다시 붙여졌고 이 이름이 현재는 더 유명해졌다.
특별한 경우
[편집]Graceful 번호매김
[편집]
이 부분의 본문은 Graceful 번호매김입니다.
그래프의 꼭짓점을 0에서 그래프의 크기 |E|까지 번호 매겼고, 이 매긴 번호가 모서리에 1에서 |E|까지 번호매김을 유도하면 "graceful"이라고 한다. 모든 모서리 e에 대해서, e의 번호가 e에 연결된 두 꼭짓점의 번호의 차이다. 다른 말로, e가 i와 j의 번호가 붙은 꼭짓점을 연결하면, e는 |i − j|의 번호가 매겨질 것이다. 따라서, 그래프 G = (V, E)가 E에서 |E|까지 자연수로 가는 전단사 함수를 내포하는 단사함수가 존재하는 것은 그래프가 graceful이라는 것과 같다.
그의 원 논문에서, 로사는 크기가 1또는 2 (mod 4)인 모든 오일러 그래프는 graceful이 아니라는 것을 증명했다. 특정한 그래프족이 graceful인지 아닌지는 광범위한 연구의 그래프 이론의 영역이다. 당연히 그래프 번호매김의 가장 중요한 미증명 추측은 Ringel–Kotzig 추측으로 모든 트리가 graceful이라는 가설이다. 이 가설은 경로 그래프, 애벌레 트리, 그리고 다른 많은 무한한 트리 그래프족에 대해서 증명되었다. Kotzig 본인은 그 추측을 증명하려는 노력은 "질병"이라고 불렀다.[6]
각주
[편집]- ↑ 가 나 Weisstein, Eric Wolfgang. “Labeled graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- ↑ "Different Aspects of Coding Theory", by Robert Calderbank (1995) ISBN 0-8218-0379-4, p. 53"
- ↑ "Developments in Language Theory", Proc. 9th. Internat.Conf., 2005, ISBN 3-540-26546-5, p. 313
- ↑ Gallian, J. “A Dynamic Survey of Graph Labelings, 1996-2005”. The Electronic Journal of Combinatorics.
- ↑ Rosa, A. “On certain valuations of vertices in a graph”.
- ↑ Vietri, Andrea (2008). “Sailing towards, and then against, the graceful tree conjecture: some promiscuous results”. 《Bull. Inst. Comb. Appl.》 53: 31–46. ISSN 1183-1278. Zbl 1163.05007.
- 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.