Teoría de Grafos: Definiciones Básicas. Teoría de grafos: conceptos básicos y tareas. Gráficos como una estructura de datos
De manera informal, un gráfico puede verse 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 es el artículo de Euler (1736), que consideró el problema del puente de Köningsberg. Euler demostró que es imposible pasar por alto siete puentes de la ciudad y volver al punto de partida pasando por 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.
Con gráficos, sin darnos cuenta, nos enfrentamos constantemente. Por ejemplo, el gráfico es el esquema de líneas de metro. Los puntos en él representan las estaciones y las líneas representan las rutas de los trenes. Explorando nuestra genealogía y elevándola a un antepasado lejano, construimos el llamado árbol genealógico. Y este árbol es un gráfico.
Los gráficos sirven como un medio conveniente para describir las relaciones entre objetos. Anteriormente hemos usado gráficos como una forma de visualizar relaciones binarias finitas.
Pero el gráfico no se usa de ninguna manera solo como ilustración. Por ejemplo, considerando un gráfico que representa una red de carreteras entre asentamientos, puede determinar la ruta desde el punto A hasta el punto B. Si hay varias rutas de este tipo, nos gustaría elegir la óptima en cierto sentido, por ejemplo, la el más corto o el más seguro. Para resolver el problema de selección, se requiere realizar ciertos cálculos en gráficos. Al resolver este tipo de problemas, es conveniente utilizar técnicas algebraicas, y se debe formalizar el concepto mismo de un gráfico.
Los métodos de teoría de grafos se utilizan ampliamente en matemáticas discretas. Es imposible prescindir de ellos en el análisis y síntesis de varios convertidores discretos: bloques funcionales de computadoras, complejos de software, etc.
Actualmente, la teoría de grafos cubre una gran cantidad de material y se está desarrollando activamente. Al presentarlo, nos restringimos a solo una parte de los resultados y nos enfocamos en la descripción y justificación de algunos algoritmos de análisis de grafos ampliamente utilizados en la teoría de lenguajes formales.
Definiciones basicas
Los gráficos, como ya se ha señalado en los ejemplos, son una forma de "visualizar" los vínculos entre determinados objetos. Estos vínculos pueden ser "dirigidos", como, por ejemplo, en un árbol genealógico, o "no direccionales" (una red de carreteras de doble sentido). De acuerdo con esto, en la teoría de grafos se distinguen dos tipos principales de grafos: dirigidos (o dirigidos) y no dirigidos.
Métodos de presentación
Hasta ahora, hemos definido grafos dirigidos y no dirigidos dibujándolos. Es posible definir un gráfico como un par de conjuntos, siguiendo la definición, pero este método es bastante engorroso y tiene un interés teórico. El desarrollo de enfoques algorítmicos para el análisis de las propiedades de los gráficos requiere otras formas de describir los gráficos que sean más adecuadas para los cálculos prácticos, incluidos los que utilizan computadoras. Considere las tres formas más comunes de representar gráficos.
Árboles
Definición 5.5. Un árbol no dirigido es un grafo no dirigido conexo y acíclico. Definición 5.6. Un árbol dirigido es un gráfico dirigido sin contorno cuyo grado de entrada de cualquier vértice es como máximo 1 y hay exactamente un vértice, llamado raíz del árbol dirigido, cuyo grado de entrada es 0.
Árbol de expansión de menor peso
El siguiente problema se conoce en teoría de grafos como el problema de Steiner: se dan n puntos en el plano; necesita conectarlos con segmentos de línea de tal manera que la longitud total de los segmentos sea la más pequeña.
Métodos para el recorrido sistemático de vértices de grafos
Los problemas importantes de la teoría de grafos son los problemas del análisis global de grafos dirigidos y no dirigidos. Estas tareas incluyen, por ejemplo, las tareas de encontrar ciclos o contornos, calcular las longitudes de caminos entre pares de vértices, enumerar caminos con ciertas propiedades, etc. El análisis global de un grafo debe distinguirse del local, un ejemplo de lo cual es el problema de determinar los conjuntos de predecesores y sucesores de un vértice fijo de un grafo dirigido.
Problema de ruta en grafos dirigidos ponderados
isomorfismo gráfico
Para un gráfico dirigido (V, E), el conjunto E de arcos se puede ver como un gráfico de una relación de accesibilidad directa binaria definida en el conjunto de vértices. En un grafo no dirigido (V, E), el conjunto E de aristas es el conjunto de pares desordenados. Para cada par desordenado (u, v) ∈ E, podemos suponer que los vértices u y v están conectados por una relación binaria simétrica p, es decir, (u, v) ∈ p y (v, u) ∈ p.
clasificación topológica
Definición 5.17. Una red dirigida (o simplemente una red) es un grafo dirigido sin contorno*. Dado que la red es un gráfico sin contorno, se puede demostrar que hay vértices (nodos) de la red con un grado de salida cero, así como vértices (nodos) con un grado de entrada cero. Los primeros se denominan sumideros o salidas de red, y los últimos se denominan fuentes o entradas de red.
Elementos de ciclomática
Al discutir el algoritmo de búsqueda primero en profundidad en un gráfico no dirigido, se consideró la cuestión de encontrar los llamados ciclos fundamentales de un gráfico. Al mismo tiempo, se entendió que un ciclo fundamental era un ciclo que contenía exactamente un borde posterior, y se estableció una correspondencia biunívoca entre los ciclos fundamentales y los bordes posteriores, los ciclos fundamentales surgen cada vez que se realiza una partición arbitraria de todos los bordes de un gráfico no dirigido en árboles (formando un bosque máximo de un solo punto 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 primero en profundidad es solo una de las formas de implementar dicha partición.
La teoría de grafos es una rama de las matemáticas discretas que estudia los objetos representados como elementos separados (vértices) y las conexiones entre ellos (arcos, aristas).
La teoría de grafos se origina a partir de la solución del problema del puente de Königsberg en 1736 por el famoso matemático Leonardo Euler(1707-1783: nació en Suiza, vivió y trabajó en Rusia).
El problema de los puentes de Königsberg.
Hay siete puentes en la ciudad prusiana de Königsberg sobre el río Pregal. ¿Es posible encontrar una ruta a pie que pase exactamente 1 vez por cada uno de los puentes y comience y termine en el mismo lugar?
Un grafo en el que hay una ruta que comienza y termina en el mismo vértice, y que pasa por todas las aristas del grafo exactamente una vez, se llamagráfico de Euler.
La secuencia de vértices (puede repetirse) por los que pasa la ruta deseada, así como la ruta en sí, 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 el plano. Dibuja un camino desde cada casa hasta cada pozo para que los caminos no se crucen. Este problema lo resolvió (se demuestra que no tiene solución) Kuratovsky (1896 - 1979) en 1930.
El problema de los cuatro colores. La división de un plano en regiones que no se cortan se llama tarjeta. Las áreas del mapa se denominan adyacentes si comparten un límite común. El problema es colorear el mapa de tal manera que no haya dos áreas vecinas llenas del mismo color. Desde finales del siglo XIX se conoce la hipótesis de que bastan cuatro colores para ello. La hipótesis no ha sido probada hasta el momento.
La esencia de la solución publicada es enumerar un número grande pero finito (alrededor de 2000) de tipos de posibles contraejemplos del teorema de los cuatro colores y mostrar que ningún caso es un contraejemplo. Esta enumeración fue realizada por el programa en unas mil horas de funcionamiento de la supercomputadora.
Es imposible verificar la solución obtenida "manualmente": la cantidad de enumeración está más allá del alcance de las capacidades humanas. Muchos matemáticos plantean la pregunta: ¿puede una "prueba de software" de este tipo considerarse una prueba válida? Después de todo, puede haber errores en el programa ...
Por lo tanto, queda confiar en las calificaciones de programador de los autores y creer que hicieron todo bien.
Definición 7.1. Contar GRAMO= GRAMO(V, mi) es la colección de dos conjuntos finitos: V - llamados muchos picos y conjuntos E de pares de elementos de V, es decir EÍV´V, llamado muchos bordes, si los pares no están ordenados, 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. Un gráfico 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), eнE, entonces decimos que la arista e conecta vértices v 1 y v 2 .
Dos vértices v 1 ,v 2 se llaman relacionado si hay un borde que los conecta. En esta situación, cada uno de los vértices se llama incidental 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 denotar v, y el número de aristas - 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) un borde de un gráfico no dirigido es un segmento;
3) el arco de un gráfico dirigido es un segmento dirigido.
Definición 7.2. Si en la arista e=(v 1 ,v 2) tiene lugar v 1 =v 2, entonces la arista e se llama círculo. Si se permite que un gráfico tenga bucles, entonces se llama gráfico con bucles o seudógrafo .
Si se permite que un gráfico tenga más de una arista entre dos vértices, entonces se llama multigrafo .
Si cada vértice y (o) borde de la gráfica está etiquetado, entonces dicha gráfica se llama etiquetado (o cargado ). Normalmente se utilizan letras o números enteros como marcas.
Definición 7.3. Grafico GRAMO (V , mi ) llamado subgrafo (o parte ) contar GRAMO(V,mi), Si V V, mi mi. Si V = V, entonces GRAMO llamado subgrafo de expansión GRAMO.
Ejemplo 7 . 1 . Se da un gráfico no dirigido.
Definición 7.4. el conteo se llama completo , Si ningún dos de sus vértices están conectados por una arista. Gráfico completo con norte vértices se denota 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ónea , Si V puede pensarse como la unión de conjuntos disjuntos, digamos V=AB, de manera que cada arista tiene la forma ( v I , v j), donde v I A y v j B.
Cada arista une un vértice de A con un vértice de B, pero no hay dos vértices de A o dos vértices de B conectados.
El 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 cada 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 gráfico completo k 4 .
gráfico de unidadesnorte-cubo dimensionalV norte .
Los vértices del gráfico son conjuntos binarios n-dimensionales. Los bordes conectan vértices que difieren en la misma coordenada.
Ejemplo: 
INSTITUCIÓN EDUCATIVA GENERAL AUTÓNOMA MUNICIPAL ESCUELA EDUCATIVA SECUNDARIA N° 2
Preparado
Legkokonets Vladislav, estudiante de 10A
Uso práctico Teorías de grafos
Supervisor
LI Noskova, profesora de matemáticas
Santa Bryukhovetskaya
2011
1.Introducción……………………………………………………………………………….………….3
2. La historia del surgimiento de la teoría de grafos………………………………………….………..4
3.Definiciones y teoremas básicos de la teoría de grafos……………………………….………6
4. Tareas resueltas con la ayuda de gráficos………………………………..……………………..8
4.1 Tareas famosas……………………………….…………………………...8
4.2 Algunas tareas interesantes……………………………….………………..9
5. Aplicación de gráficos en diversas áreas de la vida de las personas…………………………...11
6. Resolución de problemas………………………………………………………………………………...12
7. Conclusión……………….…………………………………………………………………….13
8. Lista de referencias………….……………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………….
9.Apéndice……………………………………………………………………………….…………15
Introducción
Nacido para resolver acertijos y juegos entretenidos, la teoría de grafos se ha convertido ahora en una herramienta simple, accesible y poderosa para resolver problemas relacionados con una amplia gama de problemas. Los gráficos son literalmente ubicuos. En forma de gráficos, por ejemplo, se pueden interpretar diagramas de carreteras y circuitos eléctricos, mapas geográficos y moléculas de compuestos químicos, conexiones entre personas y grupos de personas. En 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 es impulsado por las demandas de un área 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 flujo de programas, en economía y estadística, química y biología, en teoría de programación. Entonces Relevancia El tema se debe, por un lado, a la popularidad de los gráficos y métodos de investigación relacionados y, por otro lado, a un sistema integral no desarrollado para su implementación.
La solución de muchos problemas de la vida requiere largos cálculos y, a veces, estos cálculos no dan resultado. En esto consiste problema de investigación. Surge la pregunta: ¿es posible encontrar una solución simple, racional, breve y elegante para su solución? ¿Es más fácil resolver problemas si usa gráficos? determinó tema de mi investigacion: "Aplicación práctica de la teoría de grafos"
apuntar la investigación fue con la ayuda de 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 varios campos de la ciencia y la vida humana.
Investigar objetivos:
1. Estudiar la literatura y los recursos de Internet sobre este tema.
2. Comprobar la eficacia del método de grafos en la resolución de problemas prácticos.
3. Haz una conclusión.
Importancia práctica del estudio. es que los resultados sin duda despertarán el interés de muchas personas. ¿Alguno de ustedes no ha tratado de construir un árbol genealógico de su familia? ¿Y cómo hacerlo correctamente? El director de una empresa de transporte probablemente tenga que resolver el problema de un uso más rentable del transporte cuando transporta mercancías desde un destino a varios asentamientos. Cada estudiante se enfrentó a tareas de transfusión lógica. Resulta que se resuelven fácilmente con la ayuda de gráficos.
Los siguientes métodos se utilizan en el trabajo: observación, búsqueda, selección, análisis.
La historia del surgimiento de la teoría de grafos
El matemático Leonhard Euler (1707-1783) es considerado el fundador de la teoría de grafos. La historia del surgimiento de esta teoría se puede rastrear a través de la correspondencia del gran científico. Aquí hay una traducción del texto latino, que está 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 dieron un problema sobre una isla ubicada en la ciudad de Koenigsberg y rodeada por un río, a través del cual se lanzan siete puentes.
[Apéndice Fig.1] La pregunta es si cualquiera puede rodearlos continuamente, pasando solo una vez por cada puente. Y luego me informaron que nadie había podido hacer esto todavía, pero nadie había probado que fuera imposible. Esta cuestión, aunque banal, me pareció sin embargo digna de atención porque ni la geometría, ni el álgebra, ni el arte combinatorio son suficientes para su solución. Después de mucho pensar, encontré una regla fácil, basada en una prueba completamente convincente, con la ayuda de la cual en todos los problemas de este tipo uno puede determinar de inmediato si tal ronda se puede hacer a través de cualquier número y puentes ubicados arbitrariamente o no. Los puentes de Konigsberg se ubican de manera que se pueden representar en la siguiente figura [Apéndice Fig.2], donde A denota una isla, y B , C y D son partes del continente separadas entre sí por brazos de río
En cuanto al método que descubrió para resolver problemas de este tipo, Euler escribió:
"Esta solución, por su naturaleza, parece tener poco que ver con las matemáticas, y no me queda claro por qué debería esperarse esta solución de un matemático y no de cualquier otra persona, ya que esta solución está respaldada únicamente por la razón, y no hay necesidad de involucrar para encontrar esta solución, ninguna ley inherente 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 sortear los puentes de Königsberg pasando solo una vez por cada uno de estos puentes? Para encontrar la respuesta, continuemos con la carta de Euler a Marinoni:
"La pregunta es determinar si es posible sortear todos estos siete puentes, pasando por cada uno solo una vez o no. Mi regla lleva a la siguiente solución a esta pregunta. En primer lugar, debe observar cuántas secciones están separadas por agua - tales, que no tienen otra transición de una a otra, excepto a través de un puente. este ejemplo hay cuatro de esas secciones: A, B, C, D. A continuación, se debe distinguir si 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 al resto, es decir, el número de puentes que conducen a secciones individuales es impar, y este ya es suficiente para resolver el problema. Cuando esto se determina, aplicar siguiente regla: si el número de puentes que conducen a cada tramo individual fuera par, entonces sería posible el bypass en cuestión, y al mismo tiempo sería posible iniciar este bypass desde cualquier tramo. Sin embargo, si dos de estos números fueran impares, ya que solo uno no puede ser impar, entonces incluso entonces podría tener lugar la transición, como está prescrito, pero solo el comienzo del desvío debe tomarse necesariamente de una de esas dos secciones a las que el número impar derivaciones puentes. Si, finalmente, hubiera más de dos tramos a los que conduce un número impar de puentes, entonces tal movimiento es generalmente imposible... si se pudieran citar aquí otros problemas más serios, este método podría ser aún más útil y no debería ser descuidado".
Definiciones básicas y teoremas de la teoría de grafos
La teoría de grafos es una disciplina matemática creada por el esfuerzo de matemáticos, por lo que su presentación incluye las definiciones rigurosas necesarias. Entonces, procedamos a la introducción organizada de los conceptos básicos de esta teoría.
Definición 1. Una gráfica es una colección de un número finito de puntos, llamados vértices de la gráfica, y que conectan por pares algunos de estos vértices de líneas, llamadas aristas o arcos de la gráfica.
Esta definición se puede formular de manera diferente: 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 el futuro, denotaremos los vértices del gráfico en letras latinas A, B, C, D. A veces, el gráfico en su conjunto se denotará por uno letra mayúscula.
Definición 2. Los vértices del grafo que no pertenecen a ninguna arista se llaman aislados.
Definición 3. Un grafo que consta solo de vértices aislados se llama cero - contar .
Notación: O "– un gráfico con vértices y sin bordes
Definición 4. Un grafo 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. Tal gráfico se puede representar como un n-ágono 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 grafo cuyos grados de todos los k vértices son iguales se llama grafo homogéneo de grado k .
Definición 7. El complemento de un grafo dado es un grafo formado por todas las aristas y sus extremos que deben sumarse al grafo original para obtener un grafo completo.
Definición 8. Un gráfico que se puede representar en un plano de tal manera que sus bordes se cortan 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 bordes del gráfico interior se llama su cara.
Los conceptos de gráfico plano y caras de gráficos se utilizan para resolver problemas para colorear "correctamente" varios mapas.
Definición 10. Un camino de A a X es una secuencia de aristas que conducen de A a X tal 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 donde los puntos de inicio y final son los mismos.
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. largo camino , puesto en un bucle , es el número de aristas de este camino.
Definición 14. Dos vértices A y B en un grafo se llaman conectados (desconectados) si existe (no existe) un camino que conduce de A a B en él.
Definición 15. Un grafo se dice 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 grafo conexo que no contiene ciclos.
Un modelo tridimensional de un árbol gráfico 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 grafo desconectado que consta únicamente de árboles se llama bosque.
Definición 18. Un árbol cuyos n vértices están numerados del 1 al n se llama árbol con vértices renumerados.
Entonces, hemos considerado las principales definiciones de la teoría de grafos, sin las cuales sería imposible probar teoremas y, en consecuencia, resolver problemas.
Problemas resueltos usando gráficos
Desafíos famosos
El problema del viajante de comercio
El problema del viajante de comercio es uno de los problemas más famosos de la teoría de la combinatoria. Fue puesto en 1934, y los mejores matemáticos se rompieron los dientes al respecto.
El enunciado del problema es el siguiente.
El viajante de comercio (comerciante ambulante) debe salir de la primera ciudad, visitar las ciudades 2,1,3...n una vez en un orden desconocido y regresar a la primera ciudad. Las distancias entre ciudades son conocidas. ¿En qué orden se deben atravesar las ciudades para que el camino cerrado (recorrido) del viajante de comercio sea el más corto?
Método para resolver el problema del viajante de comercio
Algoritmo codicioso
“vaya a la ciudad más cercana (a la que aún no ha entrado)”.
Este algoritmo se llama “codicioso” porque en los últimos pasos hay que pagar un alto precio por la codicia.
Considere, por ejemplo, la red en la Figura [aplicación fig.3] que representa un rombo estrecho. Deje que el vendedor 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 la codicia, regresando a lo largo de la diagonal larga del rombo. El resultado no es el recorrido más corto, sino el más largo.
El problema de los puentes de Königsberg.
La tarea se formula de la siguiente manera.
La ciudad de Konigsberg se encuentra a orillas del río Pregel y dos islas. Diferentes partes de la ciudad estaban conectadas por siete puentes. Los domingos, la gente del pueblo daba paseos por la ciudad. Pregunta: ¿es posible caminar de tal manera que, habiendo salido de la casa, regrese, pasando exactamente una vez por cada puente?
Los puentes sobre el río Pregel se encuentran como en la imagen.[Apéndice Fig.1].
Considere un gráfico correspondiente al esquema del puente. [anexo fig.2].
Para responder a la pregunta del problema, basta averiguar si el grafo es de Euler. (Al menos un vértice debe tener un número par de puentes). Es imposible, caminando por la ciudad, pasar por todos los puentes una vez y volver.
Varios retos interesantes
1. "Rutas".
Tarea 1
Como recordarán, el cazador de almas muertas Chichikov visitó a terratenientes famosos una vez cada uno. Los visitó en el siguiente orden: Manilov, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Colonel Koshkarev. Se encontró un diagrama en el que Chichikov dibujó la posición relativa de las propiedades y los caminos rurales que los conectan. Determine qué propiedad pertenece a quién, si Chichikov no pasó por ninguna de las carreteras más de una vez [anexo fig.4].
Solución:
De acuerdo con el mapa de carreteras, se puede ver que Chichikov comenzó su viaje con el estado E y terminó con el estado O. Notamos que solo dos caminos conducen a los estados B y C, por lo que Chichikov tuvo que conducir por estos caminos. Vamos a marcarlos con líneas en negrita. Se determinan los tramos de la ruta que pasa por A: AC y AB. Chichikov no viajó por las carreteras AE, AK y AM. Vamos a tacharlos. Marquemos con trazo grueso ED ; tachar DK. Tache MO y MN; marque con una línea en negrita MF ; tachar FO ; marcamos FH, NK y KO con una línea en negrita. Encontremos la única ruta posible bajo la condición dada. Y obtenemos: la finca E - pertenece a Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [aplicación fig.5].
Tarea 2
La figura muestra un mapa de la zona. [anexo fig.6].
Solo puedes moverte en la dirección de las flechas. Cada punto puede ser visitado no más de una vez. ¿De cuántas maneras se puede llegar del punto 1 al punto 9? Qué ruta es la más corta y cuál es la más larga.
Solución:
Secuencialmente, "estratifique" el esquema en un árbol, comenzando desde el vértice 1 [aplicación fig.7]. Consigamos un árbol. Número formas posibles hits de 1 a 9 es igual al número de vértices "colgantes" del árbol (hay 14 de ellos). Obviamente, el camino más corto es 1-5-9; el más largo es 1-2-3-6-5-7-8-9.
2 "Grupos, citas"
Tarea 1
Los participantes del festival de música, habiéndose conocido, intercambiaron sobres con direcciones. Pruebalo:
a) en total se enviaron 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: Sean los participantes del festival 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 tipos que intercambiaron sobres [Apéndice Fig.8]
Solución:
a) el grado de cada vértice A i muestra el número de sobres que el participante A i entregó a sus amigos. Numero total envolventes transferidas N es igual a la suma de los grados de todos los vértices del gráfico N = paso. Un 1+ paso. Un 2++. . . + paso. Y n -1 + paso. Y n , N =2p , donde p es el número de aristas del gráfico, es decir N es par. Por lo tanto, se envió un número par de sobres;
b) en la igualdad N = paso. Un 1+ paso. Un 2++. . . + paso. Y n -1 + paso. Y n la suma de términos impares debe ser par, y esto sólo puede ser si el número de términos impares es par. Y esto significa que el número de participantes que intercambiaron sobres un número impar de veces es par.
Tarea 2
Una vez, Andrei, Boris, Volodya, Dasha y Galya acordaron ir al cine por la noche. Decidieron ponerse de acuerdo en la elección del cine y la sesión por teléfono. También se decidió que si no era posible llamar a alguien, se cancelaría el viaje al cine. Por la noche, no todos se reunieron en el cine y, por lo tanto, la visita al cine fracasó. Al día siguiente, comenzaron 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 llamar y por lo tanto no vino a la reunión?
Solución:
Dibujemos cinco puntos y designémoslos con las letras A, B, C, D, E. Estas son las primeras letras de los nombres. Conectemos esos puntos que corresponden a los nombres de los chicos que se llamaron entre sí.
[aplicación fig.9]
En la imagen se puede ver que cada uno de los muchachos, Andrey, Boris y Volodya, llamó a todos los demás. Es por eso que estos chicos vinieron al cine. Pero Galya y Dasha no se llamaron (los puntos D y D no están conectados por un segmento) y, por lo tanto, de acuerdo con el acuerdo, no fueron al cine.
El uso de gráficos en diversas áreas 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. procesos tecnológicos y producción, psicología, publicidad. Entonces, de todo lo anterior, se sigue irrefutablemente el valor práctico de la teoría de grafos, cuya demostración fue el objetivo de este estudio.
En cualquier campo de la ciencia y la tecnología, te encuentras con gráficos. Los gráficos son maravillosos objetos matemáticos con los que puede resolver problemas matemáticos, económicos y lógicos, varios acertijos y simplificar las condiciones de los problemas de física, química, electrónica, automatización. Es conveniente formular muchos hechos matemáticos 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 ha encontrado cada vez más aplicaciones en temas aplicados. Incluso ha surgido la química informática, un campo relativamente joven de la química basado en la aplicación de la teoría de grafos.
gráficos moleculares, utilizados en estereoquímica y topología estructural, química de grupos, polímeros, etc., son gráficos no dirigidos que muestran la estructura de las moléculas [aplicación 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 moleculares y árboles: [aplicación fig.10] a, b - multigrafos resp. etileno y formaldehído; en-mol. isómeros de pentano (los árboles 4, 5 son isomorfos al árbol 2).
En la estereoquímica de los organismos, lo más a menudo usan árboles moleculares, los árboles principales de los gráficos moleculares, que contienen solo todos los vértices correspondientes a los átomos de C. Los árboles y el establecimiento de su isomorfismo permiten determinar el muelle. estructuras y encuentre el número total de isómeros de alcanos, alquenos y alquinos
Redes de proteínas
Redes de proteínas: grupos de proteínas que interactúan físicamente y que funcionan en una célula de manera conjunta y coordinada, controlando los procesos interconectados que ocurren en el cuerpo. [aplicación fig. once].
Gráfico de 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 y bucles.
Por lo general, 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 solo un antepasado: el objeto designado por él pertenece a una clase de nivel superior. Cualquier vértice del árbol puede generar varios descendientes, vértices correspondientes a clases de nivel inferior.
Para cada par de vértices de árboles, hay un camino único que los conecta. Esta propiedad se utiliza cuando se encuentran todos los antepasados, por ejemplo, en la línea masculina, de cualquier persona cuyo árbol genealógico se presenta en forma de árbol genealógico, que también es un “árbol” en el sentido de la teoría de grafos.
Un ejemplo de mi árbol genealógico. [anexo fig.12].
Un ejemplo más. La figura muestra el árbol genealógico bíblico. [anexo fig.13].
resolución de problemas
1. Tarea de transporte. Que haya una base con materias primas en la ciudad de Krasnodar, que debe plantarse en las ciudades de Krymsk, Temryuk, Slavyansk-on-Kuban y Timashevsk de una sola vez, gastando el menor tiempo y combustible posible y regresando. a Krasnodar.
Solución:
Primero, creemos un gráfico de todas las rutas posibles. [aplicación figura 14], teniendo en cuenta los caminos reales entre estos asentamientos y la distancia entre ellos. Para resolver este problema, necesitamos crear otro gráfico, un árbol [aplicación figura 15].
Para facilitar la solución, denotamos las ciudades con números: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.
Esto resultó en 24 soluciones, pero solo necesitamos las rutas más cortas. De todas las soluciones, solo dos están satisfechas, estas son 350 km.
Del mismo modo, es posible y creo que es necesario calcular el transporte real de una localidad a otra.
Tarea lógica para la transfusión. Hay 8 litros de agua en un balde, y hay dos ollas con una capacidad de 5 y 3 litros. se requiere verter 4 litros de agua en una cacerola de cinco litros y dejar 4 litros en un balde, es decir, vierta agua por igual en un balde y una cacerola grande.
Solución:
La situación en cualquier momento se puede describir con tres números [anexo fig.16].
Como resultado, obtenemos dos soluciones: una en 7 movimientos, la otra en 8 movimientos.
Conclusión
Entonces, para aprender a resolver problemas, debe comprender qué son, cómo están organizados, en qué componentes consisten, cuáles son las herramientas que se utilizan para resolver problemas.
Al resolver problemas prácticos con la ayuda de 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 debe poder analizar y codificar la condición del problema. La segunda etapa es una notación esquemática, que consiste en la representación geométrica de 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 del gráfico. .
Al resolver un problema de transporte o un problema de compilación de un árbol genealógico, llegué a la conclusión de que el método de grafos es ciertamente interesante, hermoso y visual.
Estaba convencido de que los gráficos se utilizan ampliamente en economía, administración y tecnología. La teoría de grafos también se usa en programación, esto no se discutió en este artículo, pero creo que es solo cuestión de tiempo.
En este trabajo científico, se consideran gráficos matemáticos, sus áreas de aplicación, se resuelven varios problemas con la ayuda de gráficos. El conocimiento de los conceptos básicos de la teoría de grafos es necesario en diversas áreas relacionadas con la gestión de la producción y los negocios (por ejemplo, diagrama de red de construcción, cronogramas de entrega de correo). Además, mientras trabajaba en un trabajo científico, dominé trabajar en una computadora en un editor de texto WORD. Así, se cumplen las tareas del trabajo científico.
Entonces, de todo lo anterior, se sigue irrefutablemente el valor práctico de la teoría de grafos, cuya demostración fue el objetivo de este trabajo.
Literatura
Berge K. Teoría de grafos y sus aplicaciones. -M.: III, 1962.
Kemeny J., Snell J., Thompson J. Introducción a las matemáticas finitas. -M.: III, 1963.
mineral o. Gráficos y su aplicación. -M.: Mir, 1965.
Harary F. Teoría de grafos. -M.: Mir, 1973.
Zykov A.A. Teoría de Grafos Finitos. -Novosibirsk: Nauka, 1969.
Berezina L.Yu. Gráficos y su aplicación. -M.: Educación, 1979. -144 p.
"Soros Educational Journal" No. 11 1996 (Artículo "Flat Graphs");
Gardner M. "Ocio matemático", M. "Mir", 1972 (capítulo 35);
Olekhnik S. N., Nesterenko Yu. V., Potapov M. K. "Viejos problemas de entretenimiento", M. "Nauka", 1988 (parte 2, sección 8; apéndice 4);
Apéndice
Apéndice
PAGS 
Arroz. 6
Arroz. 7
Arroz. ocho
SolicitudApéndice
Apéndice
Apéndice
PAGS 
Arroz. 14
SolicitudApéndice
De vuelta atras
¡Atención! La vista previa de la diapositiva es solo para fines informativos y es posible que no represente la extensión total de la presentación. Si estás interesado este trabajo por favor descargue la versión completa.
Objetivos de la lección:
Equipo:
- clase de computación equipada con tecnología moderna, proyector de video, pantalla;
- computadoras con Windows XP, programa Microsoft Office 2003 PowerPoint;
- equipo de pizarra (tema de la lección, nuevos términos). Repartir.
Plan de estudios.
II. Presentación de nuevo material. (10 minutos.)
tercero Fijación del material. Trabajo practico. (15-20 minutos)
IV. Resumen de 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 resolver 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 Denesh Koenig. Los gráficos se denominaron esquemas que consisten en puntos y segmentos de líneas rectas o curvas que conectan estos puntos (en la Figura 1 se muestran ejemplos de gráficos)
Con la ayuda de gráficos, la solución de problemas formulados en varios campos del conocimiento a menudo se simplificó: 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 energía. . Los gráficos ayudan a resolver problemas matemáticos y económicos.
Graph - (del griego grapho - escribo) es un medio de representación visual de los elementos del objeto de las conexiones entre ellos. Estos son objetos matemáticos maravillosos, con su ayuda puede resolver muchos problemas diferentes y aparentemente diferentes.
Un gráfico es un modelo de información.
Un grafo consta de vértices o nodos conectados por arcos o segmentos - aristas. La línea se puede dirigir, es decir, tener una flecha (arco), si no se dirige, un borde. Dos vértices unidos por un arco o arista se llaman adyacentes.
Ejemplos de gráficos (Diapositiva 4, 5, 6)
Tarea 1 (Diapositiva 7):
Se ha establecido una comunicación espacial entre los nueve planetas del sistema solar. Los cohetes regulares 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 de la Tierra a Marte?
Solución: Dibujemos un diagrama de la condición: representaremos los planetas con puntos y las rutas de los cohetes con líneas.
Ahora queda inmediatamente claro que es imposible volar de la Tierra a Marte.
Dos vértices unidos por un arco o arista se llaman adyacentes. Cada arista o arco está asociado con 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 (diapositiva 9): la solución está 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 (11 diapositivas): la solución está en la pizarra. Cinco equipos de fútbol A, B, C, D, E deben jugar partidos entre sí. Ya jugué A con B, C, D; B c A, C, D. ¿Cuántos partidos se han jugado hasta ahora? ¿Cuánto queda por jugar?
Representación gráfica (Diapositiva 12)
El gráfico se puede representar como una lista de arcos (AB; 7), gráficamente o usando una tabla.
| Listas de arcos | forma gráfica | forma de tabla | ||||||||||||||||
| (AB; 7), |  |
|
tercero Consolidación de materiales: se invita a los estudiantes a dividirse en grupos y completar tareas. Trabajando en un grupo pequeño, los estudiantes discuten modelos basados en el conocimiento teórico adquirido al comienzo de la lección. Así se logra la repetición y consolidación del material.
Tarea 2 (Diapositiva 13)
IV. Resumen de la lección
Chicos, ¿qué nuevas palabras aprendieron hoy? (Cuenta, vértice del gráfico, bordes del gráfico).
¿Qué pueden representar los vértices de un gráfico? (Ciudades; objetos que están; conectados.)
¿Qué significan los bordes del gráfico (trayectorias, movimientos, direcciones)
Da un ejemplo de en qué parte de la vida podemos encontrarlos.
¿Cómo se muestran los gráficos?
V. Tarea. (Diapositiva 15)
El tema de los gráficos es un tema interesante, útil e intimidante. Teoría de grafos - "Horror estudiantil". Los algoritmos gráficos son una mente increíble de las personas que los descubrieron.
¿Qué es un gráfico? Para responder a esta pregunta de mis lectores, describiré un poco el tema a mi manera.
Un gráfico es un conjunto de objetos.
En la mayoría de las tareas, estos son objetos del mismo tipo. (Muchas ciudades, o muchas casas, o mucha gente, o muchas otras cosas del mismo tipo)
Para resolver problemas con un conjunto de este tipo, debe designar cada objeto de este conjunto como algo. Es común llamar a este algo los vértices de un 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, un gráfico es un conjunto de objetos. Estos objetos suelen ser del mismo tipo. La forma más fácil de dar un ejemplo es en las ciudades. Cada uno de nosotros sabe lo que es una ciudad y lo que es un camino. Cada uno de nosotros sabe que puede haber o no caminos a la ciudad. En general, cualquier conjunto de objetos se puede caracterizar como un gráfico.
Si hablamos del conteo como ciudades, entonces se pueden colocar caminos entre ciudades, o se pueden destruir en algún lugar, no construir, o la ciudad generalmente está ubicada en una isla, no hay puente, pero solo interesan los caminos pavimentados. A pesar de que no existe un camino a tal ciudad, esta ciudad puede incluirse en un conjunto de objetos analizados, y todos los objetos tomados en conjunto forman un conjunto de objetos o, más simplemente, un gráfico.
Seguramente has leído libros de texto y has visto una notación como 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 determinada ciudad. Dado que los objetos no son necesariamente ciudades, y la palabra objeto puede ser confusa, tal objeto del conjunto se puede llamar punto, punto o cualquier otra cosa, pero con mayor frecuencia se le llama la parte superior 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 tales como arcos y aristas. Esta figura muestra los bordes de un gráfico. Aquellos. estos son tres bordes E1, E2 y E3.
Un arco y un borde difieren en que un borde es una relación bidireccional. Quería, fue a un vecino, quería, regresó de un vecino. Si no está muy claro, entonces puedes imaginar una casa, un aeródromo, un avión volador y un paracaidista. Un paracaidista puede ir desde su casa al aeródromo, pero cuando llegue al aeródromo, recuerde que olvidó su paracaídas de la suerte en casa, luego regrese a casa y tome un paracaídas. - Tal camino, a lo largo del cual puedes caminar de un lado a otro, se llama costilla.
Si el paracaidista está en el avión y 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 solo va en una dirección se llama arco. Se suele decir que una arista une dos vértices y que un arco va de un vértice a otro.
En esta figura, el gráfico solo tiene arcos. Los arcos en el gráfico están indicados por flechas, porque la dirección disponible es muy clara. Si un gráfico consta solo de tales arcos, entonces dicho gráfico se llama dirigido.
 |
A menudo encontrará los conceptos de adyacencia e incendencia. En la figura se marcan en rojo dos aristas que van al mismo punto. Estos bordes, como los vértices descritos anteriormente, también se denominan adyacentes. |
No se describe mucho, pero esta información puede ayudar a alguien.