|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Решение задачи об описательной сложности изоморфизма подграфа
с помощью кнезеровских графов
В. А. Вороновa, Е. А. Дергачевb, М. Е. Жуковскийc, А. М. Неопрятнаяb a Кавказский математический центр, Адыгейский государственный университет, г. Майкоп
b Адыгейский государственный университет, г. Майкоп
c Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный
Аннотация:
В работе изучается задача нахождения наименьшего числа
переменных формулы первого порядка, записывающей свойство
input-графа содержать подграф, изоморфный заданному pattern-графу.
Рассматриваются input-графы, имеющие достаточно большую связность.
Ранее эта задача была решена для всех pattern-графов
с 4 вершинами, кроме двух – простого цикла и diamond-графа.
В настоящей работе мы нашли значение этой величины
для двух оставшихся графов.
Библиография: 8 названий.
Ключевые слова:
кнезеровские графы, input-графы, pattern-графы, игра Эренфойхта.
Поступило: 06.05.2020 Исправленный вариант: 23.06.2020
Образец цитирования:
В. А. Воронов, Е. А. Дергачев, М. Е. Жуковский, А. М. Неопрятная, “Решение задачи об описательной сложности изоморфизма подграфа
с помощью кнезеровских графов”, Матем. заметки, 109:1 (2021), 36–46; Math. Notes, 109:1 (2021), 29–37
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm12784https://doi.org/10.4213/mzm12784 https://www.mathnet.ru/rus/mzm/v109/i1/p36
|
Статистика просмотров: |
Страница аннотации: | 288 | PDF полного текста: | 49 | Список литературы: | 39 | Первая страница: | 17 |
|