Алгоритм приближенной раскраски графа

@Sergeymd · Регистрация: 13.09.2009

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

Необходимо раскрасить граф

вот есть алгоритм приближенной раскраски:

1. Вычислить степени вершин. Положить K=1.Пример.
2. Просмотреть вершины в порядке не возрастания степеней и окрасить первую неокрашенную вершину в цвет № K.
3. Просмотреть вершины в порядке не возрастания степеней и окрасить в цвет №К все вершины, которые не смежны вершинам, уже окрашенным в цвет №К.
4. Если все вершины окрашены, то К-искомое хроматическое число. Пример.Иначе К=К+1 и переход к пункту 2.

http://www.tisbi.ru/resource/l... tm#metka42
или тут
http://rain.ifmo.ru/cat/view.p... oring-2004

вроде не сложно ну что то не как не соображу , представил каждую вершину в виде структуры:

C
1
2
3
4
5
struct graf{
int stepeni;
int color;
int number;
};

и на 3-ем пункте застрял ,может как то по другому представить вершины что посоветуете???

@M128K145 · 11.11.2009, 20:37

представь граф матрицей смежности

вот

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
int main()
{
    setlocale(LC_ALL, "Russian");
    const int n(6);
    int i, j;
    int mi[n][n] = { 0, 1, 0, 1, 1, 0,
                     1, 0, 1, 1, 0, 0,
                     0, 1, 0, 1, 1, 1,
                     1, 1, 1, 0, 1, 0,
                     1, 0, 1, 1, 0, 1,
                     0, 0, 1, 0, 1, 0 };
 
    for(i = 0; i < n; ++i, std::cout<<std::endl)
        for(j = 0; j < n; ++j)
            std::cout<<mi[i][j]<<' ';
    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];
    std::cout<<"\nХроматическое число графа равно "<<max;
    std::cin.get();
    return 0;
}

@Sergeymd · 11.11.2009, 20:52 **[ТС]**

ну так я и представил в виде матрицы а каждую еще вершину в виде струтуры, и мне не просто необходимо найти хроматическое число а именно реально нарисовать граф и раскрасить вершины его

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <conio.h>
 
struct graf{
int stepeni;
int color;
int number;
};
 
using namespace std;
void ShowGraf(graf arr[22],int n);
int CheckColor(graf arr[22],int n);
void InitGraf(graf arr[22],int n);
 
int main()
{
 int color1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    
 struct graf arr[22];
 
 int mx[4][4];
 
   int m[4][4]= {0, 1, 1, 1,
                1, 0, 0, 1,
                1, 0, 0, 1,
                1, 1, 1, 0};
            
  int n=4z;  ////!!!!!!!!!!!!!!!!!!!!!!!!!!
 
//naxodim stepeni vershin
   for(int i=0; i < n; i++,versh++)
     {
       arr[versh].stepeni=0;  
       arr[versh].number=i;
     for(int j=0; j < n; j++)
       if( m[i][j] == 1 )
         arr[versh].stepeni++;
     }
 
   
//sortirovka structuri po stepeneam s naibolishei po naimenishiu
  struct graf temp;
  
     for(int i=0; i < n; i++)
       for(int j=0; j < n; j++)
         if(arr[i].stepeni > arr[j].stepeni)
         {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
         }
         
 
//algoritm prisvoeniea cvetov  
......
 
}

@Sergeymd · 12.11.2009, 00:36 **[ТС]**

Добавлено через 1 час 28 минут
вроде сделал и даже работает

но как то сложновато по моему аж 4 цикла for

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <conio.h>
 
struct graf{
int stepeni;
int color;
int number;
};
 
using namespace std;
void ShowGraf(graf arr[22],int n);
int CheckColor(graf arr[22],int n);
void InitGraf(graf arr[22],int n);
 
