name: Минимальные расширения цветных графов
keyword_list: отказы связей отказы элементов отказоустойчивость изоморфизм графов реберные расширения графов вершинные расширения графов минимальные расширения графов раскраски графов цветные графы
abstract: В работе предложены новые алгоритмы построения попарно-неизоморфных цветных реализаций заданных графов, а также алгоритмы построения минимальных вершинных и реберных расширений заданных цветных графов. Кроме того, в работе представлены схемы построения минимальных вершинных расширений для цветных графов и минимальных вершинных и реберных расширений для цветных звезд с доказательствами корректности схем построения. Основным характеристическим свойством изучаемых задач является раскраска графов. В основе алгоритмов разработан подход, который позволяет производить построение неизоморфных цветных реализаций графов и их минимальных расширений без проверки на изоморфизм графов. Основным результатом работы стало решение аналитическим путем задач построения минимальных вершинных расширений для цветных полных графов и построения минимальных вершинных и реберных расширений для цветных звезд. Полученные результаты согласуются с известными решениями для простых непомеченных графов. В случае цветных полных графов, было выявлено, что задача о построении минимального вершинного расширения для простых непомеченных полных графов является частным случаем задачи построения минимального вершинного расширения для цветных полных графов.
chairman_dissertation_council.name: Роман
chairman_dissertation_council.surname: Стронгин
chairman_dissertation_council.patronymic: Григорьевич
chairman_dissertation_council.position: Президент ННГУ, заведующий кафедрой
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: A-4743-2017
chairman_dissertation_council.scopus_author_id: 7006796582
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Михаил
organization_supervisor.surname: Иванченко
organization_supervisor.patronymic: Васильевич
organization_supervisor.position: Проректор по научной работе
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Абросимов М.Б.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Бредихин Д.А.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
opponents.fio: Жуковский М.Е.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Теоретические основы информатики
opponents.responsible_type: Оппонент
protection_organization.short_name: НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО, НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО, ННГУ ИМ. Н.И. ЛОБАЧЕВСКОГО, УНИВЕРСИТЕТ ЛОБАЧЕВСКОГО, ННГУ
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО"
protection_organization.ogrn: 1025203733510
protection_organization.supervisor_name: ЕЛЕНА
protection_organization.supervisor_surname: ЗАГАЙНОВА
protection_organization.supervisor_patronymic: ВАДИМОВНА
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: ФГБОУ ВО "СГУ имени Н.Г.Чернышевского", Саратовский университет, СГУ
author_organization.name: Федеральное государственное бюджетное образовательное учреждение высшего образования "Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского"
author_organization.ogrn: 1026402674935
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения