Matroid
En combinatoria , una rama de las matemáticas , una matriz / ˈ m eɪ t r ɔɪ d / es una estructura que abstrae y generaliza la noción de independencia lineal en espacios vectoriales . Hay muchas formas equivalentes de definir un matroide axiomáticamente , siendo las más significativas en términos de: conjuntos independientes; bases o circuitos; funciones de rango; operadores de cierre; y conjuntos cerrados o pisos. En el lenguaje de los conjuntos parcialmente ordenados , una matroide finita es equivalente a una red geométrica .
La teoría de Matroid toma mucho de la terminología del álgebra lineal y la teoría de grafos , en gran parte porque es la abstracción de varias nociones de importancia central en estos campos. Los matroides han encontrado aplicaciones en geometría , topología , optimización combinatoria , teoría de redes y teoría de codificación . [1] [2]
En términos de independencia, un matroide finito es un par , donde es un conjunto finito (llamado conjunto base ) y es una familia de subconjuntos (llamados conjuntos independientes ) con las siguientes propiedades: [4]
Las dos primeras propiedades definen una estructura combinatoria conocida como sistema de independencia (o complejo simplicial abstracto ).
Un subconjunto del conjunto base que no es independiente se llama dependiente . Un conjunto independiente máximo, es decir, un conjunto independiente que se vuelve dependiente al agregar cualquier elemento de, se denomina base de la matroide. Un circuito en una matroide es un subconjunto dependiente mínimo de , es decir, un conjunto dependiente cuyos subconjuntos propios son todos independientes. La terminología surge porque los circuitos de matroides gráficos son ciclos en los gráficos correspondientes. [4]
Los conjuntos dependientes, las bases o los circuitos de una matroide caracterizan completamente a la matroide: un conjunto es independiente si y solo si no es dependiente, si y solo si es un subconjunto de una base, y si y solo si lo es. no contiene un circuito. Las colecciones de conjuntos dependientes, de bases y de circuitos tienen propiedades simples que pueden tomarse como axiomas para una matroide. Por ejemplo, uno puede definir un matroide como un par , donde es un conjunto finito como antes y es una colección de subconjuntos de , llamados "bases", con las siguientes propiedades: [4]
