• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Сафронов Денис Сергеевич
Графы, гиперграфы и миноры их матриц инцидентности
8
2019
В данной работе представлена и исследована тема «Графы, гиперграфы и миноры их матриц инцидентности», её целью является изучение взаимосвязей между внешним видом матрицы и её определителем. Для этого исследования мы будем использовать возможности программирования на языке C++ и библиотеку uBLAS. На начальном этапе мы сделали некоторые прогнозы относительно будущих результатов, основываясь на выводах из наших двух предыдущих работ. Затем создали алгоритм, который осуществляет полный перебор, модернизировали его и сравнили полученные результаты с результатами, которые мы ожидали.

Как известно, одним из приоритетных направлений современной теории оптимизации является целочисленное линейное программирование и комбинаторная оптимизация. Задачи такого рода часто представляют собой вопросы максимизации или минимизации определенного линейного функционала на многограннике, определяемом системой линейных неравенств. Среди рассматриваемых задач мы можем выделить подкласс задач, многогранники которых определяются системами линейных неравенств с ограниченным спектром миноров. В своей статье J. W. Grossman рассматривает взаимосвязь между спектром миноров для матриц инцидентности простых графов и структурой этих графов. Матрица инцидентности - это форма представления графа, в которой указываются связи между ребрами и вершинами. Столбцы матрицы инцидентности соответствуют ребрам, а строки - вершинам. Ненулевое значение в ячейке матрицы указывает на связь между соответствующими ребрами и вершинами. Результаты этой статьи помогают лучше понять структуру матриц и систем с ограниченным спектром миноров. Гиперграф - это обобщение обычного графа, ребра которого могут содержать не только два элемента, но и любые подмножества вершин. Такие объекты давно известны в математике, но термин «гиперграф» был введен в связи с успешным распространением на них многих понятий и методов теории обыкновенных графов.

Цель исследования - сформулировать и описать минорные характеристики матриц инцидентности некоторых классов гиперграфов. Данное исследование является актуальным, поскольку оно находит применение в теории задач целочисленного линейного программирования, которая является важной частью современной теории оптимизации. Особое внимание будет уделено классам унициклических гиперграфов, гиперграфов, генерируемых циркулянтами особого типа, и гиперграфов с числом упаковки циклами равным 1. В особенности, их минимальным и максимальным минорам. Основная цель - попытаться применить методы и результаты, изученные в предыдущих работах к более широкому классу задач.
Текст работы (работа добавлена 22 мая 2019г.)

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

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

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

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

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

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