Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Раскраска ребер графа

Автор: dow 20.5.2013, 19:22

Доброго всем времени суток =)
Столкнулся с такой задачей: "Найти максимальное подмножество попарно несмежных вершин". В процессе гугления понял, что мне по-сути надо найти хроматический индекс графа. Я смог реализовать раскраску вершин графа:

Код


for(int i = 0; i < count; ++i)
   colors[i]=1;
for(int i =0; i < count; ++i)
  for(int j = 0; j < count; ++j)
                      if (mas[i][j] == 1 && colors[j] == colors[i])
                    {
                        colors[j] = colors[i] + 1;                        
                    }
     int max = colors[0];
for (int j = 0; j < table.RowCount; ++j)
            {
                if (max < colors[j])
                    max = colors[j];
            }

Помогите пожаалуйста. У меня просто реально ступор, просто не могу понять как можно раскрасить ребра графа =(((