그래프 라벨링

그래프 이론의 수학적인 분야에서, 그래프 라벨링은 전통적으로 정수로 표현되는 라벨을 그래프의 가장자리 및/또는 정점에 할당하는 것이다.^[1]

정식으로 그래프 $G{\displaystyle }$=${\displaystyle }$(${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle G=(V,E)}$을$($를) 지정하면, 정점 레이블 표시는 레이블 집합에 $대한$ V ${\displaystyle V}$의 함수로서, 이러한 함수가 정의된 그래프를 정점 레이블 그래프라고 한다.마찬가지로 에지 라벨 표시는 라벨 집합에 $대한$ E ${\displaystyle E}$의 함수다.이 경우 그래프를 가장자리 레이블 그래프라고 한다.

모서리 라벨이 순서 집합의 멤버인 경우(예: 실제 숫자) 가중 그래프라고 할 수 있다.

자격 없이 사용할 경우 일반적으로 라벨이 표시된 그래프라는 용어는 모든 라벨이 구별되는 정점 라벨이 표시된 그래프를 가리킨다.이러한 그래프는 연속된${\displaystyle \mathrm{정수}\{1,}$. .${\displaystyle }$. . . . . . . . . . . . . . . . . ${\displaystyle \{1$, $..., V$$\}$에 의해 동등하게 레이블이 표시될 수 있으며, ${\displaystyle 여기}$서 V $displaystyle V}$는 그래프에서 정점 수입니다.^[1]많은 응용 프로그램의 경우, 가장자리 또는 꼭지점에는 관련 도메인에서 의미 있는 레이블이 지정된다.예를 들어, 가장자리에는 입사 정점들 사이를 가로지르는 "비용"을 나타내는 가중치가 할당될 수 있다.^[2]

위의 정의에서 그래프는 유한한 간접적인 단순 그래프로 이해된다.그러나 라벨 표시의 개념은 그래프의 모든 확장 및 일반화에 적용될 수 있다.예를 들어 오토마타 이론과 공식 언어 이론에서는 라벨이 붙은 다중 글씨를 고려하는 것이 편리하다. 즉, 한 쌍의 꼭지점이 라벨이 붙은 여러 가장자리로 연결될 수 있다.^[3]

역사

대부분의 그래프 연구들은 알렉산더 로사가 1967년 논문에서 제시한 연구 결과에서 기원을 추적한다.^[4]로사는 세 가지 유형의 라벨링(labelling)을 확인했는데, 이를 α, β-, lab-라벨링(labelling)이라고 불렀다.^[5]β-라벨링은 나중에 솔로몬 골롬에 의해 "그레이스풀"로 개칭되었고, 그 이후부터 그 이름이 유행하고 있다.

특례

우아한 라벨 표시

그래프는 그 정점이 그래프 크기인 0부터 E까지 라벨이 붙어 있을 때 우아하다고 알려져 있으며, 이 라벨 표시는 1에서 E까지 라벨 표시를 유도한다. 어떤 에지 e에 대해서도, e의 라벨은 e와 관련된 두 정점 사이의 양의 차이다.즉, e가 i와 j라는 정점을 가진 사건인 경우 e는 i - j로 표시된다. 따라서, E로부터 E까지의 양의 정수로의 편차를 유도하는 주사가 존재하는 경우에만 그래프 G = (V, E)는 우아하다.

로사는 원문에서 크기가 1이나 2(모드 4)에 해당하는 오일러 그래프는 모두 우아하지 않다는 것을 증명했다.그래프의 특정 집단이 우아한지 여부는 광범위한 연구 아래 그래프 이론의 한 영역이다.거의 틀림없이, 그래프 라벨 표시에서 증명되지 않은 가장 큰 추측은 모든 나무가 우아하다는 가설을 세운 링겔-코치히 추측이다.이것은 모든 길, 애벌레, 그리고 많은 다른 무한한 나무의 가족들에게 증명되었다.안톤 코치히 자신도 그 추측을 증명하려는 노력을 "병"이라고 불렀다.^[6]

가장자리-그레이스 라벨 표시

p 꼭지점과 q 가장자리의 루프나 다중 가장자리가 없는 단순 그래프에 가장자리 표시는 {1, …, q}의 뚜렷한 정수로 가장자리를 표시하여 모듈로 p를 찍은 입사 가장자리의 합계가 0에서 p - 1까지의 모든 값을 정점에 할당하도록 한다.그래프 G는 가장자리 그레이스 라벨 표시를 인정할 경우 "가장자리 그레이스"라고 한다.

가장자리 좋은 노력은 1985년 성핑 로에 의해 처음 소개되었다.^[7]

그래프가 가장자리 그레이스가 되는 데 필요한 조건은 "Lo's condition"이다.

조화 라벨 표시

그래프 G의 "조화 라벨링"은 G의 꼭지점에서 정수 modulo k 그룹에 대한 주입으로, 여기서 k는 G의 가장자리 수로서 가장자리(x, y)를 두 꼭지점 x y(mod k)의 라벨의 합으로 취함으로써 G의 가장자리와 숫자 modulo k 사이의 편차를 유도한다."화합 그래프"는 조화로운 라벨 표시를 가진 그래프다.피터슨 그래프처럼 홀수 사이클은 조화롭다.꼭지점 라벨을 한 개만 재사용할 수 있게 하면 나무가 모두 조화롭다는 추측이다.^[8]7페이지 분량의 책 그래프 K_1,7 × K는₂ 조화롭지 않은 그래프의 예를 제공한다.^[9]

그래프 착색

그래프 착색은 그래프 실습의 하위 클래스다.정점 색상은 인접한 정점에 다른 라벨을 할당하는 반면, 가장자리 색상은 인접한 가장자리에 다른 라벨을 할당한다.^[10]

행운의 라벨 표시

그래프 G의 행운의 라벨 표시는 S(v)가 v의 이웃에 있는 라벨의 합을 나타내는 경우 S는 G의 정점 색상으로 G의 정점에 대한 양의 정수의 할당이다.G의 "행운의 숫자"는 G가 정수$\{{\displaystyle 1}$,${\displaystyle }$…,${\displaystyle }$k${\displaystyle }$} ${\displaystyle$\{$1,\ldots,k\}}$를 가진 행운의 라벨 표시를 할 수 있는 최소 k이다$.$^[11]

참조