B - P + G = 1, (*)

donde B es el número total de vértices, P es el número total de aristas, G es el número de polígonos (caras).

Prueba. Demostremos que la igualdad no cambia si se traza una diagonal en algún polígono de una partición determinada (Fig. 2, a).

a) b)

Fig.2

De hecho, después de dibujar dicha diagonal, la nueva partición tendrá B vértices, P+1 aristas y el número de polígonos aumentará en uno. Por lo tanto, tenemos

B - (P + 1) + (G+1) = B - P + GRAMO.

Usando esta propiedad, dibujamos diagonales que dividen los polígonos entrantes en triángulos y, para la partición resultante, mostramos la viabilidad de la relación.

Para ello, eliminaremos secuencialmente los bordes externos, reduciendo el número de triángulos. En este caso, son posibles dos casos:

para eliminar el triángulo ABC, es necesario eliminar dos aristas, en nuestro caso AB y BC;

Para eliminar el triángulo MKN, es necesario eliminar un borde, en nuestro caso MN.

En ambos casos la igualdad no cambiará. Por ejemplo, en el primer caso, después de eliminar el triángulo, el gráfico estará formado por vértices B-1, aristas P-2 y polígono G-1:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Por tanto, eliminar un triángulo no cambia la igualdad.

Continuando con este proceso de eliminar triángulos, eventualmente llegaremos a una partición que consta de un solo triángulo. Para tal partición B = 3, P = 3, G = 1 y, por lo tanto,

B - P + G = 1.

Esto significa que la igualdad también se cumple para la partición original, de lo que finalmente obtenemos que la relación es válida para esta partición del polígono.

Tenga en cuenta que la relación de Euler no depende de la forma de los polígonos. Los polígonos se pueden deformar, agrandar, reducir o incluso doblar sus lados, siempre y cuando los lados no se rompan. La relación de Euler no cambiará.

Procedamos ahora a resolver el problema de tres casas y tres pozos.

Solución . Supongamos que esto se puede hacer. Marquemos las casas con los puntos D1, D2, D3 y los pozos con los puntos K1, K2, K3 (Fig. 1). Conectamos cada punto de la casa con cada punto del pozo. Obtenemos nueve aristas que no se cruzan en pares.

Estos bordes forman un polígono en el plano, dividido en polígonos más pequeños. Por lo tanto, para esta partición se debe satisfacer la relación de Euler B - P + G = 1.

Agreguemos una cara más a las caras consideradas: la parte exterior del plano en relación con el polígono. Entonces la relación de Euler tomará la forma B - P + G = 2, con B = 6 y P = 9.

Por lo tanto, Г = 5. Cada una de las cinco caras tiene al menos cuatro aristas, ya que, según las condiciones del problema, ninguno de los caminos debe conectar directamente dos casas o dos pozos. Dado que cada arista se encuentra exactamente en dos caras, el número de aristas debe ser al menos (5 4)/2 = 10, lo que contradice la condición de que su número sea 9.

La contradicción resultante muestra que la respuesta al problema es negativa. - es imposible trazar caminos que no se crucen desde cada casa a cada pueblo

Teoría de grafos en química

Aplicación de la teoría de grafos a la construcción y análisis de diversas clases de gráficos químicos y químico-tecnológicos, que también se denominan topología, modelos, es decir. Modelos que tienen en cuenta únicamente la naturaleza de las conexiones entre los vértices. Los arcos (bordes) y vértices de estos gráficos reflejan conceptos, fenómenos, procesos u objetos químicos y químico-tecnológicos y, en consecuencia, relaciones cualitativas y cuantitativas o determinadas relaciones entre ellos.

Problemas teóricos. Los gráficos químicos permiten predecir transformaciones químicas, explicar la esencia y sistematizar algunos conceptos básicos de la química: estructura, configuración, confirmaciones, interacciones mecánica cuántica y estadístico-mecánica de moléculas, isomería, etc. Los gráficos químicos incluyen gráficos moleculares, bipartitos y de señales. de ecuaciones de reacción cinética. Los gráficos moleculares, utilizados en estereoquímica y topología estructural, química de clusters, polímeros, etc., son gráficos no dirigidos que muestran la estructura de las moléculas. Los vértices y aristas de estos gráficos corresponden a los átomos correspondientes y los enlaces químicos entre ellos.

En estereoquímica org. c-c los más utilizados son los árboles moleculares: árboles que abarcan gráficos moleculares que contienen solo todos los vértices correspondientes a los átomos. La compilación de conjuntos de árboles moleculares y el establecimiento de su isomorfismo permite determinar las estructuras moleculares y encontrar el número total de isómeros de alcanos. alquenos y alquinos. Los gráficos moleculares permiten reducir los problemas relacionados con la codificación, nomenclatura y características estructurales (ramificación, ciclicidad, etc.) de moléculas de diversos compuestos al análisis y comparación de características y propiedades puramente matemáticas de los gráficos moleculares y sus árboles, así como sus matrices correspondientes. Para identificar la cantidad de correlaciones entre la estructura de las moléculas y las propiedades fisicoquímicas (incluidas las farmacológicas) de los compuestos, se han desarrollado más de 20 de las denominadas. Índices topológicos de moléculas (Wiener, Balaban, Hosoya, Plata, Randic, etc.), que se determinan mediante matrices y características numéricas de árboles moleculares. Por ejemplo, el índice de Wiener W = (m3 + m)/6, donde m es el número de vértices correspondientes a los átomos de C, se correlaciona con volúmenes moleculares y refracciones, entalpías de formación, viscosidad, tensión superficial, constantes cromatográficas de compuestos, octanaje. Números de hidrocarburos e incluso fisiol. actividad de las drogas. Los parámetros importantes de los gráficos moleculares utilizados para determinar las formas tautoméricas de una sustancia determinada y su reactividad, así como en la clasificación de aminoácidos, ácidos nucleicos, carbohidratos y otros compuestos naturales complejos, son la capacidad de información promedio y total (H). El análisis de las gráficas moleculares de los polímeros, cuyos vértices corresponden a unidades monoméricas y cuyos bordes corresponden a enlaces químicos entre ellos, permite explicar, por ejemplo, los efectos del volumen excluido en las cualidades. cambios en las propiedades previstas de los polímeros. Utilizando la teoría de grafos y los principios de la inteligencia artificial, se ha desarrollado software para sistemas de recuperación de información en química, así como sistemas automatizados para identificar estructuras moleculares y planificar racionalmente la síntesis orgánica. Para la implementación práctica en una computadora de operaciones para seleccionar rutas químicas racionales. Las transformaciones basadas en los principios retrosintéticos y sintónicos utilizan gráficos de búsqueda ramificados de varios niveles para opciones de solución, cuyos vértices corresponden a los gráficos moleculares de reactivos y productos, y los arcos representan transformaciones.

Para resolver problemas multidimensionales de análisis y optimización de sistemas tecnológicos químicos (CTS) se utilizan los siguientes gráficos tecnológicos químicos: gráficos de flujo, flujo de información, señales y confiabilidad. Para estudiar química. La física de las perturbaciones en sistemas formados por un gran número de partículas utiliza el llamado. Los diagramas de Feynman son gráficos cuyos vértices corresponden a las interacciones elementales de partículas físicas, los bordes de sus trayectorias después de las colisiones. En particular, estos gráficos permiten estudiar los mecanismos de reacciones oscilatorias y determinar la estabilidad de los sistemas de reacción. Los gráficos de flujo de materiales muestran cambios en los caudales de productos químicos en los sistemas químicos. Los gráficos de flujo térmico muestran los balances de calor en CTS; los vértices de los gráficos corresponden a dispositivos en los que cambia el consumo de calor de los flujos físicos y, además, a las fuentes y sumideros de energía térmica del sistema; Los arcos corresponden a flujos de calor físicos y ficticios (conversión de energía físico-química en dispositivos), y los pesos de los arcos son iguales a las entalpías de los flujos. Los gráficos térmicos y de materiales se utilizan para compilar programas para el desarrollo automatizado de algoritmos para resolver sistemas de ecuaciones para balances de materiales y calor de sistemas químicos complejos. Los gráficos de flujo de información muestran la estructura lógica de información de sistemas de ecuaciones matemáticas. modelos XTS; se utilizan para desarrollar algoritmos óptimos para el cálculo de estos sistemas. Un gráfico de información bipartito es un gráfico dirigido o no dirigido cuyos vértices se corresponden respectivamente. ecuaciones fl -f6 y variables q1 – V, y las ramas reflejan su relación. Gráfico de información: un dígrafo que representa el orden de resolución de ecuaciones; los vértices del gráfico corresponden a estas ecuaciones, fuentes y receptores de información XTS, y las ramas corresponden a información. variables. Los gráficos de señales corresponden a sistemas lineales de ecuaciones de modelos matemáticos de procesos y sistemas tecnológicos químicos. Los gráficos de confiabilidad se utilizan para calcular varios indicadores de confiabilidad X.

