О сложности распознавания некоторых классов геометрических графов Тихомиров, Михаил Игоревич

brief description

Тихомиров, Михаил Игоревич.
О сложности распознавания некоторых классов геометрических графов : диссертация ... кандидата физико-математических наук : 01.01.09 / Тихомиров Михаил Игоревич; [Место защиты: Мат. ин-т им. В.А. Стеклова. С.-Петерб. отд-ние РАН]. - Москва, 2016. - 65 с. : ил.
Оглавление диссертациикандидат наук Тихомиров, Михаил Игоревич
Оглавление
Введение
1 О сложности проверки дистанционной вложимости графов
в Rd при d > 2
1.1 Формулировка результата
1.2 Описание конструкции
1.3 Понятие стержня, свойства стержней
1.4 Построение стержней
1.5 Устройство конструкции
1.6 Обсуждение предыдущего доказательства
2 Автоморфизмы графов Кэли свободных конечно порожденных абелевых групп и их конечных подграфов
2.1 Определения
2.2 Понятия шара и вложения
2.3 Свойства вложений шаров в Г
2.4 Решетки из главных и неглавных элементов
2.5 Доказательство теоремы 2
3 О сложности проверки мультидистанционной вложимости графов в R1
3.1 Формулировка результатов
3.2 Случай G ~ Z, строгая и/или инъективная A-вложимость
3.3 Задача LOGIC-ENGINE
3.4 Выбор базиса в Zk
3.5 Конструкция для случая k = 2, строгая и/или инъективная A-вложимость
3.5.1 Описание конструкции
3.5.2 Соединения звеньев с осью и между собой
3.5.3 Стыковочные конструкции
3.5.4 Флажки и их крепления
3.5.5 Выбор параметров и анализ конструкции
3.6 Случай к > 2, строгая и/или инъективная А-вложимость
Заключение
Список литературы