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.)

Gráfica de Turan

el conjunto de vértices no son adyacentes entre si ... pero si son adyacentes con todos los demás vértices de los otros conjuntos.

respuestas de la pelicula "UNA MENTE INDOMABLE"

1) matriz de adyacencia A:

P ≠ NP

P ≠ NP

Al parecer un científico de HP acaba de presentar a revisión la demostración de la proposición 'P no es igual a NP', que viene a decir que la clase de complejidad de la resolución de problemas Polinomiales es distinta de la de los No Polinomiales.

Su nombre es Deolalikar Vinay, un investigador de HP, y podría tornarse un millón de dólares más rico si es verdad lo que escribió en su último artículo científico: P ≠ NP!

Ya le han incluso creado una página en Wikipedia, y los wikipedistas están ya, como de costumbre, ferozmente debatiendo si su notabilidad es o no (todavía) suficiente como para estar en la enciclopedia en línea.

Será otro que se equivoca? ¿O esta vez vamos a tener una respuesta definitiva a la pregunta del millón de la Ciencia de la Computación?

En realidad, NP no significa "No Polinomial", sino, "No-determinista Polinomial". Los problemas de la clase NP pueden ser resueltos en tiempo polinomial por una máquina de Turing No-Determinista.

Este tipo de máquina es una construcción mental, y puedes pensar en ella como un tipo de máquina que "magicamente" sabe cuál es la ruta más corta de entre todas sus posibles rutas de ejecución, y esa es la que sigue. O también puedes pensar en ella como una máquina masivamente paralela que puede ejectuar simultáneamente todas sus posibles rutas de ejecución, y detenerse cuando una de ellas finaliza.

El que un problema sea resoluble en tiempo polinomial por una máquina así, a primera vista, no parece gran cosa, ya que la máquina "hace trampa" al seguir siempre la vía más corta. ¡Pero es que hay problemas que ni con una máquina mágica como esa podrían resolverse en tiempo polinomial!

Los problemas tipo P son los que se pueden resolver en tiempo polinomial con una máquina de Turing determinista, o lo que es lo mismo, con cualquier ordenador convencional.

El que P sea diferente de NP significa que los problemas de la categoría NP, no se pueden resolver en tiempo polinomial en una máquina determinista, requieren una no-determinista para ello. Podría parecer que esto pone a salvo los algoritmos criptográficos (que se basan en que los tiempos necesarios para "romper" el código en un computador determinista son prohibitivamente grandes). Sin embargo, no está demostrado que una máquina no-determinista no pueda ser construida. Algunos piensan que la computación cuántica podría crear una máquina así. Si se pudiera construir una máquina así, los problemas NP (entre ellos el "romper" un código criptográfico) podría ser resuelto en tiempo polinomial.


Clases de complejidad P y NP

Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos en este caso fue determinada por Ladner.
La relación entre las clases de complejidad P y NP es una pregunta que aún no ha podido ser respondida por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?
Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.
Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de $1 millón de dólares norteamericanos para quién desarrolle la primera demostración correcta.

funcion

Función

Una funcion la denotamos por “f” es una relación entre un conjunto dado X (el dominio) y otro conjunto de elementos Y (el codominio) de forma que a cada elemento x del dominio le corresponde un único elemento del codominio f(x). Se denota por: f: X—-> Y

Comúnmente, el término función se utiliza cuando el codominio son valores numéricos, reales o complejos. Entonces se habla de función real o función compleja mientras que a las funciones entre conjuntos cualesquiera se las denomina aplicaciones.

Una función puede considerarse como un caso particular de una relación o de correspondencia matemática. Cada relación o correspondencia de un elemento x pertenece a X con un (y sólo un) y pertenece a Y se denota f(x)= y , en lugar de

(x,y) pertenece f.

Formalmente, pedimos que se cumplan las siguientes dos condiciones:

Condición de existencia: Todos los elementos de X están relacionados con elementos de Y.

Condición de unicidad: Cada elemento de X está relacionado con un único elemento de Y.

Clasificación de las funciones:

Dados dos conjuntos X, Y, consideremos a todas las posibles aplicaciones (funciones) que pueden formarse entre estos dos conjuntos. Podemos diferenciar los siguientes casos:

Si a cada imagen le corresponde una única preimagen, inyectiva.

Si la imagen de la función es igual al codominio, sobreyectiva o suprayectiva.

Una función que sea inyectiva y sobreyectiva simultáneamente, se denomina biyectiva .

Puede haber funciones que sean biyectivas, inyectivas pero no suprayectivas, supreyectiva pero no inyectiva o que no se cumple ninguna de esas condiciones, en cuyo caso no tiene un nombre específico.

Definiciones alternas: sea f: X —> Y dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación:

f(x)= b (*).

La función es suprayectiva o sobreyectiva si, y sólo si, la ecuación (*) siempre tiene al menos una solución.

La función es inyectiva si, y sólo si, la ecuación (*) tiene a lo más una solución.

La función es biyectiva cuando, y sólo cuando, es inyectiva y suprayectiva a la vez.


Vamos a ilustrar esos diferentes tipos de funciones (aplicaciones) en un diagrama de venn, el conjunto universal U, representado por un rectángulo, es el conjunto de todas las posibles aplicaciones, el conjunto A es aquel de las aplicaciones inyectivas, y el conjunto B aquel de las sobreyectivas, esto nos permite ver los distintos tipos de aplicaciones de un modo gráfico.

relacion

Una relación , la llamamos “R” cuando es la relación de los conjuntos A,B….etc es un subconjunto del producto cartesiano A x B x ….. Zn. Una Relación binaria es una relación entre dos conjuntos. El concepto de relación implica la idea de enumeración, de algunos de los elementos, de los conjuntos que forman tuplas.

R(a,b….zn) o bien (a,b….zn) pertenece a R.

Un caso particular es cuando todos los conjuntos de la relación son iguales: A=B….en este caso se representa como AxAxA….A como An. , pudiéndose decir que la relación pertenece a A a la n. R pertenece An.

Tipos de relaciones

En las relaciones se diferencian los tipos según el número de conjuntos en el producto cartesiano, que es el número de términos de la relación:

Relación unaria: un solo conjunto.

Relación binaria: con dos conjuntos.

Relación ternaria: con tres conjuntos.

Relación cuaternaria: con cuatro conjuntos.

Relación n-aria: caso general con n conjuntos.

Strong Induction Principle Pinohole

(Principio Básico de la Combinatoria)

Principio de Inducción Fuerte : Dejar “D” ser un subconjunto de los números enteros no negativos Z* con las propiedades :

a) El 0 entero esta en D.

b) Cada vez que el intervalo [0,n] esta contenida en D.

Se puede demostrar que n+1 también esta en D. En estas

condiciones D=Z*.