Literatura utilizada:

1.Berge K., T. g y su aplicación, traducción del francés, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introducción a las matemáticas finitas, trad. Del inglés, 2ª ed., M., 1963;

3.Ope O., Gráficos y su aplicación, trad. Del inglés, M., 1965;

4. Belykh O.V., Belyaev E.V., Posibilidades de aplicación de la sociología en sociología, en: Hombre y sociedad, vol. 1, [L.], 1966;

5. Métodos cuantitativos en la investigación sociológica, M., 1966; Belyaev E.V., Problemas de las mediciones sociológicas, "VF", 1967, núm. 7; Bavelas. Patrones de comunicación en grupos orientados a tareas, en el libro. Lerner D., Lasswell H., Ciencias políticas, Stanford, 1951;

INSTITUCIÓN EDUCATIVA AUTÓNOMA MUNICIPAL ESCUELA SECUNDARIA N° 2

Preparado

Legkokonets Vladislav, estudiante de la clase 10A

Aplicación práctica de la teoría de grafos.

Supervisor

L. I. Noskova, profesora de matemáticas

Arte.

2011

1.Introducción…………………………………………………………………………………….………….3

2. Historia del surgimiento de la teoría de grafos………………………………………….…………..4

3. Definiciones y teoremas básicos de la teoría de grafos………………………….………6

4. Problemas resueltos usando gráficas………………………………..…………………………..8

4.1 Problemas famosos……………………………….…………………………...8

4.2 Varios problemas interesantes……………………………….………………..9

5. Aplicación de gráficas en diversos ámbitos de la vida de las personas…………………………...11

6. Resolución de problemas…………………………………………………………………………...12

7. Conclusión…………………….……………………………………………………………….13

8. Lista de referencias………….………………………………………………………………14

9.Apéndice……………………………………………………………………………….…………15

Introducción

Nacida de la resolución de acertijos y juegos entretenidos, la teoría de grafos se ha convertido ahora en una herramienta simple, accesible y poderosa para resolver preguntas relacionadas con una amplia gama de problemas. Los gráficos son literalmente omnipresentes. En forma de gráficos se pueden, por ejemplo, interpretar mapas de carreteras y circuitos eléctricos, mapas geográficos y moléculas de compuestos químicos, conexiones entre personas y grupos de personas. Durante las últimas cuatro décadas, la teoría de grafos se ha convertido en una de las ramas de las matemáticas de más rápido desarrollo. Esto está impulsado por las demandas de un campo de aplicación en rápida expansión. Se utiliza en el diseño de circuitos integrados y circuitos de control, en el estudio de autómatas, circuitos lógicos, diagramas de bloques de programas, en economía y estadística, química y biología, en teoría de programación. Es por eso pertinencia El tema está determinado, por un lado, por la popularidad de los gráficos y los métodos de investigación relacionados y, por otro, por un sistema holístico no desarrollado para su implementación.

Resolver muchos problemas en la vida requiere largos cálculos y, a veces, ni siquiera estos cálculos dan éxito. esto es lo que problema de investigacion. Surge la pregunta: ¿es posible encontrar una solución sencilla, racional, breve y elegante para solucionarlos? ¿Es más fácil resolver problemas si utilizas gráficos? esto determinado tema de mi investigación: “Aplicación práctica de la teoría de grafos”

Objetivo La investigación consistía en utilizar gráficos para aprender a resolver rápidamente problemas prácticos.

Hipótesis de investigación. El método gráfico es muy importante y ampliamente utilizado en diversos campos de la ciencia y la actividad humana.

Objetivos de la investigación:

1. Estudiar literatura y recursos de Internet sobre este tema.

2.Comprobar la eficacia del método gráfico en la resolución de problemas prácticos.

3. Saca una conclusión.

Importancia práctica del estudio. Es que los resultados sin duda despertarán el interés de muchas personas. ¿Ninguno de vosotros ha intentado construir su árbol genealógico? ¿Cómo hacer esto correctamente? El jefe de una empresa de transporte probablemente tenga que resolver el problema de un uso más rentable del transporte al transportar mercancías desde un destino a varios asentamientos. Todo escolar se ha encontrado con problemas lógicos de transfusión. Resulta que se pueden resolver fácilmente mediante gráficas.

En el trabajo se utilizan los siguientes métodos: observación, búsqueda, selección, análisis.

Historia de la teoría de grafos

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. A continuación se ofrece 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.

“Una vez me plantearon un problema sobre una isla situada en la ciudad de Königsberg y rodeada por un río con siete puentes que la cruzan.

[Apéndice Fig.1] 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 porque 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 de cualquier número de puentes ubicados. O no. Los puentes de Koenigsberg están ubicados de tal forma que se pueden representar en la siguiente figura [Apéndice Fig.2], en el que A denota una isla, y B, C y D, partes del continente separadas entre sí por brazos de ríos.

Respecto al método que descubrió para resolver problemas de este tipo, Euler escribió:

“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 Necesito involucrarme para encontrar esta solución, hay leyes inherentes a las matemáticas. Entonces, 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:

"La cuestión es determinar si es posible pasar por alto estos siete puentes, pasando por cada uno de ellos sólo una vez, o no. Mi regla lleva a la siguiente solución a esta pregunta. En primer lugar, hay que observar cuántas zonas hay están separados por agua, tales que no tienen otra transición de uno a otro, 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. El número de puentes que conducen a estas secciones individuales es par o impar. Entonces, en nuestro caso, cinco puentes conducen a la sección A, y tres puentes conducen cada uno al resto, es decir, el número de puentes que conducen a las secciones individuales es impar, y solo esto 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 individual fuera par, entonces el desvío en cuestión sería posible y al mismo tiempo sería posible. comenzar este desvío desde cualquier sección si dos de estos números fueran impares, porque solo uno no puede ser impar, entonces incluso entonces la transición podría completarse, como está prescrito, pero ciertamente solo se debe tomar el comienzo del desvío. uno de esos dos tramos a los que conduce un número impar de 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".

Definiciones y teoremas básicos de la teoría de grafos.

La teoría de grafos es una disciplina matemática creada gracias al esfuerzo de los matemáticos, por lo que su presentación incluye las definiciones estrictas necesarias. Entonces, procedamos a una introducción organizada de los conceptos básicos de esta teoría.

Definición 1. Un gráfico es una colección de un número finito de puntos, llamados vértices del gráfico, y líneas en pares que conectan algunos de estos vértices, llamadas aristas o arcos del gráfico.

Esta definición se puede formular de otra manera: un gráfico es un conjunto no vacío de puntos (vértices) y segmentos (aristas), cuyos extremos pertenecen a un conjunto dado de puntos.

En lo que sigue, denotaremos los vértices del gráfico con las letras latinas A, B, C, D. A veces, el gráfico en su conjunto se indicará con una letra mayúscula.

Definición 2. Los vértices de un gráfico que no pertenecen a ninguna arista se llaman aislados.

Definición 3. Un gráfico que consta únicamente de vértices aislados se llama nulo. - contar .

Notación: O "– un gráfico con vértices que no tiene aristas

Definición 4. Un gráfico en el que cada par de vértices está conectado por una arista se llama completo.

