Por favor, use este identificador para citar o enlazar este ítem:
https://rd.uffs.edu.br/handle/prefix/3354| Type: | Monografia |
| Título : | Grafos d-Snarks |
| Author: | Vieira, Éverton de Assis |
| First advisor: | Wuerges, Emílio |
| metadata.dc.contributor.advisor2: | Zatesko, Leandro Miranda |
| Resume: | 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. |
| Resumen : | 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. |
| Palabras clave : | Algoritmos Teoria dos grafos Ciência da computação |
| Language: | por |
| Country: | Brasil |
| Editorial : | Universidade Federal da Fronteira Sul |
| Acronym of the institution: | UFFS |
| College, Institute or Department: | Campus Chapecó |
| Type of Access: | Acesso Aberto |
| URI : | https://rd.uffs.edu.br/handle/prefix/3354 |
| Fecha de publicación : | 2019 |
| Aparece en las colecciones: | Ciência da Computação |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| VIEIRA.pdf | 3,27 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.