Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «ЗАПИСЬ СВОЙСТВА СУЩЕСТВОВАНИЯ ИЗОМОРФНОГО ПОДГРАФА НА ЯЗЫКЕ ПЕРВОГО ПОРЯДКА, "Доклады Академии наук"»

Авторы:
  • Жуковский М.Е.1
стр. 256-259
Платно
1 125047 Москва, Миусская пл., 4, ИПМ РАН
Аннотация:
Пусть S(F) - свойство содержать подграф, изоморфный графу F. Несложно показать, что это свойство нельзя записать на языке первого порядка с помощью формулы, кванторная глубина которой меньше, чем число вершин графа F. То же самое можно сказать и про количество переменных формулы, записывающей такое свойство. Тем не менее в некоторых классах графов кванторную глубину и число переменных формулы первого порядка, записывающей свойство S(F), удаётся уменьшить. В настоящей работе мы рассматриваем три класса графов: связные графы большого размера, графы с большой древесной шириной и графы с большой связностью.

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.