Fundamentos de teoría de grafos, historia del origen y desarrollo.  ¿Qué es una gráfica? Una gráfica: definición - History.NES Historia de la teoría de grafos

picos(nodos) conectados costillas. En una definición estricta, una gráfica es un par de conjuntos GRAMO = (V, mi) (\displaystyle G=(V,E)), Dónde V (\displaystyle V) es un subconjunto de cualquier conjunto contable, y mi (\ Displaystyle E)- subconjunto V × V (\displaystyle V\times V).

La teoría de grafos encuentra aplicación, por ejemplo, en los sistemas de información geográfica (SIG). Las casas, estructuras, bloques, etc. existentes o de nuevo diseño se consideran vértices, y las carreteras, redes de servicios públicos, líneas eléctricas, etc. que los conectan se consideran bordes. El uso de diversos cálculos realizados en dicho gráfico permite, por ejemplo, encontrar la ruta de desvío más corta o la tienda de comestibles más cercana, o planificar la ruta óptima.

La teoría de grafos contiene una gran cantidad de problemas sin resolver e hipótesis aún no probadas.

Historia de la teoría de grafos

Leonard Euler es considerado el fundador de la teoría de grafos. En 1736, en una de sus cartas, formuló y propuso una solución al problema de los siete puentes de Königsberg, que más tarde se convirtió en uno de los problemas clásicos de la teoría de grafos. El término "gráfico" fue acuñado por primera vez por Sylvester, James Joseph en 1878 en su artículo en Nature [ ] .

Terminología de la teoría de grafos

Aplicación de la teoría de grafos

ver también

Notas

Literatura

• Distel R. Teoría de grafos Trans. De inglés - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - 336 p. ISBN 5-86134-101-X.
• Diestel R. Teoría de grafos, edición electrónica. - Nueva York: Springer-Verlag, 2005. - P. 422.
• Basaker R., Saati T. Grafos finitos y redes. M.: Nauka, 1974. 368c.
• Belov V.V., Vorobiev E.M., Shatalov V.E. Teoría de grafos. - M.: Más alto. escuela, 1976. - P. 392.
• Bergé K. Teoría de grafos y sus aplicaciones. M.: Illinois, 1962. 320c.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Conferencias sobre teoría de grafos. M.: Nauka, 1990. 384 p. (Ed. 2, M. revisado: URSS, 2009. 392 p.)

Leonard Euler es considerado el fundador de la teoría de grafos. En 1736, en una de sus cartas, formuló y propuso una solución al problema de los siete puentes de Königsberg, que más tarde se convirtió en uno de los problemas clásicos de la teoría de grafos.

Los primeros problemas de la teoría de grafos estaban relacionados con la resolución de problemas y acertijos matemáticos recreativos. Aquí hay un recuento de un extracto de la carta de Euler del 13 de marzo de 1736: “Me dieron un problema sobre una isla ubicada en la ciudad de Königsberg y rodeada por un río con siete puentes que la cruzan. La cuestión es si alguien puede rodearlos continuamente, pasando sólo una vez por cada puente. Y luego me informaron que nadie había podido hacer esto todavía, pero nadie había demostrado que fuera imposible. Esta cuestión, aunque trivial, me pareció, sin embargo, digna de atención en el sentido de que ni la geometría, ni el álgebra, ni el arte combinatorio son suficientes para resolverla. Después de mucho pensar, encontré una regla fácil, basada en una prueba completamente convincente, con la ayuda de la cual es posible, en todos los problemas de este tipo, determinar inmediatamente si tal desvío se puede hacer a través de cualquier número y cualquier número de puentes ubicados de cualquier forma o no”. Los puentes de Königsberg se pueden representar esquemáticamente de la siguiente manera:

Regla de Euler:

1. En un gráfico que no tiene vértices de grados impares, hay un recorrido de todas las aristas (y cada arista se atraviesa exactamente una vez) comenzando en cualquier vértice del gráfico.

2. En un gráfico que tiene dos y sólo dos vértices de grado impar, hay un recorrido que comienza en un vértice de grado impar y termina en el otro.

3. En un gráfico que tiene más de dos vértices con grados impares, dicho recorrido no existe.

Existe otro tipo de problema relacionado con viajar a lo largo de gráficos. Estamos hablando de problemas en los que es necesario encontrar un camino que pase por todos los vértices, y no más de una vez por cada uno. Un ciclo que pasa por cada vértice una y sólo una vez se llama línea hamiltoniana (en honor a William Rowan Hamilton, el famoso matemático irlandés del siglo pasado que fue el primero en estudiar tales líneas). Desafortunadamente, todavía no se ha encontrado un criterio general con el que se pueda decidir si una gráfica dada es hamiltoniana y, de ser así, encontrar todas las rectas hamiltonianas en ella.

Formulado a mediados del siglo XIX. El problema de los cuatro colores también parece un problema entretenido, pero los intentos de resolverlo han dado lugar a algunos estudios de gráficos que tienen importancia teórica y aplicada. El problema de los cuatro colores se formula de la siguiente manera: "¿Se puede colorear un área de cualquier mapa plano con cuatro colores de modo que dos áreas adyacentes cualesquiera se coloreen con colores diferentes?" La hipótesis de que la respuesta es afirmativa se formuló a mediados del siglo XIX. En 1890 se demostró una afirmación más débil: cualquier mapa plano se puede colorear con cinco colores. Al asociar cualquier mapa plano con su gráfico plano dual, obtenemos una formulación equivalente del problema en términos de gráficos: ¿Es cierto que el número cromático de cualquier gráfico plano es menor o igual a cuatro? Numerosos intentos de resolver el problema influyeron en el desarrollo de varias áreas de la teoría de grafos. En 1976 se anunció una solución positiva al problema utilizando una computadora.

Otro viejo problema topológico que durante mucho tiempo ha sido particularmente difícil de resolver y que ha atormentado las mentes de los amantes de los rompecabezas es el conocido como "problema del suministro de electricidad, gas y agua". En 1917, Henry E. Dudeney le dio esta formulación. Se debe instalar gas, electricidad y agua en cada una de las tres casas que se muestran en la figura.

Teoría de grafos. 1

La historia del surgimiento de la teoría de grafos. 1

La regla de Euler. 1

Literatura

1. Teoría de grafos de Belov, Moscú, "Ciencia", 1968.

