Teoría de grafos: definiciones básicas. Teoría de grafos: conceptos y tareas básicos. Gráficos como estructura de datos.
De manera informal, se puede considerar una gráfica como un conjunto de puntos y líneas que conectan estos puntos, con o sin flechas.
Se considera que el primer trabajo de teoría de grafos como disciplina matemática fue el artículo de Euler (1736), que abordaba el problema de los puentes de Köningsberg. Euler demostró que es imposible pasar por alto los siete puentes de la ciudad y regresar al punto de partida cruzando cada puente exactamente una vez. La teoría de grafos recibió su siguiente impulso casi 100 años después con el desarrollo de la investigación sobre redes electricas, cristalografía, química orgánica y otras ciencias.
Sin siquiera darnos cuenta, nos encontramos con gráficos todo el tiempo. Por ejemplo, una gráfica es un diagrama de líneas de metro. Los puntos representan estaciones y las líneas representan rutas de tren. Al investigar nuestra ascendencia y rastrearla hasta un ancestro lejano, construimos el llamado árbol genealógico. Y este árbol es un gráfico.
Los gráficos sirven como un medio conveniente para describir relaciones entre objetos. Anteriormente hemos utilizado gráficos como una forma de representar visualmente relaciones binarias finitas.
Pero el gráfico no sirve sólo como ilustración. Por ejemplo, al considerar un gráfico que representa una red de carreteras entre áreas pobladas, puede determinar la ruta desde el punto A al punto B. Si hay varias rutas de este tipo, le gustaría elegir la óptima en cierto sentido, por ejemplo el más corto o el más seguro. Para resolver el problema de selección es necesario realizar ciertos cálculos sobre gráficas. Al resolver este tipo de problemas, es conveniente utilizar técnicas algebraicas y es necesario formalizar el concepto mismo de gráfico.
Los métodos de la teoría de grafos se utilizan ampliamente en matemáticas discretas. Es imposible prescindir de ellos a la hora de analizar y sintetizar varios convertidores discretos: bloques funcionales de ordenadores, paquetes de software, etc.
Actualmente, la teoría de grafos cubre una gran cantidad de material y se está desarrollando activamente. Al presentarlo, nos limitaremos a solo una parte de los resultados y pondremos el énfasis principal en la descripción y justificación de algunos algoritmos de análisis de grafos ampliamente utilizados en la teoría de los lenguajes formales.
Definiciones basicas
Los gráficos, como ya se señaló en los ejemplos, son una forma de "visualizar" conexiones entre ciertos objetos. Estas conexiones pueden ser "dirigidas", como, por ejemplo, en un árbol genealógico, o "no dirigidas" (una red de dos vías). carreteras). De acuerdo con esto, en teoría de grafos existen dos tipos principales de grafos: dirigidos (o dirigidos) y no dirigidos.
Métodos de presentación
Hasta ahora, hemos definido gráficos dirigidos y no dirigidos, representándolos mediante dibujos. Se puede definir un gráfico como un par de conjuntos, siguiendo la definición, pero este método es bastante engorroso y tiene más bien un interés teórico. El desarrollo de enfoques algorítmicos para analizar las propiedades de los gráficos requiere otras formas de describir gráficos que sean más adecuadas para cálculos prácticos, incluido el uso de una computadora. Veamos las tres formas más comunes de representar gráficas.
Árboles
Definición 5.5. Un árbol no dirigido es un gráfico no dirigido acíclico y conectado. Definición 5.6. Un árbol dirigido es un gráfico dirigido sin contorno en el que el medio grado de cualquier vértice no es mayor que 1 y hay exactamente un vértice, llamado raíz del árbol dirigido, cuyo medio grado es 0.
Árbol de expansión de menor peso
El siguiente problema se conoce en teoría de grafos como problema de Steiner: se dan n puntos en un plano; debes conectarlos con segmentos rectos de tal manera que la longitud total de los segmentos sea mínima.
Métodos para atravesar sistemáticamente los vértices del gráfico.
Los problemas importantes en la teoría de grafos son los problemas del análisis global de grafos dirigidos y no dirigidos. Estas tareas incluyen, por ejemplo, la tarea de encontrar ciclos o contornos, calcular las longitudes de caminos entre pares de vértices, listar caminos con ciertas propiedades, etc. El análisis de gráficos globales debe distinguirse del análisis local, un ejemplo del cual es el problema de determinar los conjuntos de predecesores y sucesores de un vértice fijo de un gráfico dirigido.
Problema de ruta en gráficos dirigidos ponderados
Isomorfismo gráfico
Para un gráfico dirigido (V, E), el conjunto E de arcos puede considerarse como un gráfico de una relación binaria de alcanzabilidad directa definida en el conjunto de vértices. En un gráfico no dirigido (V, E), el conjunto E de aristas es el conjunto de pares desordenados. Para cada par desordenado (u, v) ∈ E podemos asumir que los vértices u y v están conectados por una relación binaria simétrica p, es decir (u, v) ∈ р y (v, u) ∈ р.
clasificación topológica
Definición 5.17. Una red dirigida (o simplemente una red) es un gráfico dirigido sin contornos*. Dado que la red es un gráfico sin contorno, se puede demostrar que hay vértices (nodos) de la red con cero grados de salida, así como vértices (nodos) con cero grados de entrada. Los primeros se denominan sumideros o salidas de la red, y los segundos se denominan fuentes o entradas de la red.
Elementos de la ciclomática.
Al discutir el algoritmo de búsqueda en profundidad en un gráfico no dirigido, se consideró la cuestión de buscar los llamados ciclos fundamentales del gráfico. En este caso, un ciclo fundamental se entendió como un ciclo que contiene exactamente un borde inverso, y se estableció una correspondencia uno a uno entre los ciclos fundamentales y los bordes inversos; los ciclos fundamentales surgen siempre que una partición arbitraria de todos los bordes de un gráfico no dirigido en árboles (que forman un bosque de borde máximo del gráfico original) e inverso, y en el caso general esta partición se puede especificar de forma completamente independiente del algoritmo de búsqueda en profundidad. La búsqueda en profundidad es solo una forma de implementar dicha partición.
La teoría de grafos es una rama de las matemáticas discretas que estudia objetos representados como elementos individuales (vértices) y las conexiones entre ellos (arcos, aristas).
La teoría de grafos tiene su origen en la solución del problema de los puentes de Königsberg en 1736 por parte del famoso matemático. leonardo Euler(1707-1783: nacido en Suiza, vivió y trabajó en Rusia).
Problema con los puentes de Königsberg.
En la ciudad prusiana de Königsberg hay siete puentes sobre el río Pregal. ¿Es posible encontrar una ruta a pie que cruce cada puente exactamente una vez y comience y termine en el mismo lugar?
Un gráfico en el que hay una ruta que comienza y termina en el mismo vértice y pasa por todos los bordes del gráfico exactamente una vez se llamaGráfico de Euler.
La secuencia de vértices (tal vez repetidos) por los que pasa la ruta deseada, así como la ruta misma, se llamaciclo de euler .
El problema de las tres casas y los tres pozos.
Hay tres casas y tres pozos, de alguna manera ubicados en un plano. Dibuja un camino desde cada casa hasta cada pozo para que los caminos no se crucen. Este problema fue resuelto (se demostró que no hay solución) por Kuratovsky (1896 - 1979) en 1930.
El problema de los cuatro colores. Dividir un plano en áreas que no se cruzan se llama por tarjeta. Las áreas del mapa se denominan adyacentes si tienen un borde común. La tarea consiste en colorear el mapa de tal manera que no haya dos áreas adyacentes pintadas del mismo color. Desde finales del siglo XIX se conoce la hipótesis de que cuatro colores son suficientes para ello. La hipótesis aún no ha sido probada.
La esencia de la solución publicada es probar un número grande pero finito (alrededor de 2000) tipos de posibles contraejemplos del teorema de los cuatro colores y demostrar que ni un solo caso es un contraejemplo. El programa completó esta búsqueda en aproximadamente mil horas de funcionamiento de la supercomputadora.
Es imposible comprobar la solución resultante "manualmente": el alcance de la enumeración está más allá del alcance de las capacidades humanas. Muchos matemáticos plantean la pregunta: ¿puede considerarse válida una “demostración de programa” de este tipo? Después de todo, puede haber errores en el programa...
Por lo tanto, sólo podemos confiar en las habilidades de programación de los autores y creer que hicieron todo bien.
Definición 7.1. Contar GRAMO= GRAMO(V, mi) es una colección de dos conjuntos finitos: V – llamado muchos vértices y el conjunto E de pares de elementos de V, es decir EÍV´V, llamado muchos bordes, si los pares están desordenados, o muchos arcos, si los pares están ordenados.
En el primer caso, el gráfico GRAMO(V, mi) llamado desorientado, en el segundo - orientado.
EJEMPLO. Un gráfico con un conjunto de vértices V = (a,b,c) y un conjunto de aristas E =((a, b), (b, c))
EJEMPLO. Una gráfica con V = (a,b,c,d,e) y E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (cd)),
Si e=(v 1 ,v 2), еОЕ, entonces dicen que la arista es e conecta vértices v 1 y v 2.
Dos vértices v 1,v 2 se llaman adyacente, si hay un borde que los conecta. En esta situación, cada uno de los vértices se llama incidente borde correspondiente .
Dos costillas diferentes adyacente, si tienen un vértice común. En esta situación, cada una de las aristas se llama incidental vértice correspondiente .
Número de vértices del gráfico GRAMO vamos a denotar v, y el número de aristas es mi:
.
La representación geométrica de las gráficas es la siguiente:
1) el vértice del gráfico es un punto en el espacio (en el plano);
2) una arista de un gráfico no dirigido – un segmento;
3) un arco de un gráfico dirigido – un segmento dirigido.
Definición 7.2. Si en la arista e=(v 1 ,v 2) v 1 =v 2 ocurre, entonces la arista e se llama bucle. Si un gráfico permite bucles, entonces se llama grafico con bucles o pseudografo .
Si un gráfico permite más de una arista entre dos vértices, entonces se llama multigrafo .
Si cada vértice de un gráfico y/o arista está etiquetado, entonces dicho gráfico se llama marcado (o cargado ). Como marcas se suelen utilizar letras o números enteros.
Definición 7.3. Grafico GRAMO (V , mi ) llamado subgrafo (o parte ) grafico GRAMO(V,mi), Si V V, mi mi. Si V = V, Eso GRAMO llamado subgrafo que abarca GRAMO.
Ejemplo 7 . 1 . Dado un gráfico no dirigido.
Definición 7.4. La gráfica se llama completo , Si cualquier sus dos vértices están conectados por una arista. Gráfico completo con norte los vértices se denotan por k norte .
Cuenta K 2 , A 3, A 4 y k 5 .
Definición 7.5. Grafico GRAMO=GRAMO(V, mi) se llama dicotiledóneo , Si V se puede representar como una unión de conjuntos disjuntos, digamos V=AB, por lo que cada arista tiene la forma ( v i , v j), Dónde v i A Y v j B.
Cada arista conecta un vértice de A con un vértice de B, pero no hay dos vértices de A ni dos vértices de B están conectados.
Un grafo bipartito se llama dicotiledónea completa contar k metro , norte, Si A contiene metro picos, B contiene norte vértices y para cada v i A, v j B tenemos ( v i , v j)mi.
Así, para todos v i A, Y v j B hay un borde que los conecta.
K 12 K 23 K 22 K 33
Ejemplo 7 . 2 . Construya un gráfico bipartito completo k 2.4 y el gráfico completo k 4 .
Gráfico unitarionorte-cubo dimensionalEN norte .
Los vértices del gráfico son conjuntos binarios de n dimensiones. Las aristas conectan vértices que difieren en una coordenada.
Ejemplo: 
INSTITUCIÓN EDUCATIVA AUTÓNOMA MUNICIPAL ESCUELA SECUNDARIA No. 2
Preparado
Legkokonets Vladislav, estudiante de la clase 10A
Uso práctico Teorías de grafos
Supervisor
L. I. Noskova, profesora de matemáticas
Art. Bryukhovetskaya
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
Nació resolviendo acertijos y juegos entretenidos La teoría de grafos se ha convertido ahora en una herramienta sencilla, 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 Relevancia 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 investigación. 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 la investigación. El método gráfico es muy importante y ampliamente utilizado en diversos campos de la ciencia y la actividad humana.
Investigar objetivos:
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 el problema de una isla situada en la ciudad de Königsberg y rodeada por un río que cruzaba siete puentes.
[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 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 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 "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:
"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 conduce a la siguiente solución a esta cuestión. En primer lugar, hay que observar cuántas zonas hay están separados por el agua, tales que no tienen otro camino de uno a otro excepto a través de un puente. en este ejemplo Hay cuatro secciones de este tipo: A, B, C, D. Lo siguiente que hay que distinguir es si el número de puentes que conducen a estos tramos 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 esto por sí solo es suficiente para resolver el problema. Una vez determinado esto, aplicamos 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 iniciar este desvío desde cualquier tramo. Si dos de estos números fueran impares, porque sólo uno no puede ser impar, entonces incluso entonces la transición podría tener lugar, como está prescrito, pero ciertamente sólo se debe tomar el comienzo del circuito de una de esas dos secciones a las que conduce el número impar. 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 por 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 denotaremos el gráfico en su conjunto por uno 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 manera 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 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 con una línea en negrita MF; 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 - Nozdryov, 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. Número formas posibles Los golpes del 1 al 9 son iguales 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. Pruebalo:
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. Numero 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 hablar 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 y automatización. procesos tecnológicos y producción, psicología, publicidad. 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 estudio.
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. once].
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 del 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].
Un ejemplo más. 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.
Del mismo modo, 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 grafico.
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 trató 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. "Antigüedades tareas entretenidas", M. "Ciencia", 1988 (parte 2, sección 8; apéndice 4);
Solicitud
Solicitud
PAG 
Arroz. 6
Arroz. 7
Arroz. 8
solicitudSolicitud
Solicitud
Solicitud
PAG 
Arroz. 14
solicitudSolicitud
De vuelta atras
¡Atención! Las vistas previas de diapositivas tienen únicamente fines informativos y es posible que no representen todas las características de la presentación. Si estás interesado este trabajo, descargue la versión completa.
Objetivos de la lección:
Equipo:
- clase de computación equipada con tecnología moderna, video proyector, pantalla;
- computadoras con sistema operativo Windows XP, Microsoft Office 2003 PowerPoint;
- equipo de la junta directiva (tema de la lección, nuevos términos). Repartir.
Plan de estudios.
II. Presentación de nuevo material. (10 minutos.)
III. Fijación del material. Trabajo practico. (15-20 minutos)
IV. Resumiendo la lección (2 min)
v. Tarea.
I. Momento organizativo. Actualización de conocimientos.
¡Hola! Nuestra lección se llama "Gráficos". Nos familiarizaremos con el concepto de "Gráficos", aprenderemos a representarlos y resolveremos problemas sobre este tema.
II Presentación de nuevo material.
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 fueron los nombres dados a los esquemas que consisten en puntos y segmentos de línea o curvas que conectan estos puntos (se muestran ejemplos de gráficos en la Figura 1).
Con la ayuda de gráficos, a menudo se simplificaba la solución de problemas formulados en diversas áreas del conocimiento: en automatización, electrónica, física, química, etc. Con la ayuda de gráficos, se representan diagramas de carreteras, gasoductos, redes de calor y electricidad. . Los gráficos ayudan a resolver problemas matemáticos y económicos.
Gráfico – (del griego Grapho – escribo) es un medio para representar visualmente los elementos de un objeto y las conexiones entre ellos. Estos son objetos matemáticos maravillosos; con su ayuda puedes resolver muchos problemas diferentes y aparentemente diferentes.
Un gráfico es una especie de modelo de información.
El gráfico consta de vértices o nodos conectados por arcos o segmentos: aristas. Una línea puede estar dirigida, es decir, tener una flecha (arco); si no está dirigida, tiene una arista. Dos vértices conectados por un arco o arista se llaman adyacentes.
Ejemplos de gráficos (Diapositiva 4, 5, 6)
Tarea 1 (Diapositiva 7):
Se ha establecido comunicación espacial entre los nueve planetas del sistema solar. Los cohetes programados vuelan en las siguientes rutas:
Tierra - Mercurio; Plutón - Venus; Tierra - Plutón; Plutón - Mercurio; Mercurio - Venus; Urano - Neptuno; Neptuno - Saturno; Saturno – Júpiter; Júpiter - Marte; Marte - Urano.
¿Es posible volar en cohetes regulares desde la Tierra a Marte?
Solución: Dibujemos un diagrama de la condición: representaremos los planetas como puntos y las rutas de los cohetes como líneas.
Ahora queda inmediatamente claro que es imposible volar de la Tierra a Marte.
Dos vértices conectados por un arco o arista se llaman adyacentes. Cada arista o arco está asociado a un número. El número puede indicar la distancia entre asentamientos, el tiempo de transición de un pico a otro, etc.
Tarea 2 (9 diapositivas): solución en la pizarra. Masha vino al zoológico y quiere ver tantos animales como sea posible. ¿Qué camino debería tomar? ¿Amarillo, rojo, verde?
Tarea 3 (diapositiva 11): solución en la pizarra. Cinco equipos de fútbol A, B, C, D, D deben jugar partidos entre sí. Ya jugué A con B, C, D; B con A, C, D. ¿Cuántos partidos se han jugado ya? ¿Cuanto tiempo queda para jugar?
Presentación de gráficos (Diapositiva 12)
La gráfica se puede presentar como una lista de arcos (AB; 7), gráficamente o mediante una tabla.
| Listas de arcos | forma gráfica | Forma de tabla | ||||||||||||||||
| (AB; 7), |  |
|
III. Materiales de refuerzo: se pide a los estudiantes que se divida en grupos y completen las tareas. Trabajando en un grupo pequeño, los estudiantes discuten modelos basados en los conocimientos teóricos adquiridos al comienzo de la lección. Esto asegura la repetición y consolidación del material.
Tarea 2 (Diapositiva 13)
IV. Resumen de la lección
Chicos, ¿qué palabras nuevas aprendiste hoy? (Gráfico, vértice del gráfico, aristas del gráfico).
¿Qué pueden representar los vértices de la gráfica? (Ciudades; objetos que están; conectados.)
¿Qué significan los bordes del gráfico (trayectos, movimientos, direcciones)?
¿Da un ejemplo de en qué parte de la vida podemos encontrarlos?
¿Cómo se representan los gráficos?
V. Tarea. (Diapositiva 15)
Los gráficos son un tema divertido, gratificante y aterrador. Teoría de grafos: "El horror del estudiante". Los algoritmos gráficos son las mentes asombrosas de las personas que los descubrieron.
¿Qué es una gráfica? Para responder a esta pregunta para mis lectores, describiré el tema de forma un poco diferente.
Un gráfico es un conjunto de objetos.
En la mayoría de los problemas se trata de objetos del mismo tipo. (Muchas ciudades, o muchas casas, o muchas personas, o muchas otras cosas del mismo tipo)
Para resolver problemas con dicho conjunto, es necesario designar cada objeto de este conjunto como algo. Generalmente se acepta llamar a esto precisamente los vértices del gráfico.
Es conveniente describir gráficos y definiciones básicas con imágenes, por lo que se deben incluir imágenes para leer esta página.
Como escribí anteriormente, una gráfica es un conjunto de objetos. Estos objetos suelen ser del mismo tipo. La forma más sencilla de dar un ejemplo es en las ciudades. Cada uno de nosotros sabe qué es una ciudad y qué es una carretera. Cada uno de nosotros sabe que puede haber o no caminos hacia la ciudad. En general, cualquier conjunto de objetos puede caracterizarse como un gráfico.
Si hablamos del gráfico como de ciudades, entonces se pueden construir carreteras entre ciudades, o se pueden destruir en algún lugar, no construir, o la ciudad generalmente está ubicada en una isla, no hay puente y solo las carreteras pavimentadas son de interés. . A pesar de que no existe un camino hacia dicha ciudad, esta ciudad puede incluirse en muchos objetos analizados, y todos los objetos en conjunto forman una colección de objetos o, más simplemente, un gráfico.
Seguramente has leído libros de texto y has visto esta notación G(V,E) o algo similar. Entonces, V es un objeto del conjunto completo de objetos. En nuestro caso, el conjunto de objetos son ciudades, por lo tanto, V es una ciudad específica. Dado que los objetos no son necesariamente ciudades, y la palabra objeto puede resultar confusa, dicho objeto del conjunto se puede llamar punto, punto u otra cosa, pero la mayoría de las veces se le llama vértice del gráfico y se denota con la letra. v.
En programación, esto suele ser una columna o una fila de una matriz bidimensional, donde la matriz se denomina matriz de adyacencia o matriz de incidencia.
En la literatura, en Internet y, en general, dondequiera que se escriba algo sobre gráficos, encontrará conceptos como arcos y aristas. Esta figura muestra los bordes del gráfico. Aquellos. estos son tres bordes E1, E2 y E3.
Un arco y una arista se diferencian en que una arista es una conexión bidireccional. Lo quiso, fue con su vecino, lo quiso, regresó de su vecino. Si no está muy claro, entonces puedes imaginar una casa, un aeródromo, un avión en vuelo y un paracaidista. Un paracaidista puede ir desde su casa al aeródromo, pero cuando llega al aeródromo, recuerda que olvidó su paracaídas de la suerte en casa, luego regresa a casa y toma el paracaídas. — Un camino por el que se puede caminar de un lado a otro se llama borde.
Si un paracaidista está en un avión y está saltando del avión, pero el paracaidista olvidó ponerse su paracaídas de la suerte en el avión, ¿podrá el paracaidista recoger lo que olvidó? Un camino que va en una sola dirección se llama arco. Generalmente decimos que una arista conecta dos vértices y un arco va de un vértice a otro.
En esta figura, la gráfica solo tiene arcos. Los arcos del gráfico están indicados con flechas, porque la dirección accesible es muy clara. Si un gráfico consta únicamente de esos arcos, entonces dicho gráfico se llama dirigido.
 |
A menudo se encontrará con los conceptos de contigüidad e incidencia. En la figura, dos aristas que van a un punto están marcadas en rojo. Estas aristas, como los vértices descritos anteriormente, también se denominan adyacentes. |
No se describe mucho, pero esta información puede ayudar a alguien.