Designación: U" – un gráfico que consta de n vértices y aristas que conectan todos los pares posibles de estos vértices. Un gráfico de este tipo se puede representar como un n-gón en el que se dibujan todas las diagonales.

Definición 5. El grado de un vértice es el número de aristas a las que pertenece el vértice.

Definición 6. Un gráfico cuyos grados de todos los k vértices son iguales se llama gráfico de grados homogéneos. .

Definición 7. El complemento de una gráfica dada es una gráfica que consta de todas las aristas y sus extremos que deben sumarse a la gráfica original para obtener una gráfica completa.

Definición 8. Un gráfico que se puede representar en un plano de tal manera que sus aristas se cruzan solo en los vértices se llama plano.

Definición 9. Un polígono de un gráfico plano que no contiene vértices ni aristas del gráfico se llama cara.

Los conceptos de gráfico plano y cara del gráfico se utilizan al resolver problemas sobre la coloración "correcta" de varios mapas.

Definición 10. Un camino de A a X es una secuencia de aristas que van de A a X de modo que cada dos aristas adyacentes tienen un vértice común y ninguna arista aparece más de una vez.

Definición 11. Un ciclo es un camino en el que coinciden el punto inicial y el final.

Definición 12. Un ciclo simple es un ciclo que no pasa por ninguno de los vértices del gráfico más de una vez.

Definición 13. Longitud del camino , puesto en un bucle , Se llama el número de aristas de este camino.

Definición 14. Dos vértices A y B en un gráfico se llaman conectados (desconectados) si existe (no existe) un camino que va de A a B.

Definición 15. Un gráfico se llama conexo si cada dos de sus vértices son conexos; si el gráfico contiene al menos un par de vértices desconectados, entonces el gráfico se llama desconectado.

Definición 16. Un árbol es un gráfico conexo que no contiene ciclos.

Un modelo tridimensional de un gráfico de árbol es, por ejemplo, un árbol real con su copa intrincadamente ramificada; El río y sus afluentes también forman un árbol, pero ya plano, en la superficie de la tierra.

Definición 17. Un gráfico desconectado que consta enteramente de árboles se llama bosque.

Definición 18. Un árbol en el que todos los n vértices están numerados del 1 al n se denomina árbol con vértices renumerados.

Entonces, hemos examinado las definiciones básicas de la teoría de grafos, sin las cuales sería imposible probar teoremas y, en consecuencia, resolver problemas.

Problemas resueltos usando gráficos.

Problemas famosos

Problema del vendedor ambulante

El problema del viajante es uno de los problemas famosos de la teoría de la combinatoria. Fue propuesto en 1934 y los mejores matemáticos se rompieron los dientes.

El planteamiento del problema es el siguiente.
Un vendedor ambulante (comerciante errante) debe abandonar la primera ciudad, visitar las ciudades 2,1,3...n una vez en un orden desconocido y regresar a la primera ciudad. Se conocen las distancias entre ciudades. ¿En qué orden se debe recorrer las ciudades para que el camino cerrado (recorrido) de un viajante de comercio sea el más corto?

Método para resolver el problema del viajante.

Algoritmo codicioso "Ve a la ciudad más cercana (a la que aún no has entrado)".
Este algoritmo se llama "codicioso" porque en los últimos pasos hay que pagar mucho por la codicia.
Considere, por ejemplo, la red de la figura. [Apéndice Fig.3], que representa un rombo estrecho. Dejemos que un viajante de comercio comience desde la ciudad 1. El algoritmo “ir a la ciudad más cercana” lo llevará a la ciudad 2, luego a la 3, luego a la 4; en el último paso tendrás que pagar por tu codicia, regresando a lo largo de la larga diagonal del diamante. El resultado no será el recorrido más corto, sino el más largo.

Problema con los puentes de Königsberg.

El problema se formula de la siguiente manera.
La ciudad de Koenigsberg está situada a orillas del río Pregel y de dos islas. Las diferentes partes de la ciudad estaban conectadas por siete puentes. Los domingos, la gente del pueblo paseaba por la ciudad. Pregunta: ¿es posible dar un paseo de tal forma que, al salir de casa, regresar pases exactamente una vez por cada puente?
Los puentes sobre el río Pregel están ubicados como en la imagen.[Apéndice Fig.1].

Considere el gráfico correspondiente al diagrama del puente. [Apéndice Fig. 2].

Para responder a la pregunta del problema, basta con averiguar si la gráfica es euleriana. (Debe extenderse un número par de puentes desde al menos un vértice). No puedes caminar por la ciudad y cruzar todos los puentes una vez y regresar.

Varias tareas interesantes

1. "Rutas".

Problema 1

Como recordarás, el cazador de almas muertas Chichikov visitó a terratenientes famosos una vez a cada uno. Los visitó en el siguiente orden: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, el general Betrishchev, Petukh, Konstanzholgo, el coronel Koshkarev. Se encontró un diagrama en el que Chichikov dibujó las posiciones relativas de las fincas y los caminos rurales que las conectaban. Determine qué propiedad pertenece a quién, si Chichikov no condujo por ninguna de las carreteras más de una vez. [Apéndice Fig. 4].

Solución:

El mapa de carreteras muestra que Chichikov comenzó su viaje desde la finca E y terminó en la finca O. Observamos que solo dos caminos conducen a las fincas B y C, por lo que Chichikov tuvo que viajar por estos caminos. Marquémoslos con una línea en negrita. Se han identificado los tramos del recorrido que pasa por A: AC y AB. Chichikov no viajó por las carreteras AE, AK y AM. Tachémoslos. Marquemos con una línea en negrita ED; Tachemos a DK. Tachemos MO y MN; Marquemos MF con una línea en negrita; tachar FO; Marquemos FH, NK y KO con una línea en negrita. Busquemos la única ruta posible bajo esta condición. Y obtenemos: finca E - pertenece a Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Apéndice Fig.5].

Problema 2

La figura muestra un mapa de la zona. [Apéndice Fig. 6].

Sólo puedes moverte en la dirección de las flechas. Puede visitar cada punto no más de una vez. ¿De cuántas maneras puedes llegar del punto 1 al punto 9? ¿Qué ruta es la más corta y cuál es la más larga?

Solución:

"estratificamos" secuencialmente el circuito en un árbol, comenzando desde el vértice 1 [Apéndice Fig.7]. Consigamos un árbol. El número de formas posibles de llegar del 1 al 9 es igual al número de vértices "colgantes" del árbol (hay 14). Evidentemente el camino más corto es el 1-5-9; el más largo es 1-2-3-6-5-7-8-9.

2 "Grupos, citas"

Problema 1

Los participantes del festival de música, al conocerse, intercambiaron sobres con direcciones. Demuestre que:

a) se entregó un número par de sobres;

b) el número de participantes que intercambiaron sobres un número impar de veces es par.

Solución: Deje que los participantes del festival sean A 1, A 2, A 3. . . , Y n son los vértices del gráfico, y los bordes conectan pares de vértices que representan a los chicos que intercambian sobres. [Apéndice Fig.8]

Solución:

a) el grado de cada vértice Ai muestra el número de sobres que el participante Ai entregó a sus amigos. El número total de envolventes transmitidas N es igual a la suma de los grados de todos los vértices del gráfico N = grado. Un 1+ paso. Un 2++. . . + paso. Un grado n -1 +. Y n, N =2p, donde p es el número de aristas del gráfico, es decir N – incluso. En consecuencia, se entregó un número par de sobres;

b) en la igualdad N = grado. Un 1+ paso. Un 2++. . . + paso. Un grado n -1 +. Y n la suma de los términos impares debe ser par, y esto sólo puede serlo si el número de términos impares es par. Esto significa que el número de participantes que intercambiaron sobres un número impar de veces es par.

Problema 2

Un día, Andrei, Boris, Volodya, Dasha y Galya acordaron ir al cine por la noche. Decidieron coordinar la elección del cine y del espectáculo por teléfono. También se decidió que si no era posible contactar a alguien por teléfono, se cancelaría el viaje al cine. Por la noche no todos se reunieron en el cine, por lo que se canceló la visita al cine. Al día siguiente empezaron a averiguar quién llamó a quién. Resultó que Andrey llamó a Boris y Volodya, Volodya llamó a Boris y Dasha, Boris llamó a Andrey y Dasha, Dasha llamó a Andrey y Volodya, y Galya llamó a Andrey, Volodya y Boris. ¿Quién no pudo hablar por teléfono y por tanto no acudió a la reunión?