2. Nuevas tecnologías pedagógicas y de la información E.S. Polat , Moscú, "Academia" 1999

3. Kuznetsov O.P., Adelson-Velsky G.M. Matemáticas discretas para el ingeniero. – M.: Energoatomizdat, 1988.

4. Cook D., Baze G. Matemáticas informáticas. – M.: Ciencia, 1990.

5. Nefedov V.N., Osipova V.A. Curso de matemáticas discretas. – M.: Editorial MAI, 1992.

6. Ore O. Teoría de grafos. – M.: Ciencia, 1980.

7. Ismagilov R.S., Kalinkin A.V. Materiales para las lecciones prácticas del curso: Matemática Discreta

Se considera que el fundador de la teoría de grafos es el matemático Leonhard Euler (1707-1783). La historia de esta teoría se puede rastrear a través de la correspondencia del gran científico. Aquí hay una traducción del texto latino, tomado de la carta de Euler al matemático e ingeniero italiano Marinoni, enviada desde San Petersburgo el 13 de marzo de 1736 [ver. págs. 41-42]:

"Una vez me plantearon un problema sobre una isla situada en la ciudad de Königsberg y rodeada por un río sobre el cual hay siete puentes. La pregunta es si alguien puede rodearlos continuamente, pasando sólo una vez por cada puente. Y entonces me preguntaron "Nadie ha podido hacer esto todavía, pero nadie ha demostrado que sea imposible. Esta cuestión, aunque trivial, me pareció sin embargo digna de atención porque ni la geometría, ni el álgebra, ni el arte combinatorio son suficiente para resolverlo... Después de mucho pensar, encontré una regla fácil, basada en una prueba completamente convincente, con la ayuda de la cual es posible determinar inmediatamente en todos los problemas de este tipo si tal desvío se puede tomar a través de algún cantidad de puentes ubicados de cualquier forma o no, de manera que se pueden representar en la siguiente figura[Figura 1] , en el que A denota una isla, y B, C y D, partes del continente, separadas entre sí por brazos de ríos. Los siete puentes están etiquetados como a, b, c, d, e, f, g."

(FIGURA 1.1)

Respecto al método que descubrió para resolver problemas de este tipo, Euler escribió [ver. págs. 102-104]:

“Esta solución, por su naturaleza, aparentemente tiene poco que ver con las matemáticas, y no entiendo por qué uno debería esperar esta solución de un matemático y no de cualquier otra persona, ya que esta decisión se sustenta únicamente en el razonamiento, y no hay "Es necesario involucrar para encontrar esta solución, cualquier ley inherente a las matemáticas. Por lo tanto, no sé cómo resulta que las preguntas que tienen muy poco que ver con las matemáticas tienen más probabilidades de ser resueltas por matemáticos que por otros".

Entonces, ¿es posible rodear los puentes de Königsberg pasando sólo una vez por cada uno de estos puentes? Para encontrar la respuesta, continuemos con la carta de Euler a Marinoni:

0 "La pregunta es determinar si es posible rodear estos siete puentes, pasando por cada uno solo una vez, o no. Mi regla conduce a la siguiente solución a esta pregunta. En primer lugar, debes mirar cuántos Las secciones allí están separadas por agua, aquellas que no tienen otro paso de una a otra excepto a través de un puente. En este ejemplo, hay cuatro secciones de este tipo: A, B, C, D. A continuación, debe distinguir si el número de los puentes que conducen a estas secciones individuales son pares o impares. Entonces, en nuestro caso, cinco puentes conducen a la sección A y tres puentes cada uno al resto, es decir, el número de puentes que conducen a las secciones individuales es impar, y esto por sí solo es suficiente para resolver el problema. Una vez determinado esto, aplicamos la siguiente regla: si el número de puentes que conducen a cada tramo por separado fuera par, entonces el desvío en cuestión sería posible, y al mismo tiempo sería posible iniciar este desvío desde cualquier tramo, si fueran impares, porque sólo uno no puede ser impar, entonces incluso entonces se podría completar la transición, como está prescrito, pero ciertamente sólo se debe tomar el comienzo del desvío de uno de esos dos tramos a los que se une un número impar de conduce puentes. Si, finalmente, hubiera más de dos secciones a las que conduce un número impar de puentes, entonces tal movimiento es generalmente imposible... si se pudieran traer aquí otros problemas más serios, este método podría ser aún más beneficioso y debería no ser descuidado".

La justificación de la regla anterior se puede encontrar en una carta de L. Euler a su amigo Ehler fechada el 3 de abril del mismo año. Relataremos a continuación un extracto de esta carta.

El matemático escribió que la transición es posible si en la bifurcación del río no hay más de dos zonas a las que conduce un número impar de puentes. Para que sea más fácil imaginar esto, borraremos en la figura los puentes ya atravesados. Es fácil comprobar que si comenzamos a movernos de acuerdo con las reglas de Euler, cruzamos un puente y lo borramos, entonces la figura mostrará una sección donde nuevamente no hay más de dos áreas a las que conduce un número impar de puentes, y si hay Son zonas con un número impar de puentes estaremos ubicados en uno de ellos. Siguiendo así, cruzaremos todos los puentes una vez.

La historia de los puentes de la ciudad de Königsberg tiene una continuación moderna. Abramos, por ejemplo, un libro de texto escolar sobre matemáticas editado por N.Ya. Vilenkina para sexto grado. En él, en la página 98, bajo el título de desarrollar la atención y la inteligencia, encontraremos un problema que está directamente relacionado con el que alguna vez resolvió Euler.

Problema número 569. Hay siete islas en el lago, que están conectadas entre sí como se muestra en la Figura 1.2. ¿A qué isla debe llevar un barco a los viajeros para que puedan cruzar cada puente y solo una vez? ¿Por qué no se puede transportar a los viajeros a la isla? A?

Solución. Dado que este problema es similar al problema de los puentes de Königsberg, a la hora de resolverlo utilizaremos también la regla de Euler. Como resultado, obtenemos la siguiente respuesta: el barco debe llevar a los viajeros a la isla. mi o F para que puedan cruzar cada puente una vez. De la misma regla de Euler se deduce que el desvío requerido es imposible si parte de la isla. A.

