Construya una gráfica lo más completa posible. Construcción de gráficas en función de sus características. Problemas de gráficas para reforzar conceptos básicos.

Palabras clave:

• objeto gráfico
• gráficos de computadora
• gráficos rasterizados
• Gráficos vectoriales
• formatos de archivos gráficos

Se denominarán objetos gráficos los dibujos, pinturas, dibujos, fotografías y otras imágenes gráficas.

3.2.1. Áreas de aplicación de los gráficos por ordenador.

Los gráficos por computadora se han convertido en parte de nuestra vida diaria. Aplica:

• para una presentación visual de los resultados de mediciones y observaciones (por ejemplo, datos sobre el cambio climático durante un largo período, sobre la dinámica de las poblaciones animales, sobre el estado ecológico de varias regiones, etc.), los resultados de estudios sociológicos, planificados. indicadores, datos estadísticos, resultados de estudios de ultrasonido en medicina, etc.;
• al desarrollar diseños de interiores y paisajes, diseñar nuevos edificios, dispositivos tecnicos y otros productos;
• en simuladores y juegos de ordenador para simular diversos tipos de situaciones que surgen, por ejemplo, durante el vuelo de un avión o nave espacial, el movimiento de un automóvil, etc.;
• a la hora de crear todo tipo de efectos especiales en la industria cinematográfica;
• al desarrollar moderno interfaces de usuario software y recursos de información de la red;
• para la expresión creativa humana (fotografía digital, pintura digital, animación por computadora, etc.).

En la figura 2 se muestran ejemplos de gráficos por computadora. 3.5.

Arroz. 3.5.
Ejemplos de gráficos por computadora

• http://snowflakes.barkleyus.com/ - utilizando herramientas informáticas puedes "recortar" cualquier copo de nieve;
• http://www.pimptheface.com/create/: puedes crear una cara utilizando una gran biblioteca de labios, ojos, cejas, peinados y otros fragmentos;
• http://www.ikea.com/ms_RU/rooms_ideas/yoth/index.html: intente elegir muebles y materiales de acabado nuevos para su habitación.

3.2.2. Métodos para crear gráficos digitales.

Los objetos gráficos creados o procesados ​​por ordenador se almacenan en soportes informáticos; si es necesario, se pueden imprimir en papel u otros soportes adecuados (película, cartón, tela, etc.).

Llamaremos objetos gráficos digitales a los objetos gráficos en soportes informáticos.

Hay varias formas de obtener objetos gráficos digitales.

1. copiar imágenes terminadas desde una cámara digital, desde dispositivos de memoria externos o "descargarlas" de Internet;
2. introducción de imágenes gráficas existentes en papel mediante un escáner;
3. Creación de nuevos gráficos mediante software.

El principio de funcionamiento del escáner es dividir la imagen disponible en papel en pequeños cuadrados (píxeles), determinar el color de cada píxel y almacenarlo en código binario en la memoria de la computadora.

La calidad de la imagen obtenida como resultado del escaneo depende del tamaño del píxel: cuanto más pequeño sea el píxel, más píxeles se dividirá en la imagen original y más información completa sobre la imagen se transferirá a la computadora.

Los tamaños de píxeles dependen de la resolución del escáner, que generalmente se expresa en ppp (puntos por pulgada - puntos por pulgada 1) y se especifica mediante un par de números (por ejemplo, 600 x 1200 ppp). El primer número es el número de píxeles que el escáner puede extraer en una línea de imagen de 1 pulgada de largo. El segundo número es el número de líneas en las que se puede dividir una franja de imagen de 1 pulgada de alto.

1 Pulgada es una unidad de longitud en el sistema de medidas inglés, igual a 2,54 cm.

Tarea. Se escanea una imagen en color de 10 x 10 cm, la resolución del escáner es de 1200 x 1200 ppp y la profundidad de color es de 24 bits. Cual volumen de información¿Tendrá el archivo gráfico resultante?

Solución. La imagen escaneada mide aproximadamente 4" x 4". Teniendo en cuenta la resolución del escáner, toda la imagen se dividirá en 4 4 1200 1200 píxeles.

Respuesta: aproximadamente 66 MB.