Solución:

Dibujemos cinco puntos y etiquételos con las letras A, B, C, D, D. Estas son las primeras letras de los nombres. Conectemos los puntos que corresponden a los nombres de los chicos que llamaron.

[Apéndice Fig.9]

De la imagen se desprende claramente que cada uno de los chicos, Andrey, Boris y Volodya, llamaron a todos los demás. Por eso estos tipos vinieron al cine. Pero Galya y Dasha no pudieron comunicarse por teléfono (los puntos G y E no están conectados por un segmento de línea) y por lo tanto, de acuerdo con el acuerdo, no vinieron al cine.

Aplicación de gráficas en diversos ámbitos de la vida de las personas.

Además de los ejemplos dados, los gráficos se utilizan ampliamente en construcción, ingeniería eléctrica, gestión, logística, geografía, ingeniería mecánica, sociología, programación, automatización de procesos tecnológicos y de producción, psicología y publicidad.

En cualquier campo de la ciencia y la tecnología se encuentran gráficos. Los gráficos son maravillosos objetos matemáticos con los que puedes resolver problemas matemáticos, económicos y lógicos, diversos acertijos y simplificar las condiciones de los problemas de física, química, electrónica y automatización. Muchos hechos matemáticos pueden formularse convenientemente en el lenguaje de los gráficos. La teoría de grafos es parte de muchas ciencias. La teoría de grafos es una de las teorías matemáticas más bellas y visuales. Recientemente, la teoría de grafos está encontrando cada vez más aplicaciones en cuestiones aplicadas. Incluso ha surgido la química computacional, un campo de la química relativamente joven basado en la aplicación de la teoría de grafos.

Graficos moleculares, utilizados en estereoquímica y topología estructural, química de clusters, polímeros, etc., son gráficos no dirigidos que muestran la estructura de las moléculas. [Apéndice Fig. 10]. Los vértices y aristas de estos gráficos corresponden a los átomos correspondientes y los enlaces químicos entre ellos.

Gráficos y árboles moleculares: [Apéndice Fig. 10] a, b - multigrafos, respectivamente. etileno y formaldehído; ellos dicen isómeros de pentano (los árboles 4, 5 son isomorfos al árbol 2).

En la estereoquímica de los organismos más. A menudo se utilizan árboles moleculares, los árboles principales de los gráficos moleculares, que contienen solo todos los vértices correspondientes a los átomos de C. Compilación de conjuntos de moles. Los árboles y el establecimiento de su isomorfismo permiten determinar lo que dicen. estructuras y encontrar el número total de isómeros de alcanos, alquenos y alquinos

Redes de proteínas

Las redes de proteínas son grupos de proteínas que interactúan físicamente y funcionan en una célula de manera conjunta y coordinada, controlando procesos interconectados que ocurren en el cuerpo. [figura adjunta. 11].

Gráfico del sistema jerárquico llamado árbol. Una característica distintiva de un árbol es que solo hay un camino entre dos de sus vértices. El árbol no contiene ciclos ni bucles.

Normalmente, un árbol que representa un sistema jerárquico tiene un vértice principal, que se denomina raíz del árbol. Cada vértice del árbol (excepto la raíz) tiene un solo antepasado: el objeto designado por él se incluye en una clase de nivel superior. Cualquier vértice de un árbol puede generar varios descendientes: vértices correspondientes a clases de nivel inferior.

Para cada par de vértices de un árbol, existe un camino único que los conecta. Esta propiedad se utiliza para encontrar todos los antepasados, por ejemplo, en la línea masculina, de cualquier persona cuyo pedigrí se presente en forma de árbol genealógico, que es un "árbol" en el sentido de la teoría de grafos.

Ejemplo de mi árbol genealógico [Apéndice Fig. 12].

Otro ejemplo. La imagen muestra el árbol genealógico bíblico. [Apéndice Fig. 13].

resolución de problemas

1.Tarea de transporte. Que haya una base en la ciudad de Krasnodar con materias primas que deben distribuirse a las ciudades de Krymsk, Temryuk, Slavyansk-on-Kuban y Timashevsk en un solo viaje, gastando el menor tiempo y combustible posible y regresando a Krasnodar. .

Solución:

Primero, hagamos un gráfico de todas las rutas de viaje posibles. [Apéndice Fig.14], teniendo en cuenta los caminos reales entre estos asentamientos y la distancia entre ellos. Para resolver este problema, necesitamos crear otro gráfico, en forma de árbol. [Apéndice Fig.15].

Para facilitar la solución, designamos las ciudades con números: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

El resultado son 24 soluciones, pero sólo necesitamos los caminos más cortos. De todas las soluciones, sólo dos son satisfactorias: 350 km.

De manera similar, es posible y, creo, necesario calcular el transporte real de una localidad a otra.

Problema lógico que involucra transfusión. El balde contiene 8 litros de agua y hay dos cacerolas con capacidad de 5 y 3 litros. es necesario verter 4 litros de agua en una cacerola de cinco litros y dejar 4 litros en el balde, es decir, verter el agua en partes iguales en el balde y en una cacerola grande.

Solución:

La situación en cualquier momento se puede describir con tres números. [Apéndice Fig. 16].

Como resultado, obtenemos dos soluciones: una en 7 movimientos y la otra en 8 movimientos.

Conclusión

Entonces, para aprender a resolver problemas, es necesario comprender qué son, cómo están estructurados, en qué componentes se componen y cuáles son las herramientas con las que se resuelven los problemas.

Al resolver problemas prácticos utilizando la teoría de grafos, quedó claro que en cada paso, en cada etapa de su solución, es necesario aplicar la creatividad.

Desde el principio, en la primera etapa, radica en el hecho de que es necesario poder analizar y codificar la condición del problema. La segunda etapa es una notación esquemática, que consiste en una representación geométrica de los gráficos, y en esta etapa el elemento de creatividad es muy importante porque no es nada fácil encontrar correspondencias entre los elementos de la condición y los elementos correspondientes de la gráfico.

Mientras resolvía un problema de transporte o la tarea de elaborar un árbol genealógico, llegué a la conclusión de que el método gráfico es ciertamente interesante, hermoso y visual.

Me convencí de que los gráficos se utilizan ampliamente en economía, gestión y tecnología. La teoría de grafos también se utiliza en programación. Esto no se discutió en este trabajo, pero creo que es solo cuestión de tiempo.

Este trabajo científico examina gráficas matemáticas, sus áreas de aplicación y resuelve varios problemas utilizando gráficas. El conocimiento de los conceptos básicos de la teoría de grafos es necesario en diversas áreas relacionadas con la producción y la gestión empresarial (por ejemplo, cronograma de construcción de redes, cronogramas de entrega de correo). Además, mientras trabajaba en un artículo científico, dominé el trabajo en una computadora usando el editor de texto WORD. De esta forma se han cumplido los objetivos del trabajo científico.

Entonces, de todo lo anterior se desprende irrefutablemente el valor práctico de la teoría de grafos, cuya prueba fue el objetivo de este trabajo.

Literatura

Bergé K. Teoría de grafos y sus aplicaciones. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Introducción a las matemáticas finitas. -M.: IIL, 1963.

Ore O. Grafos y su aplicación. -M.: Mir, 1965.

Harari F. Teoría de grafos. -M.: Mir, 1973.

Zykov A.A. Teoría de grafos finitos. -Novosibirsk: Ciencia, 1969.

Berezina L.Yu. Grafos y su aplicación. -M.: Educación, 1979. -144 p.

"Soros Educational Journal" No. 11 1996 (artículo "Gráficos planos");

