Полиматроид

редактировать

В математике полиматроид - это многогранник, связанный с субмодульной функцией . Это понятие было введено Джеком Эдмондсом в 1970 году. Оно также описывается как мультимножество аналог матроида .

Содержание

1 Определение
- 1.1 эквивалентное определение
2 Отношение к матроидам
3 Отношение к обобщенным пермутаэдрам
4 Свойства
5 Контраполиматроиды
6 Дискретные полиматроиды
7 Ссылки

Определение

Пусть $E {\ displaystyle E}$ $E$ быть конечным набором и $f: 2 E → R + {\ displaystyle f: 2 ^ {E} \ rightarrow \ mathbb { R} _ {+}}$ ${\ displaystyle f: 2 ^ {E} \ rightarrow \ mathbb {R} _ {+}}$ неубывающая субмодульная функция, то есть для каждого $A ⊆ B ⊆ E {\ displaystyle A \ substeq B \ substeq E}$ ${\ displaystyle A \ substeq B \ substeq E}$ у нас есть $f (A) ≤ f (B) {\ displaystyle f (A) \ leq f (B)}$ ${\ displaystyle f (A) \ leq f (B)}$ , и для каждого $A, B ⊆ E {\ displaystyle A, B \ substeq E}$ ${\ displaystyle A, B \ substeq E}$ мы имеем $f (A) + f (B) ≥ f (A ∪ B) + f (A ∩ B) {\ displaystyle f (A) + f (B) \ geq f (A \ cup B) + f (A \ cap B)}$ ${\ displaystyle f (A) + f (B) \ geq f (A \ чашка B) + f (A \ cap B)}$ . Мы определяем полиматроид, связанный с $f {\ displaystyle f}$ $f$ , как следующий многогранник :

$P f: = {x ∈ R + E | ∑ е ∈ U Икс (е) ≤ е (U), ∀ U ⊆ E} {\ displaystyle P_ {f}: = \ left \ {{\ textbf {x}} \ in \ mathbb {R} _ {+} ^ {E} ~ | ~ \ sum _ {e \ in U} {\ textbf {x}} (e) \ leq f (U), \ forall U \ substeq E \ right \}}$ ${\ displaystyle P_ {f}: = \ left \ {{\ textbf {x}} \ in \ mathbb {R} _ {+} ^ {E} ~ | ~ \ sum _ {e \ in U} { \ textbf {x}} (e) \ leq f (U), \ forall U \ substeq E \ right \}}$ .

Когда мы разрешаем записи $x {\ displaystyle {\ textbf {x}}}$ ${\ displaystyle {\ textbf {x}}}$ , чтобы быть отрицательными, мы обозначаем этот многогранник $EP f {\ displaystyle EP_ {f}}$ $EP_ {f}$ и назовите его расширенным полиматроидом, связанным с $f {\ displaystyle f}$ $f$ .

Эквивалентным определением

. Пусть $E {\ displaystyle E}$ $E$ будет конечным установить и $u, v ∈ RE {\ displaystyle {\ textbf {u}}, {\ textbf {v}} \ in \ mathbb {R} ^ {E}}$ ${\ displaystyle {\ textbf {u}}, {\ textbf {v}} \ in \ mathbb {R} ^ {E}}$ . Мы называем модуль $u {\ displaystyle {\ textbf {u}}}$ ${\ textbf {u}}$ суммой всех его записей и обозначаем $u ≤ v {\ displaystyle {\ textbf {u}} \ leq {\ textbf {v}}}$ ${\ displaystyle {\ textbf {u}} \ leq { \ textbf {v}}}$ всякий раз, когда $vi - ui ≥ 0 {\ displaystyle v_ {i} -u_ {i} \ geq 0}$ ${\ displaystyle v_ {i} -u_ { i} \ geq 0}$ для каждого $i ∈ E {\ displaystyle i \ in E}$ ${\ displaystyle i \ in E}$ (обратите внимание, что это дает порядок на $R + E {\ displaystyle \ mathbb {R } _ {+} ^ {E}}$ ${\ displaystyle \ mathbb {R} _ {+} ^ {E}}$ ). полиматроид на наземном множестве $E {\ displaystyle E}$ $E$ представляет собой непустое компактное подмножество $P {\ displaystyle P}$ $P$ в $R + E {\ displaystyle \ mathbb {R} _ {+} ^ {E}}$ ${\ displaystyle \ mathbb {R} _ {+} ^ {E}}$ , набор независимых векторов, таких что:

У нас есть это, если $v ∈ P {\ displaystyle {\ textbf {v}} \ in P}$ ${\ displaystyle {\ textbf {v}} \ в P}$ , тогда $u ∈ P {\ displaystyle {\ textbf {u}} \ in P}$ ${\ displaystyle {\ textbf {u}} \ in P}$ для каждого $u ≤ v {\ displaystyle {\ textbf {u}} \ leq {\ textbf {v}}}$ ${\ displaystyle {\ textbf {u}} \ leq { \ textbf {v}}}$ :
Если $u, v ∈ P {\ displaystyle {\ textbf {u}}, {\ textbf {v}} \ in P}$ ${\ displaystyle {\ textbf {u}}, {\ textbf {v}} \ in P}$ с $| v |>| u | {\ displaystyle | {\ textbf {v}} |>| {\ textbf {u}} |}$ $|{\textbf {v}}|>| {\ textbf {u}} |$ , то есть вектор $w ∈ P {\ displaystyle w \ in P}$ ${\ displaystyle w \ in P }$ таким образом, что $u < w ≤ ( max { u 1, v 1 }, …, max { u | E |, v | E | }) {\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{u_{1},v_{1}\},\dots,\max\{u_{|E|},v_{|E|}\})}$ ${\ displaystyle {\ textbf {u}} <{\ textbf {w}} \ leq (\ max \ {u_ {1}, v_ {1} \}, \ точки, \ макс \ {u_ {| E |}, v_ {| E |} \})}$ .

