Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/15956
Registro completo de metadados
Campo DCValorIdioma
dc.creatorRocha, Aleffer
dc.date.accessioned2020-11-19T18:23:48Z-
dc.date.available2020-11-19T18:23:48Z-
dc.date.issued2017-12-05
dc.identifier.citationROCHA, Aleffer. Coloração arco-íris em grafos resultantes de produto cartesiano. 2017. 46 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2017.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/15956-
dc.description.abstractGiven a graph G, an edge-coloring of G is an assingment of colors to the edges of G. A proper edge-coloring is an edge coloring if adjacent edges have different colors. A rainbow coloring of a connected graph G is an edge coloring that is not necessarily proper such that there is a path between any pair of vertices of G whose edge colors are pairwise distinct. The rainbow connection number of a graph G, denoted as rc(G), is the least number of colors for which there is a rainbow coloring of G. A graph G is rainbow critical if its rainbow connection number increases when we remove any edge from G. In this work we determine the rainbow connection number for the cartesian product graphs CmxPn when mis odd and CmxCn when m and n have distinct parities. For the case in which n and m are odd, we prove that rc(CmxCn)<=(m+n)/2. We also show that the cartesian product PmxPn is rainbow critical if and only if it is a path Pn, n > 1, or a C4 and that the cartesian product Cm x Pn is not rainbow critical when m is even and n > 1.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectCorespt_BR
dc.subjectArco-írispt_BR
dc.subjectRepresentações dos grafospt_BR
dc.subjectColorspt_BR
dc.subjectRainbowpt_BR
dc.subjectRepresentations of graphspt_BR
dc.titleColoração arco-íris em grafos resultantes de produto cartesianopt_BR
dc.title.alternativeColoring of the rainbow in graphs resulting from cartesian productpt_BR
dc.typebachelorThesispt_BR
dc.description.resumoDado um grafo G, uma coloração de arestas de G é uma atribuição de cores para as arestas de G. Uma coloração de arestas é própria se arestas adjacentes têm cores distintas. Uma coloração arco-íris de um grafo conexo G é uma coloração de arestas, não necessariamente própria, tal que entre qualquer par de vértices de G existe um caminho cujas cores das arestas são duas a duas distintas. O número de conexão arco-íris de um grafo G, denotado por rc(G), é o menor número de cores necessárias para se obter uma coloração arco-íris de G. Um grafo G é arco-íris crítico se a remoção de qualquer aresta de G aumenta o seu número de conexão arco-íris. Neste trabalho determinamos o número de conexão arco-íris para os grafos que são resultantes do produto cartesiano Cm x Pn, quando m é ímpar, e Cm x Cn, quando m e n têm paridades distintas. Para os casos em que m e n são ímpares, provamos que rc(Cm x Cn) <= (m + n)/2. Também mostramos que o produto cartesiano Pm x Pn é arco-íris crítico se, e somente se, é um caminho Pn, n > 1, ou um C4 e que os produtos cartesianos Cm × Pn não são arco-íris críticos quando m é par e n > 1.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Almeida, Sheila Morais de
dc.contributor.referee1Almeida, Sheila Morais de
dc.contributor.referee2Nóbrega, Diana Sasaki
dc.contributor.referee3Queiroz, Saulo Jorge Beltrao de
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2017_2_10.pdf9,19 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.