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 53: | Línea 53: | ||
* La operación de contracción de un eje e= (v,w) consiste en eliminar el eje del grafo y considerar sus extremos como un solo nodo u. (quedan como ejes incidentes a u todos los ejes que eran incidentes en v y en w). | * La operación de contracción de un eje e= (v,w) consiste en eliminar el eje del grafo y considerar sus extremos como un solo nodo u. (quedan como ejes incidentes a u todos los ejes que eran incidentes en v y en w). | ||
* Un grafo G' es una contracción de otro grafo G si se puede obtener a partir de G por sucesivas operaciones de contracción. En este caso se dice que G es contraible a | * Un grafo G' es una contracción de otro grafo G si se puede obtener a partir de G por sucesivas operaciones de contracción. En este caso se dice que G es contraible a H. | ||
* Un grafo es planar si y sólo si no contiene ningún subgrafo contraible a <math>K_{3,3}</math> o <math>K_{5}</math>. | * Un grafo es planar si y sólo si no contiene ningún subgrafo contraible a <math>K_{3,3}</math> o <math>K_{5}</math>. |