Sobre grafos rotulados, graciosos e colorações
Este projeto de pesquisa é a continuação do projeto envolvendo grafos mágicos e jogos matemáticos, do Programa de Iniciação Científica Júnior da 2013/2014, do CNPq/UFAM (projeto PIBJR-E0001, sobre Grafos Mágicos) do qual a presente aluna é bolsista. No PIBIC Jr., os chamados grafos mágicos estão sen...
| Autor principal: | Victória Patrícia Silva Aires |
|---|---|
| Grau: | Relatório de Pesquisa |
| Idioma: | pt_BR |
| Publicado em: |
Universidade Federal do Amazonas
2016
|
| Assuntos: | |
| Acesso em linha: |
http://riu.ufam.edu.br/handle/prefix/4855 |
| id |
oai:localhost:prefix-4855 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:localhost:prefix-48552025-03-10T20:17:18Z Sobre grafos rotulados, graciosos e colorações Victória Patrícia Silva Aires Rosiane de Freitas Rodrigues Algoritmos Grafos rotulados Teoria dos grafos Otimização CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Este projeto de pesquisa é a continuação do projeto envolvendo grafos mágicos e jogos matemáticos, do Programa de Iniciação Científica Júnior da 2013/2014, do CNPq/UFAM (projeto PIBJR-E0001, sobre Grafos Mágicos) do qual a presente aluna é bolsista. No PIBIC Jr., os chamados grafos mágicos estão sendo investigados. Um grafo mágico é um grafo onde a soma dos rótulos das arestas que incidem em qualquer vértice é a mesma. A ênfase está no estudo do quadrado mágico, que consiste em um quadrado com dimensões nxn onde a soma dos elementos de cada linha, coluna e diagonal é a mesma. Agora, sendo um grafo mágico um caso particular de grafo rotulado, o objetivo deste projeto é o estudo dos outros casos de rotulação, como os grafos graciosos e problemas de colorações especiais, tópicos que serão os temas deste trabalho. Um grafo é um par ordenado G=(V,E), onde V é um conjunto de n elementos denominados de vértices, e E é um conjunto de m pares não-ordenados de elementos de V, denominados de arestas. O problema clássico de coloração de vértices de um grafo, envolve a determinação de uma coloração própria dos vértices deste grafos, onde vértices adjacentes tenham cores distintas, usando o menor número de cores possíveis. Uma k-coloração é uma coloração de um grafo com k cores, e um grafo é k-colorível se tem uma k-coloração. O inteiro positivo mínimo k para o qual um grafo G é k-colorível é seu número cromático. Dentre os problemas em teoria dos grafos com larga aplicação, destacam-se os problemas de coloração de grafos. Problemas tais como a coloração de mapas com um conjunto mínimo de cores, escalonamento de reuniões de comitês com membros dispersos entre vários comitês, programação de horários escolares [DIESTEL, 2000] e programação de períodos de exames em universidades [BONDY e MURTY, 2008], são exemplos de aplicações de coloração de grafos. Existem inúmeras variações do problema clássico de coloração de vértices em grafos, seja para coloração de arestas, vértices e arestas em conjunto, ou considerando restrições adicionais ao problema clássico. Por outro lado, existem inúmeras classes de grafos e o estudo teórico de grafos, o que envolve entender, validar e desenvolver propriedades e algoritmos para a classe geral e sub-classes específicas de grafos. Dentre os casos mais peculiares de coloração, estão os grafos graciosos. Considerando um grafo com vértices e arestas rotulados com números naturais, de modo que os rótulos das arestas recebem a diferença dos rótulos dos vértices em que incidem. Quando as arestas rotuladas determinam uma sequência de 1 a n (onde n é o número de arestas), o grafo é denominado gracioso. CNPQ 2016-09-23T15:54:57Z 2016-09-23T15:54:57Z 2015-07-31 Relatório de Pesquisa http://riu.ufam.edu.br/handle/prefix/4855 pt_BR Acesso Aberto PDF Universidade Federal do Amazonas Brasil Ciências da Computação Instituto de Ciências Exatas PROGRAMA PIBIC 2014 UFAM |
| institution |
Repositório Institucional - Universidade Federal do Amazonas |
| collection |
RI-UFAM |
| language |
pt_BR |
| topic |
Algoritmos Grafos rotulados Teoria dos grafos Otimização CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| spellingShingle |
Algoritmos Grafos rotulados Teoria dos grafos Otimização CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Victória Patrícia Silva Aires Sobre grafos rotulados, graciosos e colorações |
| topic_facet |
Algoritmos Grafos rotulados Teoria dos grafos Otimização CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO |
| description |
Este projeto de pesquisa é a continuação do projeto envolvendo grafos mágicos e jogos matemáticos, do Programa de Iniciação Científica Júnior da 2013/2014, do CNPq/UFAM (projeto PIBJR-E0001, sobre Grafos Mágicos) do qual a presente aluna é bolsista. No PIBIC Jr., os chamados grafos mágicos estão sendo investigados. Um grafo mágico é um grafo onde a soma dos rótulos das arestas que incidem em qualquer vértice é a mesma. A ênfase está no estudo do quadrado mágico, que consiste em um quadrado com dimensões nxn onde a soma dos elementos de cada linha, coluna e diagonal é a mesma. Agora, sendo um grafo mágico um caso particular de grafo rotulado, o objetivo deste projeto é o estudo dos outros casos de rotulação, como os grafos graciosos e problemas de colorações especiais, tópicos que serão os temas deste trabalho.
Um grafo é um par ordenado G=(V,E), onde V é um conjunto de n elementos denominados de vértices, e E é um conjunto de m pares não-ordenados de elementos de V, denominados de arestas. O problema clássico de coloração de vértices de um grafo, envolve a determinação de uma coloração própria dos vértices deste grafos, onde vértices adjacentes tenham cores distintas, usando o menor número de cores possíveis. Uma k-coloração é uma coloração de um grafo com k cores, e um grafo é k-colorível se tem uma k-coloração. O inteiro positivo mínimo k para o qual um grafo G é k-colorível é seu número cromático.
Dentre os problemas em teoria dos grafos com larga aplicação, destacam-se os problemas de coloração de grafos. Problemas tais como a coloração de mapas com um conjunto mínimo de cores, escalonamento de reuniões de comitês com membros dispersos entre vários comitês, programação de horários escolares [DIESTEL, 2000] e programação de períodos de exames em universidades [BONDY e MURTY, 2008], são exemplos de aplicações de coloração de grafos. Existem inúmeras variações do problema clássico de coloração de vértices em grafos, seja para coloração de arestas, vértices e arestas em conjunto, ou considerando restrições adicionais ao problema clássico.
Por outro lado, existem inúmeras classes de grafos e o estudo teórico de grafos, o que envolve entender, validar e desenvolver propriedades e algoritmos para a classe geral e sub-classes específicas de grafos. Dentre os casos mais peculiares de coloração, estão os grafos graciosos. Considerando um grafo com vértices e arestas rotulados com números naturais, de modo que os rótulos das arestas recebem a diferença dos rótulos dos vértices em que incidem. Quando as arestas rotuladas determinam uma sequência de 1 a n (onde n é o número de arestas), o grafo é denominado gracioso. |
| author_additional |
Rosiane de Freitas Rodrigues |
| author_additionalStr |
Rosiane de Freitas Rodrigues |
| format |
Relatório de Pesquisa |
| author |
Victória Patrícia Silva Aires |
| title |
Sobre grafos rotulados, graciosos e colorações |
| title_short |
Sobre grafos rotulados, graciosos e colorações |
| title_full |
Sobre grafos rotulados, graciosos e colorações |
| title_fullStr |
Sobre grafos rotulados, graciosos e colorações |
| title_full_unstemmed |
Sobre grafos rotulados, graciosos e colorações |
| title_sort |
sobre grafos rotulados, graciosos e colorações |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2016 |
| url |
http://riu.ufam.edu.br/handle/prefix/4855 |
| _version_ |
1831969627189542912 |
| score |
11.755432 |