En conclusión, observamos que el problema de los puentes de Königsberg y problemas similares, junto con un conjunto de métodos para su estudio, constituyen una rama muy importante de las matemáticas en términos prácticos, llamada teoría de grafos. El primer trabajo sobre gráficos perteneció a L. Euler y apareció en 1736. Posteriormente, Koenig (1774-1833), Hamilton (1805-1865) y los matemáticos modernos C. Berge, O. Ore y A. Zykov trabajaron en gráficos.

Teoría de grafos- una de las secciones más extensas de las matemáticas discretas, ampliamente utilizada en la resolución de problemas económicos y de gestión, en programación, química, diseño y estudio de circuitos eléctricos, comunicaciones, psicología, psicología, sociología, lingüística y otros campos del conocimiento. Teoría de grafos Estudia sistemática y consistentemente las propiedades de las gráficas, que se puede decir que consisten en conjuntos de puntos y conjuntos de líneas que representan las conexiones entre estos puntos. Se considera que el fundador de la teoría de grafos fue Leonhard Euler (1707-1882), quien resolvió el entonces conocido problema de los puentes de Königsberg en 1736.

Se construyen gráficos para mostrar relaciones en conjuntos. Sea, por ejemplo, un conjunto A = {a1 , a 2 , ... a norte)- mucha gente y cada elemento se mostrará como un punto. Un montón de B = {b1 , b 2 , ... b metro)- muchas conexiones (líneas rectas, arcos, segmentos, todavía no importa). En el set A Se da la relación de conocimiento entre personas de este conjunto. Construyendo un gráfico a partir de puntos y conectivos. Los enlaces conectarán a pares de personas que se conocen. Naturalmente, el número de conocidos de algunas personas puede diferir del número de conocidos de otras personas, y es posible que algunos no conozcan a nadie (tales elementos serán puntos que no están conectados con ningún otro). ¡Así que tenemos un gráfico!

Lo que primero llamamos "puntos" deberían llamarse vértices del gráfico, y lo que llamamos "conexiones" deberían llamarse aristas del gráfico.

La teoría de grafos no tiene en cuenta la naturaleza específica de los conjuntos. A Y B. Hay una gran cantidad de problemas específicos muy diferentes, a la hora de resolverlos uno puede olvidarse temporalmente del contenido específico de los conjuntos y sus elementos. ¡Esta especificidad no afecta de ninguna manera el progreso en la resolución del problema, independientemente de su dificultad! Por ejemplo, al decidir si es posible desde un punto a llegar al punto mi, moviéndose solo a lo largo de las líneas que conectan los puntos, no importa si se trata de personas, ciudades, números, etc. Pero, cuando se resuelve el problema, obtenemos una solución que es válida para cualquier contenido que haya sido modelado como un gráfico. No es de extrañar, por tanto, que la teoría de grafos sea una de las herramientas más populares en la creación de inteligencia artificial: después de todo, la inteligencia artificial puede discutir con un interlocutor cuestiones relacionadas con el amor, la música o los deportes, y cuestiones relativas a la resolución de diversos problemas. , y lo hace sin ninguna transición (cambio) , sin la cual una persona no puede prescindir en tales casos.

Y ahora las definiciones matemáticas estrictas de un gráfico.

Definición 1.se llama grafico un sistema de objetos de naturaleza arbitraria (vértices) y enlaces (aristas) que conectan algunos pares de estos objetos.

Definición 2. Dejar V– conjunto (no vacío) de vértices, elementos v∈V- picos. Grafico GRAMO = GRAMO(V) con muchos vértices V existe una determinada familia de pares de la forma: mi = (a, b) , Dónde a,b∈V , indicando qué vértices permanecen conectados. Cada pareja mi = (a, b) - borde del gráfico. Un montón de Ud.- muchos bordes mi grafico. Picos a Y b– puntos finales del borde mi .

Gráficos como estructura de datos. El uso generalizado de la teoría de grafos en la informática y la tecnología de la información se debe a la adición del concepto de gráfico como estructura de datos a las definiciones anteriores. En informática y tecnología de la información, un gráfico se define como una estructura de datos no lineal. ¿Qué es entonces una estructura de datos lineal y en qué se diferencian los gráficos de ellos? Las estructuras de datos lineales se caracterizan por conectar elementos mediante relaciones del tipo “vecindad simple”. Las estructuras de datos lineales son, por ejemplo, matrices, tablas, listas, colas, pilas y cadenas. Por el contrario, las estructuras de datos no lineales son aquellas en las que los elementos se ubican en diferentes niveles de la jerarquía y se dividen en tres tipos: originales, generadas y similares. Entonces, un gráfico es una estructura de datos no lineal.

La palabra gráfico es de origen griego, de las palabras “escribo”, “describo”. Desde el principio de este artículo sabemos qué describe exactamente el gráfico: describe relaciones. Es decir, cualquier gráfico describe relaciones. Y viceversa: cualquier relación se puede describir como un gráfico.

Conceptos básicos de la teoría de grafos.

El concepto de incidencia también es necesario al desarrollar algoritmos para resolver muchos problemas prácticos con gráficos. Por ejemplo, puede familiarizarse con la implementación del software. primer recorrido en profundidad del gráfico representado por la matriz de incidencia. La idea es simple: sólo puedes moverte a través de vértices conectados por aristas. Y si se asignan algunos valores a los bordes ("escalas", generalmente en forma de números, estos gráficos se denominan ponderados o etiquetados), entonces se pueden resolver problemas aplicados complejos, algunos de los cuales se mencionan en el párrafo final. de esta lección.

Problemas clásicos de la teoría de grafos y sus soluciones.

Uno de los primeros ejemplos publicados de trabajos sobre teoría de grafos y su aplicación es el trabajo sobre el “Problema de los puentes de Königsberg” (1736), escrito por el eminente matemático del siglo XVIII Leonhard Euler. El problema contiene un río, islas bañadas por este río y varios puentes. Pregunta del problema: ¿es posible, después de abandonar un determinado punto, cruzar cada puente una sola vez y volver al punto de partida? (imagen debajo)

El problema se puede modelar de la siguiente manera: un punto está unido a cada área de tierra y dos puntos están conectados por una línea si y solo si las áreas de tierra correspondientes están conectadas por un puente (figura siguiente, las líneas de conexión están dibujadas con líneas de puntos) . Así, se construye el gráfico.

La respuesta de Euler a la pregunta del problema es la siguiente. Si este problema tuviera una solución positiva, entonces en el gráfico resultante habría un camino cerrado que pasaría a lo largo de los bordes y contendría cada borde solo una vez. Si tal camino existe, entonces cada vértice debe tener sólo un número par de aristas. Pero el gráfico resultante tiene vértices que tienen un número impar de aristas. Por tanto, el problema no tiene una solución positiva.

Según la tradición establecida, un grafo euleriano es un grafo en el que es posible atravesar todos los vértices y al mismo tiempo atravesar una arista solo una vez. En él, cada vértice debe tener sólo un número par de aristas. Un problema de dificultad media sobre gráficas de Euler se encuentra en el material “Tipos básicos de gráficas”.

En 1847, Kirchhoff desarrolló la teoría de árboles para resolver un sistema simultáneo de ecuaciones algebraicas lineales, permitiendo encontrar el valor de la corriente en cada conductor (arco) y en cada circuito de un circuito eléctrico. Haciendo abstracción de los circuitos eléctricos y los circuitos que contienen resistencias, condensadores, inductancias, etc., consideró las estructuras combinatorias correspondientes que contienen solo vértices y conexiones (bordes o arcos), y para las conexiones no es necesario tener en cuenta qué tipos de elementos eléctricos. corresponden a. Así, Kirchhoff reemplazó cada circuito eléctrico con su gráfica correspondiente y demostró que para resolver un sistema de ecuaciones no es necesario considerar cada ciclo de la gráfica del circuito eléctrico por separado.

Cayley en 1858, mientras trabajaba en problemas puramente prácticos de química orgánica, descubrió una importante clase de gráficos llamados árboles. Trató de enumerar los isómeros de los hidrocarburos saturados, con un número determinado de átomos de carbono. Cayley formuló por primera vez el problema de manera abstracta: encuentre el número de todos los árboles con pag vértices, cada uno de los cuales tiene vértices con grados 1 y 4. No pudo resolver este problema de inmediato y comenzó a cambiar su formulación de tal manera que se pudiera resolver un nuevo problema de enumeración:

• árboles enraizados (en los que se selecciona uno de los vértices);
• todos los árboles;
• árboles cuyos grados de vértice no excedan de 4;
• árboles cuyos grados de vértice son 1 y 4 (planteamiento de un problema de química).

Problemas de gráficas para reforzar conceptos básicos.

Ejemplo 1. Dejar A- conjunto de números 1, 2, 3: A= (1, 2, 3) . Construya una gráfica para mostrar la relación "

Solución. Obviamente, los números 1, 2, 3 deben representarse como los vértices de un gráfico. Entonces cada par de vértices debe estar conectado por una arista. Resolviendo este problema, llegamos a conceptos básicos de la teoría de grafos como grafos dirigidos y no dirigidos. Los grafos no dirigidos son aquellos cuyas aristas no tienen dirección. O, como se suele decir aún más a menudo, el orden de los dos extremos de una arista no es significativo. De hecho, el gráfico construido al comienzo de esta lección y que refleja la relación de conocimiento entre personas no necesita direcciones de borde, ya que se puede argumentar que la "persona número 1" está familiarizada con la "persona número 2" en la misma medida. como "persona número 2" por "persona número 1". En nuestro ejemplo actual, un número es menor que otro, pero no al revés. Por lo tanto, el borde correspondiente del gráfico debe tener una dirección que indique qué número es menor que el otro. Es decir, el orden de los extremos de los bordes es significativo. Un gráfico de este tipo (con aristas que tienen una dirección) se llama gráfico dirigido o dígrafo.

Entonces, en nuestra multitud A el número 1 es menor que el número 2 y el número 3, y el número 2 es menor que el número 3. Mostramos este hecho mediante aristas que tienen una dirección, que se muestra mediante flechas. Obtenemos el siguiente gráfico:

Ejemplo 2. Dejar A- conjunto de números 2, 4, 6, 14: A= (2, 4, 6, 14) . Crea un gráfico para mostrar la relación “divisible por” en este conjunto.

Solución. En este ejemplo, algunos de los bordes tendrán una dirección y otros no, es decir, estamos construyendo grafico mixto. Enumeremos las relaciones en el conjunto: 4 es divisible por 2, 6 es divisible por 2, 14 es divisible por 2 y cada número de este conjunto es divisible por sí mismo. Esta relación, es decir, cuando un número es divisible por sí mismo, se mostrará en forma de aristas que conectan el vértice consigo mismo. Estos bordes se llaman bucles. En este caso no es necesario darle dirección al bucle. Entonces, en nuestro ejemplo hay tres aristas dirigidas regulares y cuatro bucles. Obtenemos el siguiente gráfico:

Ejemplo 3. Sean conjuntos dados A= (α, β, γ) y B= (a, b, c) . Construya una gráfica para mostrar la relación “producto cartesiano de conjuntos”.

Solución. Como se sabe por la definición Producto cartesiano de conjuntos., no existen conjuntos ordenados de elementos del mismo conjunto. Es decir, en nuestro ejemplo, no se pueden combinar letras griegas con griego y latín con latín. Este hecho se muestra como gráfica bipartita, es decir, aquel en el que los vértices se dividen en dos partes de manera que los vértices pertenecientes a una misma parte no estén conectados entre sí. Obtenemos el siguiente gráfico:

Ejemplo 4. En la agencia inmobiliaria trabajan los directores Igor, Sergey y Peter. Se reparan los objetos O1, O2, O3, O4, O5, O6, O7, O8. Construya un gráfico para mostrar las relaciones "Igor trabaja con los objetos O4, O7", "Sergey trabaja con los objetos O1, O2, O3, O5, O6", "Peter trabaja con el objeto O8".

Solución. El gráfico que muestra estas relaciones también será bipartito, ya que el administrador no trabaja con el administrador y el objeto no funciona con el objeto. Sin embargo, a diferencia del ejemplo anterior, la gráfica estará dirigida. De hecho, por ejemplo, Igor trabaja con el objeto O4, pero el objeto O4 no funciona con Igor. A menudo, cuando esa propiedad de las relaciones es obvia, la necesidad de dar dirección a los bordes puede parecer una “estupidez matemática”. Pero aún así, y esto se deriva de la naturaleza estricta de las matemáticas, si la relación es unilateral, entonces es necesario dar direcciones a los bordes. En aplicaciones relacionales, este rigor vale la pena, por ejemplo, en programas diseñados para la planificación, donde también se utilizan gráficos y el recorrido a lo largo de vértices y aristas debe pasar estrictamente en una dirección determinada. Entonces, obtenemos el siguiente gráfico bipartito dirigido:

