탐욕스러운 컬러링

서로 다른 꼭지점 순서를 사용하는 동일한 크라운 그래프의 탐욕스러운 두 가지 색상.오른쪽 예제는 n 정점이 있는 2색 그래프로 일반화되며, 여기서 탐욕스러운 알고리즘은 n/2 색상을 확장한다.

수학과 컴퓨터 과학의 그래프 색채 문제에 관한 연구에서는 탐욕스러운 색채나 순차 색채는^[1] 그래프의 정점을 순서대로 고려하고 각 정점에 사용 가능한 색상을 할당하는 탐욕스러운 알고리즘에 의해 형성된 그래프의 정점을 색칠하는 것이다.탐욕스러운 색상은 선형적인 시간에 찾을 수 있지만, 일반적으로 가능한 최소의 색상을 사용하지 않는다.

정점 순서의 다른 선택은 일반적으로 주어진 그래프의 다른 색상을 만들어 낼 것이다. 그래서 탐욕스러운 색채 연구의 많은 부분은 어떻게 좋은 순서를 찾을 것인가에 대해 걱정해 왔다.최적의 색상을 생성하는 순서가 항상 존재하지만, 그러한 순서는 많은 특별한 등급의 그래프에서 찾을 수 있지만, 그것들은 일반적으로 찾기 어렵다.정점 순서에 일반적으로 사용되는 전략에는 낮은 정점보다 높은 정점을 먼저 배치하거나, 제약을 덜 받는 정점보다 사용 가능한 색상이 적은 정점을 선택하는 것이 포함된다.

탐욕스러운 색상의 변형은 그래프의 미색 부분 구조를 전혀 알지 못한 채 온라인 방식으로 색상을 선택하거나, 총 색 수를 줄이기 위해 사용 가능한 첫 번째 색상이 아닌 다른 색상을 선택한다.탐욕스러운 컬러링 알고리즘은 스케줄링과 등록 문제, 콤비네이터 게임 분석, 브룩스의 컬러링과 학위와의 관계에 대한 정리 등 다른 수학적 결과의 입증에 적용됐다.탐욕스러운 색상에서 파생된 그래프 이론의 다른 개념은 그래프의 그룬디 수(탐욕스러운 색상으로 찾을 수 있는 가장 많은 색)와 모든 탐욕스러운 색상이 동일한 색수를 사용하는 그래프인 웰 컬러 그래프(well-coloring graph)가 있다.

알고리즘.

주어진 정점 순서에 대한 탐욕스러운 색상은 선형 시간으로 실행되는 알고리즘으로 계산할 수 있다.알고리즘은 주어진 순서에서 정점을 처리하여 처리될 때 각각의 순서에 색을 할당한다.색상은 숫자 $0{\displaystyle \mathrm{},}$ ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle }$… ${\displaystyle 0,$1, 2$,\dots }$로 나타낼 수 있으며$$, 각 꼭지점에는 인접국 중 한 곳에서 이미 사용하지 않은 가장 작은 숫자의 색상이 주어진다.사용 가능한 가장 작은 색상을 찾으려면 배열을 사용하여 각 색상의 인접 항목 수를 세고(또는 또는 인접 색의 집합을 나타내기 위해) 배열을 스캔하여 첫 번째 0의 색인을 찾을 수 있다.^[2]

Python에서 알고리즘은 다음과 같이 표현할 수 있다.

반항하다 first_available(color_list):     """주어진 색상 리스트에 없는 최소 음수가 아닌 정수를 반환한다."""     color_set = 세트(color_list)     수를 세다 = 0     하는 동안에 진실의:         만일 수를 세다 아닌 에 color_set:             돌아오다 수를 세다         수를 세다 += 1          반항하다 탐욕스러운_색깔(G, 주문):     """"""주어진 순서대로 G의 탐욕스러운 색채를 찾아라. G의 표현은 https://www.python.org/doc/essays/graphs/과 같다고 가정한다. in a node/vertex의 이웃을 "w in G[node]"로 반복할 수 있도록 허용. 반환 값은 사전 매핑 정점을 색상에 매핑하는 값이다."""     색을 칠하다 = 받아쓰게 하다()     을 위해 마디를 짓다 에 주문:         used_usour_message = [색을 칠하다[nbr] 을 위해 nbr 에 G[마디를 짓다]                                  만일 nbr 에 색을 칠하다]         색을 칠하다[마디를 짓다] = first_available(used_usour_message)     돌아오다 색을 칠하다 

그first_available서브루틴은 두 개의 루프를 실행하기 때문에 인수 목록의 길이에 비례하는 시간이 걸린다. 하나는 목록 자체에서 그리고 다른 하나는 같은 길이의 카운트 리스트에서 실행되기 때문이다.전체 색상 알고리즘의 시간은 이 서브루틴에 대한 호출에 의해 지배된다.그래프의 각 에지는 이러한 호출 중 하나에만 기여하며, 에지의 끝점에 대한 호출은 나중에 정점 순서에 있다.따라서, 인수의 길이의 합은 다음과 같다.first_available알고리즘의 총 시간은 그래프에 있는 가장자리 수에 비례한다.^[2]

동일한 색상을 생성하는 대안 알고리즘은 한 번에 한 색씩 각 색상의 정점 세트를 선택하는 것이다.^[3]이 방법에서 각 색상 클래스 $C{\displaystyle }$ ${\displaystyle C}$는 지정된 순서의 정점을 통해 스캔하여 선택된다$$.이 검색은 $C{\displaystyle }$ ${\displaystyle C}$에 인접 항목이 없는$$ 무색인 $꼭지점{\displaystyle }$ v ${\displaystyle v}$을(를) 발견하면$,$ $v{\displaystyle }$ ${\displaystyle v$}을(를) C ${\displaystystyle C}$에 추가한다$.$ 이러한 방식으로 $C{\displaystyle }$ ${\displaystyled되지$ 않은 정점 사이에 최대 독립 집합이 된다$$.알고리즘은 모든 정점이 색칠될 때까지 반복적으로 이런 방식으로 색상 클래스를 찾는다.단, 단 한 번의 스캔만 사용하는 위에서 설명한 방법 대신 각 색상 등급별로 한 번의 스캔으로 그래프를 여러 번 스캔하는 것이 포함된다.^[4]

주문 선택

그래프의 정점 순서가 다르면 탐욕스러운 색상은 최적의 색상 수에서 그래프에 정점 수에 비례하는 색상 수까지 다양한 색상을 사용할 수 있다.예를 들어, 크라운 그래프(n/2 꼭지점 {a₁, a₂, ...의 두 개의 분리 집합으로 구성된 그래프){}과(와) {b₁, b₂, ...}} i j j)가_i 있을 때마다_j a를 b에 연결하면 특히 탐욕스러운 색칠에 좋지 않은 경우가 될 수 있다.정점 a₁, b₁, a₂, b₂, b, ...를 주문할 때 탐욕스러운 색상은 각 쌍(a_i, b)에_i 대해 하나의 색상인 n/2 색상을 사용한다.그러나 이 그래프의 최적 색상 수는 정점 a와_i 정점 b의_i 두 가지 색상이다.^[5]무작위로 선택한 꼭지점 순서가 최소값보다 훨씬 큰 수의 색상으로 이어지는 그래프도 있다.^[6]따라서 정점 순서를 신중하게 선택하는 것은 탐욕스러운 색채에서 어느 정도 중요하다.

굿 오더

어떤 그래프의 정점들은 탐욕스러운 알고리즘이 최적의 색상을 생산하는 방식으로 항상 정렬될 수 있다.최적의 색상을 지정하면 정점을 색상으로 정렬할 수 있다.그런 다음 이 순서에 따라 탐욕스러운 알고리즘을 사용하면 결과 색상이 자동으로 최적이다.^[7]그러나 최적의 그래프 색상은 NP-완전이기 때문에 탐욕스러운 색상에 대한 최적의 순서를 찾는 등 이 문제를 빠르게 해결할 수 있는 모든 하위 문제는 NP-강력하다.^[8]