Le recomendamos que vea las animaciones “Escáneres: principios generales de funcionamiento”, “Escáneres: escáner de superficie plana”, publicadas en la Colección Unificada de Recursos Educativos Digitales (http://school-collection.edu.ru/). Estos recursos le ayudarán a comprender mejor cómo funciona el proceso de escaneo. El recurso “Cámara digital” ilustrará cómo se toman fotografías digitales (Fig. 3.6).

Arroz. 3.6.
Escáner de superficie plana y cámara digital.

3.2.3. Gráficos rasterizados y vectoriales

Dependiendo del método de creación. imagen grafica Hay gráficos rasterizados, vectoriales y fractales.

gráficos rasterizados

EN gráficos rasterizados La imagen tiene la forma de una trama: una colección de puntos (píxeles) que forman filas y columnas. Cada píxel puede adoptar cualquier color de una paleta que contiene millones de colores. La precisión del color es la principal ventaja de los gráficos rasterizados. Cuando una imagen rasterizada se guarda en la memoria de la computadora, se almacena información sobre el color de cada píxel incluido en ella.

La calidad de una imagen rasterizada aumenta con la cantidad de píxeles de la imagen y la cantidad de colores de la paleta. Al mismo tiempo, aumenta el volumen de información de toda la imagen. El gran volumen de información es una de las principales desventajas de las imágenes rasterizadas.

La siguiente desventaja de las imágenes rasterizadas está asociada con algunas dificultades a la hora de escalarlas. Así, cuando se reduce una imagen rasterizada, varios píxeles vecinos se convierten en uno, lo que provoca una pérdida de claridad en los pequeños detalles de la imagen. Cuando se amplía una imagen rasterizada, se le agregan nuevos píxeles, mientras que los píxeles vecinos adquieren el mismo color y se produce un efecto de paso (Fig. 3.7).

Arroz. 3.7.
Imagen rasterizada y su fragmento ampliado.

Los gráficos rasterizados rara vez se crean a mano. La mayoría de las veces se obtienen escaneando ilustraciones o fotografías preparadas por artistas; Recientemente, las cámaras digitales se han utilizado ampliamente para introducir imágenes rasterizadas en una computadora.

Gráficos vectoriales

Muchas imágenes gráficas se pueden presentar como una colección de segmentos, círculos, arcos, rectángulos y otras formas geométricas. Por ejemplo, la imagen de la Fig. 3.8 consta de círculos, segmentos y un rectángulo.

Arroz. 3.8.
Una imagen hecha de círculos, segmentos y un rectángulo.

Cada una de estas figuras se puede describir matemáticamente: segmentos y rectángulos, según las coordenadas de sus vértices, círculos, según las coordenadas de sus centros y radios. Además, puedes establecer el grosor y el color de las líneas, el color de relleno y otras propiedades de las formas geométricas. EN gráficos vectoriales las imágenes se forman sobre la base de conjuntos de datos (vectores) que describen objetos gráficos y fórmulas para su construcción. Al guardar una imagen vectorial, se ingresa en la memoria de la computadora información sobre los objetos geométricos más simples que la componen.

Los volúmenes de información de las imágenes vectoriales son significativamente menores que los volúmenes de información de las imágenes rasterizadas. Por ejemplo, para representar un círculo utilizando gráficos rasterizados, necesita información sobre todos los píxeles del área cuadrada en la que está inscrito el círculo; Para representar un círculo usando gráficos vectoriales, sólo se requieren las coordenadas de un punto (el centro) y el radio.

Otra ventaja de las imágenes vectoriales es la posibilidad de escalarlas sin perder calidad (Fig. 3.9). Esto se debe al hecho de que con cada transformación de un objeto vectorial, se elimina la imagen anterior y, en su lugar, se construye una nueva utilizando fórmulas existentes, pero teniendo en cuenta los datos modificados.

Arroz. 3.9.
Una imagen vectorial, su fragmento convertido y las formas geométricas más simples a partir de las cuales se “ensambla” este fragmento.

Al mismo tiempo, no todas las imágenes pueden representarse como una colección de formas geométricas simples. Este método de presentación es bueno para dibujos, diagramas, gráficos comerciales y otros casos en los que mantener contornos claros y nítidos de las imágenes es de particular importancia.

Los gráficos fractales, al igual que los gráficos vectoriales, se basan en cálculos matemáticos. Pero, a diferencia de los gráficos vectoriales, la memoria de la computadora no almacena descripciones de las formas geométricas que forman la imagen, sino la fórmula matemática (ecuación) en sí, que se utiliza para construir la imagen. Las imágenes fractales son variadas y extrañas (Fig. 3.10).

Arroz. 3.10.
gráficos fractales

Puede encontrar información más completa sobre este tema en Internet (por ejemplo, en http://ru.wikipedia.org/wiki/Fractal).

3.2.4. Formatos de archivos gráficos

Un formato de archivo de gráficos es una forma de representar datos gráficos en medios externos. Hay trama y formatos vectoriales archivos gráficos, entre los que, a su vez, se encuentran los formatos gráficos universales y los formatos propietarios (originales) de aplicaciones gráficas.

Los formatos gráficos universales son "comprendidos" por todas las aplicaciones que trabajan con gráficos rasterizados (vectoriales).

El formato universal de gráficos rasterizados es el formato BMP. Los archivos gráficos en este formato tienen un gran volumen de información, ya que asignan 24 bits para almacenar información sobre el color de cada píxel.

Los dibujos guardados en el formato universal de mapa de bits GIF sólo pueden utilizar 256 colores diferentes. Esta paleta es adecuada para ilustraciones y pictogramas sencillos. Los archivos gráficos de este formato tienen un pequeño volumen de información. Esto es especialmente importante para los gráficos utilizados en World Wide Web, cuyos usuarios quieren que la información que solicitaron aparezca en pantalla lo más rápido posible.

El formato rasterizado universal JPEG está diseñado específicamente para un almacenamiento eficiente de imágenes. calidad fotográfica. Computadoras modernas Proporcionan reproducción de más de 16 millones de colores, la mayoría de los cuales son simplemente indistinguibles para el ojo humano. formato JPEG le permite descartar la variedad de colores de los píxeles vecinos que son "excesivos" para la percepción humana. Parte de la información original se pierde, pero esto asegura una reducción en el volumen de información (compresión) del archivo gráfico. El usuario tiene la oportunidad de determinar el grado de compresión del archivo. Si la imagen que se guarda es una fotografía que se supone debe imprimirse en una hoja de gran formato, entonces la pérdida de información no es deseable. Si esta fotografía se publica en una página web, se puede comprimir de forma segura decenas de veces: la información restante será suficiente para reproducir la imagen en la pantalla del monitor.

Los formatos de gráficos vectoriales universales incluyen el formato WMF, utilizado para almacenar una colección de imágenes de Microsoft (http://office.microsoft.com/ru-ru/clipart).

El formato EPS universal le permite almacenar información sobre gráficos rasterizados y vectoriales. A menudo se utiliza para importar 2 archivos a programas de impresión.

2 El proceso de abrir un archivo en un programa en el que no fue creado.

Te familiarizarás con tus propios formatos directamente en el proceso de trabajar con aplicaciones graficas. Ellos proveen mejor relación calidad de imagen y volumen de información del archivo, pero son compatibles (es decir, reconocidos y reproducidos) solo por la propia aplicación que crea el archivo.

Problema 1. Para codificar un píxel, se utilizan 3 bytes. La foto, que mide 2048 x 1536 píxeles, se guardó como un archivo sin comprimir. Determine el tamaño del archivo resultante.

Solución.

Respuesta: 9 MB.

Problema 2. Una imagen de mapa de bits sin comprimir de 128 x 128 píxeles ocupa 2 KB de memoria. ¿Cuál es el número máximo posible de colores en la paleta de imágenes?

Solución.

Respuesta: 2 colores: blanco y negro.

El más importante

La infografía es un concepto amplio que se refiere a: 1) diferentes tipos de objetos gráficos creados o procesados ​​utilizando computadoras; 2) un área de actividad en la que las computadoras se utilizan como herramientas para la creación y procesamiento de objetos gráficos.

Dependiendo del método de creación de una imagen gráfica, se distinguen gráficos rasterizados y vectoriales.

En los gráficos rasterizados, una imagen se forma en forma de rasterizado: una colección de puntos (píxeles) que forman filas y columnas. Cuando una imagen rasterizada se guarda en la memoria de la computadora, se almacena información sobre el color de cada píxel incluido en ella.

En los gráficos vectoriales, las imágenes se forman a partir de conjuntos de datos (vectores) que describen un objeto gráfico particular y fórmulas para su construcción. Al guardar una imagen vectorial, se ingresa en la memoria de la computadora información sobre los objetos geométricos más simples que la componen.

Un formato de archivo de gráficos es una forma de representar datos gráficos en medios externos. Existen formatos rasterizados y vectoriales de archivos gráficos, entre los que, a su vez, se encuentran formatos gráficos universales y formatos propietarios de aplicaciones gráficas.

Preguntas y tareas

1. ¿Qué son los gráficos por computadora?
2. Enumere las principales áreas de aplicación de la infografía.
3. ¿Cómo se pueden producir gráficos digitales?
4. Se escanea una imagen en color de 10 x 15 cm, la resolución del escáner es de 600 x 600 ppp y la profundidad de color es de 3 bytes. ¿Qué volumen de información tendrá el archivo gráfico resultante?
5. ¿Cuál es la diferencia entre los métodos rasterizados y vectoriales para representar una imagen?
6. ¿Por qué se cree que las imágenes rasterizadas transmiten el color con mucha precisión?
7. ¿Qué operación de conversión de una imagen rasterizada provoca la mayor pérdida de calidad: reducción o ampliación? como puedes explicar esto?
8. ¿Por qué el escalado no afecta la calidad de las imágenes vectoriales?
9. ¿Cómo se puede explicar la variedad de formatos de archivos gráficos?
10. ¿Cuál es la principal diferencia entre los formatos de gráficos universales y los formatos de aplicaciones de gráficos propietarios?
11. Construya un gráfico lo más completo posible para los conceptos de la sección 3.2.4.
12. Dé una descripción detallada de las imágenes rasterizadas y vectoriales, indicando lo siguiente:

    a) a partir de qué elementos se construye la imagen;

    b) qué información sobre la imagen se almacena en la memoria externa;

    c) cómo se determina el tamaño de un archivo que contiene una imagen gráfica;

    d) cómo cambia la calidad de la imagen al escalar;

    e) cuáles son las principales ventajas y desventajas de las imágenes rasterizadas (vectoriales).

