Use este identificador para citar ou linkar para este item:
https://rd.uffs.edu.br/handle/prefix/2695
Tipo: | Monografia |
Título: | Um algoritmo de recoloração de arestas de grafos |
Autor(es): | Castilho, João Paulo Kubaszewski |
Primeiro Orientador: | Zatesko, Leandro Miranda |
Primeiro coorientador: | Guedes, André Luiz Pires |
Segundo coorientador: | Carmo, Renato |
Resumo: | 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 . |
Abstract/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 . |
Palavras-chave: | Ciência da computação Algoritmos Grafos aleatórios |
Idioma: | por |
País: | Brasil |
Instituição: | Universidade Federal da Fronteira Sul |
Sigla da Instituição: | UFFS |
Faculdade, Instituto ou Departamento: | Campus Chapecó |
Tipo de Acesso: | Acesso Aberto |
URI: | https://rd.uffs.edu.br/handle/prefix/2695 |
Data do documento: | 2018 |
Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
CASTILHO.pdf | 702,51 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.