Gardner M. "Ocio matemático", M. "Mundo", 1972 (capítulo 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Old Entertainment Problems”, M. “Science”, 1988 (parte 2, sección 8; apéndice 4);

Solicitud

Solicitud

PAG

Arroz. 6

Arroz. 7

Arroz. 8

Solicitud

Solicitud

Solicitud

PAG

Arroz. 14

Solicitud

Resumen sobre el tema matemáticas superiores sobre el tema:

Aplicación de la teoría de grafos en química.

Realizado por un alumno del grupo NH-202.

Moscú 2011
Los gráficos son el campo de las matemáticas finitas que estudia estructuras discretas; Se utiliza para resolver diversos problemas teóricos y aplicados.
Alguno conceptos básicos. Una gráfica es una colección de puntos (vértices) y una colección de pares de estos puntos (no necesariamente todos) conectados por líneas (Fig. 1,a). Si las líneas de un gráfico están orientadas (es decir, las flechas indican la dirección de conexión de los vértices), se llaman arcos o ramas; si no está orientado, - bordes. En consecuencia, un gráfico que contiene sólo arcos se llama gráfico dirigido o dígrafo; sólo sin bordes; arcos y nervaduras - mixtos. Un gráfico que tiene múltiples aristas se llama multigrafo; un gráfico que contiene sólo aristas que pertenecen a dos de sus subconjuntos (partes) disjuntos es bipartito; Se ponderan los arcos (aristas) y (o) vértices que corresponden a ciertos pesos o valores numéricos de cualquier parámetro. Una ruta en un gráfico es una secuencia alterna de vértices y arcos en la que ninguno de los vértices se repite (por ejemplo, a, b en la Fig. 1,a); contorno: un camino cerrado en el que coinciden el primer y el último vértice (por ejemplo, f, h); bucle: un arco (arista) que comienza y termina en el mismo vértice. Una ruta de gráfico es una secuencia de aristas en la que ninguno de los vértices se repite (por ejemplo, c, d, e); ciclo: una cadena cerrada en la que coinciden sus vértices inicial y final. Un gráfico se llama conexo si cualquier par de sus vértices está conectado por una cadena o camino; de lo contrario, el gráfico se llama desconectado.
Un árbol es un gráfico no dirigido conectado que no contiene ciclos ni contornos (Fig. 1, b). El subgrafo expansivo de un gráfico es un subconjunto del mismo que contiene todos los vértices y solo ciertas aristas. El árbol de expansión de un gráfico es su subgrafo de expansión, que es un árbol. Los gráficos se llaman isomórficos si existe una correspondencia uno a uno entre los conjuntos de sus vértices y aristas (arcos).
Para resolver problemas de teoría de grafos y sus aplicaciones, los gráficos se representan mediante matrices (adyacencia, incidencia, dos filas, etc.), así como especiales. características numéricas. Por ejemplo, en la matriz de adyacencia (Fig.1c), las filas y columnas corresponden a los números de los vértices del gráfico, y sus elementos toman los valores 0 y 1 (respectivamente, la ausencia y presencia de un arco entre un par de vértices dado); en la matriz de incidencia (Fig. 1d), las filas corresponden a los números de los vértices, las columnas corresponden a los números de los arcos y los elementos toman los valores 0, + 1 y - 1 (respectivamente, la ausencia , presencia de un arco que entra y sale del vértice). Las características numéricas más comunes: el número de vértices (m), el número de arcos o aristas (n), el número ciclomático o el rango del gráfico (n - m + k, donde k es el número de subgrafos conectados en un gráfico desconectado; por ejemplo, para el gráfico de la Fig. 1, el rango b será: 10-6+ 1 =5).
La aplicación de la teoría de grafos se basa en la construcción y análisis de diversas clases de gráficos químicos y químico-tecnológicos, que también se denominan modelos topológicos, es decir. Modelos que tienen en cuenta únicamente la naturaleza de las conexiones entre los vértices. Los arcos (bordes) y vértices de estos gráficos muestran conceptos, fenómenos, procesos u objetos químicos y químico-tecnológicos y, en consecuencia, relaciones cualitativas y cuantitativas o determinadas relaciones entre ellos.

Arroz. 1. Ilustración de algunos conceptos básicos: gráfico a-mixto; árbol de expansión b (arcos sólidos a, h, d, f, h) y un determinado subgrafo (arcos discontinuos c, e, g, k, l) del dígrafo; c, matrices r resp. Adyacencia e incidencia de un dígrafo.
Problemas teóricos. Los gráficos químicos permiten predecir transformaciones químicas, explicar la esencia y sistematizar algunos conceptos básicos de la química: estructura, configuración, conformaciones, interacciones mecánica cuántica y estadístico-mecánica de moléculas, isomería, etc. Los gráficos químicos incluyen gráficos moleculares, bipartitos y de señales. de ecuaciones de reacción cinética.
Los gráficos moleculares, utilizados en estereoquímica y topología estructural, química de clusters, polímeros, etc., son gráficos no dirigidos que muestran la estructura de las moléculas (Fig. 2). Los vértices y aristas de estos gráficos corresponden, respectivamente, a átomos y enlaces químicos entre ellos.

Arroz. 2. Gráficos y árboles moleculares: a, b - multigrafos, respectivamente. etileno y formaldehído; ellos dicen isómeros de pentano (los árboles 4, 5 son isomorfos al árbol 2).
En la estereoquímica de sustancias orgánicas, los árboles moleculares se utilizan con mayor frecuencia: árboles abarcadores de gráficos moleculares, que contienen solo todos los vértices correspondientes a los átomos de C (Fig. 2, a y b). La compilación de conjuntos de árboles moleculares y el establecimiento de su isomorfismo permite determinar estructuras moleculares y encontrar el número total de isómeros de alcanos, alquenos y alquinos (Fig. 2, c).
Los gráficos moleculares permiten reducir los problemas relacionados con la codificación, nomenclatura y características estructurales (ramificación, ciclicidad, etc.) de moléculas de diversos compuestos al análisis y comparación de características y propiedades puramente matemáticas de los gráficos moleculares y sus árboles, así como sus matrices correspondientes. Para identificar correlaciones cuantitativas entre la estructura de las moléculas y las propiedades fisicoquímicas (incluidas farmacológicas) de los compuestos, se han desarrollado más de 20 mil nombres de índices topológicos de moléculas (Wiener, Balaban, Hosoya, Plat, Randich, etc.), que son determinado utilizando matrices y características numéricas de árboles moleculares. Por ejemplo, el índice de Wiener W = (m 3 + m)/6, donde m es el número de vértices correspondientes a los átomos de C, se correlaciona con volúmenes moleculares y refracciones, entalpías de formación, viscosidad, tensión superficial, constantes cromatográficas de compuestos, índices de octanaje de los hidrocarburos e incluso la actividad fisiológica de los fármacos.
Los parámetros importantes de los gráficos moleculares utilizados para determinar las formas tautoméricas de una sustancia determinada y su reactividad, así como en la clasificación de aminoácidos, ácidos nucleicos, carbohidratos y otros compuestos naturales complejos, son las capacidades de información promedio y total (H). El parámetro se calcula utilizando la fórmula de entropía de información de Shannon: , donde p t es la probabilidad de que los vértices m del gráfico pertenezcan al i-ésimo tipo, o clase de equivalencia, k; i = , Parámetro. El estudio de estructuras moleculares como los clusters inorgánicos o las tiras de Möbius se reduce a establecer el isomorfismo de los gráficos moleculares correspondientes colocándolos (incrustados) en poliedros complejos (por ejemplo, poliedros en el caso de clusters) o especiales. superficies multidimensionales (por ejemplo, superficies de Riemann). El análisis de las gráficas moleculares de los polímeros, cuyos vértices corresponden a unidades monoméricas y los bordes a los enlaces químicos entre ellos, permite explicar, por ejemplo, los efectos del volumen excluido, lo que conduce a cambios cualitativos en las propiedades previstas de los polímeros. .

Arroz. 3. Gráficos de reacción: a-bipartito; nivel de cinética de la señal b; r 1, g 2 -r-ción; a 1 -a 6 -reactivos; constantes de velocidad k p-tsny; Variable de transformada de Laplace de complejo s.
Utilizando la teoría de grafos y los principios de la inteligencia artificial, se ha desarrollado software para sistemas de recuperación de información en química, así como sistemas automatizados para identificar estructuras moleculares y planificar racionalmente la síntesis orgánica. Para la implementación práctica en una computadora de operaciones para seleccionar rutas racionales de transformaciones químicas basadas en los principios retrosintético y sintónico, se utilizan gráficos de búsqueda ramificados de varios niveles para opciones de solución, cuyos vértices corresponden a los gráficos moleculares de reactivos y productos. y los arcos representan las transformaciones de sustancias.

Arroz. 4. Sistema químico-tecnológico de circuito único y gráficos correspondientes: diagrama a-estructural; b, gráficos de flujo de material c, respectivamente. por caudales másicos totales y caudal del componente A; r - gráfico de flujo térmico; Fragmento d del sistema de ecuaciones (f 1 - f 6) del balance de materia, obtenido del análisis de las gráficas de la Fig. 4, byc; dígrafo de información e-bipartito; gráfico de información g, mezclador I; II-reactor; III-columna de destilación; IV-refrigerador; Yo 1 -Yo 8 -tecnología. arroyos; q-flujo másico; H es la entalpía del flujo; i. s e i*, s* - resp. fuentes y sumideros reales y ficticios de materiales y flujos de calor; c-concentración del reactivo; V es el volumen del reactor.
Las representaciones matriciales de gráficos moleculares de varios compuestos son equivalentes (después de transformar los elementos matriciales correspondientes) a los métodos matriciales de la química cuántica. Por lo tanto, la teoría de grafos se utiliza al realizar cálculos químicos cuánticos complejos: para determinar el número, las propiedades y las energías de los orbitales moleculares, predecir la reactividad de polienos conjugados alternantes y no alternantes, identificar propiedades aromáticas y antiaromáticas de sustancias, etc.
Para estudiar las perturbaciones en sistemas formados por un gran número de partículas en física química, se utilizan los llamados diagramas de Feynman, gráficos cuyos vértices corresponden a las interacciones elementales de las partículas físicas y los bordes de sus trayectorias después de las colisiones. En particular, estos gráficos permiten estudiar los mecanismos de reacciones oscilatorias y determinar la estabilidad de los sistemas de reacción.
Para seleccionar caminos racionales para la transformación de moléculas de reactivos para un conjunto dado de interacciones conocidas, se utilizan gráficos de reacción bipartitos (los vértices corresponden a moléculas y estas reacciones, los arcos corresponden a las interacciones de las moléculas en la reacción; Fig. 3,a ). Dichos gráficos permiten desarrollar algoritmos interactivos para seleccionar rutas óptimas de transformaciones químicas que requieren la menor cantidad de reacciones intermedias, la cantidad mínima de reactivos de la lista de aceptables o lograr el mayor rendimiento de productos.
Los gráficos de señales de ecuaciones cinéticas de reacción muestran sistemas de ecuaciones cinéticas presentadas en forma de operador algebraico (Fig. 3b). Los vértices de los gráficos corresponden a las llamadas variables de información, o señales, en forma de concentraciones de reactivos, arcos, a relaciones de señales, y los pesos de los arcos están determinados por constantes cinéticas. Estos gráficos se utilizan para estudiar los mecanismos y la cinética de reacciones catalíticas complejas, equilibrios de fases complejos en la formación de compuestos complejos, así como para calcular los parámetros de las propiedades aditivas de las soluciones.
Problemas aplicados. Para resolver problemas multidimensionales de análisis y optimización de sistemas químico-tecnológicos (CTS) se utilizan los siguientes gráficos químico-tecnológicos (Fig. 4): gráficos de flujo, flujo de información, señales y confiabilidad. Los gráficos de flujo, que son dígrafos ponderados, incluyen material paramétrico en términos de los caudales másicos totales de los flujos físicos y los caudales másicos de algunos componentes o elementos químicos, así como gráficos térmicos. Los gráficos enumerados corresponden a las transformaciones físicas y químicas de sustancias y energía en un sistema químico determinado.
Los gráficos de flujo paramétrico muestran la transformación de parámetros (caudales másicos, etc.) de flujos físicos mediante elementos CTS; los vértices de los gráficos corresponden a los modelos matemáticos de los dispositivos, así como a las fuentes y sumideros de los flujos especificados, y los arcos corresponden a los flujos mismos, y los pesos de los arcos son iguales al número de parámetros del flujo correspondiente. Los gráficos paramétricos se utilizan para desarrollar algoritmos para analizar modos tecnológicos de sistemas químicos de circuitos múltiples. Dichos algoritmos establecen la secuencia de cálculo de sistemas de ecuaciones de modelos matemáticos de dispositivos individuales de cualquier sistema para determinar los parámetros de sus flujos de salida con valores conocidos de flujos de entrada variables.
Los gráficos de flujo de materiales muestran cambios en el consumo de sustancias en sustancias químicas. Los vértices de los gráficos corresponden a dispositivos en los que se transforman los caudales másicos totales de flujos físicos y los caudales másicos de algunos componentes o elementos químicos, así como fuentes y sumideros de sustancias de los flujos o estos componentes; En consecuencia, los arcos de los gráficos corresponden a flujos físicos o fuentes y sumideros físicos y ficticios (transformaciones químicas de sustancias en aparatos) de cualquier componente, y los pesos de los arcos son iguales a los caudales másicos de ambos tipos. Los gráficos de flujo térmico muestran los balances de calor en CTS; los vértices de los gráficos corresponden a dispositivos en los que cambia el consumo de calor de los flujos físicos y, además, a las fuentes y sumideros de energía térmica del sistema; Los arcos corresponden a flujos de calor físicos y ficticios (conversión de energía físico-química en dispositivos), y los pesos de los arcos son iguales a las entalpías de los flujos. Los gráficos térmicos y de materiales se utilizan para compilar programas para el desarrollo automatizado de algoritmos para resolver sistemas de ecuaciones para balances de materiales y calor de sistemas químicos complejos.
Los gráficos de stock de información muestran la estructura de información lógica de los sistemas de ecuaciones de modelos matemáticos de CTS; se utilizan para desarrollar algoritmos óptimos para el cálculo de estos sistemas. Un gráfico de información bipartito (Fig.4, e) es un gráfico orientado o no dirigido, cuyos vértices corresponden, respectivamente, a las ecuaciones f l - f 6 y las variables q 1 - V, y las ramas reflejan su relación. Gráfico de información (Fig.4, g): un dígrafo que representa el orden de resolución de ecuaciones; los vértices del gráfico corresponden a estas ecuaciones, fuentes y receptores de información XTS, y las ramas corresponden a variables de información.
Los gráficos de señales corresponden a sistemas lineales de ecuaciones de modelos matemáticos de procesos y sistemas tecnológicos químicos. Los vértices de los gráficos corresponden a señales (por ejemplo, temperatura) y las ramas corresponden a conexiones entre ellas. Dichos gráficos se utilizan para analizar los modos estáticos y dinámicos de procesos multiparamétricos y sistemas químicos, así como indicadores de varias de sus propiedades más importantes (estabilidad, sensibilidad, controlabilidad).
Los gráficos de confiabilidad se utilizan para calcular varios indicadores de confiabilidad de equipos químicos. Entre los numerosos grupos de estos gráficos (por ejemplo, paramétricos, lógico-funcionales), son especialmente importantes los llamados árboles de fallas. Cada uno de estos árboles es un dígrafo ponderado que muestra la interrelación de muchas fallas simples de procesos individuales y dispositivos CTS, que conducen a muchas fallas secundarias y la falla resultante del sistema en su conjunto.
Para crear complejos de programas para la síntesis automatizada de una producción óptima altamente confiable (incluido el ahorro de recursos), junto con los principios de la inteligencia artificial, se utilizan gráficos semánticos orientados o semánticos de las opciones de solución CTS. Estos gráficos, que en un caso particular son árboles, representan procedimientos para generar un conjunto de esquemas CTS alternativos racionales (por ejemplo, 14 posibles al separar una mezcla de cinco componentes de productos objetivo mediante rectificación) y procedimientos para la selección ordenada entre ellos de un esquema que es óptimo según algún criterio de eficiencia del sistema.
etc.............

Además, durante los últimos 12 años de su vida, Euler estuvo gravemente enfermo, quedó ciego y, a pesar de su grave enfermedad, continuó trabajando y creando.

Los cálculos estadísticos muestran que Euler hacía en promedio un descubrimiento por semana.

Es difícil encontrar un problema matemático que no haya sido abordado en las obras de Euler.

Todos los matemáticos de las generaciones posteriores estudiaron con Euler de una forma u otra, y no en vano el famoso científico francés P.S. Laplace dijo: "Lea a Euler, él es el maestro de todos nosotros".

Lagrange dice: "Si realmente amas las matemáticas, lee a Euler; la presentación de sus obras destaca por su asombrosa claridad y precisión". De hecho, la elegancia de sus cálculos llegó al más alto grado. Condorcet concluyó su discurso en la Academia en memoria de Euler con las siguientes palabras: “¡Así que Euler dejó de vivir y de calcular!” Vivir para calcular: ¡qué aburrido parece desde fuera!

Se acostumbra imaginar a un matemático seco y sordo a todo lo cotidiano, a lo que interesa a la gente corriente.

El problema de las tres casas y los tres pozos lleva el nombre de Euler.

Una de las ramas de la topología. Una gráfica es un diagrama geométrico que es un sistema de líneas que conectan ciertos puntos. Los puntos se llaman vértices y las líneas que los conectan se llaman aristas (o arcos). Todos los problemas de teoría de grafos se pueden resolver tanto en forma gráfica como matricial. En el caso de la escritura en forma matricial, la posibilidad de transmitir un mensaje de un vértice determinado a otro se denota por uno, y su ausencia, por cero.

El origen de la teoría de grafos en el siglo XVIII. asociado con acertijos matemáticos, pero en el siglo XIX se dio un impulso particularmente fuerte para su desarrollo. y principalmente en el siglo XX, cuando se descubrieron las posibilidades de sus aplicaciones prácticas: para calcular circuitos radioelectrónicos, resolviendo los llamados. Tareas de transporte, etc. Desde los años 50. La teoría de grafos se utiliza cada vez más en psicología social y sociología.

En el campo de la Teoría de Grafos cabe citar los trabajos de F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss, etc. . En la URSS, según T. g. METRO. Borodkin et al.

El lenguaje de teoría de grafos es muy adecuado para analizar varios tipos de estructuras y transferir estados. De acuerdo con esto, podemos distinguir los siguientes tipos de problemas sociológicos y sociopsicológicos resueltos mediante la Teoría de Grafos.

Formalización y construcción de un modelo estructural general de un objeto social en diferentes niveles de su complejidad. Por ejemplo, un diagrama estructural de una organización, sociogramas, comparación de sistemas de parentesco en diferentes sociedades, análisis de la estructura de roles de los grupos, etc.

Podemos considerar que la estructura de roles incluye tres componentes: personas, puestos (en una versión simplificada - puestos) y tareas realizadas en un puesto determinado.

Cada componente se puede representar como un gráfico:

Es posible combinar los tres gráficos para todas las posiciones o solo para una, y como resultado obtenemos una idea clara de la estructura específica del c.l. este papel. Así, para el papel de la posición P5 tenemos un gráfico (Fig.). Entretejer relaciones informales en una estructura formal especificada complicará significativamente el gráfico, pero será una copia más fiel de la realidad.

a) cantidades. evaluar el peso (estado) de un individuo en una organización jerárquica. Una de las posibles opciones para determinar el estado es la fórmula:

donde r (p) es el estatus de una determinada persona p, k es el valor del nivel de subordinación, definido como el número más pequeño de pasos de una persona determinada a su subordinado, nk es el número de personas en un nivel determinado k . Por ejemplo, en la organización representada por la siguiente. Contar:

peso a=1·2+2·7+3·4=28; 6=1·3+2·3=9, etc.

b) determinación del líder del grupo. El líder suele caracterizarse por una mayor conexión con el resto del grupo en comparación con los demás. Como en la tarea anterior, aquí también se pueden utilizar varios métodos para identificar al líder.

El método más simple viene dado por la fórmula: r=Σdxy/Σdqx, es decir el cociente de dividir la suma de todas las distancias de cada persona a todos los demás por la suma de las distancias de un individuo determinado a todos los demás.

4) Análisis de la efectividad de la actividad de este sistema, que también incluye tareas como buscar la estructura óptima de la organización, incrementar la cohesión del grupo, analizar el sistema social desde el punto de vista de su sostenibilidad; estudio de los flujos de información (transmisión de mensajes al resolver problemas, la influencia de los miembros del grupo entre sí en el proceso de unir el grupo); Con la ayuda de la tecnología, resuelven el problema de encontrar una red de comunicación óptima.

Cuando se aplica a la Teoría de Grafos, así como a cualquier aparato matemático, es cierto que los principios básicos para resolver un problema los establece una teoría sustantiva (en este caso, la sociología).