13. El dibujo de 1024 x 512 píxeles se guardó como un archivo sin comprimir de 1,5 MB. ¿Cuánta información se utilizó para codificar el color del píxel? ¿Cuál es el número máximo posible de colores en una paleta correspondiente a esta profundidad de color?
14. Una imagen de mapa de bits sin comprimir de 256 x 128 píxeles ocupa 16 KB de memoria. ¿Cuál es el número máximo posible de colores en la paleta de imágenes?

Formato de archivo de gráficos es una forma de representar datos gráficos en medios externos. Distinguir formatos rasterizados y vectoriales archivos gráficos, entre los que, a su vez, se encuentran formatos gráficos universales Y Formatos propios (originales) de aplicaciones gráficas..

Los formatos gráficos universales son "comprendidos" por todas las aplicaciones que trabajan con gráficos rasterizados (vectoriales).

El formato universal de gráficos rasterizados es formato BMP. Los archivos gráficos en este formato tienen un gran volumen de información, ya que asignan 24 bits para almacenar información sobre el color de cada píxel.

En dibujos guardados en un mapa de bits universal formato gif, sólo puedes utilizar 256 colores diferentes. Esta paleta es adecuada para ilustraciones y pictogramas sencillos. Los archivos gráficos de este formato tienen un pequeño volumen de información. Esto es especialmente importante para los gráficos utilizados en la World Wide Web, donde los usuarios quieren que la información que solicitan aparezca en la pantalla lo más rápido posible.

