Exact mathematical formulation for hyperedges portrayal of two-layer hypergraph in coopertion scheme

Abstract

Цель: решение задачи минимизации пересечения гиперребер при укладке двухслойного гиперграфа в точной постановке. Обсуждение: прорисовка ребер – заключительный этап метода Сугиямы для укладки направленного ациклического иерархического графа. В диаграммах потоков финансовых данных и схемах кооперации контрагентов при выполнении государственных и коммерческих проектов ребра обычно прорисовывают вертикальными или горизонтальными сегментами. При этом сам иерархический граф рассматривается как иерархический гиперграф, который отличается от обычного графа тем, что его ребра соединяют не две вершины различных слоев, а некоторое множество вершин (предков) верхнего слоя с некоторым множеством вершин (потомков) расположенных в нижних слоях. Для прорисовки гиперребер исходный гиперграф представляется в виде множества двухслойных подграфов, состоящих из двух соседних слоев, и задача визуализации гиперребер решается для каждого подграфа отдельно. Результаты: дана точная математическая постановка задачи минимизации пересечений гиперребер для представленных требований к прорисовке двухслойного гиперграфа, получены и проанализированы числовые результаты решения сформулированной задачи методом ветвей и границ.