int main()
{
 int color1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    
 struct graf arr[22];
 
 int mx[4][4];
 
   int m[4][4]= {0, 1, 1, 1,
                1, 0, 0, 1,
                1, 0, 0, 1,
                1, 1, 1, 0};
                
                
                
   /*                               
    
     int m[10][10]={0,0,0,0,0,0,0,1,0,0,
                    0,0,0,0,0,0,0,1,0,0,
                    0,0,0,0,0,0,0,1,0,0,
                    0,0,0,0,0,0,0,1,0,1,
                    0,0,0,0,0,0,0,0,0,0,
                    0,0,0,0,0,0,0,1,1,0,
                    0,0,0,0,0,0,0,1,0,0, 
                    1,1,1,1,0,1,1,0,1,1, 
                    0,0,0,0,0,1,0,1,0,0,
                    0,0,0,1,0,0,0,1,0,0,
};   */
 
/*
 int m[8][8]={{0,1,1,0,0,0,0,0},//se declara matricea de adiacenta
        {1,0,1,0,0,0,0,0},
        {1,1,0,1,1,1,0,0},
        {0,0,1,0,0,0,0,0},
        {0,0,1,0,0,1,0,0},
        {0,0,1,0,1,0,1,1},
        {0,0,0,0,0,0,0,1},
        {0,0,0,0,0,1,1,0}};
  */               
                
  int n=4,versh=0,z;  ////!!!!!!!!!!!!!!!!!!!!!!!!!!
 
InitGraf(arr,n);//cveta po umolceniu v 66 vse
  
//naxodim stepeni vershin
   for(int i=0; i < n; i++,versh++)
     {
       arr[versh].stepeni=0;  
       arr[versh].number=i;
     for(int j=0; j < n; j++)
       if( m[i][j] == 1 )
         arr[versh].stepeni++;
     }
 
//sortirovka structuri po stepeneam s naibolishei po naimenishiu
  struct graf temp;
  
     for(int i=0; i < n; i++)
       for(int j=0; j < n; j++)
         if(arr[i].stepeni > arr[j].stepeni)
         {
           temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
         }
   
   //algoritm prisvoeniea cvetov  
int x=0,t,i,j,st,flag=0,metk=0,s;
 
 for(x=0; CheckColor(arr,n)!=0 ; x++)//   //cikl po cvetam ulovie vixoda vse okrasheni
 {   
   if(arr[x].color == 66) arr[x].color = color1[x];      //prisvaivaem pervii cvet 
      // else continue;
                
    for(i=0; i < n; i++) //cikl ctobi ne toliko odnu vershinu raskarasiti a vse ne smejnie
      {      
         t=arr[i].number; //nomer stroki matrici smejnosti !!!!bilo - x
         flag=0;          
         for(j=0; j < n; j++)    //idem v stroku matrici po nomeru 
         {
           if((m[t][j] == 1 && t!=j))  // || mx[t][j] == 0 && j == arr[j].number && t!=j
            {
               for(s=0; s < n; s++)   //
                if(j == arr[s].number && arr[s].color != color1[x] )
                  {
                    ++flag;
                   // metk=j;         ////!!!!!!!!!!!!!!!! 
                   // break;
                  }
             }
             
           if( arr[j].number == t ) metk=j;
           
           if(flag==arr[metk].stepeni && arr[metk].color == 66 )    ///!!!
             arr[metk].color = color1[x];   
            // else break;   ////!!!!
          }
       } 
  }   
ShowGraf(arr,n);
 
getch();
return 0;
}
 
//************************************************************
//inicializiruem vse cveta v strukture v 66
void InitGraf(graf arr[22],int n)
{
         for(int s=0;s < n; s++)
         {
           arr[s].color=66;
        // cout<<;
         }
} 
 
//************************************************************
//vivodit rezulitat
void ShowGraf(graf arr[22],int n)
{
         for(int s=0;s < n; s++)
         {
           cout<<arr[s].number<<"-"<<arr[s].stepeni<<"-"<<arr[s].color<<endl;
        // cout<<;
         }
} 
//************************************************************
//vozvrashaiet 0 esli vse cveta uje prisvoeni
int CheckColor(graf arr[22],int n) 
{
  int flag2=0;  
  for(int xx=0; xx < n; xx++) //cikl provereaite vse li cveta prisvoeni
  {
   if(arr[xx].color <= 16)
   ++flag2;
      }
   if(flag2==n) return 0;
   else return 1;   
}

PS осталось только это дело нарисовать , где посоветуете думал в c#, но еще в нем не работал, сложно там будет нарисовать граф и ракрасить?

@M128K145 · 12.11.2009, 00:59

Sergeymd, пиши на java, имхо, там удобнее рисовать

Новые блоги и статьи Все статьи Все блоги /
Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .

@M128K145 8384 / 3617 / 419 Регистрация: 03.07.2009 Сообщений: 10,709
	12.11.2009, 00:59
	Sergeymd, пиши на java, имхо, там удобнее рисовать 1

Алгоритм приближенной раскраски графа

Решение