Гиперграфы: Выход за пределы попарных связей
Традиционная теория графов моделирует мир в виде парных отношений: дружба между двумя людьми, кабель между двумя серверами, дорога между двумя городами. Но что, если отношение связывает сразу три, четыре или сотню объектов одновременно? Например, несколько соавторов одной научной статьи или группа актеров в одном фильме. Для описания таких многомерных связей дискретная математика использует расширение классической теории — Гиперграфы.
Гиперграф — это обобщение графа, в котором ребро (называемое гиперребром) может соединять не ровно две вершины, а любое подмножество вершин произвольного размера. Визуально гиперребра часто рисуют как цветные множества (круги или овалы диаграммы Эйлера), охватывающие несколько точек-вершин.
Если все гиперребра в гиперграфе соединяют строго по k вершин, он называется k-однородным (обычный граф является 2-однородным гиперграфом).
В ИТ-индустрии гиперграфы являются идеальной математической моделью для двух огромных предметных областей:
- Проектирование микросхем (VLSI Design). В электронных цепях проводник (цепь питания или шина данных) редко соединяет только два контакта. Один провод часто припаян к выводам десятка различных микросхем. Топология материнской платы — это чистый гиперграф. Алгоритмы разбиения гиперграфов (Hypergraph Partitioning) используются для того, чтобы разрезать гигантскую электрическую схему на несколько физических чипов, минимизировав количество проводов, которые придется тянуть между этими чипами.
- Реляционные базы данных. Схему реляционной БД можно рассматривать как гиперграф, где атрибуты (столбцы) — это вершины, а таблицы (отношения) — гиперребра, объединяющие эти столбцы. Теория ациклических гиперграфов лежит в основе оптимизаторов сложных SQL-запросов (Join-операций).
Центральной задачей теории является поиск Трансверсали (Hitting Set) — минимального набора вершин, который "протыкает" (пересекает) абсолютно все гиперребра в гиперграфе. Эта задача является классической NP-полной. Однако благодаря концепции двойственности гиперграфов (если поменять местами роли вершин и ребер, мы получим двойственный гиперграф), многие задачи из теории множеств решаются через богатый алгебраический аппарат дробных гиперграфов и линейного программирования.
