Графы, гиперграфы и миноры их матриц инцидентности

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