Caracterização dos cografos-(3,1) por subgrafos proibidos com restrições externas

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorBravo, Raquel Francisco-
Autor(es): dc.contributorNogueira, Loana Tito-
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.creatorCruz, Maria Luíza López da-
Data de aceite: dc.date.accessioned2024-07-11T17:46:43Z-
Data de disponibilização: dc.date.available2024-07-11T17:46:43Z-
Data de envio: dc.date.issued2021-12-22-
Data de envio: dc.date.issued2021-12-22-
Data de envio: dc.date.issued2020-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/24062-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/757293-
Descrição: dc.descriptionEste trabalho de conclusão de curso é um estudo de partição de grafos em 3 (três) conjuntos independentes e 1 (uma) clique. Um problema muito conhecido da literatura é o problema dos grafos-(k, l) com restrição externa, ou seja, problema de particionar o conjunto de vértices em k conjuntos independentes (S1, . . . , Sk) e l cliques (Ck+1, . . . , Ck+l), considerando todas as possíveis restrições externas entre as partes, isto é, para quaisquer duas partes i e j definimos sua relação como completamente adjacentes (quaisquer dois vértices entre os conjuntos i e j são adjacentes), completamente não adjacentes (quaisquer dois vértices entre os conjuntos i e j não são adjacentes) ou sem restrições (não existe nenhuma restrição entre os conjuntos). Este problema dos grafos-(k, l) com restrição externa pode ser representado em uma matriz que identifica as restrições dos conjuntos, sendo internas ou externas. O problema é chamado de problema da M-partição. No projeto em questão, caracterizamos os cografos M-particionáveis em termos de obstruções. Uma obstrução de um grafo G é um subgrafo de G que não é M-particionável, ou seja, que não admite tal partição. Logo, G também não é M-particionável. Nesse trabalho estamos interessados em determinar as obstruções minimais para todos os casos de restrições externas possíveis envolvendo a clique e nenhuma restrição externa entre os conjuntos independentes.-
Descrição: dc.descriptionThis course conclusion work is a study of graph partition into 3 (three) independent sets and 1 (one) clique. A well-known problem in the literature is the problem of graphs-(k, l) with external constraint, that is, problem of partitioning the set of vertices into k independent sets (S1, . . . , Sk) and l cliques (Ck + 1, . . . , Ck+l), considering all possible external restrictions between the parts, that is, for any two parts i and j define its relationship as completely adjacent (any two vertices between the i and j sets are adjacents), completely non-adjacent (any two vertices between the i and j sets are not adjacents) or without restrictions (there is no restriction between sets). This problem of graphs-(k, l) with external constraint can be represented in a matrix that identifies the constraints of the sets, being internal or external. The problem is called the M-partition problem. In this project, we characterize the M-partitionable cographs in terms of obstructions. An obstruction of a graph G is a subgraph of G that it does not M-partitionable, that is, that does not support such a partition. Therefore, G is also not M-partitionable. In this work, we are interested in determining the minimum obstructions for all cases of possible external restrictions involving the clique and no external restrictions between the independent sets.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Federal Fluminense-
Publicador: dc.publisherNiterói-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCografos-
Palavras-chave: dc.subjectPartição em grafos-
Palavras-chave: dc.subjectM-partição-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectOtimização combinatória (Computação)-
Palavras-chave: dc.subjectAlgoritmo em grafos-
Palavras-chave: dc.subjectCombinação (Matemática)-
Palavras-chave: dc.subjectCographs-
Palavras-chave: dc.subjectGraph Partition-
Palavras-chave: dc.subjectM-partition-
Título: dc.titleCaracterização dos cografos-(3,1) por subgrafos proibidos com restrições externas-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.