Dentro de la Teoría de Grafos uno de los problemas más conocidos es la coloración de grafos, que consiste en la asignación de colores a los diferentes elementos del grafo. Se conocen varios tipos de problemas relacionados con la coloración de grafos, y en este proyecto nos centraremos en el problema de la coloración de aristas.
El problema consiste en la asignación de colores a las aristas de un grafo, de forma que las aristas adyacentes no sean del mismo color. Este tipo de problemas tienen una gran cantidad de aplicaciones, muchas se pueden utilizar para problemas de asignación, y en este proyecto haremos una aplicación a un problema de asignación de tareas dentro de una empresa.
El objetivo principal de este proyecto es realizar una aplicación de escritorio fácil de usar e intuitiva para el usuario basándonos en el estudio anterior de los diferentes algoritmos de coloración de aristas. El usuario podrá dibujar el grafo a estudiar, y posteriormente seleccionar el algoritmo deseado para realizar la coloración de aristas. Se le presentará por pantalla el dibujo del grafo coloreado, y además una serie de información como el tiempo utilizado y la cantidad de colores utilizados, indicando si según las acotaciones teóricas conocidas podría ser coloreado con menos colores o se encuentra con una coloración óptima.
Abstract:
Within Graph Theory, one of the most well-known problems is graph coloring, which consists of assigning colors to different elements of the graph. There are several types of problems related to graph coloring, and in this project, we will focus on the edge coloring problem.
The problem involves assigning colors to the edges of a graph, such that adjacent edges are not the same color. These types of problems have a large number of applications, many can be used for assignment problems, and in this project, we will focus on a task assignment problem within a company.
The main objective of this project is to create a desktop application that is easy to use and intuitive for the user, based on the previous study of different edge coloring algorithms. The user will be able to draw the graph to be studied, and then select the desired algorithm to perform the edge coloring. The drawing of the colored graph will be presented on screen, as well as a series of information such as the time used and the number of colors used, indicating whether according to known theoretical bounds it could be colored with fewer colors or if it has an optimal coloring.
Dentro de la Teoría de Grafos uno de los problemas más conocidos es la coloración de grafos, que consiste en la asignación de colores a los diferentes elementos del grafo. Se conocen varios tipos de problemas relacionados con la coloración de grafos, y en este proyecto nos centraremos en el problema de la coloración de aristas.
El problema consiste en la asignación de colores a las aristas de un grafo, de forma que las aristas adyacentes no sean del mismo color. Este tipo de problemas tienen una gran cantidad de aplicaciones, muchas se pueden utilizar para problemas de asignación, y en este proyecto haremos una aplicación a un problema de asignación de tareas dentro de una empresa.
El objetivo principal de este proyecto es realizar una aplicación de escritorio fácil de usar e intuitiva para el usuario basándonos en el estudio anterior de los diferentes algoritmos de coloración de aristas. El usuario podrá dibujar el grafo a estudiar, y posteriormente seleccionar el algoritmo deseado para realizar la coloración de aristas. Se le presentará por pantalla el dibujo del grafo coloreado, y además una serie de información como el tiempo utilizado y la cantidad de colores utilizados, indicando si según las acotaciones teóricas conocidas podría ser coloreado con menos colores o se encuentra con una coloración óptima.
Abstract:
Within Graph Theory, one of the most well-known problems is graph coloring, which consists of assigning colors to different elements of the graph. There are several types of problems related to graph coloring, and in this project, we will focus on the edge coloring problem.
The problem involves assigning colors to the edges of a graph, such that adjacent edges are not the same color. These types of problems have a large number of applications, many can be used for assignment problems, and in this project, we will focus on a task assignment problem within a company.
The main objective of this project is to create a desktop application that is easy to use and intuitive for the user, based on the previous study of different edge coloring algorithms. The user will be able to draw the graph to be studied, and then select the desired algorithm to perform the edge coloring. The drawing of the colored graph will be presented on screen, as well as a series of information such as the time used and the number of colors used, indicating whether according to known theoretical bounds it could be colored with fewer colors or if it has an optimal coloring. Read More
Related posts:
Problema de optimización de asientos en banquetes de bodas: Aplicación de algoritmos de coloración de vértices
Optimización y evaluación de Graph Neural Networks para la predicción de efectos secundarios en el conjunto de datos ogbl-ddi
Reconfigurable task assigning problem, caso de uso de Optaplanner
Automated Activity Scheduling Tools for Improving Learning and Evaluation of Cybersecurity Competencies in Computer Engineering Courses
Evaluación de dos cepas de Lachancea thermotolerans en
presencia de diferentes nutrientes
Software para ayudar en la interpretación de gammagrafías óseas