Сведение по Карпу — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
(Пример)
Строка 6: Строка 6:
 
==Пример==
 
==Пример==
 
Рассмотрим следующие языки:
 
Рассмотрим следующие языки:
<tex>IND</tex> и <tex>CLIQUE</tex> <math>-</math> множества пар <tex>\langle G, k \rangle </tex>, где <tex>G</tex> <math>-</math> граф, <tex>k</tex> <math>-</math> натуральное число. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>IND</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором все вершины не связаны ребрами. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>CLIQUE</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором между каждой парой вершин проходит ребро.
+
<tex>IND</tex> и <tex>CLIQUE</tex> <math>--</math> множества пар <tex>\langle G, k \rangle </tex>, где <tex>G</tex> <math>--</math> граф, <tex>k</tex> <math>-</math> натуральное число. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>IND</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором все вершины не связаны ребрами. Пара <tex>\langle G, k \rangle </tex> принадлежит <tex>CLIQUE</tex>, если в графе <tex>G</tex> есть подграф с <tex>k</tex> вершинами, в котором между каждой парой вершин проходит ребро.
  
 
Существует функция <tex>f</tex> такая, что <tex>f(\langle G, k \rangle ) = \langle H, k \rangle </tex>, где <tex>H</tex> <math>-</math> граф, в котором столько же вершин, сколько и в <tex>G</tex>, а ребра расставлены следующим образом: если в графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex> есть ребро, то в графе <tex>H</tex> это ребро не проводится, если же в графе <tex>G</tex> между этими вершинами его не было, то в <tex>H</tex> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.
 
Существует функция <tex>f</tex> такая, что <tex>f(\langle G, k \rangle ) = \langle H, k \rangle </tex>, где <tex>H</tex> <math>-</math> граф, в котором столько же вершин, сколько и в <tex>G</tex>, а ребра расставлены следующим образом: если в графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex> есть ребро, то в графе <tex>H</tex> это ребро не проводится, если же в графе <tex>G</tex> между этими вершинами его не было, то в <tex>H</tex> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.

Версия 20:31, 14 марта 2010

Определение

Язык [math]A\,\![/math] сводится по Карпу к языку [math]B\,\![/math], если существует функция [math]f(x)\,\![/math] такая, что [math]x \in A[/math] тогда и только тогда, когда [math]f(x) \in b[/math].

Обычно требуют, чтобы сводящая функция была вычислима за полиномиальное время от длины входа.

Пример

Рассмотрим следующие языки: [math]IND[/math] и [math]CLIQUE[/math] [math]--[/math] множества пар [math]\langle G, k \rangle [/math], где [math]G[/math] [math]--[/math] граф, [math]k[/math] [math]-[/math] натуральное число. Пара [math]\langle G, k \rangle [/math] принадлежит [math]IND[/math], если в графе [math]G[/math] есть подграф с [math]k[/math] вершинами, в котором все вершины не связаны ребрами. Пара [math]\langle G, k \rangle [/math] принадлежит [math]CLIQUE[/math], если в графе [math]G[/math] есть подграф с [math]k[/math] вершинами, в котором между каждой парой вершин проходит ребро.

Существует функция [math]f[/math] такая, что [math]f(\langle G, k \rangle ) = \langle H, k \rangle [/math], где [math]H[/math] [math]-[/math] граф, в котором столько же вершин, сколько и в [math]G[/math], а ребра расставлены следующим образом: если в графе [math]G[/math] между вершинами [math]u[/math] и [math]v[/math] есть ребро, то в графе [math]H[/math] это ребро не проводится, если же в графе [math]G[/math] между этими вершинами его не было, то в [math]H[/math] оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.

Заметим, что если в графе [math]G[/math] был независимый подграф с [math]k[/math] вершинами, то в [math]H[/math] между всеми вершинами подграфа будут ребра, следовательно, в графе [math]H[/math] будет клика с [math]k[/math] вершинами.

С другой стороны, если в [math]H[/math] есть клика с [math]k[/math] вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе [math]G[/math]. Т.о. в графе [math]G[/math] был независимый подграф с [math]k[/math] вершинами.

Из всего сказанного следует, что [math]IND \le CLIQUE[/math].