Aplicación de la teoría de grafos a problemas de costo

Abstract

En este trabajo se ha realizado un resumen de los conceptos fundamentales de la teoría de grafos, esenciales para abordar problemas de costo. También se han detallado otros puntos clave como los siguientes: - Árbol y arborescencia de unión de valor óptimo: en la teoría de grafos un árbol es un grafo conexo y acíclico, es decir, que no tiene ciclos y todos los vértices están conectados. Por otro lado, una arborescencia de unión de valor óptimo es un subconjunto de aristas de un grafo que conecta todos los vértices con el menor peso total posible. La arborescencia de unión de valor óptimo busca minimizar el peso total de las aristas para conectar todos los vértices. - Camino de menor valor: camino entre dos nodos en un grafo que tiene la menor suma de pesos en las aristas que lo componen. Es decir, es el camino más corto o con el menor costo entre dos nodos específicos en un grafo ponderado. - Redes de flujo: grafos dirigidos donde cada arista tiene una capacidad máxima de flujo y se busca encontrar la manera más eficiente de enviar un flujo desde un nodo fuente a un nodo destino, respetando las capacidades de las aristas y maximizando el flujo total. - Administración de proyectos: Técnicas para planificar, organizar, dirigir y controlar proyectos representando las actividades como nodos y arcos en un grafo para facilitar la toma de decisiones y una gestión eficiente que logre alcanzar los objetivos del proyecto en tiempo y forma. Además se ha explicado cómo aprovechar la herramienta MatLab para aplicar la teoría de grafos en la resolución de problemas, incluyendo comandos para encontrar árboles de unión y caminos de valor mínimo. En resumen, este trabajo destaca la utilidad de los grafos en la resolución de problemas cotidianos y resalta la importancia de MatLab para su implementación.

In this work, a summary of the fundamental concepts of graph theory, essential to address cost problems, has been made. Other key points have also been detailed, such as the following: - Tree and optimal value union tree: in graph theory a tree is a connected and acyclic graph, that is, it has no cycles and all vertices are connected. On the other hand, an optimal value join tree is a subset of edges of a graph that connects all vertices with the lowest possible total weight. The optimal value join tree seeks to minimize the total weight of edges to connect all vertices. - Path of least value: path between two nodes in a graph that has the smallest sum of weights on the edges that compose it. That is, it is the shortest path or path with the least cost between two specific nodes in a weighted graph. - Flow networks: directed graphs where each edge has a maximum flow capacity and the aim is to find the most efficient way to send a flow from a source node to a destination node, respecting the capacities of the edges and maximizing the total flow. - Project administration: Techniques to plan, organize, direct and control projects, representing activities as nodes and arcs in a graph to facilitate decision making and efficient management that achieves project objectives in a timely manner. In addition, it has been explained how to take advantage of the MatLab tool to apply graph theory in solving problems, including commands to find union trees and minimum value paths. In summary, this work highlights the usefulness of graphs in solving everyday problems and highlights the importance of MatLab for its implementation.