Tarea : Tres vecinos tienen tres pozos comunes. ¿Es posible construir caminos que no se crucen desde cada casa hasta cada pozo? Los caminos no pueden pasar por pozos ni casas (Fig. 1).

Arroz. 1. Al problema de las casas y los pozos.

Para resolver este problema utilizaremos un teorema demostrado por Euler en 1752, que es uno de los principales de la teoría de grafos. El primer trabajo sobre teoría de grafos pertenece a Leonhard Euler (1736), aunque el término “grafo” fue introducido por primera vez en 1936 por el matemático húngaro Dénes König. Los gráficos se denominaron diagramas que constan de puntos y segmentos de líneas rectas o curvas que conectan estos puntos.

Teorema. Si un polígono se divide en un número finito de polígonos de modo que dos polígonos cualesquiera de la partición no tengan puntos comunes, vértices comunes o aristas comunes, entonces se cumple la igualdad

B - P + G = 1, (*)

donde B es el número total de vértices, P es el número total de aristas, G es el número de polígonos (caras).

Prueba. Demostremos que la igualdad no cambia si se traza una diagonal en algún polígono de una partición determinada (Fig. 2, a).

A) b)

De hecho, después de dibujar dicha diagonal, la nueva partición tendrá B vértices, P+1 aristas y el número de polígonos aumentará en uno. Por lo tanto, tenemos

B - (P + 1) + (G+1) = B - P + GRAMO.

Usando esta propiedad, dibujamos diagonales que dividen los polígonos entrantes en triángulos y, para la partición resultante, mostramos la viabilidad de la relación.

Para ello, eliminaremos secuencialmente los bordes externos, reduciendo el número de triángulos. En este caso, son posibles dos casos:

para eliminar el triángulo ABC, es necesario eliminar dos aristas, en nuestro caso AB y BC;

Para eliminar el triángulo MKN, es necesario eliminar un borde, en nuestro caso MN.

En ambos casos la igualdad no cambiará. Por ejemplo, en el primer caso, después de eliminar el triángulo, el gráfico estará formado por vértices B-1, aristas P-2 y polígono G-1:

(B - 1) - (P + 2) + (G -1) = B – P + G.

Por tanto, eliminar un triángulo no cambia la igualdad.

Continuando con este proceso de eliminar triángulos, eventualmente llegaremos a una partición que consta de un solo triángulo. Para tal partición B = 3, P = 3, G = 1 y, por lo tanto,

Esto significa que la igualdad también se cumple para la partición original, de lo que finalmente obtenemos que la relación es válida para esta partición del polígono.

Tenga en cuenta que la relación de Euler no depende de la forma de los polígonos. Los polígonos se pueden deformar, agrandar, reducir o incluso doblar sus lados, siempre y cuando los lados no se rompan. La relación de Euler no cambiará.

Procedamos ahora a resolver el problema de tres casas y tres pozos.

Solución. Supongamos que esto se puede hacer. Marquemos las casas con los puntos D1, D2, D3 y los pozos con los puntos K1, K2, K3 (Fig. 1). Conectamos cada punto de la casa con cada punto del pozo. Obtenemos nueve aristas que no se cruzan en pares.

