Polimatroide

Dejar${\displaystyle E}$sea ​​un conjunto finito y${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$una función submodular no decreciente , es decir, para cada${\displaystyle A\subseteq B\subseteq E}$tenemos${\displaystyle f(A)\leq f(B)}$y para cada uno${\displaystyle A,B\subseteq E}$tenemos${\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)}$. Definimos el polimatroide asociado a${\displaystyle f}$ser el siguiente politopo :

${\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 \}}}$.

Cuando permitimos las entradas de${\displaystyle {\textbf {x}}}$Para que sea negativo, denotamos este politopo por${\displaystyle EP_{f}}$y lo llamamos polimatroide extendido asociado a${\displaystyle f}$. ^{[ 2 ]}

En la teoría de matroides, los polimatroides se definen como el par que consta del conjunto y la función como en la definición anterior. Es decir, un polimatroide es un par${\displaystyle (E,f)}$dónde${\displaystyle E}$es un conjunto finito y${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$, o${\displaystyle \mathbb {Z} _{\geq 0},}$es una función submodular no decreciente. Si el codominio es${\displaystyle \mathbb {Z} _{\geq 0},}$decimos que${\displaystyle (E,f)}$es un polimatroide entero . Lo llamamos${\displaystyle E}$el terreno preparado y${\displaystyle f}$la función de rango del polimatroide. Esta definición generaliza la definición de un matroide en términos de su función de rango. Un vector${\displaystyle x\in \mathbb {R} _{\geq 0}^{E}}$es independiente si${\displaystyle \sum _{e\in U}x(e)\leq f(U)}$a pesar de${\displaystyle U\subseteq E}$. Dejar${\displaystyle P}$denotemos el conjunto de vectores independientes. Entonces${\displaystyle P}$es el politopo en la definición anterior, llamado politopo de independencia del polimatroide. ^{[ 3 ]}

Según esta definición, un matroide es un caso especial de polimatroide entero. Mientras que el rango de un elemento en un matroide puede ser${\displaystyle 0}$o${\displaystyle 1}$El rango de un elemento en un polimatroide puede ser cualquier número real no negativo , o un entero no negativo en el caso de un polimatroide entero. En este sentido, un polimatroide puede considerarse un análogo multiconjunto de un matroide.

Dejar${\displaystyle E}$sea ​​un conjunto finito . Si${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$entonces denotamos por${\displaystyle |{\textbf {u}}|}$la suma de las entradas de${\displaystyle {\textbf {u}}}$y escribir${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$cuando sea${\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0}$por cada${\displaystyle i\in E}$(nótese que esto da un orden parcial a${\displaystyle \mathbb {R} _ {\geq 0}^{E}}$). Un polimatroide en el suelo${\displaystyle E}$es un subconjunto compacto no vacío${\displaystyle P}$, el conjunto de vectores independientes, de${\displaystyle \mathbb {R} _ {\geq 0}^{E}}$de tal manera que:

1. Si${\displaystyle {\textbf {v}}\en P}$, entonces${\displaystyle {\textbf {u}}\en P}$por cada${\displaystyle {\textbf {u}}\leq {\textbf {v}}.}$
2. Si${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$con${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$, entonces hay un vector${\displaystyle {\textbf {w}}\in P}$de tal manera que${\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\}).}$

Esta definición es equivalente a la descrita anteriormente, ^{[ 4 ]} donde${\displaystyle f}$es la función definida por

${\displaystyle f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}}$por cada${\displaystyle A\subseteq E}$.

La segunda propiedad puede simplificarse a

Si${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$con${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$, entonces${\displaystyle (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.}$

Entonces la compacidad está implícita si${\displaystyle P}$Se supone que está acotado.