Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/15939| Título: | O problema da inundação em grafos função-circular |
| Título(s) alternativo(s): | The flood problem in circular-function graphs |
| Autor(es): | Omai, Mayara Midori |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Algorítmos Grafos de ligação Cores Algorithms Bond graphs Colors |
| Data do documento: | 1-Jun-2016 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | OMAI, Mayara Midori. O problema da inundação em grafos função-circular. 2016. 47 f. Trabalho de Conclusão de Curso (Graduação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2016. |
| Resumo: | O Problema da Inundação consiste em determinar o menor número de movimentos que tornam uma superfície, previamente colorida, monocromática. Tal superfície pode ser modelada como um grafo, onde cada vértice corresponde a uma região monocromática contínua e se duas regiões são vizinhas, então existe uma aresta entre os vértices que as representam. Considere um grafo construído a partir de uma superfície colorida. Um subgrafo conexo composto por vértices coloridos com a mesma cor é denominado componente monocromática. Um movimento se caracteriza pela atribuição de uma cor aos vértices de uma componente monocromática. Existem duas variações do Problema da Inundação, o Problema da Inundação com pivô fixo e o Problema da Inundação com pivô livre. No Problema da Inundação com pivô fixo a atribuição de cor é feita sempre na mesma componente monocromática. Já no Problema da Inundação com pivô livre pode-se escolher uma componente monocromática diferente para a atribuição de cores a cada movimento. Este trabalho apresenta uma solução em tempo polinomial para o Problema da Inundação com pivô fixo em uma classe de grafos que está sendo definida pela primeira vez neste trabalho, a classe dos grafos função-circular. Os grafos função-circular são aqueles que possuem uma representação por interseção de curvas de função entre dois círculos concêntricos, onde cada vértice é representado por uma curva e dois vértices são vizinhos se, e somente se, as curvas correspondentes se intersectam na representação. Os grafos função-circular são uma superclasse dos grafos de co-comparabilidade e a solução apresentada neste trabalho foi baseada na solução do Problema da Inundação com pivô fixo para grafos de co-comparabilidade dada por Fleischer e Woeginger em 2012. A solução do Problema da Inundação com pivô fixo em grafos função-circular implica na solução do Problema da Inundação com pivô fixo para os grafos trapézio circular, arco-circular, círculo, permutação circular, concave-round, potência de ciclo, entre outras. |
| Abstract: | The Flood it Problem aims to determine the smallest number of movements required to convert a colored surface into a monochromatic one. Such surface can be modeled as a graph, where each vertex is a continous monochromatic region. If two regions are neighbors, then there is an edge connecting the vertices representing these regions. In a graph modeled from a colored surface, a connected subgraph composed by vertices of the same color is called monochromatic component. A movement is the assignment of a color to the vertices of a monochromatic component. There are two variations of the Flood it Problem, one is called Fixed Flood it and the other one Free Flood it. In the former, all the color assignments are made in the same monochromatic component. In the latter, it’s possible to choose a distinct monochromatic component for each movement. This paper presents a polynomial time solution for the Fixed Flood it Problem in circular-function graphs. The circular-function graphs are a new graph class defined for the first time in this work. Circular-function graphs are graphs which are intersection graphs of curves between two concentric circles, where each vertex is represented by a curve, and two vertex are neighbors if and only if their corresponding curves intersect each other. This graph class is a superclass of the co-comparability graphs, and the solution proposed in this paper is based on the solution of the Fixed Flood it Problem for co-comparability graphs, given by Fleischer and Woeginger in 2012. The solution of the Fixed Flood it Problem in circular-function graphs implies the solution to the same problem in circular trapezoid graphs, circular-arc graphs, circle graphs, circular permutation graphs, concave-round graphs, cycles, among others. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/15939 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PG_COCIC_2016_1_05.pdf | 1,25 MB | 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.