Edición de «Resumen (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 41: | Línea 41: | ||
=== Teorema de Kuratowski === | === Teorema de Kuratowski === | ||
* Subdividir un eje e = (v,w) de un grafo G, consiste en agregar un nodo | * Subdividir un eje e = (v,w) de un grafo G, consiste en agregar u un nodo a G y reemplazar el eje e por dos ejes e'= (v,u) y e" = (u,w). | ||
* Un grafo G' es una subdivisión de otro grafo G si G' se puede obtener de G por sucesivas operaciones de subdivisión. | * Un grafo G' es una subdivisión de otro grafo G si G' se puede obtener de G' por sucesivas operaciones de subdivisión. | ||
* Dos grafos G y H se dicen homeomorfos si hay un isomorfismo entre una subdivisión de G y una de H. | * Dos grafos G y H se dicen homeomorfos si hay un isomorfismo entre una subdivisión de G y una de H. | ||
Línea 140: | Línea 140: | ||
* Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> (Dem: Como un eje solo puede tocar un solo nodo de I (pq es indep), necesitas al menos tantos ejes como nodos en I para cubrir todo) | * Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> (Dem: Como un eje solo puede tocar un solo nodo de I (pq es indep), necesitas al menos tantos ejes como nodos en I para cubrir todo) | ||
* Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. | * Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. (NDL: no entendi) | ||
* Dado un grafo G, si I es un conjunto independiente máximo y Rn un recubrimiento mínimo de los ejes de V, entonces <math>|I| + |R_n| = n</math>. No es un problema bien resuelto. | * Dado un grafo G, si I es un conjunto independiente máximo y Rn un recubrimiento mínimo de los ejes de V, entonces <math>|I| + |R_n| = n</math>. No es un problema bien resuelto. (No entendi) | ||
* Dado un grafo G bipartito de m aristas, con I conjunto independiente máximo y Rn recubrimiento mínimo de aristas, vale que <math>m \leq |I|*|R_n|</math>. | * Dado un grafo G bipartito de m aristas, con I conjunto independiente máximo y Rn recubrimiento mínimo de aristas, vale que <math>m \leq |I|*|R_n|</math>. |