Use este identificador para citar ou linkar para este item:
https://rd.uffs.edu.br/handle/prefix/2695
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor1 | Zatesko, Leandro Miranda | - |
dc.contributor.advisor-co1 | Guedes, André Luiz Pires | - |
dc.contributor.advisor-co2 | Carmo, Renato | - |
dc.creator | Castilho, João Paulo Kubaszewski | - |
dc.date | 2018 | - |
dc.date.accessioned | 2019-04-10T16:54:54Z | - |
dc.date.available | 2019 | - |
dc.date.available | 2019-04-10T16:54:54Z | - |
dc.date.issued | 2018 | - |
dc.identifier.uri | https://rd.uffs.edu.br/handle/prefix/2695 | - |
dc.description.abstract | 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 . | pt_BR |
dc.description.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 . | pt_BR |
dc.description.provenance | Submitted by SUELEN SPINDOLA BILHAR (suelen.bilhar@gmail.com) on 2019-04-09T11:50:17Z No. of bitstreams: 1 CASTILHO.pdf: 719366 bytes, checksum: 35fa95a7c696f5055c035ef1eb8efc52 (MD5) | en |
dc.description.provenance | Approved for entry into archive by Diego dos Santos Borba (dborba@uffs.edu.br) on 2019-04-10T16:54:54Z (GMT) No. of bitstreams: 1 CASTILHO.pdf: 719366 bytes, checksum: 35fa95a7c696f5055c035ef1eb8efc52 (MD5) | en |
dc.description.provenance | Made available in DSpace on 2019-04-10T16:54:54Z (GMT). No. of bitstreams: 1 CASTILHO.pdf: 719366 bytes, checksum: 35fa95a7c696f5055c035ef1eb8efc52 (MD5) Previous issue date: 2018 | en |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal da Fronteira Sul | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Campus Chapecó | pt_BR |
dc.publisher.initials | UFFS | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Ciência da computação | pt_BR |
dc.subject | Algoritmos | pt_BR |
dc.subject | Grafos aleatórios | pt_BR |
dc.title | Um algoritmo de recoloração de arestas de grafos | pt_BR |
dc.type | Monografia | pt_BR |
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.