Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/39056| Título: | Coloração de arestas em grafos cobipartidos |
| Título(s) alternativo(s): | Edge coloring in cobipartite graphs |
| Autor(es): | Lima, João Vitor Fagundes de |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Cores Teoria dos grafos Complexidade computacional Algorítmos Colors Graph theory Computational complexity Algorithms |
| Data do documento: | 1-Jul-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | LIMA, João Vitor Fagundes de. Coloração de arestas em grafos cobipartidos. 2025. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2025. |
| Resumo: | A minimização do número de cores para uma coloração de arestas em grafos é um problema relevante na teoria dos grafos, com aplicações em diversas áreas, como redes de comunicação, alocação de recursos e otimização. Este trabalho investiga métodos eficientes para a coloração de arestas de grafos cobipartidos, considerando técnicas já estabelecidas e propriedades estruturais que influenciam a distribuição das cores. O estudo justifica-se pela necessidade de compreender melhor a relação entre a estrutura desses grafos e a coloração, permitindo avanços teóricos e práticos na área. Para isso, são analisadas as características desses grafos, com ênfase na organização dos vértices em cliques, além da revisão de algoritmos existentes que podem ser aplicados ou adaptados. A metodologia envolve a formulação de provas matemáticas. Como resultado, são identificadas propriedades estruturais que impactam a coloração, além da adaptação de algoritmos para essa classe de grafos. A sistematização desses achados contribui para o desenvolvimento de diretrizes que ampliam o conhecimento sobre a coloração de arestas em grafos cobipartidos. |
| Abstract: | The minimization of the number of colors for edge coloring of graphs is a relevant problem in graph theory, with applications in several areas such as communication networks, resource allocation, and optimization. We investigate efficient methods for edge coloring in cobipartite graphs, considering established techniques and structural properties that influence the distribution of colors. The study is justified by the need to better understand the relationship between the structure of these graphs and their coloring, enabling both theoretical and practical advances in the field. To this end, the characteristics of these graphs are analyzed, with emphasis on the organization of vertices into cliques, along with a review of existing algorithms that can be applied or adapted. The methodology involves the formulation of mathematical proofs. As a result, structural properties that impact coloring are identified, as well as adaptations of algorithms for this class of graphs. The systematization of these findings contributes to the development of guidelines that expand the understanding of edge coloring in cobipartite graphs. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/39056 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| coloracaoarestascobipartidos.pdf | 468,58 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
