Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Bravo, Raquel Francisco | - |
Autor(es): dc.contributor | Nogueira, Loana Tito | - |
Autor(es): dc.contributor | Souza, Uéverton dos Santos | - |
Autor(es): dc.creator | Cruz, Maria Luíza López da | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:46:43Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:46:43Z | - |
Data de envio: dc.date.issued | 2021-12-22 | - |
Data de envio: dc.date.issued | 2021-12-22 | - |
Data de envio: dc.date.issued | 2020 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/24062 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/757293 | - |
Descrição: dc.description | Este 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.description | This 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Federal Fluminense | - |
Publicador: dc.publisher | Niterói | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Cografos | - |
Palavras-chave: dc.subject | Partição em grafos | - |
Palavras-chave: dc.subject | M-partição | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Otimização combinatória (Computação) | - |
Palavras-chave: dc.subject | Algoritmo em grafos | - |
Palavras-chave: dc.subject | Combinação (Matemática) | - |
Palavras-chave: dc.subject | Cographs | - |
Palavras-chave: dc.subject | Graph Partition | - |
Palavras-chave: dc.subject | M-partition | - |
Título: dc.title | Caracterização dos cografos-(3,1) por subgrafos proibidos com restrições externas | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: