Дельта-матроид - Delta-matroid

В математике дельта-матроид или же Δ-матроид это семейство наборов подчиняясь аксиоме обмена, обобщающей аксиому матроиды. Непустое семейство множеств является дельта-матроидом, если для каждых двух множеств ${ displaystyle E}$ и ${ displaystyle F}$ в семье и для каждого элемента ${ displaystyle e}$ в их симметричная разница ${ Displaystyle E треугольник F}$, существует ${ displaystyle f in E треугольник F}$ такой, что ${ Displaystyle E треугольник {е, f }}$ находится в семье. Для базисных наборов матроида соответствующая аксиома обмена требует дополнительно, чтобы ${ displaystyle e in E}$ и ${ displaystyle f in F}$, гарантируя, что ${ displaystyle E}$ и ${ displaystyle F}$ имеют одинаковую мощность. Для дельта-матроида любой из двух элементов может принадлежать любому из двух наборов, и также допускается, чтобы эти два элемента были равными.^[1]Альтернативное и эквивалентное определение состоит в том, что семейство множеств образует дельта-матроид, когда выпуклый корпус своего индикаторные векторы (аналог матроидный многогранник ) обладает тем свойством, что каждая длина ребра равна единице или квадратный корень из двух.

Дельта-матроиды были определены Андре Буше в 1987 году.^[2]Алгоритмы для пересечение матроидов и проблема четности матроидов можно распространить на некоторые случаи дельта-матроидов.^[3][4]

Дельта-матроиды также использовались для изучения проблемы удовлетворения ограничений.^[5] В частном случае даже дельта-матроид является дельта-матроидом, в котором либо все наборы имеют четное число элементов, либо все наборы имеют нечетное число элементов. Если проблема удовлетворения ограничений имеет Логическая переменная на каждом ребре плоского графа, и если переменные ребер, инцидентных каждой вершине графа, ограничены принадлежностью четному дельта-матроиду (возможно, другому четному дельта-матроиду для каждой вершины), тогда проблема может быть решено в полиномиальное время. Этот результат играет ключевую роль в характеристике плоских задач удовлетворения логических ограничений, которые могут быть решены за полиномиальное время.^[6]

Рекомендации