PROYECTO
BRAYHA DANIEL TRUJILLO ORJUELA
NICOLL VALENTINA LEON VANEGAS
JENNIFER TATIANA PULIDO MAHECHA
AUTORES
COREDUCACION
TECNOLOGÍA EN DESARROLLO DE SISTEMAS INFORMÁTICOS
INGENIERÍA
TEORIA GENERAL DE SISTEMA
HONDA, TOLIMA
2023
PROYECTO
BRAYHA DANIEL TRUJILLO ORJUELA
NICOLL VALENTINA LEON VANEGAS
JENNIFER TATIANA PULIDO MAHECHA
AUTORES
ING: MONICA ZARATE PUÑUELAS
DOCENTE
COREDUCACION
TECNOLOGÍA EN DESARROLLO DE SISTEMAS INFORMÁTICOS
INGENIERÍA
TEORIA GENERAL DE SISTEMA
HONDA, TOLIMA
2023
Teoría de redes
La modelación de redes permite la resolución de múltiples problemas de
programación matemática mediante la implementación de algoritmos especiales
creados para tal fin, conocidos como Algoritmos de optimización de redes.
Dentro de los problemas más comúnmente resueltos mediante la modelación de
redes se encuentran los ya vistos modelos de transporte, transbordo además de
los muy conocidos modelos de determinación de cronograma de actividades para
proyectos como lo son el PERT y el CPM.
Conceptos básicos en teoría de redes
Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas
líneas llamadas ramales o arcos.
Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por
ejemplo, una gráfica cuyo flujo en sus ramales sea la electricidad es una red eléctrica.
En las redes se usa una simbología específica para denotar su tamaño y elementos que
la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que
contiene la red y A representa el número de arcos o ramales.
Cadena: Una cadena corresponde a una serie de elementos ramales que van de un
nodo a otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el
nodo 7 y que se compone por los elementos [1-4, 4-7].
Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente
caso [1, 4, 7].
Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el
siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido
determinado, es decir que posee un nodo fuente y un nodo destino.
Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se
encuentran orientados.
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.
Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos
de la red, de igual manera no permite la existencia de ciclos.
Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se
encuentran orientados hacia afuera.
Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se
encuentran orientados hacia él.
Algoritmo árbol de expansión mínima
El algoritmo del árbol de expansión mínima es un modelo de optimización de redes
que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el
objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por
longitud del arco una cantidad variable según el contexto operacional de
minimización, y que puede bien representar una distancia o unidad de medida).
Sean:
N = {1,2,3,…,n} el conjunto de nodos de la red.
Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k
Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
Paso cero (0): Conceptualización del algoritmo
Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han
enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a
los nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de
nodos que existen en la red.
Paso 1:
Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual
será el primer nodo permanente, a continuación, se debe de actualizar el conjunto C 1 =
{i}, que significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto
Č0pierde el elemento i por ende ahora será igual a Č1 = N – {i}, además se debe
actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.
Paso 2: Paso general «K»
Se debe de seleccionar un nodo j del conjunto ČK-1 («k-1» es el subíndice que indica
que se está haciendo referencia al conjunto de la iteración inmediatamente anterior) el
cual tenga el arco o ramal con menor longitud con uno de los nodos que se
encuentran en el conjunto de nodos de enlace permanente C K-1. Una vez seleccionado
se debe de enlazar de forma permanente lo cual representa que pasa a formar parte
del conjunto de enlaces permanentes y deja de formar parte del conjunto que todavía
se debe conectar para lograr la expansión. Al actualizar el algoritmo en este paso los
conjuntos deben de quedar de la siguiente forma.
CK = CK-1 + {j} mientras que ČK = ČK-1 – {j}
El paso general que define k que al mismo tiempo representa a las iteraciones debe de
ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea igual a
vacío se tendrá el árbol de expansión mínima.
El entendimiento del algoritmo desde el punto de vista algebraico no es quizá el más
simple, sin embargo, mediante el ejemplo gráfico se verá que es un algoritmo muy
sencillo de elaborar.
Teoría de grafos
La teoría de grafos es una mezcla extraordinaria de historia, cultura y soluciones a
problemas complejos desde el mundo de las matemáticas. Con esta teoría se busca
representar de forma visual conjuntos de datos abstractos en formas de nodos o vértices
y la unión o relaciones que estas pueden tener con otros nodos a través de aristas.
Gracias a esta teoría se han podido lograr grandes avances en el análisis de amplios
volúmenes de data.
En la actualidad los grafos integran parte central de un número increíble de soluciones a
problemas complejos. Son uno de los componentes fundamentales de la analítica social,
relaciones entre personas y más recientemente se han utilizado sus propiedades para
incrementar la eficiencia en la lucha contra el blanqueo de capitales y el fraude bancario.
Para empezar a navegar en el mar de los grafos, conozcamos un poco sobre la historia
de la teoría de grafos.
Historia de la teoría de grafos
Los orígenes que fundamentan la teoría de grafos nacen con un estudio realizado por el
matemático suizo Leonhard Euler en 1736. La investigación de Euler trataba de resolver
el mítico problema de los puentes de Konisberg.
Este problema consistía en obtener una ruta eficiente para cruzar todos los puentes de la
ciudad, cruzándolos una sola vez. Las conclusiones de Euler demostraron su
improbabilidad, pero fue el punto de partida a un número increíble de estudios.
Entre los estudios más relevantes que le han dado forma a la teoría de grafos como la
conocemos hoy se encuentran las investigaciones de Gustav Kirchhoff (1845) con los
circuitos de cálculo de voltaje y Francis Guthrie (1852) con la presentación de la hipótesis
de los cuatros colores.
Este problema plantea la posibilidad de llenar un mapa geográfico solo con cuatro colores,
de forma que países vecinos no compartan nunca un mismo color. El problema fue
resuelto casi un siglo después por Kenneth Appel y Wolfang Haken, donde plantearon
conceptos fundamentales de los grafos.
Continuemos profundizando sobre los Conceptos de esta teoría.
Principales conceptos de la teoría de grafos
Debemos tener presentes que existen diferentes tipos de grafos. Dependiendo del tipo de
grafo podemos lograr obtener diferentes características que podemos implementar en
nuestros proyectos. Los grafos simples o multigrafos son composiciones de complejidad
ligera en las que los conjuntos de nodos pueden estar unidos por varias aristas.
Los grafos también tienen propiedades especiales que indican orientaciones, estas
características se encuentran en los grafos o multígrafos dirigidos. En este tipo de grafos
cuentan con la particularidad de que sus aristas vinculan a los nodos en una sola
dirección. Además de estos conceptos también podemos conseguir grafos, completos,
conexos y etiquetados.
Estructura de datos en la representación de grafos
Uno de los puntos más importantes que integra la teoría de grafos son sus estructuras de
representación. Gracias a estas estructuras podemos aprovechar al máximo la
visualización de los conjuntos de datos para analizar se forma simple los elementos para
tomar decisiones.
Entre las estructuras más sencillas e implementadas se encuentran las listas y las
matrices. Aunque frecuentemente existen modelos combinados entre ambas.
Una estructura de lista es donde las aristas son representadas con un vector de pares
ordenados, en el caso de que el grafo sea dirigido, donde cada par representa a una de
las aristas.
Por su parte las listas de adyacencia, ocurre que cada vértice tiene una lista de vértices
los cuales son adyacentes al mismo nodo. Esto causa redundancia en un grafo no
dirigido, pero este tipo de listas ofrece una gran rapidez en las búsquedas.
En las estructuras de datos de datos descritas la idea es asociar cada uno de los vértices
del grafo con una lista que contenga al resto de los vértices adyacentes. De esta forma
solo se reservará memoria para los arcos adyacentes.
Aplicaciones de la teoría de grafos
Al abordar aspectos básicos de la teoría de grafos podemos descubrir que estos nos
presentan características y prestaciones para resolver diversos tipos de problemas. Con
ellos podemos brindar soluciones de dibujo computacional, perfeccionar técnicas de
PERT en el área gerencial o potenciar el estudio de las relaciones en ambientes
biológicos complejos.
Además, con esta teoría se ha podido aprovechar el máximo el potencial de las redes
sociales. Con el análisis de grafos es posible comprender las relaciones, preferencias y
similitudes entre los usuarios. Esto ha sido de una utilidad gigantesca para las empresas
del sector. Aunque el sector más prominente en el cual se ha avanzado es en la detección
de fraude bancario.
Las herramientas de grafos permiten analizar miles de millones de datos de forma rápida,
también pueden usarse softwares complementarios para determinar de forma eficiente
comportamientos que puedan orientar a la presencia de un fraude.
Esperamos que esta información te sea útil conociendo el mundo de los grafos.
Teoría de grafos
Teo