Parte 2 Parte 3 Parte 4 Me impulsó a escribir este artículo una tarea dañina de la búsqueda Java Multithreading, que, no sin algunas burlas por parte de los desarrolladores, fue llamada "tarea StringBuilder". La esencia de su condición era que un conjunto de palabras (en la condición en que se dan los nombres de las ciudades, lo que recuerda a un juego de palabras para niños) debían ordenarse según el principio del dominó, la última letra de la palabra n' debía ser igual a la primera letra de la palabra (n+1) go, y se sabía que todas las palabras dadas (individualmente) se sumaban en dicha cadena. Si era posible componer varias opciones para la cadena de palabras deseada, se aceptaba cualquiera como solución. A pesar de la aparente simplicidad y claridad de la condición, resolver el problema no fue nada fácil y el uso magistral de StringBuilder no salvó la situación. Los desarrolladores del problema resultaron ser isomorfos ordenados del planeta Linear Chaos, que más de una vez aterrorizaron a los cadetes de JavaRush. Como era de esperar, las soluciones superficiales no le convenían al validador, ya que siempre había cadenas que obligaban al ingenuo algoritmo a saltarse palabras. Fue necesario acumular “muletas” adicionales que, si bien complicaban el problema, no acercaban la solución en el caso general y reforzaban cada vez más la sensación de que una condición simple debería tener una solución igualmente simple. Tuve que cambiar de táctica y sumergirme un poco en áreas más fundamentales. Permítanme hacer una reserva de inmediato que en ningún caso me considero un experto en teoría de grafos; los temas que tocaré casi no van más allá del alcance de la resolución del problema verbal de dominó, con la excepción, quizás, de solo un par de digresiones de carácter teórico. Entonces, gráficos. Qué es un gráfico: es una colección (conjunto, conjunto, lista, lo que sea) de vértices conectados entre sí . Las conexiones suelen denominarse aristas , los vértices también se denominan nodos o nodos. Esta es una gráfica: Esto también es una gráfica: Si podemos decir acerca de una arista que tiene una dirección, entonces la gráfica se llama orientada : Las gráficas en las dos primeras imágenes no están dirigidas. Podemos decir de ellos que la arista (u, v) es idéntica a la arista (v, u), es decir, por ejemplo, las aristas (0, 4) y (4, 0) son la misma arista. Las flechas en los bordes de un gráfico dirigido significan que el borde (u, v) es un camino desde el vértice u al vértice v y el borde (v, u) no existe. En la tercera imagen hay un borde (E, A). No hay borde (A, E). Echemos un vistazo más de cerca al último dibujo. Puedes notar que el vértice F no tiene ninguna arista, esto es muy posible. También notamos que apareció una arista cerca del vértice A, un bucle, y entre los vértices B y D hay dos aristas dirigidas de manera diferente. Los gráficos dirigidos permiten tales artefactos. Digamos que el gráfico describe a un grupo de conocidos que se hacen regalos entre sí. Vemos que el codicioso F no le dio nada a nadie, B y D intercambiaron regalos (excepto el hecho de que cada uno de ellos le dio un regalo a otra persona), y A se dio un regalo a sí mismo, probablemente con motivo de resolver con éxito un problema. problema del planeta Caos Lineal. Por cierto, fíjate que los vértices del gráfico no tienen por qué ser números ni contener números; son más bien contenedores, es decir. Pueden almacenar cualquier objeto. Un gráfico es una descripción de conexiones. Un término importante que nos será útil más adelante: el número de aristas unidas a un vértice (o, como también dicen, incidentes con él) se llama grado de un vértice dado. Por ejemplo, en la primera imagen, el vértice 0 tiene grado 2, 1 tiene grado 4, 3 tiene grado 3, el vértice 0 de la segunda figura tiene grado 1. En este artículo no profundizaremos en la variedad de diferentes tipos de gráficos, Solo mencionaremos que también existen gráficos ponderados, esos. aquellos en los que a cada borde se le atribuye un número determinado, que indica el “precio” de su paso. Los gráficos conectados tienen varios subtipos, que se distinguen por sus propiedades. Por ejemplo, los gráficos cuyos bordes no forman un ciclo en ninguna parte se llaman árboles (tienen familias interesantes con nombres asombrosos como “árboles rojo-negro”, por ejemplo) y se usan ampliamente en una variedad de algoritmos y estructuras de datos importantes. Usar una gráfica para resolver un problema Todo esto es muy interesante, dirás, pero ¿qué tiene que ver todo esto con la construcción de una cadena de palabras? Resulta que lo más directo es. Veamos nuestro ejemplo de prueba a partir de la condición: { Amsterdam Melbourne Nueva York Kiev Viena }. Escribamos en cualquier orden las letras "nodales" a las que se adhieren las palabras: {A, M, N, K, B} y conectémoslas con palabras. Como podemos ver, tenemos un gráfico dirigido en el que los nodos son letras. y los bordes son palabras que los conectan. Si encontramos una manera de atravesar todas las aristas de vértice a vértice de modo que visitemos cada arista solo una vez, nuestro problema se resolverá. Intentemos distribuir los nodos en el diagrama de manera un poco diferente: Ahora podemos ver mejor que nuestra gráfica es un circuito cerrado. Podemos empezar la secuencia con cualquier palabra, y será la decisión acertada. Sin embargo, la condición del problema nos dice que cualquier solución será suficiente. Reemplacemos a Vena con Vladimir: Vemos dos consecuencias: en primer lugar, tuvimos que agregar un nuevo vértice, la letra P, y en segundo lugar, vemos que ya no es posible hacer un bucle en nuestro gráfico. Resumamos todo lo anterior e introduzcamos dos términos nuevos: 1. Un grafo conectado cuyos bordes se pueden atravesar visitando cada uno de ellos solo una vez se llama un grafo que contiene un “ camino euleriano” . Una característica de dicho gráfico (excepto la ausencia de vértices sin aristas) es el grado par de todos los vértices excepto dos (y solo dos). 2. Si resulta posible volver al nodo original, decimos que hay un “ciclo euleriano” en el gráfico . Una característica de dicho gráfico (a excepción de la ausencia de vértices sin aristas) es el grado par de todos los vértices. Imaginemos nuestra lista de ciudades así: {Moscú Anapa Adler Rostov-on-Don Wuhan}. Construyamos una gráfica: En el diagrama puedes ver que esta gráfica tiene un camino euleriano. Solo hay dos vértices con grado impar: estos son M y L, el resto son pares: A tiene grado 4, porque el bucle se cuenta dos veces y P e Y tienen grado 2. Si creamos un algoritmo que pueda construir una ruta euleriana basada en este esquema, digamos, en forma de lista {M, A, A, P, Y , L}, entonces resolveremos el problema , porque generar palabras en un orden determinado será solo una cuestión de técnica. Por lo tanto, la solución a nuestro problema verbal de dominó se reduce a implementar un algoritmo para encontrar una trayectoria euleriana (el ciclo es “libre”) en un gráfico dirigido. Siguiente ->
Esto también es una gráfica: 
Si podemos decir acerca de una arista que tiene una dirección, entonces la gráfica se llama orientada : 
Las gráficas en las dos primeras imágenes no están dirigidas. Podemos decir de ellos que la arista (u, v) es idéntica a la arista (v, u), es decir, por ejemplo, las aristas (0, 4) y (4, 0) son la misma arista. Las flechas en los bordes de un gráfico dirigido significan que el borde (u, v) es un camino desde el vértice u al vértice v y el borde (v, u) no existe. En la tercera imagen hay un borde (E, A). No hay borde (A, E). Echemos un vistazo más de cerca al último dibujo. Puedes notar que el vértice F no tiene ninguna arista, esto es muy posible. También notamos que apareció una arista cerca del vértice A, un bucle, y entre los vértices B y D hay dos aristas dirigidas de manera diferente. Los gráficos dirigidos permiten tales artefactos. Digamos que el gráfico describe a un grupo de conocidos que se hacen regalos entre sí. Vemos que el codicioso F no le dio nada a nadie, B y D intercambiaron regalos (excepto el hecho de que cada uno de ellos le dio un regalo a otra persona), y A se dio un regalo a sí mismo, probablemente con motivo de resolver con éxito un problema. problema del planeta Caos Lineal. Por cierto, fíjate que los vértices del gráfico no tienen por qué ser números ni contener números; son más bien contenedores, es decir. Pueden almacenar cualquier objeto. Un gráfico es una descripción de conexiones. Un término importante que nos será útil más adelante: el número de aristas unidas a un vértice (o, como también dicen, incidentes con él) se llama grado de un vértice dado. Por ejemplo, en la primera imagen, el vértice 0 tiene grado 2, 1 tiene grado 4, 3 tiene grado 3, el vértice 0 de la segunda figura tiene grado 1. En este artículo no profundizaremos en la variedad de diferentes tipos de gráficos, Solo mencionaremos que también existen gráficos ponderados, esos. aquellos en los que a cada borde se le atribuye un número determinado, que indica el “precio” de su paso. Los gráficos conectados tienen varios subtipos, que se distinguen por sus propiedades. Por ejemplo, los gráficos cuyos bordes no forman un ciclo en ninguna parte se llaman árboles (tienen familias interesantes con nombres asombrosos como “árboles rojo-negro”, por ejemplo) y se usan ampliamente en una variedad de algoritmos y estructuras de datos importantes. Usar una gráfica para resolver un problema Todo esto es muy interesante, dirás, pero ¿qué tiene que ver todo esto con la construcción de una cadena de palabras? Resulta que lo más directo es. Veamos nuestro ejemplo de prueba a partir de la condición: { Amsterdam Melbourne Nueva York Kiev Viena }. Escribamos en cualquier orden las letras "nodales" a las que se adhieren las palabras: {A, M, N, K, B} 
y conectémoslas con palabras. 
Como podemos ver, tenemos un gráfico dirigido en el que los nodos son letras. y los bordes son palabras que los conectan. Si encontramos una manera de atravesar todas las aristas de vértice a vértice de modo que visitemos cada arista solo una vez, nuestro problema se resolverá. Intentemos distribuir los nodos en el diagrama de manera un poco diferente: 
Ahora podemos ver mejor que nuestra gráfica es un circuito cerrado. Podemos empezar la secuencia con cualquier palabra, y será la decisión acertada. Sin embargo, la condición del problema nos dice que cualquier solución será suficiente. Reemplacemos a Vena con Vladimir: 
Vemos dos consecuencias: en primer lugar, tuvimos que agregar un nuevo vértice, la letra P, y en segundo lugar, vemos que ya no es posible hacer un bucle en nuestro gráfico. Resumamos todo lo anterior e introduzcamos dos términos nuevos: 1. Un grafo conectado cuyos bordes se pueden atravesar visitando cada uno de ellos solo una vez se llama un grafo que contiene un “ camino euleriano” . Una característica de dicho gráfico (excepto la ausencia de vértices sin aristas) es el grado par de todos los vértices excepto dos (y solo dos). 2. Si resulta posible volver al nodo original, decimos que hay un “ciclo euleriano” en el gráfico . Una característica de dicho gráfico (a excepción de la ausencia de vértices sin aristas) es el grado par de todos los vértices. Imaginemos nuestra lista de ciudades así: {Moscú Anapa Adler Rostov-on-Don Wuhan}. Construyamos una gráfica: 
En el diagrama puedes ver que esta gráfica tiene un camino euleriano. Solo hay dos vértices con grado impar: estos son M y L, el resto son pares: A tiene grado 4, porque el bucle se cuenta dos veces y P e Y tienen grado 2. Si creamos un algoritmo que pueda construir una ruta euleriana basada en este esquema, digamos, en forma de lista {M, A, A, P, Y , L}, entonces resolveremos el problema , porque generar palabras en un orden determinado será solo una cuestión de técnica. Por lo tanto, la solución a nuestro problema verbal de dominó se reduce a implementar un algoritmo para encontrar una trayectoria euleriana (el ciclo es “libre”) en un gráfico dirigido. Siguiente ->
GO TO FULL VERSION