LengAut_IntroducciónGrafos

Matematicas Dicretas II

Grafos

2021/2022

Facilitador: Saúl Olaf Loaiza Melendez

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

¿Quién soy?

Saúl Olaf Loaiza MeléndezIng. Computación

Estimado alumno(a): A partir de este momento, perteneces oficalmente a la asignatura Lenguajes y Autómatas de la Universidad Politécnica de Tlaxcala, recuerda tener presente el compromiso adquirido, es importante tu constancia, motivación y sentido de responsabilidad para culminar satisfactoriamente el cuatrimestre.

Introducción a la Teoría de Grafos

La Teoría de grafos puede usurse para analizar cualquier situación en la que intervenga un conjunto de elementos en el que varios pares de ellos estén relacionados según una misma propiedad, como puede ser un circuito eléctrico, una red de carreteras, una red de comunicaciones, etc. El origen de la teoría de grafos tiene una clara referencia histórica en el problema de los puentes de Konigsber, resuelto de una manera muy elegante por el matemático suizo Leonhard Euler en 1736.

info

Figura 1. Los siete puentes de Konigsberg

1ra. Situación Grupo de Alumnos

La Maestro de Matemáticas Discreta quiere hacer grupos de 9 alumnos para realizar un proyecto. El primero de estos grupos esta formado por: María, Marta, Segio, Lidia, Irene, Eloy, Alicia, Carlos, Francisco y Guille. Algunos ya eran amigos antes de empezar el curso concretamente Maria es amiga de Sergio, Eloy e Irene, Sergio de Lidia, Alicia, Marta y Guille , Lidia de Sergio y Alicia, Alicia de Lidia, Sergio y Guille, Eloy de Martha, Irene, Carlos y Guille, Carlos de Eloy y Francisco, Guille de Sergio, Alicia, Francisco, Carlos y Eloy y finalmente Franciso de Guille y Carlos. Para que sea más fácil saber en un momento dado quién es amigo de quién, ¿cómo podrías representar la situación gráficamente?

1ra. Situación Grupo de Alumnos

La Maestro de Matemáticas Discreta quiere hacer grupos de 9 alumnos para realizar un proyecto. El primero de estos grupos esta formado por: María, Marta, Segio, Lidia, Irene, Eloy, Alicia, Carlos, Francisco y Guille. Algunos ya eran amigos antes de empezar el curso concretamente Maria es amiga de Sergio, Eloy e Irene, Sergio de Lidia, Alicia, Marta y Guille , Lidia de Sergio y Alicia, Alicia de Lidia, Sergio y Guille, Eloy de Martha, Irene, Carlos y Guille, Carlos de Eloy y Francisco, Guille de Sergio, Alicia, Francisco, Carlos y Eloy y finalmente Franciso de Guille y Carlos. Para que sea más fácil saber en un momento dado quién es amigo de quién, ¿cómo podrías representar la situación gráficamente?

2da. Situación Grupo de Intercambio

Se ofrecen 4 becas de intercambio en México, Argentina, Chile y Colombia a 4 estudiantes, Sergio, Eloy, Alba y Marta. Se les pide que seleccionen un máximo de 3 destinos según sus preferencias. Apuntamos de forma esquemática las opciones elegidas por nuestros alumnos y que ahora se indica: Sergio elige México, Chile y Colombia. Eloy elige Argentina Alba elige México y Colombia Marta solo elige Argentina

3ra. Situación Red de Ordenadores

Estamos diseñando una red de 10 ordenadores los cuáles identificamos con números. Representamos dicha red teneiendo en cuenta que las conexiones a realizar entre ellos son las siguientes:El 1 con el 2El 4 y el 5, El 2 con el 1, 3, 5 y 6El 3 con el 2 y con el 6El 4 con el 1El 5 con el 1,2 y 8El 6 con el 2,5,7 y 9El 7 con el 3, 6 y 9El 8 con el 5,9 y 10El 9 con el 6,7 y 8El 10 con el 8 ¿Cómo lo representaríamos?

4ta. Situación Diseño urbanización

Se está diseñando una pequeña urbanización de adosados. Como innovación han decidido que los cruces de las calles sean pequeñas placitas, lo que da una sensación de amplitud. Uno de los puntos a estudiar es el sentido de la circulación vial en cada uno de los tramos. El concejal de uranismo nos proponen la siguiente opción, donde P significa plaza de la P1 hacia la 2 y la 9, de la P2 hacia la 3, de la P3 hacia la 4 y la 6, de la P4 hacia la 3, de la P5 hacia la 4, de la P6 hacia la 7 y la 5, de la P7 hacia la 2 y la 8 y finalmente de la P9 haica la 2 y la 8. ¿Cómo representariamos un mapa de urbanización?

Definición y representación de grafos

El término gráfo proviene de la expresión graphic notation (notación gráfica), usada por primera vez por Edward Frankland y adoptada posteriormente por Alexander Crum Brown, en 1884, la cuál hacía referencia a la representación gráfica de los enlaces entre los átomos de una molécula. No existe una definición precisa acerca de lo que es un grafo, aunque, de manera intuitiva, siempre se ha trabajado con ellos; por lo tanto, este es el momento preciso para hecerlo. No obstante, cabe señalar que hay dos maneras de definirlo:

Algebraica

Geométrica

Desde el punto de vista geométrico, a la representación gráfica de los elementos de un conjunto y las relaciones binarias sobre estos se les conoce como grafo y consta de

Un grafo G = (V, E, Ø) , es una tripleta que consta de un conjunto V no vacío de los vértices del grafo, un conjunto

Resumen Actividad 1.3

En esta actividad se reforzó la importancia de realizar una gráfica para mejorar la información sobre la relaciones entre grupos, administración de recursos y la mejor visualización de como están conectados o relacionados un elemento contra otro. Una de las princiapales características de un grafo es que se puede dibujar de varias formas. Figura 5. Tres dibujos que representan el mismo grafo. Figuf

Referencias

Ramón Espinoza, A. (2017). Capítulo XVII Grafos dirigidos En Matemáticas Discretas (2da. ed., pp. 429-451). Alfaomega Villalpando Becerra, J. F., & Gacría Sandoval, A.(Eds.). (2014). Capítulo 6, Teoría de grafos. En Matemáticas discretas aplicaciones y ejercicios (1ra ed., pp. 185-233) Grupo Editorial Patria. EPP, S. (2012). Capítulo 10 Grafos y árboles En Matemáticas discretas con aplicaciones (4ta. ed., pp. 625-675). Cengage Learning. Johnsonbaugh R. (2005). Capítulo 8 Teoría de gráficas En Matemáticas discretas (6ta. ed., pp. 318-377). Educación Pearson. Tremblay, J. P. & Manohar. R. (Eds.). (1999). Capítulo 5 Teoría de gráficas En Matemáticas discretas con aplicación a las ciencias de la computación (1ra. ed., pp. 463-488). CECSA Figufds

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

¡Gracias!