Use este identificador para citar ou linkar para este item:
https://rd.uffs.edu.br/handle/prefix/3354
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor1 | Wuerges, Emílio | - |
dc.contributor.advisor2 | Zatesko, Leandro Miranda | - |
dc.creator | Vieira, Éverton de Assis | - |
dc.date | 2019 | - |
dc.date.accessioned | 2020-02-03T13:23:01Z | - |
dc.date.available | 2019 | - |
dc.date.available | 2020-02-03T13:23:01Z | - |
dc.date.issued | 2019 | - |
dc.identifier.uri | https://rd.uffs.edu.br/handle/prefix/3354 | - |
dc.description.abstract | Snarks are graphs with peculiar properties. They are related to important conjectures such as the Overfull Conjecture. According to how snarks are defined, we propose in thisworkthed-snarks,whichareasnarkgeneralization. Inthiswork,besidesdefining d-snarks,wepresenttheresultofanexperimentwherein5-regulargraphsweretested in order to find some 5-snark. Although we have not found any 5-snark, we prove that if 5-snarks do not exist, thenP =NP. Also, we prove that, unlessP =NP, there are many 5-snarks, so that the number of 5-snarks cannot be bounded above by a polynomial function. | pt_BR |
dc.description.resumo | Os snarks são grafos com propriedades peculiares. Eles se relacionam com importantesconjecturascomoaConjecturadosGrafosSobrecarregados. Deacordocomaforma como os snarks são definidos, propomos neste trabalho os d-snarks, os quais são uma generalização dos snarks. Neste trabalho, além de definirmos os d-snarks, apresentamosoresultadodeumexperimentonoqualgrafos5-regularesforamtestadosafimde encontrar algum 5-snark. Apesar de não termos encontrado 5-snark algum, demonstramos que se os 5-snarks não existem, então P =NP. Ainda, demonstramos que, a menos queP =NP, existem muitos 5-snarks, de forma que o número de 5-snarks não pode ser limitado superiormente por um função polinomial. | pt_BR |
dc.description.provenance | Submitted by Suelen Spindola Bilhar (suelen.bilhar@uffs.edu.br) on 2019-12-19T20:04:50Z No. of bitstreams: 1 VIEIRA.pdf: 3343825 bytes, checksum: 342f9bb63b35a7e0d248e3605beac7e1 (MD5) | en |
dc.description.provenance | Approved for entry into archive by Franciele Scaglioni da Cruz (franciele.cruz@uffs.edu.br) on 2020-02-03T13:23:01Z (GMT) No. of bitstreams: 1 VIEIRA.pdf: 3343825 bytes, checksum: 342f9bb63b35a7e0d248e3605beac7e1 (MD5) | en |
dc.description.provenance | Made available in DSpace on 2020-02-03T13:23:01Z (GMT). No. of bitstreams: 1 VIEIRA.pdf: 3343825 bytes, checksum: 342f9bb63b35a7e0d248e3605beac7e1 (MD5) Previous issue date: 2019 | en |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal da Fronteira Sul | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Campus Chapecó | pt_BR |
dc.publisher.initials | UFFS | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Algoritmos | pt_BR |
dc.subject | Teoria dos grafos | pt_BR |
dc.subject | Ciência da computação | pt_BR |
dc.title | Grafos d-Snarks | pt_BR |
dc.type | Monografia | pt_BR |
Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
VIEIRA.pdf | 3,27 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.