Exploración matemática
Tema: Teoría de los grafos
Pregunta de investigación: ¿Cuáles son los diferentes
tipos de grafos y qué características los distinguen
Alumna: Camila Cueva Suárez
III DE SECUNDARIA
Gamma
Profesor: Luis Alberto Flores del Carpio
Arequipa, Abril del 2024
La teoría de grafos es una rama fundamental en las matemáticas y la ciencia de la
computación que se encarga del estudio de las relaciones entre objetos,
representándolos mediante estructuras llamadas grafos. Un grafo se compone de
nodos (también conocidos como vértices) y aristas (también llamadas arcos), que
conectan los nodos entre sí. Los grafos se utilizan para modelar y analizar una
amplia variedad de fenómenos y situaciones en diferentes campos, su simplicidad y
flexibilidad los convierten en una herramienta poderosa y versátil para representar y
resolver problemas complejos.
La teoría de grafos proporciona un conjunto de conceptos, definiciones y algoritmos
de los cuales hablaré que permiten estudiar las propiedades estructurales de los
grafos, así como analizar su comportamiento y realizar operaciones sobre ellos.
Algunos de los conceptos clave en la teoría de grafos incluyen la conectividad, los
ciclos, los caminos más cortos, los árboles, los grafos bipartitos y los grafos
ponderados.
Desde muy pequeñita vi crecer a mi primo, personalmente siempre lo admiré. Es 8
años más grande que yo y siempre le vi que tenía una gran pasión por la ingeniería
ya que siempre hablaba de eso, sobre todo, todo lo que tenía que ver con las
matemáticas, y una vez que estuvo a punto de escoger una carrera, escogió
ingeniería. El día de hoy es un muy buen ingeniero diseñador de sistemas
electrónicos eficientes. Sin embargo siempre me pregunté de dónde venía toda esa
pasión por la ingeniería, sistemas electrónicos entre otros, por lo cual empecé a
investigar sobre ello y descubrí una teoría muy interesante que cambió mi
perspectiva de las matemáticas y fue mi inspiración a investigar este tema sobre “La
teoría de los grafos”. Descubrí que tiene muchas utilidades para nuestra vida diaria,
como la optimización de rutas, la planificación de horarios, la detección de
comunidades en redes sociales y la resolución de problemas de asignación.
Algunos de los algoritmos más conocidos en la teoría de grafos son el algoritmo de
Dijkstra para encontrar el camino más corto, el algoritmo de Kruskal para encontrar
el árbol de expansión mínima y el algoritmo de Ford-Fulkerson para problemas de
flujo máximo.
Es por eso que me animé a hablar de este interesante tema respecto a las
matemáticas y no solo eso, tiene que ver bastante con todo tipo de geometría.
Nunca oí hablar de esto lo cual me parece muy raro porque es una teoría muy
interesante y utilizada en nuestra vida diaria
MARCO TEÓRICO
Problema de conexión
Luciana, Matias y Sergio deciden construir tres casas en el campo para sus familias
en una misma parcela. La problemática de este proyecto surge cuando la empresa
de electricidad les comunica que sólo pueden colocar una conexión por parcela, las
conexiones de cables y cañerías no deben cruzarse.
Matias trata de dibujar ubicando convenientemente las tres casas y los tres
medidores, los conductos pueden ser rectos o pueden ser curvos; en el plano no lo
consigue porque la novena conexión se cruza siempre con algunas de las
anteriores, como lo muestra la siguiente figura:
Universidad del Bío-Bío - Sistema de Bibliotecas - Chile
Los cuadrados representan las casas y las circunferencias las respectivas fuentes
Sergio hace una nueva distribución, pero al igual que él anterior la novena conexión
se va a cruzar con algunas de las otras. Uno de ellos dice; creo que la dificultad
reside en que, al considerar el problema nos hemos limitado al plano, debemos
darnos cuenta de que hay tres dimensiones. Bastará hacer la conexión eléctrica por
el aire en lugar de hacerla a ras de la superficie de la tierra o lo otro sería hacer las
conexiones a diferente altura. Esta es una distribución hecha por Sergio que
tampoco tiene solución.
La respuesta al trabajar en el espacio es correcta en la práctica, pero nos hacemos
las siguientes preguntas; ¿será esto posible resolver el problema sin salirse del
plano? ¿Qué característica de la configuración hace irrealizable la conexión del
plano? Bueno a la última hermana se le ocurrió hacer lo siguiente; Sí ubicamos en
cada una de las casas cualquiera de las fuentes, ya sean de electricidad, agua y
gas, sería una de las maneras en que al hacer la distribución de las fuentes, los
cables y cañerías no se crucen.
NOCIONES BÁSICAS
Imagínate por un momento que estás mirando un mapa de tu ciudad. ¿Qué ves?
Puntos que representan lugares como parques, edificios, y calles que los conectan.
Ahora, piensa en esos puntos como nodos y en esas calles como las líneas que los
unen. ¡Eso es básicamente un grafo!
En términos sencillos, un grafo es como un juego de conectar puntos con líneas.
Los puntos se llaman vértices, nudos o nodos, mientras que las líneas que los unen
son las aristas. Algunos libros también usan el término "red" para referirse a un
grafo.
1.1 Definición : Podríamos decir que un grafo se representa como G(V, A), donde V
es el conjunto de puntos y A es el conjunto de líneas que conectan dos
puntos de V. Es importante señalar que el conjunto de líneas de A(∅) puede estar
vacío, lo que significa que no hay conexiones entre los [Link] conjunto de
las aristas que están relacionados mediante la aplicación T. ¡Así de simple es
entender la base de la teoría de grafos!
[Link]ón:Se podría decir que un grafo "de verdad" es aquel en el que las
conexiones no tienen una dirección específica, lo que significa que la relación entre
los elementos es recíproca, como una amistad donde ambas partes se valoran por
igual.
EJEMPLO:
En un diagrama geométrico, los puntos de conexión, llamados nudos o vértices, se
representan típicamente con pequeños círculos, mientras que las conexiones entre
ellos se muestran mediante arcos o líneas rectas. Estas conexiones pueden o no
tener una dirección específica, lo que lleva a dos categorías principales de grafos:
los dirigidos, donde las conexiones tienen una dirección definida, y los no dirigidos,
donde las conexiones son bidireccionales o simétricas.
Imagina que estás dibujando un mapa donde los puntos importantes son como tus
amigos, representados por pequeños círculos, y las líneas que los conectan son
como los lazos que te unen a ellos. Algunos lazos pueden tener una dirección
específica, como una invitación a una fiesta, mientras que otros pueden ser
bidireccionales, como compartir consejos y apoyo mutuo. Esto nos lleva a dos tipos
de grafos: los dirigidos, donde las conexiones tienen una dirección definida, como
una carta que se envía de un lugar a otro, y los no dirigidos, donde las conexiones
son como conversaciones donde ambas partes participan libremente.
CIRCUITO
Es el camino que vuelve a su punto de origen.
● Cualquier punto
punto
de
inicio.
● Al mismo
como
punto
de
llegada.
Circuito Elemental:Es aquel camino elemental que vuelve a su punto de partida.
Circuito Compuesto:
Camino compuesto que vuelve a su punto de partida.
Se forma a partir de un circuito, pero sin tener una dirección específica, es decir, se
trata de una secuencia que se cierra sobre sí misma.
Observación:
● Cada lugar en el ciclo podría ser el inicio.
● Cada inicio también puede ser el final.
Para resumir, en un grafo, podríamos considerar cambiar o ajustar los términos: en
lugar de "arco", usar "arista"; en vez de "camino", utilizar "cadena"; en lugar de
"circuito", referirnos a "ciclo", y en vez de "bucle", mencionar "lazo".
LEONHARD EULER
Wikipedia.(s.f). Wikipedia, The Free Encyclopedia.
La teoría de grafos se inició gracias a un problema
turístico que resolvió Leonhard Euler llamado el
problema de los siete puentes
Dice la historia que en 1736 se detuvo, en uno de
sus viajes en la costa del Mar Báltico, en la Prusia
oriental (Rusia), famosa por sus puentes, ya que
cuenta con siete de ellos que se unen mutuamente a
una Isla. Su lógica mente matemática de Euler
plantea un problema en el que podía llegar a un
lugar en diferentes sentidos, sin embargo se dio
cuenta que le faltaba algo y eran resoluciones de
fórmulas de la teoría de grafos viéndose obligado a
inventar una nueva fórmula
Fórmula de Euler
Considérese un polígono convexo con sus n vértices ylas
correspondientes aristas V1,V2,V3…., Vn-1, Vn, VnV1
Al margen de las longitudes de los lados, de los ángulos, de
la rectitud de las aristas, etc. Una relación que siempre vale
es que el número de aristas es igual al número de vértices. Si
mantiene los vértices y entre los correspondientes sustituye
la arista recta por cualquier curva simple, la relación
vértices /aristas se mantendrá.
Ahora en R3 , consideremos un poliedro convexo cualquier determinado por V
vértices, A aristas y C caras poligonales. Si desde un punto interior se proyecta el
poliedro en una esfera grande que lo incluya, en dicho esfera quedan marcadas las
líneas y los vértices correspondientes, de forma que los valores de V, A y C
mantendrán en la configuración esférica.
También puede hacerse corresponder el poliedro con un mapa poligonal que tenga
el mismo número de aristas A, el mismo número de vértices V y C caras. Entonces
puede observar inductivamente que si C = 2 se tiene un polígono y V = A , o lo que
es lo mismo C + V = A+2
Si con C = n se tienen Vn vértices, An aristas y se supone inductivamente que:
N + Vn = An + 2
En todo poliedro convexo se cumple la relación C + V = A+2
Tipos de Grafos
Es bastante común distinguir entre tres tipos de grafos: los grafos, los multigrafos
y los pseudografos
- Multígrafo: Es aquel grafo en donde dos vértices se pueden conectar por más
de una arista, Ejemplo:
Entonces es un multígrafo
- Pseudografo: Es aquel multígrafo en donde al menos exista un bucle (un
vértice conectado con sí mismo).
GRAFOS PLANOS
[Link]ón: Un grafo se considera plano únicamente si es posible representarlo
en un plano sin que las líneas que simbolizan las conexiones se crucen, excepto en
los puntos que representan a los vértices.
EJEMPLO:
Imagina que estás dibujando un mapa de tu vecindario. Este mapa es plano si
puedes representarlo de manera que las líneas que conectan los puntos solo se
crucen en los lugares donde están ubicados los lugares importantes, como las
intersecciones de calles. Es como si estuvieras dibujando un mapa donde las líneas
son como senderos que se cruzan sólo en las plazas de tu vecindario.
Est
os tres elementos finales tienen un papel crucial en la evaluación de si un grafo es
plano o no. Si concluimos que estos grafos no pueden ser representados en un
plano sin que las líneas se crucen, entonces es evidente que cualquier grafo que los
incluya como parte tampoco podrá ser representado de manera plana. Es como si
estos elementos fueran los indicadores clave que determinan si el mapa puede ser
dibujado sin problemas de superposición de líneas.
Grafos y Geometría
La inspiración es tan necesaria en geometría como en poesía
Alexander Pushkin
Finalmente debemos saber que muchísimas propiedades que se estudian en
geometría dependen de las medidas de los objetos: ángulos, distancias,
perpendicularidades, superficies, volúmenes, etc. Sin embargo, las consideraciones
típicas de la teoría de grafos y la topología también han ayudado a aclarar hechos
geométricos que no dependen tanto de las mediciones como de la configuración en
sí.
La fórmula de Descartes de 1640 y la fórmula de Euler de 1752, al basarse sólo en
caras, vértices y aristas, eran aplicables a muchas figuras diferentes y seguían
siendo válidas al hacer determinadas deformaciones. Ello daría pie a una nueva
rama de la matemática la topología que adquirió gran desarrollo en el siglo XX. De
forma resumida, podría decirse que la topología se libera de las estructuras rígidas
de la geometría euclidiana, o de la geometría proyectiva, y al permitir
“deformaciones continuas” logra modelar un nuevo mundo de formas y usar nuevas
categorías de transformaciones. Imagine un triángulo dibujado en la superficie de un
globo. Al apretar el globo (sin hacerlo estallar) el triángulo adquiere formas diversas
en las cuales variarán ángulos y longitudes, aunque la “esencia triangular” de figura
determinada por tres puntos y tres líneas entre ellos se mantendrá. El hecho de
pensar en figuras de goma que se puedan deformar es un buen recurso visual para
pensar topológicamente. Por ejemplo una esfera nunca dará por deformaciones un
Donut, pero Donut (con agujero) es equivalente a una taza de café.
Conclusión:
Concluyo finalmente que la teoría de grafos es una disciplina matemática y de
ciencias de la computación de gran importancia y aplicabilidad en diversos campos.
A través de la representación de objetos y sus relaciones mediante nodos y aristas,
los grafos nos permiten analizar y resolver problemas complejos de manera eficiente
y efectiva. La versatilidad de los grafos se refleja en su amplio espectro de
aplicaciones en la vida diaria. En el ámbito de las redes sociales, los grafos son
utilizados para comprender las interacciones entre usuarios, identificar comunidades
y analizar la difusión de información.
En el campo de la logística y el transporte, los grafos ayudan a optimizar las rutas
de entrega de paquetes, gestionar el tráfico en las ciudades y programar vuelos en
aerolíneas. En el diseño de circuitos electrónicos, los grafos permiten representar y
analizar la conectividad entre componentes, mejorando la eficiencia y confiabilidad
de los sistemas electrónicos.
La teoría de grafos proporciona un conjunto de herramientas y conceptos
fundamentales para el estudio de estas estructuras. Desde propiedades
estructurales como la conectividad y los ciclos, hasta algoritmos para resolver
problemas específicos como encontrar el camino más corto o el árbol de expansión
mínima, los conceptos de la teoría de grafos nos permiten analizar y manipular los
grafos de manera sistemática. Además, como dije anteriormente, los algoritmos de
grafos desempeñan un papel crucial en la resolución de problemas complejos.
Algoritmos como el algoritmo de Dijkstra, el algoritmo de Kruskal y el algoritmo de
Ford-Fulkerson son solo algunos ejemplos de las herramientas poderosas que la
teoría de grafos ofrece para abordar problemas de optimización, flujo y búsqueda en
diferentes contextos.
La teoría de grafos también se relaciona estrechamente con otras áreas de las
matemáticas y la ciencia de la computación, como la teoría de números, la
geometría combinatoria y los sistemas complejos. Esta interconexión permite un
enfoque multidisciplinario para resolver problemas complejos y comprender mejor
las estructuras y relaciones subyacentes en diversos fenómenos. La teoría de grafos
se aplica en una amplia gama de problemas en diferentes campos y como ejemplo
tenemos los problemas de planificación y programación donde los algoritmos de los
grafos ayudan a encontrar la secuencia óptima de acciones y minimizar el tiempo y
los recursos requeridos, asi mismo problemas de enrutamiento y transporte: Los
grafos se aplican en problemas de enrutamiento y transporte, permitiendo encontrar
la ruta más eficiente y minimizar la distancia o el tiempo de viaje.
Referencias APA:
● (N.d.). [Link]. Retrieved April 26, 2024, from
[Link]
nez_Marcelino.pdf
● Tomé, C. (2020, June 3). Un teorema en la biblioteca — Cuaderno de
Cultura Científica. Cuaderno de Cultura Científica.
[Link]
● Montero, G. (n.d.). Teorema de Grafos. [Link]. Retrieved April 26,
2024, from
[Link]
[Link]