Раскраска графа, хроматическое число

@Switty · Регистрация: 15.05.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте, есть код для нахождения хроматического числа. До 4 вершин работает правильно, но с 5 и выше находит не правильно, в данном примере необходимо 3 цвета, а он находит 2. Помогите исправить, пожалуйста:

C++

#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
    setlocale(LC_ALL, "Russian");
    const int n = 5;
    int i, j;
    int mi[n][n] = { 0, 1, 1, 0, 0,
                      1, 0, 0, 1, 0,
                      1, 0, 0, 1, 1,
                      0, 1, 1, 0, 1,
                      0, 0, 1, 1, 0 };
     
    cout << "Вывод матрицы: " << endl;
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            cout << mi[i][j] << ' ';
        }
        cout << endl;
    }
 
    //Хроматическое число:
    int col[n];
    for (i = 0; i < n; ++i)
        col[i] = 1;
    for (i = 0; i < n; ++i)
        for (j = i + 1; j < n + 1; ++j)
            if (mi[i][j] == 1 && col[j] == col[i])
                col[j] = col[i] + 1;
 
    int max = col[0];
    for (j = 1; j < n; ++j)
        if (max < col[j])
            max = col[j];
 
 
    cout << "\nХроматическое число графа равно: " << max<<endl;
    return 0;
}

	24.12.2016, 14:24