Por favor, use este identificador para citar o enlazar este ítem: https://rd.uffs.edu.br/handle/prefix/3354
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.contributor.advisor1Wuerges, Emílio-
dc.contributor.advisor2Zatesko, Leandro Miranda-
dc.creatorVieira, Éverton de Assis-
dc.date2019-
dc.date.accessioned2020-02-03T13:23:01Z-
dc.date.available2019-
dc.date.available2020-02-03T13:23:01Z-
dc.date.issued2019-
dc.identifier.urihttps://rd.uffs.edu.br/handle/prefix/3354-
dc.description.abstractSnarks 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.resumoOs 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.provenanceSubmitted 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.provenanceApproved 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.provenanceMade available in DSpace on 2020-02-03T13:23:01Z (GMT). No. of bitstreams: 1 VIEIRA.pdf: 3343825 bytes, checksum: 342f9bb63b35a7e0d248e3605beac7e1 (MD5) Previous issue date: 2019en
dc.languageporpt_BR
dc.publisherUniversidade Federal da Fronteira Sulpt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentCampus Chapecópt_BR
dc.publisher.initialsUFFSpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmospt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectCiência da computaçãopt_BR
dc.titleGrafos d-Snarkspt_BR
dc.typeMonografiapt_BR
Aparece en las colecciones: Ciência da Computação

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
VIEIRA.pdf3,27 MBAdobe PDFVisualizar/Abrir
Mostrar el registro sencillo del ítem Recomiende este ítem


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.