Лабораторная работа 25. Np полные задачи

3. Описание программ

Текст программы

using namespace std;

const int INF = (int)1e9;
const long long INF64 = (long long)1e18;
#define forn(i,n) for(int i = 0; i < n; i++)
#define ford(i,n) for(int i = n - 1; i >= 0; i--)
vector > g;
vector used;
vector color;
int n, m;
void dfs(int v, int col)
{
int dx;
used[v] = true;
color[v] = col;
forn(i, g[v].size())
{
dx = g[v][i];
if(!used[dx])
dfs(dx, col ^ 1);
}
}
void solve(){
scanf("%d%d", &n, &m);
g = vector >(n, vector());
used = vector(n);
color = vector(n);
forn(i, m){
int x, y;
scanf("%d%d", &x, &y);
x--;y--;
g[x].pb(y);
g[y].pb(x);
}
forn(i, n)
if(!used[i])
dfs(i, 0);
bool ok = true;
forn(i, n)
forn(j, g[i].size())
if(color[g[i][j]] == color[i])ok = false;
if(ok)printf("YES\n");
else printf("NO\n");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
int t;
scanf("%d", &t);
forn(i, t)
solve();
return 0;
}

Сложность вычислений

Раскраска графа является вычислительно сложной задачей. Узнать, допускает ли граф k-раскраску для заданного k — это NP-полная задача, кроме случаев k = 1 и k = 2. В частности, задача вычисления хроматического числа NP-сложна. Задача о 3-раскраске NP-полная даже для случая планарного графа степени 4.

Контрольные вопросы:

1. 
   Сферы применения графов. Способы машинного представления графов, их достоинства и недостатки.
   
2. 
   Алгоритмы поиска в графе: поиск в ширину, поиск в глубину.
   
3. 
   Эйлеров путь, эйлеров цикл, эйлеров граф. Алгоритм нахождения эйлерова цикла.
   
4. 
   Нахождение кратчайших расстояний. Алгоритм Дейкстры.
   
5. 
   Остовные деревья графа. Алгоритмы нахождения дерева минимального веса: алгоритм Прима, алгоритм Крускала.
   
6. 
   Эффективность алгоритмов и её составляющие. Алгоритмы и их сложность. Доминирование. О-функции и их особенности.
   
7. 
   Правила для определения сложности. Функции, часто используемые для оценки сложности алгоритмов (список функционального доминирования). Сравнение алгоритмов с различными порядками сложности.
   
8. 
   Анализ алгоритмов и определение их сложности по управляющим структурам. Контрольные замеры. Критический взгляд на О-анализ. (ограниченность О-анализа).
   
9. 
   Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости зада
   

ЗАДАНИЕ
1. Представьте заданный граф в виде матрицы смежности, в которой на пересечении соответствующей строки и столбца, указывается расстояние между соответствующими вершинами графа.
2. Решите поставленную задачу и приведите описание расчета всех шагов решения задачи.
3. Представьте ответ задания в наглядной форме, например, на нарисованном графе выделите минимальный остов, центральную вершину, таблицу, подтверждающую правильность решения.
1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

Содержание отчета
В отчете следует указать:

• 
  Название работы.
  
• 
  Цель работы.
  
• 
  Теоретическая часть.
  
• 
  Выполненное задание.
  
• 
  Заключение (выводы).
  
• 
  Литература.