Estos bordes forman un polígono en el plano, dividido en polígonos más pequeños. Por lo tanto, para esta partición se debe satisfacer la relación de Euler B - P + G = 1.

Agreguemos una cara más a las caras consideradas: la parte exterior del plano en relación con el polígono. Entonces la relación de Euler tomará la forma B - P + G = 2, con B = 6 y P = 9.

Por lo tanto, Г = 5. Cada una de las cinco caras tiene al menos cuatro aristas, ya que, según las condiciones del problema, ninguno de los caminos debe conectar directamente dos casas o dos pozos. Dado que cada arista se encuentra exactamente en dos caras, el número de aristas debe ser al menos (5 4)/2 = 10, lo que contradice la condición de que su número sea 9.

La contradicción resultante muestra que la respuesta al problema es negativa. - es imposible trazar caminos que no se crucen desde cada casa a cada pueblo

Teoría de grafos en química

Aplicación de la teoría de grafos a la construcción y análisis de diversas clases de gráficos químicos y químico-tecnológicos, que también se denominan topología, modelos, es decir. Modelos que tienen en cuenta únicamente la naturaleza de las conexiones entre los vértices. Los arcos (bordes) y vértices de estos gráficos reflejan conceptos, fenómenos, procesos u objetos químicos y químico-tecnológicos y, en consecuencia, relaciones cualitativas y cuantitativas o determinadas relaciones entre ellos.

Problemas teóricos. Los gráficos químicos permiten predecir transformaciones químicas, explicar la esencia y sistematizar algunos conceptos básicos de la química: estructura, configuración, confirmaciones, interacciones mecánica cuántica y estadístico-mecánica de moléculas, isomería, etc. Los gráficos químicos incluyen gráficos moleculares, bipartitos y de señales. de ecuaciones de reacción cinética. Los gráficos moleculares, utilizados en estereoquímica y topología estructural, química de clusters, polímeros, etc., son gráficos no dirigidos que muestran la estructura de las moléculas. Los vértices y aristas de estos gráficos corresponden a los átomos correspondientes y los enlaces químicos entre ellos.

En estereoquímica org. c-c los más utilizados son los árboles moleculares: árboles que abarcan gráficos moleculares que contienen solo todos los vértices correspondientes a los átomos. La compilación de conjuntos de árboles moleculares y el establecimiento de su isomorfismo permite determinar las estructuras moleculares y encontrar el número total de isómeros de alcanos. alquenos y alquinos. Los gráficos moleculares permiten reducir los problemas relacionados con la codificación, nomenclatura y características estructurales (ramificación, ciclicidad, etc.) de moléculas de diversos compuestos al análisis y comparación de características y propiedades puramente matemáticas de los gráficos moleculares y sus árboles, así como sus matrices correspondientes. Para identificar la cantidad de correlaciones entre la estructura de las moléculas y las propiedades fisicoquímicas (incluidas las farmacológicas) de los compuestos, se han desarrollado más de 20 de las denominadas. Índices topológicos de moléculas (Wiener, Balaban, Hosoya, Plata, Randic, etc.), que se determinan mediante matrices y características numéricas de árboles moleculares. Por ejemplo, el índice de Wiener W = (m3 + m)/6, donde m es el número de vértices correspondientes a los átomos de C, se correlaciona con volúmenes moleculares y refracciones, entalpías de formación, viscosidad, tensión superficial, constantes cromatográficas de compuestos, octanaje. Números de hidrocarburos e incluso fisiol. actividad de las drogas. Los parámetros importantes de los gráficos moleculares utilizados para determinar las formas tautoméricas de una sustancia determinada y su reactividad, así como en la clasificación de aminoácidos, ácidos nucleicos, carbohidratos y otros compuestos naturales complejos, son la capacidad de información promedio y total (H). El análisis de las gráficas moleculares de los polímeros, cuyos vértices corresponden a unidades monoméricas y cuyos bordes corresponden a enlaces químicos entre ellos, permite explicar, por ejemplo, los efectos del volumen excluido en las cualidades. cambios en las propiedades previstas de los polímeros. Utilizando la teoría de grafos y los principios de la inteligencia artificial, se ha desarrollado software para sistemas de recuperación de información en química, así como sistemas automatizados para identificar estructuras moleculares y planificar racionalmente la síntesis orgánica. Para la implementación práctica en una computadora de operaciones para seleccionar rutas químicas racionales. Las transformaciones basadas en los principios retrosintéticos y sintónicos utilizan gráficos de búsqueda ramificados de varios niveles para opciones de solución, cuyos vértices corresponden a los gráficos moleculares de reactivos y productos, y los arcos representan transformaciones.

Para resolver problemas multidimensionales de análisis y optimización de sistemas tecnológicos químicos (CTS) se utilizan los siguientes gráficos tecnológicos químicos: gráficos de flujo, flujo de información, señales y confiabilidad. Para estudiar química. La física de las perturbaciones en sistemas formados por un gran número de partículas utiliza el llamado. Los diagramas de Feynman son gráficos cuyos vértices corresponden a las interacciones elementales de partículas físicas, los bordes de sus trayectorias después de las colisiones. En particular, estos gráficos permiten estudiar los mecanismos de reacciones oscilatorias y determinar la estabilidad de los sistemas de reacción. Los gráficos de flujo de materiales muestran cambios en los caudales en sistemas de calentamiento químicos. Los gráficos de flujo térmico muestran balances de calor en sistemas de calentamiento químicos. los vértices de los gráficos corresponden a dispositivos en los que cambia el consumo de calor de los flujos físicos y, además, a las fuentes y sumideros de energía térmica del sistema; Los arcos corresponden a flujos de calor físicos y ficticios (conversión de energía físico-química en dispositivos), y los pesos de los arcos son iguales a las entalpías de los flujos. Los gráficos térmicos y de materiales se utilizan para compilar programas para el desarrollo automatizado de algoritmos para resolver sistemas de ecuaciones para balances de materiales y calor de sistemas químicos complejos. Los gráficos de flujo de información muestran la estructura lógica de información de sistemas de ecuaciones matemáticas. modelos XTS; se utilizan para desarrollar algoritmos óptimos para el cálculo de estos sistemas. Un gráfico de información bipartito es un gráfico dirigido o no dirigido cuyos vértices se corresponden respectivamente. ecuaciones fl -f6 y variables q1 – V, y las ramas reflejan su relación. Gráfico de información: un dígrafo que representa el orden de resolución de ecuaciones; los vértices del gráfico corresponden a estas ecuaciones, fuentes y receptores de información XTS, y las ramas corresponden a información. variables. Los gráficos de señales corresponden a sistemas lineales de ecuaciones de modelos matemáticos de procesos y sistemas tecnológicos químicos. Los gráficos de confiabilidad se utilizan para calcular varios indicadores de confiabilidad X.

Literatura utilizada:

1.Berge K., T. g y su aplicación, traducción del francés, M., 1962;

2. Kemeny J., Snell J., Thompson J., Introducción a las matemáticas finitas, trad. Del inglés, 2ª ed., M., 1963;

3.Ope O., Gráficos y su aplicación, trad. Del inglés, M., 1965;

4. Belykh O.V., Belyaev E.V., Posibilidades de aplicación de la sociología en sociología, en: Hombre y sociedad, vol. 1, [L.], 1966;

5. Métodos cuantitativos en la investigación sociológica, M., 1966; Belyaev E.V., Problemas de las mediciones sociológicas, "VF", 1967, núm. 7; Bavelas. Patrones de comunicación en grupos orientados a tareas, en el libro. Lerner D., Lasswell H., Ciencias políticas, Stanford, 1951;

6. Kemeny J. G., Snell J., Modelos matemáticos en las ciencias sociales, N. Y., 1962; Filament C., Aplicaciones de la teoría de grafos a la estructura de grupos, N. Y., 1963; Оeser Ο. A., Hararu F., Estructuras de roles y descripción en términos de teoría de grafos, en el libro: Biddle V., Thomas E. J., Teoría de roles: conceptos e investigación, N. Y., 1966. E. Belyaev. Leningrado.