En matemáticas, una matroide de partición o matroide de partición es una matroide que es una suma directa de matroides uniformes . [1] Se define sobre un conjunto básico en el que los elementos se dividen en diferentes categorías. Para cada categoría, hay una restricción de capacidad : un número máximo de elementos permitidos de esta categoría. Los conjuntos independientes de una matriz de partición son exactamente los conjuntos en los que, para cada categoría, el número de elementos de esta categoría es como máximo la capacidad de la categoría.
Definicion formal
Dejar ser una colección de conjuntos disjuntos ("categorías"). Dejar ser enteros con ("capacidades"). Definir un subconjunto ser "independiente" cuando, para cada índice , . Los conjuntos que satisfacen esta condición forman los conjuntos independientes de un matroide , llamado matroide de partición .
Los conjuntos se denominan bloques o categorías de la matriz de partición.
Una base de la matroide de partición es un conjunto cuya intersección con cada bloque tiene el tamaño exacto . Un circuito de la matroide es un subconjunto de un solo bloque con el tamaño exactamente . El rango del matroide es. [2]
Cada matroide uniforme es una matroide de partición, con un solo bloque de elementos y con . Cada matroide de partición es la suma directa de una colección de matroides uniformes, una para cada uno de sus bloques.
En algunas publicaciones, la noción de matroide de partición se define de manera más restrictiva, con cada . Las particiones que obedecen a esta definición más restrictiva son las matroides transversales de la familia de conjuntos disjuntos dados por sus bloques. [3]
Propiedades
Al igual que con las matroides uniformes de las que están formadas, la matroide dual de una matroide de partición también es una matroide de partición, y cada menor de una matroide de partición es también una matroide de partición. Las sumas directas de matroides de partición también son matroides de partición.
Pareo
Una coincidencia máxima en un gráfico es un conjunto de bordes lo más grande posible sujeto a la condición de que no haya dos bordes que compartan un punto final. En un gráfico bipartito con bipartición, los conjuntos de aristas que cumplen la condición de que no haya dos aristas que compartan un punto final en son los conjuntos independientes de una matriz de partición con un bloque por vértice en y con cada uno de los números igual a uno. Los conjuntos de aristas que cumplen la condición de que no haya dos aristas que compartan un punto final enson los conjuntos independientes de una segunda matriz de partición. Por lo tanto, el problema de emparejamiento máximo bipartito se puede representar como una intersección matroide de estas dos matroides. [4]
De manera más general, las correspondencias de un gráfico se pueden representar como una intersección de dos matroides si y solo si cada ciclo impar en el gráfico es un triángulo que contiene dos o más vértices de grado dos. [5]
Complejos de camarilla
Un complejo de camarilla es una familia de conjuntos de vértices de un gráfico. que inducen subgrafos completos de . Un complejo de camarilla forma un matroide si y solo sies un gráfico multipartito completo , y en este caso el matroid resultante es un matroid de partición. Los complejos de camarillas son exactamente los sistemas de conjuntos que pueden formarse como intersecciones de familias de matroides de partición para las cuales cada. [6]
Enumeración
El número de matrices de partición distintas que se pueden definir en un conjunto de elementos etiquetados, para , es
La función de generación exponencial de esta secuencia es. [7]
Referencias
- ↑ Recski, A. (1975), "Sobre matroides particionales con aplicaciones", Conjuntos infinitos y finitos (Colloq., Keszthely, 1973; dedicado a P. Erdős en su 60 cumpleaños), vol. III , Coloq. Matemáticas. Soc. János Bolyai, 10 , Amsterdam: North-Holland, págs. 1169-1179, MR 0389630.
- ^ Lawler, Eugene L. (1976), Optimización combinatoria: redes y matroides , Rinehart y Winston, Nueva York: Holt, p. 272, MR 0439106.
- ^ Por ejemplo, ver Kashiwabara, Okamoto & Uno (2007) . Lawler (1976) utiliza la definición más amplia, pero señala que el La restricción es útil en muchas aplicaciones.
- ^ Papadimitriou, Christos H .; Steiglitz, Kenneth (1982), Optimización combinatoria: algoritmos y complejidad , Englewood Cliffs, Nueva Jersey: Prentice-Hall Inc., págs. 289-290, ISBN 0-13-152462-3, MR 0663728.
- ^ Fekete, Sándor P .; Firla, Robert T .; Spille, Bianca (2003), "Caracterización de emparejamientos como la intersección de matroides", Métodos matemáticos de investigación de operaciones , 58 (2): 319–329, arXiv : math / 0212235 , doi : 10.1007 / s001860300301 , MR 2015015.
- ^ Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), "Representación matroide de complejos de camarillas", Matemáticas aplicadas discretas , 155 (15): 1910-1929, doi : 10.1016 / j.dam.2007.05.004 , MR 2351976. Para obtener los mismos resultados en una forma complementaria usando conjuntos independientes en lugar de camarillas, ver Tyshkevich, RI ; Urbanovich, OP; Zverovich, I. È. (1989), "Descomposición matroidal de un gráfico", Combinatoria y teoría de grafos (Varsovia, 1987) , Banach Centre Publ., 25 , Varsovia: PWN, págs. 195-205, MR 1097648.
- ^ Recski, A. (1974), "Enumeración de matroides particionales", Studia Scientiarum Mathematicarum Hungarica , 9 : 247–249 (1975), MR 0379248.