miércoles, 19 de octubre de 2011

MATROID THEORY



Matroid teoría fue introducida por Hassler Whitney ( 1935 ). También fue descubierto independientemente por Takeo Nakasawa , cuyo trabajo fue olvidado durante muchos años ( Nishimura y Kuroda 2009 ).

En su trabajo seminal, Whitney siempre dos axiomas de la independencia, y se define cualquier estructura de la adhesión a estos axiomas como "matroides". (A pesar de que estaba implicado tal vez, no incluyó un axioma que requiera al menos un subconjunto de ser independiente.) Su observación clave fue que estos axiomas proporcionan una abstracción de la "independencia" que es común a ambos gráficos y matrices. Debido a esto, muchos de los términos utilizados en la teoría matroid se asemejan a los términos de sus conceptos análogos en álgebra lineal o la teoría de grafos .


Una de las definiciones más valioso es que se da en términos de independencia. En esta definición, un finito matroid M es un par (E, I), donde E es un recurso conjunto (llamado el conjunto de suelo) y que es una colección de subconjuntos de E (llamados los conjuntos independientes) con las siguientes propiedades:

El conjunto vacío es independiente, es decir, ∅ ∈ I. (Por otra parte, al menos un subconjunto de E es independiente, es decir, I ≠ ∅).
Cada subconjunto de un conjunto independiente es independiente, es decir, para cada A '⊆ A ⊆ E, A ∈ I → A' ∈ I. A veces se denomina la propiedad hereditaria.
Si A y B son dos conjuntos independientes de I y A tiene más elementos de B, entonces existe un elemento de A que no está en B, que cuando se añade a B todavía da un conjunto independiente. A veces se denomina la propiedad o el aumento del intercambio de bienes conjunto independiente.

Las dos primeras propiedades son simples, y definir una estructura combinatoria conocido como un sistema de independencia , pero la motivación detrás de la propiedad de terceros no es obvia.

Se puede definir un M matroid a un par (E, B), donde E es un conjunto finito como antes, y B es una colección de subconjuntos de E, llamadas "bases", con las siguientes propiedades:

B es no vacío.
Ningún miembro de B es un subconjunto propio de sí.
Si A y B son diferentes miembros de B y es un elemento de A que no pertenecen a B, entonces existe un elemento b perteneciente a B - A tal que A - a + ​​b es una base. (Esta propiedad se llama el intercambio de bienes básicos.)