Y nuevamente a ejemplos con números.

Ejemplo 5. Deja que se dé un conjunto C = {2, 3, 5, 6, 15, 18} . Construya una gráfica que implemente una relación que defina todos los pares de números. a Y b desde muchos C, en el que al dividir el segundo elemento por el primero obtenemos un cociente que es un número entero mayor que 1.

Solución. El gráfico que muestra estas relaciones estará orientado, ya que la condición contiene una mención del segundo y primer elemento, es decir, el borde se dirigirá desde el primer elemento al segundo. De esto queda claramente claro qué elemento es el primero y cuál el segundo. Agreguemos también algo de terminología: los bordes orientados generalmente se llaman arcos. Habrá 7 arcos en nuestro gráfico: mi1 = (3, 15) , mi2 = (3, 18) , mi3 = (5, 15) , mi4 = (3, 6) , mi5 = (2, 18) , mi6 = (6, 18) , mi7 = (2, 6) . En este ejemplo, los bordes (arcos) del gráfico simplemente están numerados, pero los números de serie no son lo único que se puede asignar a un arco. Al arco también se le pueden asignar escalas que significan, por ejemplo, el costo de enviar la carga de un punto a otro. Pero nos familiarizaremos con los pesos de arco más adelante y con más detalle. Entonces obtenemos el siguiente gráfico dirigido:

Como ya sabemos por la parte introductoria teórica, la teoría de grafos no tiene en cuenta la naturaleza específica de los conjuntos y con la ayuda de un mismo gráfico es posible definir relaciones en conjuntos con contenidos muy diferentes. Es decir, de este mismo contenido se puede abstraer al modelar una tarea. Pasemos a ejemplos que ilustran esta notable propiedad de la teoría de grafos.

Ejemplo 6. En una pieza de un tablero de ajedrez que mide 3 X 3, se colocan dos caballos blancos y dos caballos negros como se muestra en la siguiente figura.

¿Es posible mover los caballos al estado que se muestra en la siguiente figura, sin olvidar que dos piezas no pueden estar en la misma casilla?

Solución. En el gráfico construido, los pares de vértices estarán conectados por la relación de "movimiento del caballo". Es decir, un vértice es aquel de donde salió el caballero, y el otro es aquel al que llegó, y la celda intermedia de la letra “r” quedará fuera de esta relación. Obtenemos el siguiente gráfico:

Y, sin embargo, el diseño resultó engorroso. En él se ven las celdas de un tablero de ajedrez y muchos de los bordes del gráfico se cruzan. ¿Es posible abstraerse de la apariencia física del tablero de ajedrez e imaginar la relación de manera más simple? Resulta que es posible. En el nuevo gráfico, los vértices vecinos serán aquellos que estén conectados por la relación de “movimiento del caballo”, y no los vecinos en el tablero de ajedrez (figura siguiente).

Ahora es fácil ver que la respuesta a la pregunta de este problema es negativa. En el estado inicial no hay ningún caballero negro entre dos caballeros blancos, pero en el estado final debe existir este caballero negro. Los bordes del gráfico están colocados de manera que dos caballeros adyacentes no puedan saltar entre sí.

Ejemplo 7. El problema del lobo, la cabra y la col. En una orilla del río hay un hombre (H), un barco, un lobo (V), una cabra (Kz) y una col (Kp). En la embarcación podrán estar al mismo tiempo una persona y no más de uno de los objetos transportados. Una persona debe transportar todos los objetos al otro lado, observando la condición: no se debe dejar desatendido a un lobo con una cabra y una cabra con repollo.

Solución. En el gráfico construido, los vértices son configuraciones y los bordes son la relación de "conexión por un viaje en bote" entre las configuraciones. La configuración se refiere a la disposición de los objetos en el banco original y en el banco opuesto. Cada configuración se muestra como ( A|B) , Dónde A- objetos ubicados en la orilla original, y B- objetos ubicados en la orilla opuesta. Por lo tanto, la configuración inicial es: (PMCpKz| ) . Por ejemplo, después de transportar una cabra al otro lado, la configuración será (VKP|ChKz) . La configuración final es siempre ( |PMCpKz) . Ahora podemos construir un gráfico, sabiendo ya qué significan los vértices y las aristas:

Coloquemos los vértices del gráfico de manera que las aristas no se crucen, y los vértices vecinos sean aquellos que estén conectados por una relación en el gráfico. Entonces será mucho más fácil ver las relaciones (para ampliar la imagen, haga clic izquierdo sobre ella):

Como vemos, existen dos recorridos continuos diferentes desde la configuración inicial hasta la final. Por tanto, el problema tiene dos soluciones diferentes (y ambas son correctas).

Teoría de grafos y los problemas aplicados modernos más importantes.

Basados ​​en la teoría de grafos, se han desarrollado métodos para resolver problemas aplicados en los que se modelan sistemas muy complejos en forma de gráficos. En estos modelos, los nodos contienen componentes individuales y los bordes representan conexiones entre componentes. Normalmente, los gráficos ponderados se utilizan para modelar redes de transporte, sistemas de colas y planificación de redes. Ya hemos hablado de ellos, son gráficos en los que se asignan pesos a los arcos.

Los gráficos de árbol se utilizan, por ejemplo, para construir árboles de decisión(sirve para análisis de riesgos, análisis de posibles ganancias y pérdidas en condiciones de incertidumbre). Utilizando la teoría de grafos, desarrollada y otros numerosos modelos matemáticos para resolver problemas en áreas temáticas específicas.

Gráficos y el problema del flujo.

Formulación del problema. Existe un sistema de tuberías de agua, representado por el gráfico de la siguiente figura.

Cada arco del gráfico representa una tubería. Los números sobre los arcos (escalas) son la capacidad de la tubería. Los nodos son lugares donde se conectan las tuberías. El agua fluye a través de tuberías en una sola dirección. Nudo S- fuente de agua, nodo t- existencias. Se requiere maximizar el volumen de agua que fluye desde la fuente hasta el drenaje.