구간 그래프와 화음 그래프에서, 정점이 완벽한 제거 순서의 역순으로 정렬되면, 모든 정점의 초기 이웃들이 패를 형성하게 된다.이 특성은 탐욕스러운 색채들이 최적의 색채를 생산하게 하는데, 왜냐하면 그것은 결코 이들 각각의 색채에 필요한 것보다 더 많은 색을 사용하지 않기 때문이다.제거 순서는 존재하는 선형 시간에서 찾을 수 있다.^[9]

더 강하게 말하면, 완벽한 제거 순서는 유전적으로 최적이며, 이는 그래프 자체와 모든 유도 서브그래프 모두에 최적이라는 것을 의미한다.완벽하게 순서가 가능한 그래프(현현 그래프, 비교가능성 그래프, 거리-계통 그래프 포함)는 유전적으로 최적의 순서가 있는 그래프로 정의된다.^[10]완벽하게 정렬 가능한 그래프를 인식하는 것도 NP-완전하다.^[11]

주문 불량

주어진 그래프의 최악의 순서에 대해 탐욕스러운 색상이 만들어내는 색의 수를 그룬디 숫자라고 부른다.^[12]탐욕스러운 색칠을 위해 좋은 꼭지점 순서를 찾는 것이 어렵듯이, 나쁜 꼭지점 순서를 찾는 것도 어렵다.주어진 그래프 G와 숫자 k에 대해 탐욕스러운 알고리즘이 k 또는 그 이상의 색을 사용하도록 하는 G의 정점 순서가 있는지 여부를 결정하는 것은 NP-완전이다.특히 G에 대한 최악의 주문을 찾기 어렵다는 뜻이다.^[12]

순서와 무관한 그래프

색상이 양호한 그래프는 모든 정점 순서가 동일한 수의 색상을 생성하는 그래프다.이 그래프에서 색의 수는 색수와 그룬디 숫자와 같다.^[12]그것들은 cographs를 포함하는데, 이것은 정확히 유도된 모든 서브그래프가 잘 색을 띠는 그래프들이다.^[13]그러나 그래프의 색상이 양호한지 여부를 결정하는 것은 공동 NP 완성이다.^[12]

각 가장자리를 포함할 확률이 일정한 Erdős-Rényi 모델에서 랜덤 그래프를 그릴 경우, 그래프 가장자리와 독립적으로 선택한 정점 순서는 색상 수가 최적 값의 두 배, 높은 확률의 색상으로 이어진다.이러한 그래프의 색상을 현저히 더 잘 찾을 수 있는 다항식 시간 방법이 있는지 여부는 아직 알려지지 않았다.^[3]

퇴보

삼각형 프리즘과 사각형 항정신병(Square Antirism) 그래프, 변질 순서를 사용한 탐욕스러운 색상이 최적 색상보다 더 많은 색상을 제공하는 그래프

최적의 정점 순서는 찾기 어렵기 때문에 최적의 색상 수를 보장하지 않으면서 색상 수를 줄이려는 휴리스틱스가 사용돼 왔다.탐욕스러운 색상에 일반적으로 사용되는 순서는 최소도의 꼭지점 v를 선택하고 v가 제거된 서브그래프를 반복적으로 순서에 따라 순서에 따라 순서에 v를 마지막으로 배치하는 것이다.이 알고리즘이 마주친 가장 큰 제거 정점 정도는 그래프의 퇴행성(d)으로 표시된다.탐욕스러운 색채의 맥락에서 같은 주문 전략을 가장 작은 마지막 주문이라고도 한다.^[14]이 정점 순서와 퇴행성은 선형 시간으로 계산할 수 있다.^[15]그것은 정점을 각도로 내림차순으로 정렬하는 가장 큰 첫 번째 순서인 이전의 정점 순서법의 개선된 버전으로 볼 수 있다.^[16]

