НГУ

Форумы НГУ
Текущее время: Вт окт 15, 2019 3:57 pm

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




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: another one
СообщениеДобавлено: Пн авг 23, 2004 5:37 pm 
Не в сети
Частый гость

Зарегистрирован: Чт авг 19, 2004 1:32 am
Сообщения: 33
Откуда: безусловно настоящее имя
Попробую и я подкинуть задачку...

Какое наибольшее число пар элементов n-элементного множества может содержать антитранзитивное отношение на этом множестве? (Антитранзитивность означает невыполнение условия транзитивности ни на каких трёх (не обязательно различных) элементах.) Здесь n - натуральное число.

_________________
Если посмотреть сверху, то спьяну кажется, что снизу - это всё равно что сбоку.


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

Зарегистрирован: Чт авг 19, 2004 1:32 am
Сообщения: 33
Откуда: безусловно настоящее имя
Уточню определение. Отношение R на множестве A
назовём антитранзитивным, если для любых x,y,z
из A из того, что (x,y) в R и (y,z) в R, следует, что
(x,z) не в R.
Т.е. под "невыполнением условия транзитивности",
конечно, не понималось выполнение отрицания
этого условия.

_________________
Если посмотреть сверху, то спьяну кажется, что снизу - это всё равно что сбоку.


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

Зарегистрирован: Чт авг 19, 2004 1:32 am
Сообщения: 33
Откуда: безусловно настоящее имя
Видимо, неинтересная задача, однако...

А если добавить условие симметричности?

_________________
Если посмотреть сверху, то спьяну кажется, что снизу - это всё равно что сбоку.


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

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Если добавить условие симметричности, то решать будет почти нечего, поскольку задача сведётся к известной задаче о максимальном числе рёбер в графе без треугольников с n вершинами (легко доказать, что петель там тоже нет). Ответ будет \lfloor n^2/4 \rfloor, где \lfloor t \rfloor --- это наибольшее целое число, не превосходящее t.


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

Зарегистрирован: Чт авг 19, 2004 1:32 am
Сообщения: 33
Откуда: безусловно настоящее имя
Правильно. Только на 2 умножить забыли :)))

_________________
Если посмотреть сверху, то спьяну кажется, что снизу - это всё равно что сбоку.


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

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Я сообщил ответ к задаче, к которой сводится исходная. А в исходной действительно на два надо ещё умножить.


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

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


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

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


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

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