Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15966
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.creator | Castro, Luis Angelo Loss de | |
dc.date.accessioned | 2020-11-19T18:24:06Z | - |
dc.date.available | 2020-11-19T18:24:06Z | - |
dc.date.issued | 2018-06-13 | |
dc.identifier.citation | CASTRO, Luis Angelo Loss de. Caracterização e coloração de arestas em grafos split-co-comparabilidade. 2018. 35 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2018. | pt_BR |
dc.identifier.uri | http://repositorio.utfpr.edu.br/jspui/handle/1/15966 | - |
dc.description.abstract | A characterization of a graph class is the determination of structural properties that uniquely identify the graphs in this class. Those characterizations can give important information that supports many combinatorial problems, such as the Edge Coloring Problem. An edge coloring of a graph G is an assigment of colors to the edges of G such that the colors of any two edges that share a common vertex are distinct. The Edge Coloring Problem is to determine the minimum number of colors that allows an edge coloring for a given graph G. It is known that any simple graph G has an edge coloring with (G)+1 colors, where (G) is the maximum degree of G. However, some graphs G have an edge coloring with (G) colors. It is an NP-complete problem to decide if a graph G has an edge coloring with (G) colors. This work shows new characterizations for split-co-comparability graphs. Using these characterizations, it is determined a subset of split-co-comparability graphs for which the decision version of the Edge Coloring Problem has polynomial time solution. | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Tecnológica Federal do Paraná | pt_BR |
dc.rights | openAccess | pt_BR |
dc.subject | Representações dos grafos | pt_BR |
dc.subject | Solução de problemas | pt_BR |
dc.subject | Polinômios | pt_BR |
dc.subject | Representations of graphs | pt_BR |
dc.subject | Problem solving | pt_BR |
dc.subject | Polynomials | pt_BR |
dc.title | Caracterização e coloração de arestas em grafos split-co-comparabilidade | pt_BR |
dc.title.alternative | Characterization and edge coloring on split-co-comparability graphs | pt_BR |
dc.type | bachelorThesis | pt_BR |
dc.description.resumo | Uma caracterização de um conjunto de grafos é a determinação de propriedades estruturais que identifiquem unicamente os grafos desse conjunto. Essas caracterizações podem dar informações importantes que auxiliam na solução de diversos problemas combinatoriais, como por exemplo, o Problema da Coloração de Arestas. Uma coloração de arestas em um grafo G é uma atribuição de cores para as arestas de G de forma que as cores de quaisquer duas arestas que incidem no mesmo vértice são distintas. O Problema da Coloração de Arestas é determinar o menor número de cores que permite uma coloração de arestas para um dado grafo G. Sabe-se que qualquer grafo simples G tem uma coloração de arestas com _(G) + 1 cores, onde _(G) é o grau máximo do grafo G. Entretanto, alguns grafos G têm uma coloração de arestas com _(G) cores. Decidir se um grafo G tem uma coloração de arestas com _(G) cores é um problema NP completo. Este trabalho apresenta novas caracterizações para os grafos split-co comparabilidade. Usando essas caracterizações, determina-se um subconjunto dos grafos split-co comparabilidade para o qual a versão de decisão do Problema da Coloração de Arestas tem solução em tempo polinomial. | pt_BR |
dc.degree.local | Ponta Grossa | pt_BR |
dc.publisher.local | Ponta Grossa | pt_BR |
dc.contributor.advisor1 | Almeida, Sheila Morais de | |
dc.contributor.referee1 | Almeida, Sheila Morais de | |
dc.contributor.referee2 | Queiroz, Saulo Jorge Beltrão de | |
dc.contributor.referee3 | Matos, Simone Nasser | |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Departamento Acadêmico de Informática | pt_BR |
dc.publisher.program | Ciência da Computação | pt_BR |
dc.publisher.initials | UTFPR | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | pt_BR |
Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
PG_COCIC_2018_1_04.pdf | 896,3 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.