Раздел матроида

Прямая сумма однородных матроидов

В математике матроид разделов или матроид разделов — это матроид , который является прямой суммой однородных матроидов . [1] Он определяется над базовым набором, в котором элементы разделены на различные категории. Для каждой категории существует ограничение емкости — максимальное количество разрешенных элементов из этой категории. Независимые наборы матроида разделов — это в точности те наборы, в которых для каждой категории количество элементов из этой категории не превышает емкость категории.

Формальное определение

Пусть будет набором непересекающихся множеств («категорий»). Пусть будут целыми числами с («емкостями»). Определим подмножество как «независимое», когда для каждого индекса , . Множества, удовлетворяющие этому условию, образуют независимые множества матроида , называемого матроидом разбиения . С я {\displaystyle C_{i}} г я {\displaystyle d_{i}} 0 ≤ г я ≤ | С я | {\displaystyle 0\leq d_{i}\leq |C_{i}|} я ⊂ ⋃ я С я {\displaystyle I\subset \bigcup _{i}C_{i}} я {\displaystyle я} | я ∩ С я | ≤ г я {\displaystyle |I\cap C_{i}|\leq d_{i}}

Множества называются категориями или блоками матроида разбиения. С я {\displaystyle C_{i}}

Базис матроида разбиения — это множество, пересечение которого с каждым блоком имеет размер ровно . Контур матроида — это подмножество одного блока с размером ровно . Ранг матроида равен . [2] С я {\displaystyle C_{i}} г я {\displaystyle d_{i}} С я {\displaystyle C_{i}} г я + 1 {\displaystyle d_{i}+1} ∑ г я {\displaystyle \sum d_{i}}

Каждый однородный матроид является матроидом раздела с одним блоком элементов и с . Каждый матроид раздела является прямой суммой набора однородных матроидов, по одному для каждого из его блоков. У н г {\displaystyle U{}_{n}^{r}} С 1 {\displaystyle C_{1}} н {\displaystyle n} г 1 = г {\displaystyle d_{1}=r}

В некоторых публикациях понятие матроида раздела определяется более строго, с каждым . Разделы, которые подчиняются этому более строгому определению, являются трансверсальными матроидами семейства непересекающихся множеств, заданных их блоками. [3] г я = 1 {\displaystyle d_{i}=1}

Характеристики

Как и в случае с однородными матроидами, из которых они образованы, дуальный матроид матроида раздела также является матроидом раздела, и каждый минор матроида раздела также является матроидом раздела. Прямые суммы матроидов раздела также являются матроидами раздела.

Соответствие

Максимальное соответствие в графе — это набор ребер, который является максимально большим при условии, что никакие два ребра не имеют общей конечной точки. В двудольном графе с двудольностью наборы ребер, удовлетворяющие условию, что никакие два ребра не имеют общей конечной точки в , являются независимыми наборами матроида разбиения с одним блоком на вершину в и с каждым из чисел, равным единице. Наборы ребер, удовлетворяющие условию, что никакие два ребра не имеют общей конечной точки в , являются независимыми наборами второго матроида разбиения. Следовательно, двудольная задача максимального соответствия может быть представлена ​​как пересечение матроидов этих двух матроидов. [4] ( У , В ) {\displaystyle (U,V)} У {\displaystyle U} У {\displaystyle U} г я {\displaystyle d_{i}} В {\displaystyle V}

В более общем смысле паросочетания графа могут быть представлены как пересечение двух матроидов тогда и только тогда, когда каждый нечетный цикл в графе является треугольником, содержащим две или более вершин степени два. [5]

Клика комплексов

Кликовый комплекс — это семейство множеств вершин графа , которые индуцируют полные подграфы графа . Кликовый комплекс образует матроид тогда и только тогда, когда — полный многодольный граф , и в этом случае полученный матроид является матроидом разбиения. Кликовые комплексы — это в точности системы множеств, которые могут быть образованы как пересечения семейств матроидов разбиения, для которых каждый . [6] Г {\displaystyle G} Г {\displaystyle G} Г {\displaystyle G} г я = 1 {\displaystyle d_{i}=1}

Перечисление

Число различных матроидов разделов, которые можно определить по набору помеченных элементов, для , равно н {\displaystyle n} н = 0 , 1 , 2 , … {\displaystyle n=0,1,2,\точки}

1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (последовательность A005387 в OEIS ).

Экспоненциальная производящая функция этой последовательности равна . [7] ф ( х ) = опыт ⁡ ( е х ( х − 1 ) + 2 х + 1 ) {\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}

Ссылки

  1. ^ Рецки, А. (1975), «О матроидах с разделами с приложениями», Бесконечные и конечные множества (Colloq., Keszthely, 1973; посвящено П. Эрдешу в день его 60-летия), Vol. III , коллок. Математика. Соц. Янош Бояи, том. 10, Амстердам: Северная Голландия, стр. 1169–1179, MR  0389630..
  2. ^ Лоулер, Юджин Л. (1976), Комбинаторная оптимизация: сети и матроиды , Райнхарт и Уинстон, Нью-Йорк: Холт, стр. 272, MR  0439106.
  3. ^ Например, см. Kashiwabara, Okamoto & Uno (2007). Lawler (1976) использует более широкое определение, но отмечает, что ограничение полезно во многих приложениях. г я = 1 {\displaystyle d_{i}=1}
  4. ^ Пападимитриу, Христос Х.; Стейглиц , Кеннет (1982), Комбинаторная оптимизация: алгоритмы и сложность , Энглвуд Клиффс, Нью-Джерси: Prentice-Hall Inc., стр. 289–290, ISBN 0-13-152462-3, МР  0663728.
  5. ^ Фекете, Шандор П.; Фирла, Роберт Т.; Шпилле, Бьянка (2003), «Характеристика сопоставлений как пересечения матроидов», Математические методы исследования операций , 58 (2): 319–329, arXiv : math/0212235 , doi :10.1007/s001860300301, MR  2015015.
  6. ^ Кашивабара, Кендзи; Окамото, Ёсио; Уно, Такеаки (2007), «Матроидное представление кликовых комплексов», Discrete Applied Mathematics , 155 (15): 1910–1929, doi : 10.1016/j.dam.2007.05.004 , MR  2351976. Для тех же результатов в дополнительной форме с использованием независимых множеств вместо клик см. Тышкевич, Р.И .; Урбанович, О.П.; Зверович, И. Э. (1989), "Матроидальное разложение графа", Комбинаторика и теория графов (Варшава, 1987) , Banach Center Publ., т. 25, Варшава: PWN, стр. 195–205, MR  1097648.
  7. ^ Рецки, А. (1974), «Перечисление раздельных матроидов», Studia Scientiarum Mathematicarum Hungarica , 9 : 247–249 (1975), MR  0379248.
Получено с "https://en.wikipedia.org/w/index.php?title=Partition_matroid&oldid=1054177024"