Alianças defensivas em grafos

Página do item simplificado
dc.contributor.advisor1Barbosa, Rommel Melgaço
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6228227125338610pt_BR
dc.contributor.referee1Barbosa, Rommel Melgaço
dc.contributor.referee2Martins, Wellington Santos
dc.contributor.referee3Tronto, Íris Fabiana de Barcelos
dc.creatorDias, Elisângela Silva
dc.creator.Latteshttp://lattes.cnpq.br/0138908377103572pt_BR
dc.date.accessioned2022-12-26T13:14:04Z
dc.date.available2022-12-26T13:14:04Z
dc.date.issued2010-03-26
dc.description.abstractA defensive alliance in graph G = (V,E) is a set of vertices S ⊆V satisfying the condition that every vertex v ∈ S has at most one more neighbor in V − S than S. Due to this type of alliance, the vertices in S together defend themselves to the vertices in V − S. This dissertation introduces the basic concepts for the understanding of alliances in graphs, along with a variety of alliances and their numbers and provides some mathematical properties for these alliances, focusing mainly on defensive alliances in graphs. It shows theorems, corollaries, lemmas, propositions and observations with appropriate proofs with respect to the minimum degree of a graph G δ(G), the maximum degree ∆(G), the algebraic connectivity µ, the total dominanting set γt(G), the eccentricity, the edge connectivity λ(G), the chromatic number χ(G), the (vertex) independence number β0(G), the vertex connectivity κ(G), the order of the largest clique ω(G) and the domination number γ(G). It also shows a generalization of defensive alliances, called defensive k alliance, and the definition and properties of a security set in G. A secure set S ⊆ V of graph G = (V,E) is a set whose every nonempty subset can be successfully defended of an attack, under appropriate definitions of “attack” and “defence”.eng
dc.description.provenanceSubmitted by Leandro Machado (leandromachado@ufg.br) on 2022-12-19T20:52:32Z No. of bitstreams: 2 Dissertação - Elisângela Silva Dias - 2010.pdf: 1096923 bytes, checksum: 026c8ba9fccad23ae84e062cc79de4b3 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2022-12-26T13:14:04Z (GMT) No. of bitstreams: 2 Dissertação - Elisângela Silva Dias - 2010.pdf: 1096923 bytes, checksum: 026c8ba9fccad23ae84e062cc79de4b3 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceMade available in DSpace on 2022-12-26T13:14:04Z (GMT). No. of bitstreams: 2 Dissertação - Elisângela Silva Dias - 2010.pdf: 1096923 bytes, checksum: 026c8ba9fccad23ae84e062cc79de4b3 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Previous issue date: 2010-03-26en
dc.description.resumoUma aliança defensiva no grafo G = (V,E) é um conjunto de vértices S ⊆ V satisfazendo a condição de que todo vértice v ∈ S tem no máximo um vizinho a mais em V −S que em S. Devido a este tipo de aliança, os vértices em S juntam para se defenderem dos vértices em V −S. Nesta dissertação, são introduzidos os conceitos básicos para o entendimentos das alianças em grafos, junto com uma variedade de tipos de alianças e seus respectivos números, bem como são fornecidas algumas propriedades matemáticas para estas alian ças, focando principalmente nas alianças defensivas em grafos. Apresentamos teoremas, corolários, lemas, proposições e observações com as devidas provas com relação ao grau mínimo de um grafo G δ(G), ao grau máximo ∆(G), à conectividade algébrica µ, ao con junto dominante total γt(G), à excentricidade, à conectividade de arestas λ(G), ao número cromático χ(G), ao número de independência (de vértices) β0(G), à conectividade de vér tices κ(G), à ordem da maior clique ω(G) e ao número de dominação γ(G). Também é mostrada a generalização de alianças defensivas, chamada k-aliança defensiva, e a defi nição e propriedades de um conjunto seguro em G. Um conjunto seguro S ⊆ V do grafo G = (V,E) é um conjunto no qual todo subconjunto não-vazio pode ser defendido com sucesso de um ataque, sob as definições apropriadas de “ataque” e “defesa”.pt_BR
dc.identifier.citationDIAS, E. S. Alianças Defensivas em Grafos. 2010. 105 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2010.pt_BR
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/12521
dc.languageporpt_BR
dc.publisherUniversidade Federal de Goiáspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Informática - INF (RMG)pt_BR
dc.publisher.initialsUFGpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)pt_BR
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectAlianças em grafospor
dc.subjectAlianças defensivaspor
dc.subjectConjuntos segurospor
dc.subjectAlliances in graphseng
dc.subjectDefensive allianceseng
dc.subjectSecure setseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOpt_BR
dc.titleAlianças defensivas em grafospt_BR
dc.title.alternativeDefensive alliance in graphseng
dc.typeDissertaçãopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Elisângela Silva Dias - 2010.pdf
Tamanho:
1.05 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)