0
연결된 무채색 그래프 G가 있다고 가정하십시오. G의 모든 노드를 색깔이있는 노드 또는 색깔이있는 노드에 인접하게 놓기를 원합니다. 그래프 G를 적절하게 색칠하는 알고리즘을 설계하십시오. 색상 층 (n/2) 노드 만 허용됩니다. 여기서 n은 총 노드 수입니다.모든 노드가 색깔이있는 노드에 착색되거나 인접하도록 그래프를 색칠하십시오.
솔루션에서 시도했지만 제약 조건의 문제를 완전히 해결하지 못했음을 알았습니다. 나는 뉘앙스 또는 잘못된 방향으로 가고 있다고 말하고 싶습니다.
내 솔루션은 기본적으로 BFS를 실행하고 3 번째 "레벨"마다 노드를 색칠했습니다. 그러나 이것이 실패한 인스턴스 하나를 발견했습니다. 링크 된 세 노드의 목록입니다. 만약 내가 머리 나 꼬리를 색칠한다면, 노드들 중 하나는 착색 된 노드로부터 거리 2 떨어져있을 것이고, 나는 중간 노드가 착색 될 것이라는 것을 확실히 확신 할 방법이 없다.
n = 1로 간주하십시오. –