{"id":24037,"date":"2025-11-18T07:09:16","date_gmt":"2025-11-18T06:09:16","guid":{"rendered":"https:\/\/www.rasc.es\/blogacademia\/?p=24037"},"modified":"2026-02-12T02:07:30","modified_gmt":"2026-02-12T01:07:30","slug":"coloreado-de-grafos","status":"publish","type":"post","link":"https:\/\/www.rasc.es\/blogacademia\/?p=24037","title":{"rendered":"Coloreado de grafos"},"content":{"rendered":"<figure id=\"attachment_24040\" aria-describedby=\"caption-attachment-24040\" style=\"width: 240px\" class=\"wp-caption alignright\"><img fetchpriority=\"high\" decoding=\"async\" class=\"size-medium wp-image-24040\" src=\"http:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/retrato-Euler-240x300.jpg\" alt=\"\" width=\"240\" height=\"300\" srcset=\"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/retrato-Euler-240x300.jpg 240w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/retrato-Euler.jpg 614w\" sizes=\"(max-width: 240px) 100vw, 240px\" \/><figcaption id=\"caption-attachment-24040\" class=\"wp-caption-text\">Leonhard Euler (1707\u20131783).<\/figcaption><\/figure>\n<p>La historia de la teor\u00eda de grafos comienza en 1736, cuando Leonhard Euler, en su art\u00edculo [1] escrito en lat\u00edn, resolvi\u00f3 el denominado <em>problema de los puentes de K\u00f6nigsberg<\/em>. En esa \u00e9poca, K\u00f6nigsberg era una ciudad de Prusia Oriental, luego fue alemana, y desde 1945 se denomina Kaliningrado y pertenece a Rusia; est\u00e1 en el enclave ruso del mismo nombre, junto al mar B\u00e1ltico, que, con quince mil kil\u00f3metros cuadrados y medio mill\u00f3n de habitantes, tiene frontera con Lituania (al este) y con Polonia (al sur). De camino hacia su desembocadura en el B\u00e1ltico, K\u00f6nigsberg estaba atravesada por el r\u00edo Pregel, que actualmente se conoce como Pregolia.<\/p>\n<p>Al atravesar K\u00f6nigsberg, el r\u00edo Pregel se bifurcaba y formaba una isla en el interior de la ciudad (y otra que se extend\u00eda hacia fuera), de manera que la ciudad quedaba dividida en 4 regiones distintas, que estaban unidas por 7 puentes, tal como se muestra en la figura.<\/p>\n<figure id=\"attachment_24042\" aria-describedby=\"caption-attachment-24042\" style=\"width: 302px\" class=\"wp-caption aligncenter\"><img decoding=\"async\" class=\"wp-image-24042 size-full\" src=\"http:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/puentes.png\" alt=\"\" width=\"302\" height=\"238\" srcset=\"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/puentes.png 302w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/puentes-300x236.png 300w\" sizes=\"(max-width: 302px) 100vw, 302px\" \/><figcaption id=\"caption-attachment-24042\" class=\"wp-caption-text\">Los puentes de K\u00f6nigsberg en la \u00e9poca de Euler.<\/figcaption><\/figure>\n<p>Por si el lector siente curiosidad por la situaci\u00f3n actual de los puentes, de los siete de la \u00e9poca de Euler, uno fue reconstruido, en el mismo lugar, en 1935, y dos de los puentes quedaron destruidos en la Segunda Guerra Mundial; m\u00e1s tarde, dos m\u00e1s fueron demolidos y sustituidos por carreteras modernas. Y, por supuesto, la ciudad ha crecido y se han a\u00f1adido puentes nuevos, as\u00ed que la configuraci\u00f3n actual ya no es la misma, pero eso no tiene relevancia en lo que aqu\u00ed perseguimos, as\u00ed que volvamos a la \u00e9poca de Euler.<\/p>\n<p>Entre los intelectuales de la ciudad, se hab\u00eda popularizado el siguiente problema:<\/p>\n<blockquote>\n<p>En la ciudad de K\u00f6nigsberg, dividida por el r\u00edo Pregel en cuatro regiones distintas unidas a trav\u00e9s de siete puentes, \u00bfes posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo s\u00f3lo una vez cada uno, y regresando al mismo punto de partida?<\/p>\n<\/blockquote>\n<p>Eso no parec\u00eda un problema matem\u00e1tico, pues las matem\u00e1ticas <em>tradicionales<\/em> no ten\u00edan ninguna utilidad para abordarlo. Ni la geometr\u00eda, ni la aritm\u00e9tica ni el c\u00e1lculo diferencial ten\u00edan ah\u00ed nada que decir. No hab\u00eda medidas, ni n\u00fameros. Si se encuentra un recorrido que cumple los requisitos, el problema ya est\u00e1 resuelto. Pero, si no lo encontramos, \u00bfc\u00f3mo saber si no hemos buscado suficientemente bien o si ese camino no puede existir? \u00bfQu\u00e9 se pod\u00eda hacer, aparte de emplear fuerza bruta e intentar probar con todos los caminos posibles?<\/p>\n<p>Para resolver el problema, Euler recurre a una abstracci\u00f3n del mapa y tiene en cuenta, exclusivamente, las regiones terrestres y las conexiones entre ellas. Cada regi\u00f3n queda representada con un punto, y cada puente mediante una l\u00ednea que une dos puntos, tal como muestra la figura. De este modo, el problema se reduce a saber si existe o no un camino que comience por uno de los puntos, recorra todas las l\u00edneas una sola vez y regrese al mismo punto de partida.<\/p>\n<figure id=\"attachment_24041\" aria-describedby=\"caption-attachment-24041\" style=\"width: 1024px\" class=\"wp-caption aligncenter\"><img decoding=\"async\" class=\"wp-image-24041 size-large\" src=\"http:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-1024x218.png\" alt=\"\" width=\"1024\" height=\"218\" srcset=\"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-1024x218.png 1024w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-300x64.png 300w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-768x164.png 768w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-1536x327.png 1536w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo.png 1752w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption id=\"caption-attachment-24041\" class=\"wp-caption-text\">Representaci\u00f3n esquem\u00e1tica de los puentes de K\u00f6nigsberg como grafo.<\/figcaption><\/figure>\n<p>Con esa formulaci\u00f3n, resolver el problema le result\u00f3, ya, muy sencillo. Si existiera un recorrido tal como el que se propone, incluso sin exigir que el punto inicial y final sean el mismo, los puntos intermedios necesariamente han de estar conectados a un n\u00famero par de l\u00edneas (si llegamos a un punto desde alguna l\u00ednea, entonces el \u00fanico modo de salir de ese punto es por una l\u00ednea diferente). Esto significa que tanto el punto inicial como el final son los \u00fanicos que podr\u00edan estar conectados a un n\u00famero impar de l\u00edneas (si el recorrido debe comenzar y acabar en el mismo punto, ese punto tampoco puede tener un n\u00famero impar de l\u00edneas). Pero hay cuatro puntos en los que inciden un n\u00famero impar de l\u00edneas, as\u00ed que tal recorrido no puede existir.<\/p>\n<p>El esquema que ide\u00f3 Euler para resolver el problema de K\u00f6nigsberg da lugar a lo que se denomina un grafo; en un grafo, los puntos se denominan <em>v\u00e9rtices<\/em> y las l\u00edneas se denominan <em>aristas<\/em>. Adem\u00e1s, y aunque aqu\u00ed no lo detallaremos, Euler resolvi\u00f3 el problema de manera mucho m\u00e1s general a como estaba planteado originalmente, demostrando que las consideraciones anteriores sobre el n\u00famero par o impar de aristas en los v\u00e9rtices dan lugar a una condici\u00f3n necesaria y suficiente para que, en un grafo cualquiera, exista un recorrido de ese tipo. No est\u00e1 de m\u00e1s comentar que las demostraciones de Euler no ten\u00edan el rigor de las matem\u00e1ticas actuales, y hay quien considera que realmente no dio una demostraci\u00f3n completa de la suficiencia; en cualquier caso, Carl Hierholzer resolvi\u00f3 definitivamente la cuesti\u00f3n con una demostraci\u00f3n algor\u00edtmica (publicada p\u00f3stumamente en 1873, m\u00e1s de cien a\u00f1os despu\u00e9s del trabajo de Euler).<\/p>\n<p>La abstracci\u00f3n de Euler supuso el nacimiento de una nueva rama de las matem\u00e1ticas, la teor\u00eda de grafos (incluso, podr\u00edamos decir, el nacimiento de la topolog\u00eda). Si bien la naturaleza est\u00e1 regida mediante ecuaciones diferenciales o en derivadas parciales (casi todas las ecuaciones importantes de la f\u00edsica lo son), estas herramientas no tienen, aqu\u00ed, ninguna utilidad. Las ecuaciones en derivadas parciales se ocupan de <em>problemas continuos<\/em>, en los que aparecen los n\u00fameros reales o los complejos, pero ahora nos encontramos con <em>problemas discretos<\/em>. Los problemas continuos est\u00e1n presentes por doquier en f\u00edsica o en ingenier\u00eda (por supuesto, tambi\u00e9n en otras ciencias, que los han incorporado m\u00e1s recientemente), pero en inform\u00e1tica son mucho m\u00e1s importantes los problemas discretos (internet es un grafo enorme, por ejemplo). De ah\u00ed el auge actual de la matem\u00e1tica discreta, pese a que no se incluye en los planes de estudio de las titulaciones cient\u00edficas, salvo en matem\u00e1ticas o en inform\u00e1tica (v\u00e9ase, por ejemplo, [3]). Lo mismo ocurre, por cierto, con la teor\u00eda de n\u00fameros y su uso en criptograf\u00eda, omnipresente en la seguridad y las comunicaciones inform\u00e1ticas.<\/p>\n<p>Hay muchas propiedades que se pueden estudiar en los grafos, pero no es \u00e9ste lugar para explicarlas. En vez de eso, y para ver la utilidad de la teor\u00eda de grafos, vamos a ver un par de problemas que se pueden analizar mediante teor\u00eda de grafos; m\u00e1s en concreto, mediante coloraciones de grafos. Para ello, s\u00f3lo vamos a necesitar decir que <em>colorear un grafo<\/em> mediante \\(k\\) colores distintos significa asignar, a cada uno de los v\u00e9rtices, uno de los \\(k\\) colores disponibles, de manera que no haya dos v\u00e9rtices adyacentes (es decir, unidos por una arista) que tengan el mismo color. Aunque no es lo que ahora nos preocupa, no est\u00e1 de m\u00e1s comentar que un problema interesante es, dado un grafo, encontrar el menor n\u00famero de colores con el que es posible colorearlo (el llamado <em>n\u00famero crom\u00e1tico<\/em> del grafo). Tanto en estos problemas, como en otros de la teor\u00eda de grafos, existen algoritmos, pero no siempre son suficientemente r\u00e1pidos, sobre todo cuando el grafo es grande. Esto hace que la teor\u00eda de grafos sea un \u00e1rea de investigaci\u00f3n muy activa.<\/p>\n<h4>Confecci\u00f3n de horarios<\/h4>\n<p>&nbsp;<\/p>\n<p>Uno de los usos del coloreado de grafos es la elaboraci\u00f3n de horarios. Si hay dos actividades que no se pueden simultanear (bien porque hay una persona que tiene que estar en las dos actividades, o porque no hay recursos suficientes para que ambas tengan lugar a la vez), esas dos actividades ser\u00e1n, en un grafo, dos v\u00e9rtices conectados por una arista, y elaborar un horario equivaldr\u00e1 a colorear un grafo. Vamos a verlo con un ejemplo sencillo, que realmente se podr\u00eda resolver por tanteo. A todos se nos pueden ocurrir ejemplos de elaboraci\u00f3n de horarios mucho m\u00e1s sofisticados que el que aqu\u00ed presentamos (es decir, grafos con muchos m\u00e1s v\u00e9rtices y aristas), de modo que automatizarlo con herramientas inform\u00e1ticas destinadas a ello facilita enormemente el trabajo.<\/p>\n<p>Supongamos que, en la sesi\u00f3n inaugural de un festival de cine, se proyectan diez pel\u00edculas. Cinco famosos cr\u00edticos cinematogr\u00e1ficos, de nombres Ana, Benito, Carlos, Daniel y Eva, han decidido ir a algunas de las pel\u00edculas, tal y como se muestra en la siguiente tabla:<\/p>\n<table class=\" aligncenter\" style=\"width: 100%;border: 1px solid black;border-collapse: collapse;border-style: solid\">\n<tbody>\n<tr>\n<td style=\"width: 10%\">Pel\u00edcula<\/td>\n<td style=\"width: 9%\">1<\/td>\n<td style=\"width: 9%\">2<\/td>\n<td style=\"width: 9%\">3<\/td>\n<td style=\"width: 9%\">3<\/td>\n<td style=\"width: 9%\">5<\/td>\n<td style=\"width: 9%\">6<\/td>\n<td style=\"width: 9%\">7<\/td>\n<td style=\"width: 9%\">8<\/td>\n<td style=\"width: 9%\">9<\/td>\n<td style=\"width: 9%\">10<\/td>\n<\/tr>\n<tr>\n<td style=\"width: 10%\">Cr\u00edtico<\/td>\n<td style=\"width: 9%\">A,B<\/td>\n<td style=\"width: 9%\">A,C<\/td>\n<td style=\"width: 9%\">A,D<\/td>\n<td style=\"width: 9%\">A,E<\/td>\n<td style=\"width: 9%\">B,C<\/td>\n<td style=\"width: 9%\">B,D<\/td>\n<td style=\"width: 9%\">B,E<\/td>\n<td style=\"width: 9%\">C,D<\/td>\n<td style=\"width: 9%\">C,E<\/td>\n<td style=\"width: 9%\">D,E<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Los organizadores del festival disponen de suficientes salas de proyecci\u00f3n, as\u00ed que puede haber tantas sesiones simult\u00e1neas como se desee (en cada sesi\u00f3n s\u00f3lo se proyecta una pel\u00edcula), pero cada pel\u00edcula la quieren proyectar una sola vez, y prefieren usar el menor n\u00famero de franjas horarias posible. Adem\u00e1s, han decidido que todos los cr\u00edticos puedan acudir a las pel\u00edculas que quieren ver. \u00bfCu\u00e1ntas franjas horarias de proyecci\u00f3n son necesarias?<\/p>\n<p>Para plantear esto como un problema de coloraci\u00f3n de grafos, construyamos un grafo en el que los v\u00e9rtices son las pel\u00edculas, y las aristas unen dos pel\u00edculas si un mismo cr\u00edtico quiere verlas. Por ejemplo, los v\u00e9rtices 1 y 2 est\u00e1n unidos por una arista pues Ana quiere ver ambas pel\u00edculas (tambi\u00e9n Benito, pero lo mismo da un cr\u00edtico interesado en ver la pel\u00edcula que m\u00e1s de uno). Los v\u00e9rtices 1 y 8 no est\u00e1n unidos porque ning\u00fan cr\u00edtico tiene intenci\u00f3n de asistir a las proyecciones de ambas pel\u00edculas. Esto da lugar al grafo de la izquierda en la figura adjunta.<\/p>\n<figure id=\"attachment_24063\" aria-describedby=\"caption-attachment-24063\" style=\"width: 1024px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-24063 size-large\" src=\"http:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis-1024x495.png\" alt=\"\" width=\"1024\" height=\"495\" srcset=\"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis-1024x495.png 1024w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis-300x145.png 300w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis-768x371.png 768w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis-1536x742.png 1536w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-pelis.png 1589w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption id=\"caption-attachment-24063\" class=\"wp-caption-text\">Interpretaci\u00f3n de las restricciones de un horario como grafo, y su coloraci\u00f3n.<\/figcaption><\/figure>\n<p>Podemos suponer que cada franja horaria es un color, y dos pel\u00edculas conectadas por alguna arista no pueden compartir franja horaria de proyecci\u00f3n; es decir, tienen que ser v\u00e9rtices de distinto color. As\u00ed que lo que tenemos que hacer es colorear el grafo con el menor n\u00famero posible de colores.<\/p>\n<p>La teor\u00eda de coloraciones de grafos (que aqu\u00ed no vamos a explicar) nos asegura que es imposible conseguirlo con menos de cinco colores. Con cinco colores s\u00ed se puede, tal como se ve en la parte derecha de la figura (la soluci\u00f3n no es \u00fanica). As\u00ed, la organizaci\u00f3n ha de reservar cinco franjas horarias: la primera para las pel\u00edculas 1 y 9 (se proyectan a la vez en salas distintas), la segunda para las pel\u00edculas 2 y 6, la tercera para las pel\u00edculas 3 y 7, la cuarta para las pel\u00edculas 4 y 8, y la quinta para las pel\u00edculas 5 y\u00a010.<\/p>\n<h4>Resolver un sudoku es colorear un grafo<\/h4>\n<p>&nbsp;<\/p>\n<p>Un sudoku habitual, de tama\u00f1o \\(9 \\times 9\\), es una cuadr\u00edcula con \\(9\\) filas, \\(9\\) columnas y \\(9\\) bloques de tama\u00f1o \\(3\\times3\\), como en la figura.<\/p>\n<figure id=\"attachment_24049\" aria-describedby=\"caption-attachment-24049\" style=\"width: 300px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-24049 size-medium\" src=\"http:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/sudoku-300x297.png\" alt=\"\" width=\"300\" height=\"297\" srcset=\"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/sudoku-300x297.png 300w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/sudoku-150x150.png 150w, https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/sudoku.png 590w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><figcaption id=\"caption-attachment-24049\" class=\"wp-caption-text\">Plantilla de un sudoku [latex]9 \\times 9[\/latex] sin rellenar.<\/figcaption><\/figure>\n<p>Resolver un sudoku es rellenarlo con n\u00fameros del \\(1\\) al \\(9\\) con un n\u00famero en cada casilla, de forma que cada fila, cada columna y cada bloque contenga los n\u00fameros \\(\\{1, 2,\\dots, 9\\}\\) exactamente una vez (cuando se emplea como pasatiempo, que es lo habitual, el sudoku comienza con algunas casillas ya rellenadas, y el objetivo es rellenar el resto, pero eso no es relevante ahora).<\/p>\n<p>\u00bfQu\u00e9 tiene que ver un sudoku con la teor\u00eda de grafos? Para ver la relaci\u00f3n, construimos un grafo de la siguiente forma:<\/p>\n<ol>\n<li>Cada casilla va a ser un v\u00e9rtice del grafo, con lo cual el grafo tendr\u00e1 \\(9^2 = 81\\) v\u00e9rtices.<\/li>\n<li>Dos v\u00e9rtices estar\u00e1n unidos por una arista si no pueden tener el mismo n\u00famero, es decir, si las correspondientes casillas est\u00e1n en la misma fila, en la misma columna o en el mismo bloque \\(3\\times3\\). No es complicado ver que, de esa forma, el grafo tiene \\(810\\) aristas: a cada v\u00e9rtice le corresponden \\(8\\) aristas de su bloque \\(3\\times3\\), \\(6\\) m\u00e1s de de su fila, y \\(6\\) m\u00e1s de su columna, luego de cada v\u00e9rtice salen \\(20\\) aristas; eso da un total de \\(81 \\cdot 20\/2 = 810\\) aristas (se divide por \\(2\\) pues cada arista la hab\u00edamos contado dos veces, una por cada uno de los dos v\u00e9rtices que une).\u00a0<\/li>\n<\/ol>\n<p>Resolver un sudoku es rellenarlo usando \\(9\\) n\u00fameros; pero dar\u00eda igual usar \\(9\\) n\u00fameros o \\(9\\) colores. As\u00ed pues, resolver un sudoku es exactamente lo mismo que encontrar una coloraci\u00f3n del grafo usando \\(9\\) colores. De este modo, los sudokus y su soluci\u00f3n han quedado modelizados por medio de la teor\u00eda de grafos, y podr\u00edamos utilizar los algoritmos de la teor\u00eda de grafos para resolver sudokus, con varias casillas previamente rellenadas; un ordenador con un programa adecuado lo podr\u00eda hacer de manera pr\u00e1cticamente instant\u00e1nea. Por supuesto, no es eso lo que se pretende, ya que resolver un sudoku es un desaf\u00edo mental y la idea es resolverlo pensando. Pero s\u00ed que puede ser \u00fatil para construir sudokus. Desde luego, esto se puede aplicar no s\u00f3lo a sudokus \\(9 \\times 9\\), sino de cualquier otro tama\u00f1o; se pueden construir sudokus de tama\u00f1o \\(n^2 \\times n^2\\) para cualquier entero \\(n \\ge 2\\): tendr\u00e1n \\(n^2\\) filas, \\(n^2\\) columnas y \\(n^2\\) bloques de tama\u00f1o \\(n \\times n\\), y hay que rellenarlos usando los n\u00fameros desde \\(1\\) hasta \\(n^2\\), lo cual equivale a colorear el correspondiente grafo con \\(n^2\\) colores.<\/p>\n<p>Para finalizar, y como curiosidad, comentemos que el n\u00famero de formas distintas de rellenar un sudoku \\(9 \\times 9\\) (es decir, el n\u00famero de sudokus distintos que se pueden construir) es enorme, y no es f\u00e1cil de calcular. Dicho n\u00famero es<br \/>\n\\(6\\,670\\,903\\,752\\,021\\,072\\,936\\,960 \\approx 6.671 \\cdot 10^{21}\\), v\u00e9ase [4] o [2]. Asimismo, hay \\(288\\) sudokus distintos de tama\u00f1o \\(4 \\times 4\\); pero, para sudokus de tama\u00f1o \\(16 \\times 16\\), su n\u00famero no se conoce.<\/p>\n<h4>Referencias<\/h4>\n<p>&nbsp;<\/p>\n<p>[1] L. Euler, Solutio problematis ad geometriam situs pertinensis, <em>Commentarii Academiae Scientarum Imperialis Petropolitanae<\/em> <strong>8<\/strong> (1736), 128\u2013140. Reimpreso en <em>Opera Omnia Series Prima<\/em>, Vol. 7, pp. 1\u201310, 1766.<\/p>\n<p>[2] B. Felgenhauer y F. Jarvis, Mathematics of Sudoku I, <em>Mathematical Spectrum<\/em> <strong>39<\/strong> (2006\/2007), no. 1, 15\u201322.<\/p>\n<p>[3] J. M. Guti\u00e9rrez Jim\u00e9nez y V. Lanchares Barrasa, <em>Elementos de matem\u00e1tica discreta<\/em>, Servicio de Publicaciones de la Universidad de La Rioja, 2010.<\/p>\n<p>[4] K. Y. Lin, Number of Sudokus, <em>Journal of Recreational Mathematics<\/em>\u00a0<strong>33<\/strong> (2004), no. 2, 120\u2013124.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La historia de la teor\u00eda de grafos comienza en 1736, cuando Leonhard Euler, en su art\u00edculo [1] escrito en lat\u00edn, resolvi\u00f3 el denominado problema de los puentes de K\u00f6nigsberg. En esa \u00e9poca, K\u00f6nigsberg era una ciudad de Prusia Oriental, luego fue alemana, y desde 1945 se denomina Kaliningrado y pertenece a Rusia; est\u00e1 en el [&hellip;]<\/p>\n","protected":false},"author":78,"featured_media":24060,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2802],"tags":[],"ppma_author":[2896],"class_list":["post-24037","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-mathema"],"jetpack_featured_media_url":"https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png","uagb_featured_image_src":{"full":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false],"thumbnail":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo-150x150.png",150,150,true],"medium":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo-300x238.png",300,238,true],"medium_large":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false],"large":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false],"1536x1536":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false],"2048x2048":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false],"bdpp-medium":["https:\/\/www.rasc.es\/blogacademia\/wp-content\/uploads\/2025\/08\/grafo-dos-colores-curvo.png",462,367,false]},"uagb_author_info":{"display_name":"Juan Luis Varona","author_link":"https:\/\/www.rasc.es\/blogacademia\/?author=78"},"uagb_comment_info":1,"uagb_excerpt":"La historia de la teor\u00eda de grafos comienza en 1736, cuando Leonhard Euler, en su art\u00edculo [1] escrito en lat\u00edn, resolvi\u00f3 el denominado problema de los puentes de K\u00f6nigsberg. En esa \u00e9poca, K\u00f6nigsberg era una ciudad de Prusia Oriental, luego fue alemana, y desde 1945 se denomina Kaliningrado y pertenece a Rusia; est\u00e1 en el&hellip;","jetpack_sharing_enabled":true,"authors":[{"term_id":2896,"user_id":78,"is_guest":0,"slug":"elvarona","display_name":"Juan Luis Varona","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/03d96fbfeb4ff58ee11f43b3ff00cf7562de82f9bad7bfb936b2276380e1dbef?s=96&d=mm&r=g","author_category":"","first_name":"Juan Luis","last_name":"Varona","user_url":"","job_title":"","description":"Matem\u00e1tico, alfare\u00f1o nacido en Tudela. Profesor del Departamento de Matem\u00e1ticas y Computaci\u00f3n de la Universidad de La Rioja (Logro\u00f1o)"}],"_links":{"self":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/24037","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=24037"}],"version-history":[{"count":20,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/24037\/revisions"}],"predecessor-version":[{"id":24723,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/posts\/24037\/revisions\/24723"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=\/wp\/v2\/media\/24060"}],"wp:attachment":[{"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=24037"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=24037"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=24037"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.rasc.es\/blogacademia\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=24037"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}