그래프의 반음계 수를 찾고 그 수를 사용하여 유효한 색을 제공하는 알고리즘을 개발 중입니다. 이 목적을 위해, 나는 가능한 답 K를 찾고 유전자 알고리즘을 사용하여 K가 가능한지를 확인하기 위해 이진 검색을 사용한다. 문제는 색수가 고르지 않게 분산된다는 것입니다. 예를 들어 1000 개의 꼭지점이있는 그래프의 경우, 그 반음계는 100 이하일 것입니다. 이진 검색에서이 방법을 사용하면 왼쪽 경계와 오른쪽 경계 사이의 중간에서 나눌 필요가 없지만 반음계 숫자 분포. 이 배포판에 대한 정보를 얻을 수있는 자료를 알고 있습니까? 나는 세부 사항을 알려주는 소스를 발견했지만, 노드가 10 개 미만인 그래프의 경우 : http://keithbriggs.info/cgt.html.그래프 분포의 색수
특정 크기의 그래프에는 의미있는 숫자 분포가 없습니다. 실제로 이러한 분포를 정의하려면 먼저 입력 그래프에 분포를 정의해야합니다. 나는 의미하는 바를 설명 할 것이다. 먼저 P_G를 입력 그래프의 분포로 정의하십시오. 그런 다음 색수를 그래프를 정수로 매핑하는 임의의 변수 X로 간주합니다. 마지막으로, P_X (X = k) = P_G ({G와 같은 f (G) = k})를 호출하여 X에 대한 분포를 구할 수 있습니다. 지저분한 서식에 대해 사과 드리며,이 말이 맞는다면 알려 주시기 바랍니다.
그래서 나는 (1) 입력 그래프 P_G에 대한 분포가 없을 수도 있고 (2) 닫힌 형식을 얻기가 어려울 수 있기 때문에 반음계 분포가 필요하다고 생각하지 않습니다. P_G가 있더라도 P_X. 단순한 Erdos Renyi 임의 그래프 모델조차도 예상되는 반음계 수는 알려지지 않았습니다.
사용할 수있는 범위는 (1) 최대 수위 + 1, (2) 반경 수는 적어도 최대 도당 수의 크기입니다. 살펴볼 수있는 것은 several other bounds이며, 하나는 호프만 경계입니다.이 값을 구하는 것은 어렵지만, 고유 값 계산이 필요하기 때문에 어려울 수 있습니다. 가장 좋은 방법은 당신이 (1) 그래프를 분해하여보다 작은 부분 그래프로 분해하고 그 그래프를 색칠 (2) 색칠을 결합하는 것입니다. 나는 아마 대략 이것을하는 좋은 hueristics가 있다고 상상할 것이다. 그러나 나는 불행하게도 어떤 참조도 가지지 않고있다.
프로그래밍 주제가 아닌 어려운 수학 문제 인 주제에 관한 경우에도 의미있는 대답을 얻으려면 입력 그래프의 분포를 지정해야합니다. –
그래서 저는 꼭지점이 n 인 그래프를 얻었을 때, 1-chromatic, 2-chromatic 등의 확률을 알고 싶습니다. 이것은 당신이 찾고있는 입력 그래프의 분포입니까? –
Paul이 입력 그래프 분포를 참조하고있는 것과 색채 수에 대한 더 많은 정보가 도움이 될 수있는 지에 대한 자세한 설명은 아래의 내 대답을 참조하십시오. –