이분 그래프의 최적의 가장자리 채색

Question

다음 문제에 직면했습니다. 두 가지 그래프에서 최적의 가장자리 채색을 찾습니다. 나는 탐욕스러운 착색 알고리즘이 때로는 최적의 색상 수를 반환 할 수 없다는 것을 알고 있습니다. 'greedy colouring algorithm'은 다음과 같습니다. 가장 높은 차수를 가진 첫 번째 정점을 선택하고 1 ... 정도의 색상에서 가장자리를 채 웁니다. 그 다음에 학위를 가진 정점을 선택합니다. < = 사용 가능한 숫자 (이웃에 의해 사용되지 않는 가장 낮은 숫자), 다음 정점 등을 선택하십시오.

하지만 하나의 수정 사항을 소개했습니다. 처음 선택한 정점의 가장자리는 내림차순으로 나타납니다. 1), 이전에 1 ...도에있는 다음 꼭지점의 가장자리. 이 수정으로 인해 나는 최적의 수의 색상을 얻었습니다. 하지만 항상 규칙이라고 확신하지는 않습니다. 누군가가 가장자리 채색 알고리즘의이 버전이 최적인지 또는 누군가가 어떤 반례를 보여줄 수 있는지 알고 있습니까?

Answer 1

"순진한"욕심 많은 알고리즘에 대한 반례를 가져다가 "정교한"욕심쟁이 알고리즘의 반례 사례로 바꿀 수 있습니다. 적절한 정도의 더미 노드를 삽입하기 만하면 후방 착색을 "흡수"합니다. 그래프의 임의의 부분에 학위 n의 새 노드를 만들 수 있습니다. n 노드를 다른 노드에 삽입하고 단일 가장자리로 각각 원하는 새 노드에 연결하면됩니다.

내림차순으로 채색 된 모든 노드가 새로 삽입되므로 원래 반례 예에있는 모든 노드는 오름차순으로 색상이 지정되어 원본 "순진한"욕심 알고리즘과 동일한 색상을 얻습니다. 최적의 채색은 최소한 원래의 그래프의 정도만큼의 색상을 가지며 새로 삽입 된 노드는 모두 원래 그래프의 최대도보다 작은 각도를 갖기 때문에 새로운 그래프는 원본보다 더 이상 색상을 필요로하지 않습니다. 따라서 "정교한"알고리즘 (원래 그래프에 필요한 것보다 더 많은 색상을 갖음)에 의해 생성 된 컬러링은 새 그래프에 적합하지 않습니다.

예를 들어 왼쪽에 노드 B, C, D가 있고 오른쪽에 E, F, G, H가있는 아래의 설명에서 설명한 그래프를 가져옵니다. 그것은 이러한 가장자리가 : 순간을 위해

B connects to E, F, and G 
C connects to E, F, and G 
D connects to G and H 

을, 당신이 내림차순으로 착색됩니다 만지지 첫 번째 노드를 가정합니다. (다른 노드의 경우, "내림차순"이 의미하는 것조차도 명확하지 않습니다 - 최대 값에서 내림차순입니까? 노드의 차수가 충분히 높지 않을 수 있습니다.) 따라서 우리는 노드 A에 새로운 노드 A를 삽입합니다. 오른쪽에는 왼쪽과 세 개의 노드 I, J, K가있다. 연결성은 지금 정교한 욕심 알고리즘에 따라서 색상 AI-3, AJ-2, AK-1, 다음 나머지 노드에서 소박한 욕심 알고리즘으로 진행됩니다

A connects to I, J, and K 
B connects to E, F, and G 
C connects to E, F, and G 
D connects to G and H 

입니다.