ポリマトロイド

させて${\displaystyle E}$有限集合であり、${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$非減少劣モジュラ関数、すなわち各${\displaystyle A\subseteq B\subseteq E}$我々は持っています${\displaystyle f(A)\leq f(B)}$、そしてそれぞれについて${\displaystyle A,B\subseteq E}$我々は持っています${\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)}$我々は、以下に関連付けられたポリマトロイドを定義する。${\displaystyle f}$以下の多面体となる：

${\displaystyle P_{f}={\Big \{}{\textbf {x}}\in \mathbb {R} _{\geq 0}^{E}~{\Big |}~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E{\Big \}}}$。

入力を許可すると${\displaystyle {\textbf {x}}}$負であることを表すために、この多面体を次のように表します。${\displaystyle EP_{f}}$そして、それを拡張ポリマトロイドと呼び、${\displaystyle f}$[ ^{2 ]​}

マトロイド理論では、ポリマトロイドは、上記の定義にあるように、集合と関数からなるペアとして定義されます。つまり、ポリマトロイドはペアです。${\displaystyle (E,f)}$どこ${\displaystyle E}$は有限集合であり、${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$、 または${\displaystyle \mathbb {Z} _{\geq 0},}$は非減少劣モジュラ関数です。終域が${\displaystyle \mathbb {Z} _{\geq 0},}$私たちは言う${\displaystyle (E,f)}$は整数ポリマトロイドです。${\displaystyle E}$地面がセットされ、${\displaystyle f}$ポリマトロイドのランク関数。この定義は、ランク関数に関してマトロイドの定義を一般化したものです。ベクトル${\displaystyle x\in \mathbb {R} _{\geq 0}^{E}}$独立している${\displaystyle \sum _{e\in U}x(e)\leq f(U)}$すべての人々のために${\displaystyle U\subseteq E}$。 させて${\displaystyle P}$独立ベクトルの集合を表す。すると${\displaystyle P}$は、前述の定義における多面体であり、ポリマトロイドの独立多面体と呼ばれる。 ^{[ 3 ]}

この定義によれば、マトロイドは整数ポリマトロイドの特殊なケースである。マトロイド内の要素のランクは、${\displaystyle 0}$または${\displaystyle 1}$ポリマトロイドの要素のランクは、任意の非負の実数、または整数ポリマトロイドの場合は非負の整数となる。この意味で、ポリマトロイドはマトロイドの多重集合類似物とみなすことができる。

させて${\displaystyle E}$有限集合である。${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$すると、${\displaystyle |{\textbf {u}}|}$エントリの合計${\displaystyle {\textbf {u}}}$、そして書く${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$いつでも${\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0}$すべての${\displaystyle i\in E}$（これは部分的な順序を与えることに注意してください）${\displaystyle \mathbb {R} _{\geq 0}^{E}}$地上セット上のポリマトロイド${\displaystyle E}$は空でないコンパクトな部分集合である${\displaystyle P}$独立ベクトルの集合、${\displaystyle \mathbb {R} _{\geq 0}^{E}}$すなわち、

1. もし${\displaystyle {\textbf {v}}\in P}$、 それから${\displaystyle {\textbf {u}}\in P}$すべての${\displaystyle {\textbf {u}}\leq {\textbf {v}}.}$
2. もし${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$と${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$するとベクトルが存在する${\displaystyle {\textbf {w}}\in P}$そのため${\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\}).}$

この定義は、前述の定義と同等である[ ^{4 ] 。}${\displaystyle f}$関数は次のように定義されます

${\displaystyle f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}}$すべての${\displaystyle A\subseteq E}$。

2番目の性質は次のように簡略化できます。

もし${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$と${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$、 それから${\displaystyle (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.}$

コンパクト性は、${\displaystyle P}$は有界であると仮定する。