Раскраска Ребер Графа

rabbit

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

C++:
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];
}
Помогите пожаалуйста. У меня просто реально ступор, просто не могу понять как можно раскрасить ребра графа =(((