퇴보적인 순서와 함께 탐욕스러운 색상은 최대 d + 1 색상을 사용할 것이다.색칠하면 각 꼭지점마다 이미 색이 바랜 이웃이 많으므로 처음 d+1색 중 하나가 무료로 사용할 수 있기 때문이다.^[17]퇴행성 순서가 있는 탐욕스러운 색상은 나무, 사이비숲, 크라운그래프를 포함한 특정 등급의 그래프에 대한 최적의 색상을 찾을 수 있다.^[18]Markosian, Gasparian & Reed(1996)는 $그래프{\displaystyle }$ $G{\displaystyle }$${\displaystyle$ $G$$}$을(를$)$ β {\\displaystyle \beta $}-$완벽하다고$$ 정의하며, G ${\displaystyle G}$의 모든 유도 하위 그래프에 대해 색도 수가 변질성 + 1과 같을 경우.이러한 그래프의 경우 변질 순서가 있는 탐욕스러운 알고리즘이 항상 최적이다.^[19]모든 $\beta {\displaystyle }$ ${\displaystyle \beta }$ -완벽한$$ 그래프는 짝수 구멍이 없는 그래프여야 하는데, 짝수 사이클은 색도 숫자 2와 퇴보성 2를 가지며, $\beta {\displaystyle }$ ${\displaystyle \beta}$ -완벽한$$ 그래프 정의의 동일성과 일치하지 않기 때문이다.그래프와 그 보완 그래프가 모두 짝수 구멍이 없는 경우, 둘 다 $\beta {\displaystyle }$ ${\displaystyle \beta }-$완벽하다$$.완벽한 그래프와 $\beta {\displaystyle }$ ${\displaystyle \beta }-$완벽한$$ 그래프는 정확히 화음 그래프다.보다 일반적으로 홀이 없는 그래프에서 변질 순서는 최적 색상 수의 최대 두 배 이내, 즉 근사율은 2이다.^[20]단위 디스크 그래프에서 근사 비율은 3이다.^[21]삼각형 프리즘은 그 퇴행성 순서 중 하나가 비최적색상으로 이어지는 가장 작은 그래프이며, 정사각형 반향성은 그 퇴행성 순서 중 어떤 것을 사용해도 최적으로 색칠할 수 없는 가장 작은 그래프다.^[18]

적응명령

브렐라즈(1979)는 탐욕스러운 색상으로 정점을 주문하는 전략을 DSatur라고 하며, 주문의 구조를 색칠 과정과 섞는다.탐욕스러운 색채 알고리즘의 그의 버전에서, 각 단계에서 색칠할 다음 꼭지점은 그 근방에서 가장 많은 수의 뚜렷한 색을 가진 것으로 선택된다.동점일 경우, 정렬되지 않은 정점의 하위 그래프에서 최대 정도의 정점을 동점 정점에서 선택한다.각각의 단계에서 이웃 색과 그 기질을 추적함으로써, 이 방법을 선형 시간에 구현하는 것이 가능하다.^[22]

이 방법은 초당적 그래프,^[23] 모든 선인장 그래프, 모든 휠 그래프, 최대 6개의 정점에 있는 모든 그래프 및 거의 모든 $k{\displaystyle }$ ${\displaystyle k}$ 컬러링 가능한$$ 그래프에 대한 최적의 색상을 찾을 수 있다.^[24]레베크 & 마프레이(2005)는 원래 이 방법이 메이니엘 그래프에 대한 최적의 색상을 찾는다고 주장했지만, 나중에 이 주장에 대한 counterrexample을 발견했다.^[25]

대체 색상 선택 방식

주어진 그래프의 정점이 주어진 순서에 따라 색칠되지만 각 정점에 대해 선택한 색상이 반드시 사용 가능한 첫 번째 색일 필요는 없는 탐욕스러운 색상 알고리즘의 변형을 정의할 수 있다.여기에는 그래프의 미색인 부분이 알고리즘에 알려지지 않거나 알고리즘이 기본 탐욕 알고리즘보다 더 나은 색상을 선택할 수 있는 자유가 주어지는 방법이 포함된다.

온라인 선택

대체 색상 선택 전략은 온라인 알고리즘의 틀 안에서 연구되어 왔다.온라인 그래프 색상 지정 문제에서, 그래프의 정점이 한 번에 한 개씩 컬러링 알고리즘에 임의의 순서로 제시된다. 알고리즘은 이미 처리된 정점의 색과 조정성에만 기초하여 각 정점에 대한 색상을 선택해야 한다.이런 맥락에서, 사람들은 색상 선택 전략의 경쟁률, 사용하는 색의 수와 주어진 그래프에 대한 최적의 색상 수의 비율에 따라 색상 선택 전략의 품질을 측정한다.^[26]

그래프에 추가적인 제약이 주어지지 않을 경우 최적 경쟁률은 약간 하위 선형에 불과하다.^[27]그러나 구간 그래프의 경우 일정한 경쟁률이 가능한 반면,^[28] 초당적 그래프와 희소성 그래프의 경우 로그비율을 달성할 수 있다.실제로 희소성 그래프의 경우, 사용 가능한 첫 번째 색상을 선택하는 표준 탐욕스러운 색칠 전략은 이러한 경쟁률을 달성하며, 온라인 색칠 알고리즘의 경쟁률에 대해 일치하는 하한을 증명하는 것이 가능하다.^[26]

파시모노스 컬러링

주어진 그래프와 꼭지점 순서에 대한 파시미닉 컬러링은 주어진 순서에 따라 정점을 색칠하는 탐욕스러운 알고리즘에 의해 생성된 컬러로 정의되었으며, 기존의 모든 색상이 주어진 꼭지점에 인접해 있을 때만 새로운 컬러를 도입하지만 (항상 가장 작은 색을 선택하는 대신) 사용할 컬러를 선택할 수 있다.기존 색상을 재사용할 수 있다.순서가 지정된 색수는 이러한 방식으로 주어진 순서에 대해 얻을 수 있는 가장 작은 색이며, 오크롬 번호는 주어진 그래프의 모든 정점 색상 중에서 순서가 가장 큰 색수다.그것의 다른 정의에도 불구하고, 오크롬 숫자는 항상 그룬디 숫자와 같다.^[29]

적용들

빠르고 많은 경우 색을 거의 사용할 수 없기 때문에, 탐욕스러운 색상은 좋지만 최적의 그래프 색상이 필요한 어플리케이션에서 사용될 수 있다.탐욕스러운 알고리즘의 초기 적용 중 하나는 과제 모음을 지정된 시간 간격 집합에 할당해야 하는 과정 스케줄링과 같은 문제에 대한 것으로, 동일한 시간 슬롯에 할당되는 호환되지 않는 작업을 피했다.^[4]또한 정점이 레지스터에 할당될 값을 나타내고 가장자리가 동일한 레지스터에 할당할 수 없는 두 값 사이의 충돌을 나타내는 그래프에 적용하여 레지스터 할당을 위한 컴파일러에서도 사용할 수 있다.^[30]대부분의 경우 이러한 간섭 그래프는 화음 그래프여서 탐욕스러운 색상이 최적의 레지스터 할당을 생성할 수 있다.^[31]

결합형 게임 이론에서, 정점이 게임 위치를 나타내고 가장자리가 한 위치에서 다른 위치로 유효한 이동을 나타내는 지시된 AC 순환 그래프로서 명시적인 형태로 주어진 공정한 게임의 경우, 탐욕스러운 색상 알고리즘(그래프의 위상학적 순서의 역순을 사용)은 각 위치의 님 값을 계산한다.이 값들은 어떤 단일 게임이나 어떤 이분법적인 게임 합계에서 최적의 플레이를 결정하는 데 사용될 수 있다.^[32]

최대 도 Δ의 그래프의 경우, 탐욕스러운 색상은 최대 Δ + 1 색상을 사용한다.브룩스의 정리에서는 최대 Δ 색상에서 두 가지 예외(클릭과 홀수 사이클)가 필요하다고 기술하고 있다.브룩스의 정리에 대한 한 가지 증거는 처음 두 정점이 최종 정점에 인접하지만 서로 인접하지 않는 정점 순서를 찾는 것을 포함한다. 그리고 마지막 정점이 아닌 다른 정점들은 적어도 하나 이상의 후자의 이웃을 가지고 있다.이 속성을 가진 주문의 경우 탐욕스러운 컬러링 알고리즘은 최대 Δ 색상을 사용한다.^[33]

메모들

참조