плоскость и матрицы (задача алгебраического программирования

[Galyna]

Всем привет!
У меня мимоходом возникла одна задачка. Никак не могу в ней разобраться. Может, кто что подскажет? Может, кто-то уже такое делал?

Вот предположим, что на плоскости у нас отмечено некоторое конечное количество точек. Эти точки мы можем перенумеровать. Теперь фиксируем некоторое $R$ и строим матрицу $A$: если расстояние между точками $i, j$ больше $R$, то $a_{ij}=0$, иначе $a_{ij}=1$.

Итак, по каждому набору точек и фиксированному "радиусу" мы можем построить матрицу.
Вопрос: для каких матриц возможна обратная процедура?

Это возможно отнють не для всех матриц.
1) если в фиксированном ряду не менее 7 единиц (включая диагональ) (пусть это в столбиках с1, с2, с3, с4, с5, с6 и тот, который пересекает ряд на диагонали), то существуют i и j (от 1 до 6 каждый), такие, что Асiсj = 1.

Заранее благодарна за любые соображения на этот счет...

[Руст]

Задача не простая и вряд ли можно дать необходимое и достаточное условие. Для небольших n (до 10) можно анализировать все варианты. Для больших n можно только разные необходимые условия составить. Очевидное необходимое условие - матрица симметричная и на диагонали 1. Если i,j,k попарно отдалены (т.е. все соответствующие элементы матриц равны 0), то все элементы n,m принадлежащие окружностям в точках i,j,k (т.е. a(i,n)=a(i,m)=a(j,n)=a(j,m)=a(k,m)=a(k,n)=1), то a(n,m)=1.

[Sasha Rybak]

Представляем точки в виде (x_1,y_1), ..., (x_n,y_n). Нам нужно проверить, есть ли набор (x_1,y_1,...,x_n,y_n), удовлетворяющий системе неравенств типа
$(x_i-x_j)^2+(y_i-y_j)^2>1$ или $(x_i-x_j)^2+(y_i-y_j)^2 \le 1$.
Замена R на 1 мало что меняет.

Это задача алгебраического программирования - обобщение задачи линейного программирования. Плохо, что есть строгие неравенства - придётся повозиться с окрестностями точек. Но это потом.
Сначала заменяем некоторое количество неравенств на равенства, чтобы количество решений было конечным, но при этом любая подвыборка равенств ещё не давала конечности - надо будет перебрать все такие выборки. Для каждой выборки проверяем, согласуется ли хотя-бы одно её решение с оставшимися неравенствами. Если да - проверяем, можно ли "пошевелить" решение, чтобы строгие неравенства, заменённые на равенства, снова стали строгими.
Системы алгебраических уравнений можно анализировать с помощью алгоритма Евклида (подробнее - в некоторых учебниках по алгебраической геометрии). Чтобы проверить, можно ли сделать неравенство строгим, нужно использовать производные в точках решений.

В общем, принципиальная алгоритмичность есть, но для реальных вычислений - легче повесицца.

А для прямой решать не пробовала?

[Galyna]

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