VPF::Раскраска ребер графа - Форум программистов

dow

Дата 20.5.2013, 19:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 20.5.2013

Репутация: нет
Всего: нет

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

Код


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];
            }

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »