2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 плоскость и матрицы (задача алгебраического программирования
Сообщение03.10.2007, 16:09 


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

Вот предположим, что на плоскости у нас отмечено некоторое конечное количество точек. Эти точки мы можем перенумеровать. Теперь фиксируем некоторое $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.

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

 Профиль  
                  
 
 
Сообщение03.10.2007, 18:22 
Заслуженный участник


09/02/06
4382
Москва
Задача не простая и вряд ли можно дать необходимое и достаточное условие. Для небольших 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.

 Профиль  
                  
 
 General idea
Сообщение04.10.2007, 13:29 
Аватара пользователя


08/06/07
52
Киев
Представляем точки в виде (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 мало что меняет. :)

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

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

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

 Профиль  
                  
 
 
Сообщение04.10.2007, 14:36 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group