Para resolver el problema del flujo, puede utilizar el método Ford-Fulkerson. La idea del método: la búsqueda del caudal máximo se realiza por pasos. Al comienzo del algoritmo, el flujo se establece en cero. En cada paso posterior, el valor del flujo aumenta, por lo que se busca un camino complementario por donde llegue el flujo adicional. Estos pasos se repiten siempre que existan rutas adicionales. El problema se ha aplicado con éxito en varios sistemas distribuidos: sistema de suministro de energía, red de comunicaciones, sistema ferroviario y otros.

Gráficos y planificación de redes.

En los problemas de planificación de procesos complejos que constan de muchas tareas, algunas de las cuales se realizan en paralelo y otras de forma secuencial, se han utilizado ampliamente los gráficos ponderados, conocidos como redes PERT.

PERT - Técnica de revisión y evaluación de programas (proyectos): una técnica para evaluar y analizar programas (proyectos), que se utiliza en la gestión de proyectos.

La red PERT es un gráfico dirigido acíclico ponderado en el que cada arco representa un trabajo (acción, operación) y el peso del arco es el tiempo necesario para completarlo.

Si hay arcos en la red ( a, b) Y ( b, C), entonces el trabajo representado por el arco ( a, b) debe completarse antes del trabajo representado por el arco ( b, C). Cada vértice ( vi) representa el punto en el tiempo en el que todos trabajan, definido por arcos que terminan en un vértice ( vi).

En una columna como esta:

• un vértice, que no tiene predecesores, determina la hora de inicio del trabajo;
• un vértice, que no tiene seguidores, corresponde al momento en el tiempo en que se completa el conjunto de obras.

El camino de longitud máxima entre estos vértices del gráfico (desde el principio hasta el final del proceso de trabajo) se llama camino crítico. Para reducir el tiempo necesario para completar todo el conjunto de trabajos, es necesario encontrar trabajos que se encuentren en la ruta crítica y reducir su duración, por ejemplo, atrayendo artistas, mecanismos y nuevas tecnologías adicionales.

Todo el bloque "Teoría de grafos"

Material de Wikipedia: la enciclopedia libre

Teoría de grafos- una rama de las matemáticas discretas que estudia las propiedades de las gráficas. En un sentido general, una gráfica se representa como un conjunto picos(nodos) conectados costillas. En una definición estricta, ese par de conjuntos se llama gráfico. $GRAMO\; =\; (V,\; mi)$, Dónde $V$ es un subconjunto de cualquier conjunto contable, y $mi$- subconjunto $V\backslash veces\; V$.

La teoría de grafos encuentra aplicación, por ejemplo, en los sistemas de información geográfica (SIG). Las casas, estructuras, bloques, etc. existentes o de nuevo diseño se consideran vértices, y las carreteras, redes de servicios públicos, líneas eléctricas, etc. que los conectan se consideran bordes. El uso de diversos cálculos realizados en dicho gráfico permite, por ejemplo, encontrar la ruta de desvío más corta o la tienda de comestibles más cercana, o planificar la ruta óptima.

La teoría de grafos contiene una gran cantidad de problemas sin resolver e hipótesis aún no probadas.

Historia de la teoría de grafos

Leonard Euler es considerado el fundador de la teoría de grafos. En 1736, en una de sus cartas, formuló y propuso una solución al problema de los siete puentes de Königsberg, que más tarde se convirtió en uno de los problemas clásicos de la teoría de grafos.

Terminología de la teoría de grafos

Representación de gráficas en un plano.

Al representar gráficos en dibujos, se usa con mayor frecuencia el siguiente sistema de notación: los vértices del gráfico se representan como puntos o, al especificar el significado del vértice, rectángulos, óvalos, etc., donde el significado del vértice se revela en el interior. la figura (gráficos de diagramas de flujo de algoritmos). Si hay una arista entre los vértices, entonces los puntos (formas) correspondientes están conectados por una línea o un arco. En el caso de un gráfico dirigido, los arcos se reemplazan por flechas o se indica explícitamente la dirección de un borde. A veces se colocan inscripciones explicativas junto al borde, que revelan el significado del borde, por ejemplo, en gráficos de transición de máquinas de estados finitos. Hay gráficos planos y no planos. Un gráfico plano es un gráfico que se puede representar en una imagen (plano) sin bordes que se crucen (los más simples son un triángulo o un par de vértices conectados); de lo contrario, el gráfico no es plano. En el caso de que el gráfico no contenga ciclos (que contenga al menos una ruta una vez recorrido de aristas y vértices con retorno al vértice original), generalmente se le llama “árbol”. Los tipos importantes de árboles en la teoría de grafos son los árboles binarios, donde cada vértice tiene un borde entrante y exactamente dos salientes, o es finito: no tiene bordes salientes y contiene un vértice raíz sin borde entrante.

La imagen de un gráfico no debe confundirse con el gráfico en sí (estructura abstracta), ya que a un gráfico se le puede asociar más de una representación gráfica. La imagen pretende únicamente mostrar qué pares de vértices están conectados por aristas y cuáles no. En la práctica, a menudo resulta difícil responder a la pregunta de si dos imágenes son modelos del mismo gráfico o no (en otras palabras, si los gráficos correspondientes a las imágenes son isomórficos). Dependiendo de la tarea, algunas imágenes pueden proporcionar más claridad que otras.

Algunos problemas de la teoría de grafos.

• El problema de los siete puentes de Königsberg es uno de los primeros resultados en teoría de grafos, publicado por Euler en .
• El problema de los cuatro colores se formuló en 1852, pero no se obtuvo una demostración no clásica hasta 1976 (4 colores son suficientes para un mapa en una esfera (plano)).
• El problema del viajante es uno de los problemas NP-completos más famosos.
• El problema de la camarilla es otro problema NP-completo.
• Encontrar el árbol de expansión mínimo.
• Isomorfismo de gráficos: ¿es posible obtener otro renumerando los vértices de un gráfico?
• Planaridad del gráfico: ¿es posible representar el gráfico en un plano sin intersecciones de bordes (o con un número mínimo de capas, que se utiliza al trazar interconexiones de elementos de placas de circuito impreso o microcircuitos)?

Aplicación de la teoría de grafos

ver también

Escribe una reseña sobre el artículo "Teoría de grafos"

Notas

Literatura

