Por favor, use este identificador para citar o enlazar este ítem:
https://rd.uffs.edu.br/handle/prefix/2695
Type: | Monografia |
Título : | Um algoritmo de recoloração de arestas de grafos |
Author: | Castilho, João Paulo Kubaszewski |
First advisor: | Zatesko, Leandro Miranda |
metadata.dc.contributor.advisor-co1: | Guedes, André Luiz Pires |
metadata.dc.contributor.advisor-co2: | Carmo, Renato |
Resume: | O problema de determinar o mínimo de cores necessárias para colorir todas as arestas de um grafo G, chamado de Problema da Classificação de Grafos, é um problema NP-completo. Como enunciado pelo Teorema de Vizing, existem apenas duas classes que abrangem todos os grafos, o que implica que todo grafo G tem índice cromático (menor quantidade de cores necessárias pala colorir todas as arestas de G) ∆, em que é denominado Classe 1, ou ∆+1, em que é denominado Classe 2. Para algumas classes de grafos foram encontrados algoritmos polinomiais para determinar o seu índice cromático. Este trabalho apresenta um estudo de um procedimento de tempo polinomial para construir uma ∆-aresta-coloração para as arestas dos grafos pertencentes à classe X , que é a classe dos grafos cujos ∆-vértices (vértices com grau máximo) têm soma de grau local (a soma de grau local de um vértice u é a soma dos graus de todos os seus vizinhos) no máximo ∆2 − ∆. Por fim são apresentadas algumas propostas para trabalhos futuros que consistem em ampliar a classe X . |
Resumen : | The problem to find the minimum of colors that are necessary to color all edges on a graph G, known as Classification Problem, is an NP-complete problem. As stated by the Vizing’s Theorem, we have only two classes for all graphs, that is, the chromatic index of G (the minimum number of colours needed to colour the edges of G) is either ∆, in that case G is Class 1, or ∆ +1, in that case G is Class 2. For some graph classes some polynomial algorithms had been found to determine its chromatic index. This workshowsastudyonapolynomialtimerecolouringproceduretoconstructa ∆-edgecolouring of graphs which belong to the class X , that is, the class of graphs whose majors (vertices of degree ∆) have local degree sum (the local degree sum of some vertex u is the sum of the degrees of all neighbors of u) at most ∆2 − ∆. We conclude showing some ideas for future works which consist of an extension of the class X . |
Palabras clave : | Ciência da computação Algoritmos Grafos aleatórios |
Language: | por |
Country: | Brasil |
Editorial : | Universidade Federal da Fronteira Sul |
Acronym of the institution: | UFFS |
College, Institute or Department: | Campus Chapecó |
Type of Access: | Acesso Aberto |
URI : | https://rd.uffs.edu.br/handle/prefix/2695 |
Fecha de publicación : | 2018 |
Aparece en las colecciones: | Ciência da Computação |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
CASTILHO.pdf | 702,51 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.