{"id":2689,"date":"2016-02-16T16:44:27","date_gmt":"2016-02-16T15:44:27","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2689"},"modified":"2022-12-03T22:59:01","modified_gmt":"2022-12-03T21:59:01","slug":"coloration-cliques-et-stables","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/","title":{"rendered":"Colorear, clicks y establos"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2689\" class=\"elementor elementor-2689\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7717f12 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7717f12\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1c80c33\" data-id=\"1c80c33\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ebeee03 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ebeee03\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Teor\u00eda de grafos<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-bed0043\" data-id=\"bed0043\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-152529e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"152529e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3a72af2\" data-id=\"3a72af2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-482fc6e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"482fc6e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Coloration_de_graphe\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6bca73e1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6bca73e1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5886b16a\" data-id=\"5886b16a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1347f53 elementor-widget elementor-widget-text-editor\" data-id=\"1347f53\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/#Coloration-de-graphe\" >Coloraci\u00f3n gr\u00e1fica<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/#Probleme-cliques\" >Problema: clics<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/#Probleme-stables\" >Problema: estable<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/#Relation-entre-les-trois-problemes-et-heuristiques\" >Relaci\u00f3n entre los tres problemas y la heur\u00edstica<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/#Exemple\" >Ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Coloration-de-graphe\"><\/span>Coloraci\u00f3n gr\u00e1fica<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">El problema de la coloraci\u00f3n de grafos, para un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> G no dirigida, consiste en asignar un color a cada v\u00e9rtice de tal manera que no se asigne el mismo color a dos v\u00e9rtices adyacentes.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Cuando el gr\u00e1fico es plano, esto equivale al problema de colorear un mapa geogr\u00e1fico. El problema de la coloraci\u00f3n de gr\u00e1ficos surge en muchas \u00e1reas pr\u00e1cticas, como la coincidencia de patrones, <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/\">planificaci\u00f3n<\/a> deportes, dise\u00f1o de distribuci\u00f3n de asientos, revisi\u00f3n de horarios, programaci\u00f3n de taxis y resoluci\u00f3n de Sudoku.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">El n\u00famero m\u00ednimo de colores necesarios para colorear el gr\u00e1fico G se denomina n\u00famero crom\u00e1tico de G y se denota por X (G).<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">El problema de encontrar el n\u00famero crom\u00e1tico de una gr\u00e1fica es un problema Np-completo. El problema de colorear un gr\u00e1fico con un n\u00famero limitado de colores: \u00bfes posible colorear el gr\u00e1fico con x colores? Si es as\u00ed, \u00bfc\u00f3mo? - tambi\u00e9n es un problema de Np-completo.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Un gr\u00e1fico plano es como m\u00e1ximo 4 crom\u00e1tico.<\/p>\n<p>Una cadena es como mucho 2-crom\u00e1tica.<\/p>\n<p>Un ciclo es como mucho 3 crom\u00e1tico.<\/p>\n<p>Una camarilla de tama\u00f1o n es n-crom\u00e1tica.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Ejemplo: un conjunto determinado de tareas debe asignarse a intervalos de tiempo, cada tarea requiere solo un intervalo. Las tareas se pueden programar en cualquier orden, pero los pares de tareas pueden entrar en conflicto en el sentido de que no se pueden asignar al mismo intervalo de tiempo, por ejemplo, porque ambos dependen de un recurso compartido. El gr\u00e1fico correspondiente contiene un v\u00e9rtice para cada trabajo y una ventaja para cada par de trabajos en conflicto. El n\u00famero crom\u00e1tico del gr\u00e1fico es exactamente el m\u00ednimo requerido, el tiempo \u00f3ptimo para completar todo el trabajo sin conflictos.<\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-cliques\"><\/span>Problema: clics<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Dado un gr\u00e1fico G no dirigido, una camarilla es un subconjunto de v\u00e9rtices que est\u00e1n todos conectados en pares por aristas. En otras palabras, es un subgrafo completo.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Encuentra un clic <strong>w<\/strong> pedido <strong>k<\/strong> en una gr\u00e1fica es un problema Np-completo.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>El siguiente gr\u00e1fico tiene una camarilla de orden 5:<\/p>\n<p><\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-2714 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique-300x291.jpg\" alt=\"hacer clic\" width=\"300\" height=\"291\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique-300x291.jpg 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/grapheclique.jpg 444w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-stables\"><\/span>Problema: estable<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Dado un gr\u00e1fico G no dirigido, un establo es un subconjunto de v\u00e9rtices que no est\u00e1n conectados en pares por aristas. Encontrar un establo de orden k equivale a encontrar una camarilla de orden k en la gr\u00e1fica inversa, es decir que tiene una arista si no existe en la gr\u00e1fica original, y viceversa.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p style=\"text-align: justify;\">Encuentra un establo <strong>Para<\/strong> de orden k en una gr\u00e1fica es un problema Np-completo.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2723\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg.png\" alt=\"estable\" width=\"280\" height=\"280\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg.png 280w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/280px-independent_set_graph-svg-150x150.png 150w\" sizes=\"(max-width: 280px) 100vw, 280px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Relation-entre-les-trois-problemes-et-heuristiques\"><\/span>Relaci\u00f3n entre los tres problemas y la heur\u00edstica<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Tenemos las siguientes tres propuestas:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>a (G) = w (no G)<\/li>\n<li>w (G) = a (no G)<\/li>\n<li>X (G)&gt; = w (G)<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>Se dice que un S estable de G es m\u00e1ximo por inclusi\u00f3n si no hay un S &#039;estable de G tal que S est\u00e9 estrictamente contenido en S&#039;. Una camarilla K es m\u00e1xima por inclusi\u00f3n si no hay camarillas K &#039;de G tales que K est\u00e9 estrictamente contenido en K&#039;.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Por esta definici\u00f3n, deducimos que un estable de orden m\u00e1ximo tambi\u00e9n es un estable m\u00e1ximo por inclusi\u00f3n, lo contrario no es cierto. La heur\u00edstica cl\u00e1sica para obtener un establo grande es buscar un establo m\u00e1ximo por inclusi\u00f3n.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2743\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2.png\" alt=\"estable\" width=\"497\" height=\"209\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2.png 497w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/stable2-300x126.png 300w\" sizes=\"(max-width: 497px) 100vw, 497px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>El algoritmo de Br\u00e9laz es un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> voraz que permite conocer un l\u00edmite m\u00e1ximo del n\u00famero crom\u00e1tico de una gr\u00e1fica. Su principio es simple y procede iterativamente.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p style=\"text-align: justify;\">Siempre que haya un v\u00e9rtice sin color, elegimos el v\u00e9rtice sin color con el mayor n\u00famero de vecinos coloreados con diferentes colores. Luego, este v\u00e9rtice se colorea con el color m\u00e1s peque\u00f1o posible (los colores se ordenan en un orden ascendente arbitrario). Si todos los colores existentes ya son usados por un vecino, agregamos un nuevo color a nuestra paleta (agregando un color con un valor m\u00e1s alto que todos los dem\u00e1s existentes).<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>La noci\u00f3n de estable tambi\u00e9n puede proporcionar indicaciones sobre el color de un gr\u00e1fico. De hecho, podemos suponer que en un establo, todos los v\u00e9rtices tienen el mismo color. Colorear en <strong>k<\/strong> colores equivale a encontrar una partici\u00f3n del conjunto de v\u00e9rtices estables en k.<\/p>\n<p><\/p>\n<p><\/p>\n<p>El algoritmo de Welsh and Powell se basa en esta proposici\u00f3n:<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li style=\"text-align: justify;\">Ordena los v\u00e9rtices del gr\u00e1fico en orden decreciente de grado<\/li>\n<li style=\"text-align: justify;\">Recorriendo la lista en orden, asigne un color no utilizado al primer v\u00e9rtice sin colorear <strong>pag<\/strong>, y asigne este color a cada v\u00e9rtice incoloro siguiente de modo que no sea adyacente al v\u00e9rtice <strong>pag<\/strong>.<\/li>\n<li style=\"text-align: justify;\">Regrese a 2 si hay v\u00e9rtices sin color en la lista. De lo contrario, devuelva la lista.<\/li>\n<\/ol>\n<\/div>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6437\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku.png\" alt=\"sudoku gr\u00e1fico para colorear\" width=\"294\" height=\"282\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Para ver la conexi\u00f3n entre Sudoku y el coloreado de gr\u00e1ficos, primero describiremos el gr\u00e1fico de Sudoku, que llamaremos por conveniencia S. El gr\u00e1fico S tiene 81 v\u00e9rtices, cada v\u00e9rtice representa una celda. Cuando dos celdas no pueden tener el mismo n\u00famero (ya sea porque est\u00e1n en la misma fila, en la misma columna o en el mismo recuadro), ponemos una arista que conecta los v\u00e9rtices correspondientes del gr\u00e1fico de Sudoku S. <\/p>\n<p>Por ejemplo, dado que las celdas a3 y a7 est\u00e1n en la misma fila, existe una arista que une sus v\u00e9rtices correspondientes; tambi\u00e9n hay una arista que conecta a1 y b3 (est\u00e1n en la misma caja), y as\u00ed sucesivamente. Cada v\u00e9rtice en el gr\u00e1fico de Sudoku tiene 20 grados y el gr\u00e1fico tiene un total de 810 aristas. S es demasiado grande para dibujarlo, pero podemos hacernos una idea de la estructura de S mirando un dibujo parcial. El dibujo muestra los 81 v\u00e9rtices de S, pero solo dos (a1 y e5) tienen su conjunto completo de aristas incidentes.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6438\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2.png\" alt=\"sudoku gr\u00e1fico para colorear\" width=\"429\" height=\"441\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2.png 429w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku2-292x300.png 292w\" sizes=\"(max-width: 429px) 100vw, 429px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>El segundo paso para convertir un Sudoku en un problema de coloraci\u00f3n de gr\u00e1ficos es asignar colores a los n\u00fameros del 1 al 9. Esta asignaci\u00f3n es arbitraria y no es un orden de prioridad de colores como en el algoritmo.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6439\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3.png\" alt=\"sudoku gr\u00e1fico para colorear\" width=\"348\" height=\"62\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3.png 348w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku3-300x53.png 300w\" sizes=\"(max-width: 348px) 100vw, 348px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>Una vez que tenemos el gr\u00e1fico de Sudoku y una asignaci\u00f3n de colores a los n\u00fameros del 1 al 9, cualquier Sudoku se puede describir mediante un gr\u00e1fico de Sudoku donde algunos de los v\u00e9rtices ya est\u00e1n coloreados (los correspondientes a los datos). Para resolver el Sudoku, todo lo que tenemos que hacer es colorear el resto de los v\u00e9rtices usando los nueve colores.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6440\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4.png\" alt=\"sudoku gr\u00e1fico para colorear\" width=\"425\" height=\"424\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4.png 425w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4-300x300.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/06\/sudoku4-150x150.png 150w\" sizes=\"(max-width: 425px) 100vw, 425px\" \/><\/figure>\n<\/div>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Teor\u00eda de grafos P\u00e1gina de inicio de Wiki Coloraci\u00f3n de grafos El problema de coloraci\u00f3n de grafos, para un grafo no dirigido G, consiste en asignar un... <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2689","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2689","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=2689"}],"version-history":[{"count":11,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2689\/revisions"}],"predecessor-version":[{"id":18432,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2689\/revisions\/18432"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=2689"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}