그래프 색칠하기
그래프 색칠은 그래프의 정점에 색상을 할당하는 과정으로 설명할 수 있습니다. 이때 인접한 두 정점을 동일한 색상으로 채우면 안 됩니다. 그래프 색칠을 정점 색칠(Vertex Colouring)이라고 부를 수도 있습니다. 그래프 색상 지정 시 그래프의 끝 꼭짓점이 동일한 색상으로 표시되는 간선이 포함되어서는 안 된다는 점에 주의해야 합니다. 이러한 유형의 그래프를 적절한 색상 그래프라고 합니다.
그래프 색칠의 예
이 그래프에서는 다음과 같이 적절하게 색상이 지정된 그래프를 보여줍니다.
위의 그래프에는 다음과 같은 몇 가지 사항이 포함되어 있습니다.
- 동일한 색상을 사용하여 인접한 두 정점을 색칠할 수 없습니다.
- 따라서 이를 적절하게 색칠된 그래프라고 부를 수 있습니다.
그래프 채색의 응용
그래프 채색에는 다양한 응용이 있습니다. 중요한 응용 프로그램 중 일부는 다음과 같습니다.
- 과제
- 지도 색칠하기
- 작업 예약
- 스도쿠
- 시간표 준비
- 갈등 해결
반음계수
색수는 그래프를 적절하게 색칠하는 데 필요한 최소 색상 수로 설명할 수 있습니다. 즉, 유채색수는 그래프의 인접한 두 정점에 동일한 색상이 할당되지 않도록 그래프를 색칠하는 데 필요한 최소 색상 수로 설명할 수 있습니다.
자바의 str.substring
반음계수의 예:
색수를 이해하기 위해 다음과 같이 설명되는 그래프를 고려해 보겠습니다.
위의 그래프에는 다음과 같은 몇 가지 사항이 포함되어 있습니다.
- 인접한 두 정점을 색칠하는 데 동일한 색상이 사용되지 않습니다.
- 이 그래프의 최소 색상 수는 3개이며 정점을 적절하게 색상 지정하는 데 필요합니다.
- 따라서 이 그래프에서 색수 = 3입니다.
- 이 그래프에 적절한 색상을 지정하려면 최소한 3가지 색상이 필요합니다.
그래프의 색채 수 유형:
그래프의 색수에는 다양한 유형이 있으며 다음과 같이 설명됩니다.
사이클 그래프:
그래프에 길이 'n'의 순환을 형성하는 'n'개의 모서리와 'n'개의 정점(n >= 3)이 포함되어 있으면 순환 그래프라고 합니다. 순환 그래프의 모든 정점에는 2~3개의 각도만 있을 수 있습니다.
반음계수:
- 순환 그래프의 색수는 해당 그래프의 정점 수가 짝수인 경우 2가 됩니다.
- 순환 그래프의 색수는 해당 그래프의 정점 수가 홀수인 경우 3이 됩니다.
사이클 그래프의 예:
사이클 그래프의 다양한 예가 있습니다. 그 중 일부는 다음과 같이 설명됩니다.
예시 1: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위의 순환 그래프에서는 3개의 정점에 3가지 다른 색상이 있으며 인접한 정점 중 어느 것도 동일한 색상으로 색칠되어 있지 않습니다. 이 그래프에서 꼭지점의 개수는 홀수입니다. 그래서
반음계수 = 3
예 2: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위의 순환 그래프에서는 4개의 꼭지점에 2가지 색상이 있으며 인접한 꼭지점 중 어느 하나도 같은 색상으로 색칠되어 있지 않습니다. 이 그래프에서는 꼭짓점의 개수가 짝수입니다. 그래서
반음계수 = 2
예시 3: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에서는 5개의 꼭지점에 4가지 다른 색상이 있고, 인접한 2개의 꼭지점은 같은 색상(파란색)으로 칠해져 있습니다. 따라서 이 그래프는 사이클 그래프가 아니며 색수를 포함하지 않습니다.
예시 4: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에서는 6개의 꼭지점에 2개의 서로 다른 색상이 있으며, 인접한 꼭지점 중 어느 하나도 같은 색상으로 색칠되어 있지 않습니다. 이 그래프에서는 꼭짓점의 개수가 짝수입니다. 그래서
반음계수 = 2
플래너 그래프
그래프를 평면에 그리면 플래너 그래프라고 합니다. 플래너 그래프의 가장자리가 서로 교차하면 안 됩니다.
반음계 번호:
자바의 배열 인쇄
- 플래너 그래프에서 색채수는 4보다 작거나 같아야 합니다.
- 플래너 그래프는 예제 3을 제외하고 위의 모든 사이클 그래프로도 표시할 수 있습니다.
플래너 그래프의 예:
평면 그래프의 예는 다양합니다. 그 중 일부는 다음과 같이 설명됩니다.
예시 1: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에는 3개의 꼭짓점에 3개의 서로 다른 색상이 있으며, 이 그래프의 모서리는 서로 교차하지 않습니다. 그래서
반음계수 = 3
여기서 색수는 4보다 작으므로 이 그래프는 평면 그래프이다.
예 2: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에는 4개의 꼭지점에 2개의 서로 다른 색상이 있으며 이 그래프의 모서리 중 어느 것도 서로 교차하지 않습니다. 그래서
반음계수 = 2
여기서 색수는 4보다 작으므로 이 그래프는 평면 그래프이다.
예시 3: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에는 5개의 꼭지점에 5개의 서로 다른 색상이 있으며, 이 그래프의 모서리는 서로 교차하지 않습니다. 그래서
반음계수 = 5
여기서 색수는 4보다 크므로 이 그래프는 평면 그래프가 아닙니다.
예시 4: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에는 6개의 꼭지점에 2개의 서로 다른 색상이 있으며, 이 그래프의 모서리는 서로 교차하지 않습니다. 그래서
반음계수 = 2
자바의 스택이란 무엇입니까?
여기서 색수는 4보다 작으므로 이 그래프는 평면 그래프이다.
완전한 그래프
모든 두 개의 정점을 연결하는 데 하나의 간선만 사용되는 경우 그래프는 완전한 그래프로 알려져 있습니다. 완전한 그래프의 모든 정점은 다른 모든 정점과 연결됩니다. 이 그래프에서는 모든 정점이 다른 색상으로 표시됩니다. 이는 전체 그래프에서 두 정점에 동일한 색상이 포함되어 있지 않음을 의미합니다.
반음계수
완전한 그래프에서 색수는 해당 그래프의 정점 수와 같습니다.
전체 그래프의 예:
완전한 그래프의 다양한 예가 있습니다. 그 중 일부는 다음과 같이 설명됩니다.
예시 1: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 4개의 서로 다른 정점에 4개의 서로 다른 색상이 있으며, 위 그래프에서는 색상 중 어느 것도 동일하지 않습니다. 정의에 따르면 색수는 정점의 수입니다. 그래서,
사이라 바누 배우
반음계수 = 4
예 2: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 5개의 서로 다른 정점에 5개의 서로 다른 색상이 있으며, 위 그래프에서는 색상 중 어느 것도 동일하지 않습니다. 정의에 따르면 색수는 정점의 수입니다. 그래서,
반음계수 = 5
예시 3: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 4개의 서로 다른 정점에 3개의 서로 다른 색상이 있으며, 위 그래프에서는 두 개의 정점에서 하나의 색상이 반복됩니다. 따라서 이 그래프는 완전한 그래프가 아니며 유채색수를 포함하지 않습니다.
이분 그래프
그래프에 두 개의 꼭짓점 집합 A와 B가 포함되어 있으면 이분 그래프라고 합니다. A의 꼭짓점은 B의 꼭짓점과만 결합할 수 있습니다. 이는 가장자리가 집합과 꼭짓점을 결합할 수 없음을 의미합니다.
반음계수
모든 이분 그래프에서 색수는 항상 2와 같습니다.
이분 그래프의 예:
이분 그래프의 다양한 예가 있습니다. 그 중 일부는 다음과 같이 설명됩니다.
예시 1: 다음 그래프에서는 색수를 결정해야 합니다.
해결책: 위 그래프에는 2개의 서로 다른 정점 세트가 있습니다. 따라서 모든 이분 그래프의 색수는 항상 2입니다.
반음계수 = 2
C++ 문자열 분할
나무:
연결된 그래프는 해당 그래프에 회로가 없으면 트리로 알려져 있습니다. 트리에서는 트리에 정점이 몇 개 있든 상관없이 색수는 2와 같습니다. 모든 이분 그래프는 트리이기도 합니다.
반음계수
모든 나무에서 색수는 2와 같습니다.
트리의 예:
나무의 다양한 예가 있습니다. 그 중 일부는 다음과 같이 설명됩니다.
예시 1: 다음 트리에서는 색수를 결정해야 합니다.
해결책: 4개의 꼭지점에는 2가지 색상이 있습니다. 임의 개수의 꼭짓점을 가진 트리는 위 트리에서 색수 2를 포함해야 합니다. 그래서,
반음계수 = 2
예 2: 다음 트리에서는 색수를 결정해야 합니다.
해결책: 5개의 꼭지점에는 2가지 색상이 있습니다. 임의 개수의 꼭짓점을 가진 트리는 위 트리에서 색수 2를 포함해야 합니다. 그래서,
반음계수 = 2
반음수의 실제 예
Marry가 Xyz Company의 관리자라고 가정해 보겠습니다. 회사는 몇 명의 신입 직원을 고용하고 있으며, 그녀는 해당 신입 직원에 대한 교육 일정을 받아야 합니다. 그녀는 세 번의 회의 일정을 잡아야 하며 가능한 한 적은 시간을 회의에 사용하려고 노력하고 있습니다. 두 개의 서로 다른 회의에 참석해야 하는 직원이 있는 경우 관리자는 해당 회의에 서로 다른 시간 일정을 사용해야 합니다. 이 회의를 시각적으로 표현하고 싶다고 가정해 보겠습니다.
시각적 표현을 위해 Marry는 점을 사용하여 회의를 나타냅니다. 두 개의 회의가 있고 두 회의에 모두 참여해야 하는 직원이 있는 경우 두 회의 모두 엣지의 도움으로 연결됩니다. 다양한 시간 슬롯은 색상의 도움으로 표시됩니다. 따라서 관리자는 두 점이 가장자리를 공유하는 동일한 색상을 포함하지 않는 방식으로 이러한 색상으로 점을 채웁니다. (즉, 두 회의에 참석해야 하는 직원의 시간이 동일해서는 안 됩니다.) 이를 시각적으로 표현하면 다음과 같습니다.