Это определение эквивалентно описанному ранее, где $f {\ displaystyle f}$ $f$ - функция, определенная как $f (A) = макс {∑ i ∈ A v (i) | v ∈ P} {\ displaystyle f (A) = \ max \ left \ {\ sum _ {i \ in A} {\ textbf {v}} (i) ~ | ~ {\ textbf {v}} \ in P \ right \}}$ ${\ dis стиль игры е (А) = \ макс \ влево \ {\ сумма _ {я \ in A} {\ textbf {v}} (я) ~ | ~ {\ textbf {v}} \ in P \ right \}}$ для каждого $A ⊂ E {\ displaystyle A \ subset E}$ ${\ displaystyle A \ subset E}$ .

Связь с матроидами

С каждым матроидом $M {\ displaystyle M}$ $M$ на наземном наборе $E {\ displaystyle E}$ $E$ мы можем связать набор $PM = {w F | F ∈ M} {\ displaystyle P_ {M} = \ {{\ textbf {w}} _ {F} ~ | ~ F \ in M \}}$ ${\ displaystyle P_ {M} = \ {{\ textbf {w}} _ {F} ~ | ~ F \ in M \}}$ , где для каждого $i ∈ E {\ displaystyle i \ in E}$ ${\ displaystyle i \ in E}$ мы имеем, что

$w F (i) = {1, i ∈ F; 0, i ∉ F. {\ d isplaystyle {\ textbf {w}} _ {F} (я) = {\ begin {case} 1, i \ in F; \\ 0, i \ not \ in F. \ end {cases}}}$ ${\ displaystyle {\ textbf {w}} _ {F} ( я) = {\ begin {cases} 1, i \ in F; \\ 0, i \ not \ in F. \ end {cases}}}$

Взяв выпуклую оболочку $PM {\ displaystyle P_ {M}}$ ${\ displaystyle P_ {M}}$ , мы получим полиматроид в смысле второго определения, связанный с функцией ранга $M {\ displaystyle M}$ $M$ .

Связь с обобщенными пермутаэдрами

Поскольку обобщенные пермутаэдры могут быть построены из субмодульных функций, и каждый обобщенный пермутаэдр имеет связанную субмодулярную функцию, мы имеем, что должно быть соответствие между обобщенные пермутаэдры и полиматроиды. Фактически, каждый полиматроид - это обобщенный пермутаэдр, который был переведен так, чтобы иметь вершину в начале координат. Этот результат предполагает, что комбинаторная информация полиматроидов является общей с обобщенными пермутаэдрами.

Свойства

$P f {\ displaystyle P_ {f}}$ $P_ {е}$ непусто тогда и только тогда, когда $f ≥ 0 {\ displaystyle f \ geq 0}$ $f \ geq 0$ и что $EP f {\ displaystyle EP_ {f}}$ $EP_ {f}$ непусто тогда и только тогда, когда $f (∅) ≥ 0 {\ displaystyle f (\ emptyset) \ geq 0}$ $f (\ emptyset) \ geq 0$ .

Для любого расширенного полиматроида $EP {\ displaystyle EP}$ $EP$ существует уникальная субмодульная функция $f {\ displaystyle f}$ $f$ такая, что $f ( ∅) = 0 {\ displaystyle f (\ emptyset) = 0}$ $е (\ emptyset) = 0$ и $EP f = EP {\ displaystyle EP_ {f} = EP}$ $EP_ {f} = EP$ .

Контраполиматроиды

Для a супермодульный f аналогичным образом можно определить контраполиматроид

{w ∈ R + E: ∀ S ⊆ E, ∑ e ∈ S w (e) ≥ f (S)} {\ displaystyle \ left \ {w \ in \ mathbb {R} _ {+} ^ {E}: \ forall S \ substeq E, \ sum _ {e \ in S} w (e) \ geq f (S) \ right \ }}

{\ displaystyle \ left \ {w \ in \ mathbb {R} _ {+} ^ {E}: \ forall S \ substeq E, \ sum _ {e \ in S} w (е) \ geq е (S) \ право \}}

Это аналогично обобщает доминанту остовного множества многогранника матроидов.

Дискретные полиматроиды

Когда мы фокусируемся только на точках решетки наших полиматроидов, мы получаем так называемые, дискретные полиматроиды . Формально говоря, определение дискретного полиматроида идет точно так же, как и для полиматроидов, за исключением того места, где будут жить векторы, вместо $R + E {\ displaystyle \ mathbb {R} _ {+ } ^ {E}}$ ${\ displaystyle \ mathbb {R} _ {+} ^ {E}}$ они будут жить в $Z + E {\ displaystyle \ mathbb {Z} _ {+} ^ {E}}$ ${\ displaystyle \ mathbb {Z} _ {+} ^ {E}}$ . Этот комбинаторный объект представляет большой интерес из-за их связи с мономиальными идеалами.

Ссылки

Сноски

Дополнительная литература

Ли, Джон (2004), Первый курс комбинаторной оптимизации, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
Нараянан, Х. (1997), Субмодульные функции и электрические сети, ISBN 0-444-82523- 1