Ráster universal formato JPEG Diseñado específicamente para el almacenamiento eficiente de imágenes de calidad fotográfica. Las computadoras modernas pueden reproducir más de 16 millones de colores, la mayoría de los cuales son simplemente indistinguibles para el ojo humano. El formato JPEG permite descartar la variedad de colores de los píxeles vecinos que son "excesos" para la percepción humana. Parte de la información original se pierde, pero esto asegura una reducción en el volumen de información (compresión) del archivo gráfico. El usuario tiene la oportunidad de determinar el grado de compresión del archivo. Si la imagen que se guarda es una fotografía que se supone debe imprimirse en una hoja de gran formato, entonces la pérdida de información no es deseable. Si esta foto se coloca en una página web, se puede comprimir de forma segura decenas de veces: la información restante será suficiente para reproducir la imagen en la pantalla del monitor.

Los formatos de gráficos vectoriales universales incluyen formato WMF, utilizado para almacenar una colección de imágenes de Microsoft.

Universal formato EPS le permite almacenar información sobre gráficos rasterizados y vectoriales. A menudo se utiliza para importar archivos a programas de producción impresa.

Se familiarizará con sus propios formatos directamente en el proceso de trabajo con aplicaciones gráficas. Proporcionan la mejor relación entre calidad de imagen y volumen de información del archivo, pero solo son compatibles (es decir, reconocidos y reproducidos) por la propia aplicación que crea el archivo.

Tarea 1.
Para codificar un píxel, se utilizan 3 bytes. La foto, que mide 2048 x 1536 píxeles, se guardó como un archivo sin comprimir. Determine el tamaño del archivo resultante.

Solución:
yo = 3 bytes
k= 2048 1536
I - ?

Yo=K yo
I = 2048 1536 3 = 2 2 10 1,5 2 10 3 = 9 2 20 (bytes) = 9 (MB).

Respuesta: 9 MB.

Tarea 2.
Una imagen de mapa de bits sin comprimir de 128 x 128 píxeles ocupa 2 KB de memoria. ¿Cuál es el número máximo posible de colores en la paleta de imágenes?

Solución:
k = 128 128
Yo = 2 KB
N-?

Yo=K yo
i=I/K
norte=2i
i = (2 1024 8)/(128 128) = (2 2 10 2 3) /(2 7 2 7) = 2 1+10+3 /2 7+7 = 2 14 /2 14 = 1 (bit) .
norte = 2 1 = 2.

Respuesta: 2 colores: blanco y negro.

El más importante:

• Un formato de archivo de gráficos es una forma de representar datos gráficos en medios externos. Existen formatos rasterizados y vectoriales de archivos gráficos, entre los que, a su vez, se encuentran formatos gráficos universales y formatos propietarios de aplicaciones gráficas.

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ónea , Si V se puede representar como una unión de conjuntos disjuntos, digamos V=AB, 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:

Es aconsejable introducir el concepto de gráfico después de haber analizado varios problemas similares al Problema 1, cuya consideración decisiva es la representación gráfica. Es importante que los estudiantes se den cuenta inmediatamente de que se puede dibujar la misma gráfica diferentes caminos. En mi opinión, no es necesario dar una definición estricta de gráfico, porque es demasiado engorroso y sólo complicará el debate. Al principio bastará con un concepto intuitivo. Cuando se analiza el concepto de isomorfismo, puedes resolver varios ejercicios para identificar gráficas isomorfas y no isomorfas. Uno de los puntos centrales del tema es el teorema de la paridad del número de vértices impares. Es importante que los estudiantes comprendan completamente su demostración y aprendan a aplicarla a la resolución de problemas. Al analizar varios problemas, recomiendo no hacer referencia al teorema, sino repetir su demostración. El concepto de conectividad gráfica también es extremadamente importante. Una consideración significativa aquí es la consideración del componente de conectividad; a esto se debe prestar especial atención. Los gráficos de Euler son casi un tema de juego.

El primer y principal objetivo que se debe perseguir al estudiar gráficas es enseñar a los escolares a ver la gráfica en el planteamiento del problema y a traducir correctamente la condición al lenguaje de la teoría de grafos. No deberías contárselo a todo el mundo en varias clases seguidas. Es mejor distribuir las clases en 2 o 3 años académicos. (Se adjunta desarrollo de la lección “El concepto de gráfica. Aplicación de gráficas a la resolución de problemas” de 6to grado).

2. Material teórico para el tema “Gráficos”.

Introducción

Los gráficos son objetos matemáticos maravillosos; con su ayuda puedes resolver muchos problemas diferentes y aparentemente diferentes. Hay una sección completa en matemáticas: teoría de grafos, que estudia los gráficos, sus propiedades y aplicaciones. Discutiremos solo los conceptos más básicos, las propiedades de las gráficas y algunas formas de resolver problemas.

Concepto de gráfico

Consideremos dos problemas.

Tarea 1. Se ha establecido 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 - Viena; Urano - Neptuno; Neptuno - Saturno; Saturno – Júpiter; Júpiter - Marte y 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.

Tarea 2. El tablero tiene forma de doble cruz, que se obtiene quitando los cuadrados de las esquinas de un cuadrado de 4x4.

¿Es posible evitarlo moviendo un caballo de ajedrez y regresar a la casilla original, visitando todas las casillas exactamente una vez?

Solución: Numeremos los cuadrados del tablero secuencialmente:

Y ahora, usando la figura, mostraremos que es posible atravesar la tabla como se indica en la condición:

Consideramos dos problemas diferentes. Sin embargo, las soluciones a estos dos problemas están unidas por una idea común: una representación gráfica de la solución. Al mismo tiempo, los dibujos dibujados para cada tarea resultaron ser similares: cada dibujo consta de varios puntos, algunos de los cuales están conectados por líneas.

Estas imágenes se llaman graficos. Los puntos se llaman picos, y las líneas – costillas grafico. Tenga en cuenta que no todas las imágenes de este tipo se denominarán gráficos. Por ejemplo. Si te piden que dibujes un pentágono en tu cuaderno, ese dibujo no será un gráfico. A un dibujo de este tipo, como en los problemas anteriores, lo llamaremos gráfico si existe alguna tarea específica para la cual se construyó dicho dibujo.

Otra nota se refiere al aspecto del gráfico. Intente comprobar que la gráfica para el mismo problema se puede dibujar de diferentes maneras; y viceversa, para diferentes tareas puedes dibujar gráficos de la misma apariencia. Lo único que importa aquí es qué vértices están conectados entre sí y cuáles no. Por ejemplo, el gráfico de la tarea 1 se puede dibujar de otra manera:

Estos gráficos idénticos, pero dibujados de manera diferente, se denominan isomórfico.

Grados de vértices y conteo del número de aristas de un gráfico.

Anotemos una definición más: el grado de un vértice en un gráfico es el número de aristas que emergen de él. En este sentido, un vértice de grado par se denomina vértice par, respectivamente, un vértice de grado impar se denomina vértice impar.

Uno de los principales teoremas de la teoría de grafos está relacionado con el concepto de grado de vértice: el teorema sobre la equidad del número de vértices impares. Lo demostraremos un poco más tarde, pero primero, a modo de ilustración, consideraremos el problema.

Tarea 3. En la ciudad de Malenky hay 15 teléfonos. ¿Es posible conectarlos con cables para que cada teléfono esté conectado exactamente a otros cinco?

Solución: Supongamos que tal conexión entre teléfonos es posible. Luego imagina un gráfico en el que los vértices representan teléfonos y los bordes representan los cables que los conectan. Contemos cuántos cables hay en total. Cada teléfono tiene exactamente 5 cables conectados, es decir. el grado de cada vértice de nuestra gráfica es 5. Para encontrar el número de cables, debe sumar los grados de todos los vértices del gráfico y dividir el resultado resultante entre 2 (dado que cada cable tiene dos extremos, al sumar los grados, cada cable se tomará 2 veces) . Pero entonces la cantidad de cables será diferente. Pero este número no es un número entero. Esto significa que nuestra suposición de que cada teléfono se puede conectar exactamente a otros cinco resultó ser incorrecta.

Respuesta. Es imposible conectar teléfonos de esta manera.

Teorema: Cualquier gráfico contiene un número par de vértices impares.

Prueba: El número de aristas de un gráfico es igual a la mitad de la suma de los grados de sus vértices. Dado que el número de aristas debe ser un número entero, la suma de los grados de los vértices debe ser par. Y esto sólo es posible si el gráfico contiene un número par de vértices impares.

Conectividad gráfica

Hay otro concepto importante relacionado con los gráficos: el concepto de conectividad.

La gráfica se llama coherente, si dos de sus vértices se pueden conectar por, aquellos. secuencia continua de aristas. Existen una serie de problemas cuya solución se basa en el concepto de conectividad de grafos.

Tarea 4. Hay 15 ciudades en el país de Seven, cada ciudad está conectada por carreteras con al menos otras siete. Demuestra que está de moda llegar de cada ciudad a cualquier otra.

Prueba: Considere dos ciudades arbitrarias A y B y suponga que no hay ningún camino entre ellas. Cada una de ellas está conectada por carreteras con al menos otras siete, y no hay ninguna ciudad que esté conectada con ambas ciudades en cuestión (de lo contrario habría un camino de A a B). Dibujemos una parte del gráfico correspondiente a estas ciudades:

Ahora se ve claramente que hemos recibido al menos 16 ciudades diferentes, lo que contradice las condiciones del problema. Esto significa que la afirmación ha sido probada por contradicción.

Si tomamos en cuenta la definición anterior, entonces el planteamiento del problema se puede reformular de otra manera: “Demuestre que el mapa de carreteras del país Siete está conectado”.

Ahora sabes cómo se ve un gráfico conectado. Un gráfico desconectado tiene la forma de varias "piezas", cada una de las cuales es un vértice separado sin aristas o un gráfico conectado. Puedes ver un ejemplo de un gráfico desconectado en la figura:

Cada una de estas piezas individuales se llama componente conectado del gráfico. Cada componente conexo representa un gráfico conexo y todas las afirmaciones que hemos demostrado para los gráficos conexos son válidas para él. Veamos un ejemplo de un problema que utiliza un componente conectado:

Problema 5. En el Reino Muy Muy Lejano sólo hay un tipo de transporte: una alfombra voladora. Hay 21 líneas de alfombras que salen de la capital, una desde la ciudad de Dalniy y 20 desde todas las demás ciudades. Demuestre que puede volar desde la capital hasta la ciudad de Dalniy.

Prueba: Está claro que si dibujas un gráfico de la alfombra del Reino, puede resultar incoherente. Veamos el componente de conectividad que incluye la capital del Reino. Hay 21 alfombras que salen de la capital y 20 de cualquier otra ciudad excepto la ciudad de Dalniy, por lo tanto, para que se cumpla la ley sobre un número par de vértices impares, es necesario que se incluya la ciudad de Dalniy. en el mismo componente de conectividad. Y como el componente conexo es un gráfico conexo, desde la capital hay un camino a lo largo de las alfombras hasta la ciudad de Dalniy, que era lo que había que demostrar.

Gráficos de Euler

Probablemente te hayas encontrado con tareas en las que necesitas dibujar una forma sin levantar el lápiz del papel y dibujar cada línea solo una vez. Resulta que tal problema no siempre tiene solución, es decir. Hay figuras que no se pueden dibujar con este método. La cuestión de la solucion de tales problemas también se incluye en la teoría de grafos. Fue explorado por primera vez en 1736 por el gran matemático alemán Leonhard Euler, resolviendo el problema de los puentes de Königsberg. Por lo tanto, las gráficas que se pueden dibujar de esta manera se llaman gráficas de Euler.

Tarea 6. ¿Es posible dibujar la gráfica que se muestra en la figura sin levantar el lápiz del papel y dibujar cada borde exactamente una vez?

Solución. Si dibujamos la gráfica como se indica en la condición, entonces entraremos en cada vértice, excepto el inicial y el final, el mismo número de veces que salimos de él. Es decir, todos los vértices del gráfico, excepto dos, deben ser pares. Nuestro gráfico tiene tres vértices impares, por lo que no se puede dibujar de la forma especificada en la condición.

Ahora hemos demostrado el teorema sobre las gráficas de Euler:

Teorema: Un gráfico de Euler debe tener como máximo dos vértices impares.

Y para terminar, el problema de los puentes de Königsberg.

Tarea 7. La figura muestra un diagrama de puentes en la ciudad de Königsberg.

¿Es posible dar un paseo para cruzar cada puente exactamente una vez?

3. Problemas del tema “Gráficos”

El concepto de gráfico.

1. En un tablero cuadrado de 3x3, se colocan 4 caballeros como se muestra en la Fig. 1. ¿Es posible, después de realizar varios movimientos con los caballos, reorganizarlos a la posición que se muestra en la Fig. 2?

Arroz. 1

Arroz. 2

Solución. Numeremos los cuadrados del tablero como se muestra en la figura:

Asignemos un punto en el plano a cada celda, y si se puede llegar a una celda moviendo un caballo de ajedrez desde una celda, conectaremos los puntos correspondientes con una línea. La colocación inicial y requerida de los caballeros se muestra en las figuras:

Para cualquier secuencia de movimientos de caballero, su orden obviamente no puede cambiar. Por tanto, es imposible reorganizar los caballos de la manera requerida.

2. En el país de Digit hay 9 ciudades con nombres 1, 2, 3, 4, 5, 6, 7, 8, 9. Un viajero descubrió que dos ciudades están conectadas por una aerolínea si y solo si los dos dígitos número formado por los nombres de las ciudades, dividido por 3. ¿Es posible volar en avión desde la ciudad 1 a la ciudad 9?

Solución. Al asignar un punto a cada ciudad y conectar los puntos con una línea, si la suma de los números es divisible por 3, obtenemos una gráfica en la que los números 3, 5, 9 están conectados entre sí, pero no conectados al descansar. Esto significa que no puedes volar de la ciudad 1 a la ciudad 9.

Grados de vértices y conteo del número de aristas.

3. Hay 100 ciudades en un estado y cada ciudad tiene 4 carreteras. ¿Cuántas carreteras hay en el estado?

Solución. Contamos el número total de carreteras que salen de la ciudad: 100. . 4 = 400. Sin embargo, con este cálculo, cada camino se cuenta 2 veces: sale de una ciudad y entra en otra. Esto significa que en total hay dos veces menos carreteras, es decir, 200.

4. Hay 30 personas en la clase. ¿Será que 9 personas tienen 3 amigos, 11 tienen 4 amigos y 10 tienen 5 amigos?

Respuesta. No (teorema de la paridad del número de vértices impares).

5. El rey tiene 19 vasallos. ¿Será que cada vasallo tiene 1, 5 o 9 vecinos?

Respuesta. No, no puede.

6. ¿Puede un estado en el que salen exactamente 3 carreteras de cada ciudad tener exactamente 100 carreteras?

Solución. Contemos el número de ciudades. El número de caminos es igual al número de ciudades x multiplicado por 3 (el número de caminos que salen de cada ciudad) y dividido por 2 (ver problema 3). Entonces 100 = 3x/2 => 3x = 200, lo que no puede suceder con x natural. Esto significa que no puede haber 100 carreteras en ese estado.

7. Demuestre que el número de personas que alguna vez vivieron en la Tierra y dieron un número impar de apretones de manos es par.

La prueba se deriva directamente del teorema sobre la paridad del número de vértices impares en un gráfico.

Conectividad.

8. En el país salen 100 carreteras de cada ciudad y de cada ciudad se puede llegar a cualquier otra. Una carretera estaba cerrada por reparaciones. Demuestra que ahora puedes llegar de cualquier ciudad a cualquier otra.

Prueba. Consideremos el componente de conectividad, que incluye una de las ciudades cuya carretera estaba cerrada. Según el teorema de la paridad del número de vértices impares, también incluye la segunda ciudad. Esto significa que aún puedes encontrar una ruta y llegar de una de estas ciudades a otra.

Graficas de Euler.

9. Hay un grupo de islas conectadas por puentes para que desde cada isla se pueda llegar a cualquier otra. El turista recorrió todas las islas, cruzando cada puente una vez. Visitó Threefold Island tres veces. ¿Cuántos puentes salen de Troyekratnoye si eres un turista?

a) ¿no empezó con eso y no terminó con eso?
b) ¿empezó con ello, pero no terminó?
c) ¿comenzó con eso y terminó con eso?

10. La imagen muestra un parque dividido en varias partes por vallas. ¿Es posible caminar por el parque y sus alrededores para poder saltar cada valla una vez?

Gráfico nulo y gráfico completo.

Hay algunas gráficas especiales que aparecen en muchas aplicaciones de la teoría de grafos. Por ahora, consideraremos nuevamente el gráfico como un diagrama visual que ilustra el curso de las competiciones deportivas. Antes del inicio de la temporada, aunque aún no se han jugado partidos, no hay aristas en el gráfico. Un gráfico de este tipo consta únicamente de vértices aislados, es decir de vértices conectados sin aristas. A un gráfico de este tipo lo llamaremos gráfico nulo. En la Fig. 3 muestra dichos gráficos para casos en los que el número de comandos, o vértices, es 1, 2, 3, 4 y 5. Estos gráficos nulos generalmente se indican con los símbolos O1, O2, O3, etc., por lo que On es un valor nulo. Grafo con n vértices y sin aristas.

Consideremos otro caso extremo. Supongamos que al final de la temporada, cada equipo juega un partido contra cada uno de los demás equipos. Luego, en el gráfico correspondiente, cada par de vértices estará conectado por una arista. Tal gráfico se llama grafico completo. La Figura 4 muestra gráficas completas con el número de vértices n = 1, 2, 3, 4, 5. Denotamos estas gráficas completas por U1, U2, U3, U4 y U5, respectivamente, de modo que la gráfica Un consta de 11 vértices y aristas, conectando todos los pares posibles de estos vértices. Esta gráfica se puede considerar como un n-gón en el que se dibujan todas las diagonales.

Teniendo algún gráfico, por ejemplo el gráfico G que se muestra en la Fig. 1, siempre podemos convertirlo en un gráfico completo con los mismos vértices sumando las aristas que faltan (es decir, aristas correspondientes a juegos que aún están por jugarse). En la Fig. 5 hicimos esto para el gráfico de la Fig. 1 (los juegos que aún no se han jugado se muestran en líneas de puntos). También puedes dibujar por separado un gráfico correspondiente a juegos futuros que aún no se han jugado. Para el gráfico G esto dará como resultado el gráfico que se muestra en la Fig. 6.

A este nuevo gráfico lo llamamos complemento del gráfico G; Se acostumbra denominarlo G1. Tomando el complemento del gráfico G1, obtenemos nuevamente el gráfico G. Las aristas de ambos gráficos G1 y G juntas forman un gráfico completo.