• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Сироткин Дмитрий Валерьевич
Методы редукции графов и их приложения
10
2019
Задача о независимом множестве для заданного графа состоит в том, чтобы найти размер наибольшего множества его попарно несмежных вершин. Известны многочисленные случаи NP-трудности и случаи полиномиальной разрешимости этой задачи. Для установления вычислительного статуса задачи о независимом множестве в рассматриваемом классе графов часто используются локальные преобразования графов. В данной работе рассматривается некоторый класс замен подграфов в графах, причем замены из этого класса изменяют число независимости контролируемым образом. Каждое такое локальное преобразование графов определяется некоторым шаблоном ——- совокупностью подмножеств множества. Очевидно, что совокупность должна быть градуируемой. Показывается, что заменяющий подграф существует для любого градуируемого шаблона. Этот результат вносит вклад в алгоритмическую теорию графов и в теорию построения графов с заданными свойствами.
Текст работы (работа добавлена 23 мая 2019г.)

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

ВКР являются объектами авторских прав, на их использование распространяются ограничения, предусмотренные законодательством Российской Федерации об интеллектуальной собственности.

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР