НГУ

Форумы НГУ
Текущее время: Вс фев 25, 2018 10:43 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
СообщениеДобавлено: Чт июн 30, 2005 7:45 pm 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Пусть дана матрица
(a_1, a_2 \\ b_1, b_2), все больше нуля
Рассмотрим вектор (b_1/a_1, b_2/a_2) – назовем его вектором сравнения строк a и b. Возможны три варианта:
b_1/a_1 < b_2/a_2, b_1/a_1 = b_2/a_2, b_1/a_1 > b_2/a_2. Для упрощения предположим (и здесь, и везде далее), что равенство в таких сравнениях никогда не возникает. Т.о., остается 2 варианта.
Но! Пусть ситуация такова, что порядок строк на самом деле не важен, т.е. строки можно переставить и переименовать переменные. Тогда легко понять, что варианты "<" и ">" эквивалентны с точностью до перестановки. Т.е., в этом смысле любые наборы четырех вещественых чисел эквивалентны (напомним, что варианты равенства не рассматриваются).
Предположим далее, что нумерация столбцов тоже не важна.

Теперь усложним задачу – рассмотрим матрицу 3х3.
(a_1, a_2, a_3 \\ b_1, b_2, b_3 \\ c_1, c_2, c_3)
Здесь возникает уже три вектора сравнений – для каждой пары строк. Соответственно, интересующий вопрос – сколько существует классов таких девяток, что девятки из разных классов друг к другу не сводятся с помощью перестановок строк и перенумераций. Также весьма интересны вопросы о какой-то характеризации этих классов. Например, хорошо бы найти какие-то достаточные условия того, что две матрицы (не) лежат в одном классе, не перибирая всевозможных вариантов преобразований.

Формально этот дело записывается так. Для каждой пары строк рассматриваем вектор сравнений. Т.к. равенств нет, то вектор можно однозначно упорядочить и представить это упорядочение подстановкой (k_1 k_2 k_3) – число k_i означает место i-го элемента вектора сравнений по порядку. В матрице имеется 3 пары строк, т.о. имеем три подстановки. Т.е. любые отношения 9-ток чисел представляются в виде 3-х подстановок. Вспоминая о том, что можно произвольно перенумеровать элементы, можно считать, что перестановка, отвечающая за первую пару суть тождественная, т.е.
b_1/a_1 < b_2/a_2 < b_3/a_3. Тогда варьируются только 2 подстановки упорядочения (для 2 и 3 строк, и для 1 и 3).

Наборы из трех подстановок будем называть триплетами. Не всякий триплет “реализуется” на некоторой матрице 3x3. Критерий следующий – если номер k_1 предшествует номеру k_2 одновременно в триплете для 1 и 2 строк, и в триплете для 2 и 3 строки, то в таком же порядке они должны находится и в триплете для 1 и 3 строки.
Такие триплеты назовем допустимыми.

В ходе выч. экспериментов выяснилось, что для матриц 3х3 допустимых триплетов 17 (всего 6x6=36) при фиксированном первом.
Они разбиваются на 5 классов, число элементов в которых (3,6,6,1,1). То есть результат абсолютно не очевидный, что наводит на мысль о том, что поставленные вопросы не бессодержательны.
Соответственно, хорошо бы обобщить все это дело на ситуацию матриц n x m.

У меня такое ощущение, что эта проблематика может где-то (т.е. в какой-то области математики) детально изучаться – т.к. дело касается достаточно общих закономерностей среди вещ. чисел. Если кто-то с этим сталкивался или знает таких людей – буду весьма признателен.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт июл 01, 2005 12:53 pm 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Да, забыл сказать, что данная задача проистекла из моделирования некоторых реальных процессов.

В общем виде формулировка такая. Рассматриваем множество P наборов подстановок (длина подстановки n) с m(m-1)/2 элементами для некоторого фиксированного m. При этом элементы в таком наборе обозначаеются как x_ij, где i<j<=m. (При этом принимается соглашение, что через x_ji обозначается x_ij, прочитанная наоборот). На множестве P заданы две операции.
1) Преобразование перенумерования через подстановку t (обозначим как N^t:P \to P): N^t(x)_ij=(tx)_ij – т.е. каждый элемент набора х умножается слева на t.
2) Преобразование переименования через подстановку s (обозначим как M^s:P \to P): M^s(x)_ij=x_s(i)s(j).

Преобразования N^t и M^s, очевидно, коммуцируют. На множестве P задается отношение эквивалентности: x~y, если существуют такие t,s, что x=M^s(N^t(y)).

Кроме того, определим подмножество допустимых наборов P_0. Набор назвается допустимым, если для любой пары x_ij, x_jk (не обязательно i<j, j<k) из того, что p предшествует q в x_ij и x_jk, следует, что p предшествует q в x_ik.
Формально: ((x_ij^(-1)(p)) < x_ij^(-1)(q)) & (x_jk^(-1)(p) < x_jk^(-1)(q))) \to (x_ik^(-1)(p) < x_ik^(-1)(q)).
P_0 замкнуто относительно операций перенумерования и переименования.

Интересует вопрос о том, что можно сказать о классах эквивалентности (как в P, так и в P_0) – например, найти достаточные условия принадлежности или непринадлежности двух наборов одному классу


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: изоморфизм графов
СообщениеДобавлено: Вт июл 26, 2005 4:50 pm 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Vova Chuma писал(а):
Рассматриваем множество P наборов подстановок (длина подстановки n) с m(m-1)/2 элементами для некоторого фиксированного m. При этом элементы в таком наборе обозначаеются как x_ij, где i<j<=m. (При этом принимается соглашение, что через x_ji обозначается x_ij, прочитанная наоборот). На множестве P заданы две операции.
1) Преобразование перенумерования через подстановку t (обозначим как N^t:P \to P): N^t(x)_ij=(tx)_ij – т.е. каждый элемент набора х умножается слева на t.
2) Преобразование переименования через подстановку s (обозначим как M^s:P \to P): M^s(x)_ij=x_s(i)s(j).

Преобразования N^t и M^s, очевидно, коммуцируют. На множестве P задается отношение эквивалентности: x~y, если существуют такие t,s, что x=M^s(N^t(y)).


Задача об эквивалентности на множестве P не проще задачи об изоморфизме графов.
Рассмотрим задачу об изоморфизме графов в такой форме: даны две матрицы (смежности) A1 и A2 размера mxm из элементов {0,1}, существуют ли перестановки строк и столбцов переводящие A1 в A2?

Зафиксируем две подстановки на множестве из n элементов: u - четная, v - нечетная. По заданной матрице A размера mxm определим множество наборов подстановок
x(A) = { x_ij = u, если A_ij = 0; x_ij = v, если A_ij = 1 }.
Вопрос: эквивалентны ли x(A1) и x(A2)?

Легко видеть, что если x(A1) и x(A2) эквивалентны, то исходные графы изоморфны (за исключением случая, когда число нулей в A1, A2 равно числу единиц - в этом случае один граф может быть изоморфен дополнению другого), и наоборот.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 01, 2005 11:09 pm 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Спасибо за ответ!

Объясните, пожалуйста, подробнее – пусть x(A1) ~ x(A2) через M^s и N^t. Как из подстановок s и t получить подcтановку для соответствующего перенумерования вершин в графе?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 02, 2005 1:28 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Vova Chuma писал(а):
Объясните, пожалуйста, подробнее – пусть x(A1) ~ x(A2) через M^s и N^t. Как из подстановок s и t получить подcтановку для соответствующего перенумерования вершин в графе?

Пусть количество нулей и единиц в матрицах различны. Тогда если x(A1) ~ x(A2), то подстановка t обязана быть тождественной, а подстановка s как раз и дает искомую подстановку строк и стобцов, переводящую одну матрицу смежности в другую.
Если количества нулей и единиц равны, то возможен еще случай t=u^(-1)v=v^(-1)u (т.е. tu=v и tv=u). В этом случае подстановка s будет переводить одну матрицу смежности в дополнение другой.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 02, 2005 11:45 am 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Maxal, боюсь, Вы немного неправы. Думаю, ошибка в следующем - преобразование М^s не просто перемешивает элементы набора, а действует немного сложнее. Пусть мы хотим заполнить элемент y_ij (i<j), где y=M^s(x). Если s(i)<s(j), то элемент получает ту же подстановку, что была в x_s(i)s(j). Но если s(i)>s(j), y_ij получает подстановку x_s(j)s(i), прочитанную наоборот (= Inv*x_s(j)s(i), где Inv = (n ... 1)). Такое преобразование суть перестановка строк исходной матрицы – см. пост №1.

Поэтому, если t – тождественная подстановка, а s – не тождественная, то преобразование M^s(N^t) обязательно перевернет хотя бы одну подстановку в наборе, и эквивалентности не получится.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 02, 2005 12:44 pm 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Хотя в общем-то можно взять v = Inv*u.. Но четность Inv зависит от n.. Как-то все равно не ясно. Собсна, я также не очень понял, в чем был смысл брать именно четную и нечетную подстановки, объясните пожалуйста..

Ну и в любом случае вопрос – а что можно сказать о решении задачи об изоморфизме графов?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 02, 2005 1:48 pm 
Изоморфизм графов -- открытая задача.

В смысле имея два графа, за полиномиальное время выдать изоморфны они или нет.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 03, 2005 6:53 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
Vova Chuma писал(а):
Maxal, боюсь, Вы немного неправы. Думаю, ошибка в следующем - преобразование М^s не просто перемешивает элементы набора, а действует немного сложнее. Пусть мы хотим заполнить элемент y_ij (i<j), где y=M^s(x). Если s(i)<s(j), то элемент получает ту же подстановку, что была в x_s(i)s(j). Но если s(i)>s(j), y_ij получает подстановку x_s(j)s(i), прочитанную наоборот (= Inv*x_s(j)s(i), где Inv = (n ... 1)). Такое преобразование суть перестановка строк исходной матрицы – см. пост №1.


Все нормально. Матрицы смежности являются симметричными, а поэтому x_{s(i)s(j)} = x_{s(j)s(i)} и отношение между s(i) и s(j) нас не волнуют. Нас волнуют именно перестановки строк/столбцов, задающие изоморфизм графов.

Vova Chuma писал(а):
Собсна, я также не очень понял, в чем был смысл брать именно четную и нечетную подстановки, объясните пожалуйста..

Особого смысла действительно нет. Достаточно, чтобы u и v были неравными.

По поводу изоморфизма графов - см. http://en.wikipedia.org/wiki/Graph_isomorphism_problem


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 29, 2005 5:58 pm 
Не в сети
Опытный автор

Зарегистрирован: Вс мар 28, 2004 9:08 pm
Сообщения: 447
Прошу извинения за длительную задержку.

Уважаемый Maxal! Очень признателен Вам за подробное обсуждение этой задачи, но я все-таки пока не понял до конца Вашего рассуждения (хотя оно кажется правдоподобным и, вероятно, дело действительно обстоит именно так, как Вы говорите). Смотрите, вот Вы написали:
Maxal писал(а):
Все нормально. Матрицы смежности являются симметричными, а поэтому x_{s(i)s(j)} = x_{s(j)s(i)} и отношение между s(i) и s(j) нас не волнуют. Нас волнуют именно перестановки строк/столбцов, задающие изоморфизм графов.

Дело в том, что просто в определении действия преобразования M^s(x) используется тот факт, что x_ji равно по определению Inv*x_ij, т.е. x_ij, прочитанной наоборот. Это – нотационное соглашение, т.е. независимо задаются только те x_ij, для которых i<j. Поэтому равенство
x_{s(i)s(j)} = x_{s(j)s(i)}
невозможно в принципе.
Так что пока не могу быть уверенным, что Вы правы. Напишите, пожалуйста, более подробно обоснование того, что x(A1)~x(A2) -> A1~A2


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB