Introducción

La era de la teoría de grafos comenzó con Euler en el año 1735 para resolver el conocido problema del puente de Königsberg. En la era moderna, la teoría de grafos es un componente integral de la informática, ingenieria artificial, máquina de aprendizaje, deep learning, Ciencia de los datosy redes sociales. Aplicaciones modernas de la teoría de grafos analiza muchas aplicaciones de vanguardia de la teoría de grafos, como las redes de tráfico, las redes navegables y el enrutamiento óptimo para la respuesta de emergencia, y los enfoques de teoría de grafos para la epidemiología molecular.

¿Qué es la teoría de grafos? 

Un gráfico G(V, E) no es lineal estructura de datos, que consta de un par de conjuntos (V, E) donde V es el conjunto no vacío de vértices (puntos o nodos). E es el conjunto de aristas (líneas o ramas) tales que existe una aplicación f: E →V es decir, del conjunto E al conjunto de pares ordenados o desordenados de elementos de V. El número de llamado el orden de los gráficos y el número de aristas se llama el tamaño del gráfico G (V, E). 

Los gráficos son de tres tipos: gráficos no dirigidos, gráficos dirigidos y gráficos ponderados.

• Gráficos no dirigidos: en los gráficos no dirigidos, los bordes están asociados con un par de vértices no ordenados. Un grafo G (V, E) sin bucle y aristas paralelas se llama grafo simple. Un gráfico que tiene más de una arista entre cualquier par de vértices se llama multigrafo. Nuevamente, si cualquier multigrafo contiene bucles, entonces el gráfico es un pseudográfico. Según la estructura, existen diferentes tipos de grafos no dirigidos, como grafos nulos, grafos completos, grafos regulares, grafos bipartitos, ciclos, ruedas, grafos eulerianos y grafos hamiltonianos.
• Gráfico dirigido: Un gráfico dirigido o dígrafo G consta de un conjunto V de vértices y un conjunto E de aristas tales que eϵE está asociado con un par ordenado de vértices, es decir, cada arista tiene una dirección. Hay diferentes tipos de grafos dirigidos. Gráficos dirigidos simétricos, gráficos dirigidos simples, gráficos dirigidos completos, dígrafos cuasi-transitivos y gráficos orientados.
• Gráficos ponderados: muchos gráficos pueden tener bordes que contienen un peso asociado para representar implicaciones del mundo real, como el costo, la distancia y la cantidad. Los gráficos ponderados pueden ser gráficos dirigidos o no dirigidos.
• Los árboles son una de las subcategorías de gráficos más utilizadas. En informática, los árboles son útiles para organizar y almacenar datos en una base de datos. Un árbol es un gráfico acíclico conectado sin ciclo. Un árbol T con n vértices tiene n-1 aristas. Un subgrafo T un grafo conexo G (V, E) se denomina árbol de expansión si T es un árbol y si incluye todos los vértices de G. Hay dos algoritmos a) BFS (búsqueda primero en amplitud) y b) DFS (búsqueda en profundidad) primera búsqueda) para construir los árboles de expansión de un gráfico G no dirigido dado. Para los gráficos ponderados, se puede construir el árbol de expansión mínimo usando el algoritmo de Prim y Kruskal. Los árboles binarios que tienen un vértice de grado dos y los otros vértices de grado uno o grado tres, se utilizan para representar una expresión algebraica y una representación de almacenamiento. La representación de almacenamiento del árbol binario tiene dos formas a) Representación secuencial yb) Representación de enlace.

Ex. Usa un árbol binario para representar la expresión ((a + b)* c) + (d/e)

¿Cómo funciona la teoría de grafos?

La teoría de grafos se trata, en última instancia, de estudiar las relaciones entre diferentes nodos (vértices) y conexiones (aristas). El estudio de gráficos a lo largo de una estructura proporciona respuestas a numerosos problemas de diseño, redes, optimización, coincidencia y operación.

Problemas de coloreado de gráficos 

La coloración de grafos es una de las técnicas más útiles en la que los vértices adyacentes obtienen diferentes colores. El número mínimo de colores utilizados para la coloración correcta del gráfico es nuestro objetivo, que es un problema de optimización.

El problema de la coloración de gráficos tiene muchas aplicaciones, como la creación de un cronograma o tabla de horarios, la asignación de radiofrecuencia móvil, el sudoku, la asignación de registros y la coloración de mapas.

Problema de programación de tiempo 

Piense en un semestre específico; hay estudiantes tomando cada una de las siguientes combinaciones de temas. En este problema, nuestro objetivo es encontrar el número mínimo de días de examen para programar el examen en las 8 materias para que los estudiantes que toman cualquiera de las combinaciones dadas de la materia no tengan conflicto.

Además, encuentre un horario disponible utilizando un número mínimo de días.

Tabla: Combinaciones de Sujetos

El resultado del problema

Algunos problemas clásicos de la teoría de grafos

• Un viejo problema es conectar cuatro casas H1, H2, H3 y H4 a tres servicios cada una: agua (W), gas (G), electricidad (E) y cable de TV (C). ¿Se puede conectar cada servicio a cada una de las cuatro casas sin tener dos conexiones cruzadas entre ellas?

• Problema del vendedor ambulante:

Supongamos que el territorio de un vendedor incluye varias ciudades con carreteras que unen algunos pares de estas ciudades. Debería visitar cada ciudad una vez. La teoría de grafos puede ser útil para resolver este sistema de transporte. El problema se puede representar gráficamente mediante un grafo G cuyos vértices corresponden a las ciudades. Los dos vértices están unidos por una arista si y solo si una carretera conecta las ciudades correspondientes. Comenzando en el vértice a, el vendedor puede visitar tomando los bordes e1, e2, e3, e4, e5 y e6 y regresando al vértice a.

Algoritmo para la aplicación moderna de la vida real 

Google Maps

Los mapas de Google usan gráficos para los sistemas de construcción y transporte. La intersección de dos (o más) caminos se considera un vértice, y el camino que conecta dos vértices se considera un borde. Luego, su sistema de navegación usa el algoritmo para calcular el camino más corto entre dos vértices. En GPS también utilizamos diferentes algoritmos de ruta más corta, como el algoritmo DFS (búsqueda primero en profundidad) y BFS (búsqueda primero en respiración). Por el Algoritmo de Dijkstra, uno puede encontrar la ruta más corta entre un nodo dado (nodo de origen) y todos los demás nodos (nodo de destino) en un gráfico. Este algoritmo utiliza pesos de borde para encontrar una forma de reducir la distancia total (peso) entre el nodo de origen y todos los demás nodos.

Facebook y LinkedIn

¿Alguna vez se preguntó cómo sabe Facebook que una persona es su amigo en común o cómo LinkedIn sabe si una conexión es una segunda o tercera? Facebook y LinkedIn modelan a sus usuarios como un gráfico en el que cada vértice es un perfil de usuario. El límite entre dos personas es el hecho de que son amigos entre ellos o se siguen. El algoritmo de sugerencia de Facebook y LinkedIn Friend utiliza la teoría de grafos. Facebook es un ejemplo de un gráfico no dirigido. 

World Wide Web

En la World Wide Web, las páginas web se consideran vértices. Hay un borde entre la página 'u' y otra página 'v' si hay un enlace desde la página 'v' a la página 'u'. Ese es un ejemplo de un gráfico dirigido. Ese es el concepto básico detrás del algoritmo de Page Rank de Google.

Social Network

En los sitios de redes sociales, usamos gráficos para rastrear la información del usuario. Gustó mostrar sugerencias de publicaciones preferidas, recomendaciones, etc. Por lo tanto, el desarrollo de algoritmos para administrar gráficos es de gran interés en el campo de las tecnologías de la información.

Conclusión

Debido a la creciente aplicación de inteligencia artificial, aprendizaje automático, aprendizaje profundo, ciencia de datos y criptografía en varios campos como ciencias de la salud, ciencias sociales, industria manufacturera, servicios de defensa y diferentes actividades gubernamentales, el enfoque teórico de gráficos y su aplicación es un tema muy exigente para el investigador. Después de terminar el estudio de la teoría de grafos, los estudiantes pueden aplicar su conocimiento de la teoría de grafos en varios campos de la ciencia moderna.

• Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
• Platoblockchain. Inteligencia del Metaverso Web3. Conocimiento amplificado. Accede Aquí.
• Fuente: https://www.mygreatlearning.com/blog/application-of-graph-theory/