Emparelhamentos desconexos

Exportar este item:

Use este identificador para citar ou linkar para este item: http://www.bdtd.uerj.br/handle/1/7663

Tipo do documento:	Dissertação
Título:	Emparelhamentos desconexos Emparelhamentos desconexos
Título(s) alternativo(s):	Disconnected matchings Disconnected matchings
Autor:	Masquio, Bruno Porto
Primeiro orientador:	Pinto, Paulo Eustáquio Duarte
Primeiro coorientador:	Szwarcfiter, Jayme Luiz
Primeiro membro da banca:	Oliveira, Fabiano de Souza
Segundo membro da banca:	Nóbrega, Diana Sasaki
Terceiro membro da banca:	Souza, Uéverton dos Santos
Resumo:	A determinação de emparelhamentos máximos em grafos corresponde a problemas há muito tempo estudados e que trazem grandes contribuições à Teoria de Grafos, tanto do ponto de vista teórico quanto prático. Como tradição, há numerosos estudos na área destinados a emparelhamentos irrestritos e sem pesos. Mais recentemente, foram propostos os emparelhamentos restritos a subgrafos, que consideram propriedades dos subgrafos induzidos pelos vértices do emparelhamento. Neste trabalho, abordamos uma dessas novas propostas, que são os emparelhamentos desconexos, os quais procuram estudar emparelhamentos tais que os subgrafos induzidos pelos vértices dos emparelhamentos sejam desconexos. Conseguimos resolver o problema para classes simples de grafos tais como caminhos, ciclos, completos. Além disso, também obtivemos resultados para grafos split, árvores, grafos bloco e grafos cordais. Para essas três últimas classes, apresentamos uma base teórica que inclui teoremas de caracterizações, assim como três novos algoritmos. O trabalho também inclui um quarto algoritmo que determina um emparelhamento máximo para grafos bloco em tempo linear
Abstract:	Graph matchings are problems that have been studied for a long time and which bring great contributions to Graph Theory from both the theoretical and practical points of view. As a tradition, there are numerous studies in this field for unrestricted and unweightedmatchings. Morerecently, subgraph-restrictedmatchingshavebeenproposed, which consider properties from the subgraph induced by the matching vertices. In this paper, we approach one of these new proposals, which are disconnected matchings, which seekstostudymatchingsanditscardinalities,suchthatthesubgraphinducedbymatching vertices is disconnected. We were able to solve the problem for simple classes of graphs like paths, cycles and complete. In addition, we obtained results for split graphs, trees, block graphs and chordal graphs. For these last three classes, we present a theoretical basis that includes theorems of characterizations, as well as three new algorithms. This paper also includes a fourth algorithm, which finds a maximum matching for block graphs in linear time
Palavras-chave:	Algorithms Block Graphs Disconnected Matching Matching Split Graphs Chordal Graphs Trees Minimal separators Algoritmos Árvores Emparelhamento Emparelhamento Desconexo Grafo Bloco Grafo Split Grafo Cordal Separadores minimais Grafos - Teoria Algoritimos
Área(s) do CNPq:	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	BR
Instituição:	Universidade do Estado do Rio de Janeiro
Sigla da instituição:	UERJ
Departamento:	Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística
Programa:	Programa de Pós-Graduação em Ciências Computacionais
Citação:	MASQUIO, Bruno Porto. Emparelhamentos desconexos. 2019. 80 f. Dissertação (Mestrado em Modelagem matemático-estatístico-computacional) - Universidade do Estado do Rio de Janeiro, Rio de Janeiro, 2019.
Tipo de acesso:	Acesso Aberto
URI:	http://www.bdtd.uerj.br/handle/1/7663
Data de defesa:	13-Mar-2019
Aparece nas coleções:	Mestrado em Ciências Computacionais

Arquivos associados a este item:

Arquivo	Tamanho	Formato
Bruno_CComp_final.pdf	1,81 MB	Adobe PDF	Baixar/Abrir Pré-Visualizar ×

Mostrar registro completo do item Recomendar este item Visualizar estatísticas