• Distel R. Teoría de grafos Trans. De inglés - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - 336 p. ISBN 5-86134-101-X.
• Diestel R.. - Nueva York: Springer-Verlag, 2005. - P. 422.
• Basaker R., Saati T.
• Belov V.V., Vorobiev E.M., Shatalov V.E. Teoría de grafos. - M.: Más alto. escuela, 1976. - P. 392.
• Bergé K.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Conferencias sobre teoría de grafos. M.: Nauka, 1990. 384 p. (Ed. 2, M. revisado: URSS, 2009. 392 p.)
• Zykov A.A.. - M.: “Libro Universitario”, 2004. - P. 664. - ISBN 5-9502-0057-8.(M.: Nauka, 1987. 383c.)
• Aplicaciones químicas de la topología y la teoría de grafos. Ed. R. Rey. Por. De inglés M.: Mir, 1987.
• Kirsánov M. N. Gráficos en arce. M.: Fizmatlit, 2007. 168 p. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Cristofides N.
• Cormen TH et al. Parte VI. Algoritmos para trabajar con gráficos // Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2ª ed. - M.: Williams, 2006. - P. 1296. - ISBN 0-07-013151-1.
• Ore O.. - 2ª ed. - M.: Ciencia, 1980. - P. 336.
• Salii V. N. Bogomolov A. M.. - M.: Literatura de Física y Matemáticas, 1997. - ISBN 5-02-015033-9.
• Swami M., Thulasiraman K.
• Tutt W.
• Wilson R.
• Harari F.. - M.: Mir, 1973.(Ed. 3, M.: KomKniga, 2006. - 296 p.)
• Harari F., Palmer E.. - Mundo, 1977.
• Serguéi Mélnikov// Ciencia y vida. - 1996. - Edición. 3. - págs. 144-145. El artículo trata sobre el juego de gráficos Sim, inventado por Gustav Simmons.

Enlaces

• : un programa que proporciona al usuario una amplia gama de herramientas y métodos para visualizar y buscar información en gráficos

Análisis clásico Teoría de funciones diferencial y ecuaciones integrales

Un extracto que caracteriza la teoría de grafos.

Pero antes de terminar estas palabras, el príncipe Andrés, sintiendo cómo le subían a la garganta lágrimas de vergüenza y de ira, ya saltaba de su caballo y corría hacia el estandarte.
- ¡Chicos, adelante! – gritó infantilmente.
"¡Aquí lo tienes!" pensó el príncipe Andrei, agarrando el asta de la bandera y escuchando con placer el silbido de las balas, obviamente dirigidas específicamente a él. Varios soldados cayeron.
- ¡Hurra! - gritó el príncipe Andrei, apenas sosteniendo el pesado estandarte en sus manos, y corrió hacia adelante con indudable confianza en que todo el batallón correría tras él.
De hecho, solo corrió unos pocos pasos solo. Un soldado partió, luego otro, y todo el batallón gritó “¡Hurra!” corrió hacia él y lo alcanzó. El suboficial del batallón corrió y tomó la pancarta, que temblaba por el peso en manos del príncipe Andrei, pero fue asesinado de inmediato. El príncipe Andrés volvió a agarrar el estandarte y, arrastrándolo por el poste, huyó con el batallón. Delante de él vio a nuestros artilleros, algunos de los cuales luchaban, otros abandonaban sus cañones y corrían hacia él; También vio soldados de infantería franceses que agarraron caballos de artillería y apuntaron los cañones. El príncipe Andrei y su batallón ya estaban a 20 pasos de los cañones. Escuchó el incesante silbido de las balas sobre él y los soldados gemían constantemente y caían a derecha e izquierda de él. Pero él no los miró; sólo miró lo que sucedía frente a él: la batería. Vio claramente una figura de un artillero pelirrojo con un shako golpeado en un lado, tirando una pancarta en un lado, mientras un soldado francés tiraba la pancarta hacia él en el otro lado. El príncipe Andrey ya vio claramente la expresión confusa y al mismo tiempo amargada en los rostros de estas dos personas, que aparentemente no entendían lo que estaban haciendo.
"¿Qué están haciendo? - pensó el príncipe Andrei, mirándolos: - ¿Por qué el artillero pelirrojo no corre cuando no tiene armas? ¿Por qué el francés no lo apuñala? Antes de que pueda alcanzarlo, el francés recordará el arma y lo matará a puñaladas”.
De hecho, otro francés, con un arma a su favor, corrió hacia los combatientes, y el destino del artillero pelirrojo, que aún no entendía lo que le esperaba y sacó triunfalmente la pancarta, estaba por decidirse. Pero el príncipe Andrei no vio cómo terminó todo. Le pareció que uno de los soldados cercanos, como blandiendo un palo fuerte, lo golpeó en la cabeza. Le dolía un poco y, lo más importante, era desagradable, porque ese dolor lo entretenía y le impedía ver lo que miraba.
"¿Qué es esto? ¿Estoy cayendo? Mis piernas están flaqueando”, pensó y cayó de espaldas. Abrió los ojos, esperando ver cómo terminaba la lucha entre los franceses y los artilleros, y queriendo saber si el artillero pelirrojo había muerto o no, si los cañones habían sido tomados o salvados. Pero él no vio nada. Ya no había nada encima de él excepto el cielo: un cielo alto, no claro, pero aún inconmensurablemente alto, con nubes grises arrastrándose silenciosamente a través de él. “Qué tranquilo, tranquilo y solemne, nada parecido a cómo corrí”, pensó el príncipe Andrei, “no como corrimos, gritamos y peleamos; No se parece en nada a cómo el francés y el artillero se tiraban mutuamente sus pancartas con caras amargadas y asustadas; no se parece en nada a cómo las nubes se arrastran por este cielo alto e infinito. ¿Cómo es que no he visto este cielo tan alto antes? Y qué feliz estoy de haberlo reconocido finalmente. ¡Sí! Todo está vacío, todo es engaño, excepto este cielo infinito. No hay nada, nada, excepto él. Pero ni siquiera eso está ahí, no hay más que silencio, calma. ¡Y gracias a Dios!..."

En el flanco derecho de Bagration, a las nueve, el asunto aún no había comenzado. Al no querer aceptar la demanda de Dolgorukov de iniciar el negocio y querer desviar la responsabilidad de sí mismo, el príncipe Bagration sugirió que se enviara a Dolgorukov para preguntarle al comandante en jefe sobre esto. Bagration sabía que, debido a la distancia de casi 10 verstas que separaban un flanco del otro, si el enviado no moría (lo cual era muy probable), e incluso si encontraba al comandante en jefe, lo cual era muy difícil, el enviado no tendría tiempo de regresar más temprano por la noche.
Bagration miró a su séquito con sus ojos grandes, inexpresivos y privados de sueño, y el rostro infantil de Rostov, involuntariamente congelado por la emoción y la esperanza, fue el primero en llamar su atención. Él lo envió.
- ¿Y si me encuentro con Su Majestad ante el Comandante en Jefe, Excelencia? - dijo Rostov, llevándose la mano a la visera.
"Puede entregárselo a Su Majestad", dijo Dolgorukov, interrumpiendo apresuradamente a Bagration.
Liberado de la cadena, Rostov logró dormir varias horas antes de la mañana y se sintió alegre, valiente, decidido, con esa elasticidad de movimientos, confianza en su felicidad y en ese estado de ánimo en el que todo parece fácil, divertido y posible.
Todos sus deseos se cumplieron esa mañana; se libró una batalla general, él participó en ella; Además, era ordenanza bajo el mando del general más valiente; Además, iba a hacer un recado a Kutuzov, y tal vez incluso al propio soberano. La mañana estaba clara y el caballo que tenía debajo estaba bien. Su alma estaba alegre y feliz. Habiendo recibido la orden, montó en su caballo y galopó a lo largo de la línea. Al principio cabalgó a lo largo de la línea de las tropas de Bagration, que aún no habían entrado en acción y permanecían inmóviles; luego entró en el espacio ocupado por la caballería de Uvarov y aquí ya notó movimientos y señales de preparativos para el caso; Habiendo pasado junto a la caballería de Uvarov, ya escuchó claramente los sonidos de cañones y disparos delante de él. El tiroteo se intensificó.
En el aire fresco de la mañana ya no se oían, como antes, a intervalos irregulares, dos, tres disparos y luego uno o dos disparos, y a lo largo de las laderas de las montañas, frente a Pratzen, se oían los disparos, interrumpidos. por disparos tan frecuentes que a veces varios disparos de cañón ya no estaban separados entre sí, sino que se fusionaban en un rugido común.
Se veía cómo el humo de los cañones parecía correr por las laderas, alcanzándose unos a otros, y cómo el humo de los cañones se arremolinaba, se desdibujaba y se fusionaba uno con otro. Por el brillo de las bayonetas entre el humo se veían las masas de infantería en movimiento y las estrechas franjas de artillería con cajas verdes.
Rostov detuvo su caballo en una colina por un minuto para examinar lo que estaba sucediendo; pero por mucho que esforzaba su atención, no podía entender ni entender nada de lo que estaba sucediendo: algunas personas se movían allí entre el humo, algunas lonas de tropas se movían tanto por delante como por detrás; ¿pero por qué? ¿OMS? ¿Dónde? era imposible de entender. Esta vista y estos sonidos no sólo no despertaron en él ningún sentimiento de embotamiento o timidez, sino que, por el contrario, le dieron energía y determinación.
“Pues más, ¡dale más!” - Se volvió mentalmente hacia estos sonidos y nuevamente comenzó a galopar por la línea, penetrando cada vez más en la zona de las tropas que ya habían entrado en acción.
"No sé cómo será allí, ¡pero todo estará bien!" Pensó Rostov.
Habiendo pasado algunas tropas austriacas, Rostov notó que la siguiente parte de la línea (era la guardia) ya había entrado en acción.
"¡Todo lo mejor! Lo miraré más de cerca”, pensó.
Condujo casi a lo largo de la línea del frente. Varios jinetes galoparon hacia él. Estos eran nuestros lanceros salvavidas, que regresaban del ataque en filas desordenadas. Rostov los pasó, involuntariamente vio a uno de ellos cubierto de sangre y siguió galopando.
"¡No me importa esto!" el pensó. Antes de haber recorrido unos cientos de pasos después de esto, a su izquierda, a lo largo de todo el campo, apareció una enorme masa de soldados de caballería sobre caballos negros, con brillantes uniformes blancos, trotando directamente hacia él. Rostov puso su caballo a todo galope para apartarse del camino de estos jinetes, y se habría alejado de ellos si hubieran mantenido el mismo paso, pero siguieron acelerando, de modo que algunos caballos ya galopaban. Rostov escuchó cada vez más claramente sus pisadas y el ruido de sus armas, y sus caballos, figuras e incluso rostros se hicieron más visibles. Estos eran nuestros guardias de caballería, atacando a la caballería francesa, que avanzaba hacia ellos.
Los guardias de caballería galoparon, pero aún sujetando a sus caballos. Rostov ya vio sus caras y escuchó la orden: "¡marchen, marchen!" Pronunció un oficial que desató su caballo de sangre a toda velocidad. Rostov, temiendo ser aplastado o atraído a atacar a los franceses, galopó por el frente lo más rápido que pudo su caballo y aún así no logró pasarlos.
El último guardia de caballería, un hombre enorme y picado de viruela, frunció el ceño con enojo cuando vio frente a él a Rostov, con quien inevitablemente chocaría. Esta guardia de caballería ciertamente habría derribado a Rostov y sus beduinos (el propio Rostov parecía tan pequeño y débil en comparación con estas enormes personas y caballos), si no hubiera pensado en golpear con su látigo en los ojos del caballo de la guardia de caballería. El caballo negro, pesado, de quince pulgadas, se alejó, bajando las orejas; pero la guardia de caballería picada de viruelas le clavó enormes espuelas en los costados y el caballo, agitando la cola y estirando el cuello, corrió aún más rápido. Tan pronto como los guardias de caballería pasaron por Rostov, los escuchó gritar: "¡Hurra!" y al mirar atrás vio que sus primeras filas se estaban mezclando con desconocidos, probablemente franceses, soldados de caballería con charreteras rojas. Era imposible ver nada más allá, porque inmediatamente después, los cañones comenzaron a disparar desde algún lugar y todo se cubrió de humo.
En ese momento, cuando los guardias de caballería, tras pasar junto a él, desaparecieron entre el humo, Rostov dudó si galopar tras ellos o ir a donde tenía que ir. Este fue ese brillante ataque de la guardia de caballería, que sorprendió a los propios franceses. Rostov se asustó al escuchar más tarde que de toda esta masa de gente enorme y hermosa, de todos estos jóvenes brillantes y ricos en miles de caballos, oficiales y cadetes que galopaban junto a él, después del ataque solo quedaban dieciocho personas.