PROBLEMAS NP Y P

El concepto de "NP-completo" fue introducido por Stephen Cook en un artículo titulado 'The complexity of theorem-proving procedures' en las páginas 151-158 de Proceedings of the 3rd Annual ACM Symposium on Theory of Computing en 1971, aunque el término "NP-completo" como tal no aparece en el documento. En la conferencia de ciencias de la computación hubo un intenso debate entre los científicos de la computación sobre si los problemas NP-completos podían ser resueltos en tiempo polinómico o en una máquina de Turing determinista.John Hopcroft llevó a todos los asistentes de la conferencia a consenso concluyendo que el estudio sobre si los problemas NP-completos son resolubles en tiempo polinómico debiera ser pospuesto ya que nadie había conseguido probar formalmente sus hipótesis ni en un sentido ni en otro. Esto se conoce como el problem ¿P=NP?

Un problema interesante en teoría de grafos es el de isomorfismo de grafos: Dos grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando los vértices. De los dos problemas siguientes:

Isomorfismo de grafos: ¿Es el grafo G₁ isomorfo al grafo G₂?

Isomorfismo de subgrafos: ¿Es el grafo G₁ isomorfo a un subgrafo del grafo G₂?

¿Qué son los árboles de Steiner?

Son una solucion mas óptima que los árboles EMST (Euclidean Minimum Spanning Tree), de hecho se forman mediante este tipo de árboles pero con la diferencia que para lograr la maxima optimizacion se puede agregar mas vértices. Estos vértices adicionales
se denominan Vértices o Nodos de Steiner.
Mediante estos vértices se busca efectuar una minimización más óptima de los árboles de recubrimiento.

Consideraciones:
Para un conjunto de N vértices, se tiene como máximo N-2 vértices de Steiner.

Complejidad Computacional:

La generación de Árboles de Steiner representa un tipo de problemas en el cual la respuesta es la mejor aproximación, pero el costo computacional es elevado.

En 1973 Karp demostró que el problema del árbol de Steiner es NP-Completo. Desde entonces, diferentes enfoques de métodos heurísticos han sido aplicados para obtener buenas soluciones del problema en tiempos razonables.

Se estan llevando a cabo investigaciones para diseñar e implementar en un "futuro próximo" los métodos heurísticos correspondientes a técnicas evolutivas, que permitan llegar a la optimización de un conjunto de N vértices fuertemente conexo, más allá del obtenido por los árboles EMST, permitiendo obtener inclusive la solución del Problema de Steiner Generalizado.

 kruskal

 Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010) fue un matemático y estadístico estadounidense.

Investigador del Math Center (Bell-Labs), en 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo , el cual es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Un árbol de un grafo es un subgrafo que contiene todos sus vértices. Un grafo puede tener múltiples árboles.

Matroid Theory

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. 

 

Teorema de la Galería de Arte

Para vigilar una galería de arte poligonal con n vértices, n/3 guardias son siempre suficientes. Existen salas que necesitan ese nº de guardias.

DEMOSTRACIÓN:

Consideremos un polígono simple P de n vértices y observamos gráficamente los siguientes pasos.

Primer paso (Triangulación)

Triangulamos P, es decir, descomponemos P e triángulos cuya unión es P, con interiores disjuntos y cuyos vértices son vértices de P. Observamos que un guardia situado en cualquier vértice de un triángulo vigila completamente dicho triángulo.

Segundo paso(Coloración)

La triangulacion anterior en una gráfica plana. El teorema de los cuatro colores, probado en 1976 por Appel y Haken, asegura que toda gráfica plana puede colorearse utilizando sólo cuatro colores. Pero podemos colorear los vértices de una triangulación T de un polígono utilizando tan sólo tres colores. En esta 3-coloración de T cada triángulo tiene un vértice de cada color.

Tercer paso (Colocación de Guardias).

Cada triángulo de T tiene un vértice rojo. Si colocamos un guardia en cada vértice rojo, vigilaran todos los triángulos y, por tanto, todo el polígono. Lo mismo sucederá si colocamos guardias en todos los vértices negros o si los colocamos en todos los vértices azules.

El polígono tiene n vértices y disponemos de tres colores. Por tanto, alguno de los tres colores se utiliza en, a lo mas n/3 vértices.  Basta pues colocar los guardias en los vértices  con color el color menos utilizado para garantizar que n/3 guardias son siempre suficientes para vigilar cualquier polígono en n vértices.

Cuarto paso (Necesidad de los n/3 guardias).

Para comprobar que este número de guardias es a veces necesario basta considerar el polígono “peineta” con n=3k vértices . Es fácil observar que para vigilar este polígono se necesita al menos k guardias, uno por cada púa de la peineta.