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 27: | Línea 27: | ||
=== Viajante de comercio === | === Viajante de comercio === | ||
* El problema del viajante de comercio consiste en hallar un circuito hamiltoniano de | * El problema del viajante de comercio consiste en hallar un circuito hamiltoniano de longitud minima en un grafo. | ||
* No es un problema bien resuelto, hay muchas heurísticas para resolverlo. Si las distancias en el grafo son euclideanas, entonces algunas heurísticas son epsilon aproximadas. | * No es un problema bien resuelto, hay muchas heurísticas para resolverlo. Si las distancias en el grafo son euclideanas, entonces algunas heurísticas son epsilon aproximadas. | ||
Línea 119: | Línea 119: | ||
** M es un matching máximo si y sólo si no existe un camino alternado entre pares de nodos no saturados. | ** M es un matching máximo si y sólo si no existe un camino alternado entre pares de nodos no saturados. | ||
* Un '''conjunto independiente''' I de nodos de G, es un conjunto de nodos tal que para todo eje del grafo, e es incidente a lo sumo a un nodo v de I. Es decir, en el subgrafo inducido por I, todos los nodos son aislados | * Un '''conjunto independiente''' I de nodos de G, es un conjunto de nodos tal que para todo eje del grafo, e es incidente a lo sumo a un nodo v de I. Es decir, en el subgrafo inducido por I, todos los nodos son aislados. | ||
* Un '''recubrimiento de los ejes''' de G, es un conjunto Rn de nodos tal que para todo eje e de G, e es incidente al menos a un nodo v de Rn. Es decir, '''vertex cover''' | * Un '''recubrimiento de los ejes''' de G, es un conjunto Rn de nodos tal que para todo eje e de G, e es incidente al menos a un nodo v de Rn. Es decir, '''vertex cover'''. | ||
* Un '''recubrimiento de los nodos de G''', es un conjunto Re de ejes tal que para todo nodo v de G, v es incidente al menos a un eje e de Re | * Un '''recubrimiento de los nodos de G''', es un conjunto Re de ejes tal que para todo nodo v de G, v es incidente al menos a un eje e de Re. | ||
=== Equivalencias === | === Equivalencias === | ||
Línea 136: | Línea 136: | ||
* En particular, si el grafo es bipartito, la cantidad de ejes del matching máximo es igual a la cantidad de nodos de un vertex cover mínimo. (Nota de un lector: Esto no me lo creo. Para un grafo con puntos aislados, es bipartito, el matching maximo tiene 0 ejes y no existe vertex cover, quizas tengo alguna definicion mal, pero aviso por las dudas) | * En particular, si el grafo es bipartito, la cantidad de ejes del matching máximo es igual a la cantidad de nodos de un vertex cover mínimo. (Nota de un lector: Esto no me lo creo. Para un grafo con puntos aislados, es bipartito, el matching maximo tiene 0 ejes y no existe vertex cover, quizas tengo alguna definicion mal, pero aviso por las dudas) | ||
(Nota de otro lector: El problema es que tomas vertex cover como cubrimiento de vertices, para la bibliografia en ingles vertex cover es recubrimiento de aristas, por lo que en el ejemplo el matching maximo tiene 0 ejes y el vertex cover tiene 0 vertices porque no hay aristas). | (Nota de otro lector: El problema es que tomas vertex cover como cubrimiento de vertices, para la bibliografia en ingles vertex cover es recubrimiento de aristas, por lo que en el ejemplo el matching maximo tiene 0 ejes y el vertex cover tiene 0 vertices porque no hay aristas). | ||
* 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) |