Uma caracterização de grafos imersíveis

Página do item simplificado
dc.contributor.authorCortez Morales, Walter Julio [UNESP]
dc.contributor.institutionUniversidade Estadual Paulista (Unesp)
dc.date.accessioned2014-05-20T14:01:48Z
dc.date.available2014-05-20T14:01:48Z
dc.date.issued2005-04-01
dc.description.abstractEste trabalho é motivado pelo resultado de Berge, que é uma generalização do teorema de Tutte o qual expressamos na forma: Dado o grafo G de ordem |V(G)| eni(G) o número de arestas em um emparelhamento máximo, existe um conjunto X de vértices de G tal que |V(G)|+|X| - ômega(G\X) - 2n(G)=0, onde ômega(G\X) é o número de componentes de ordem ímpar de G\X. Tal expressão chamamos a equação de Tutte-Berge associada de G, e escrevemos simplesmente T(G; X)=0. Os grafos podem ser classificados a partir das soluções da equação de Tutte-Berge. Um grafo G é chamado imersível se, e somente se, T(G; X)=0 possui pelo menos um conjunto solução não vazio de vértices, e G é denominado não imersível se, e somente se, o conjunto vazio é a única solução de T(G; X)=0. O resultado principal deste artigo é a caracterização de grafos imersíveis pelos conjuntos antifatores completos, além disso, provamos que os grafos fatoráveis estão contidos na classe dos imersíveis.pt
dc.description.abstractThis paper is motivated by the result of Berge who generalized Tutte's theorem which states that: Given a graph G with |V(G)| vertices and nu(G) the number of edges in a maximum matching, then there is a subset X Í V(G) such that |V(G)|+|X| - omega(G\X) - 2n( G)=0, where omega(G\X) denotes the number of odd components of G\X, such expression is called Tutte-Berge's equation associated to G, denoted by T(G;X)=0. These graphs are then studied from solutions of T(G;X)=0. A graph G is called immersible graph if and only if, its associated equation T(G;X)=0 has at least one non-emptyset for X, and it is non-immersible graph if and only if, the unique solution to T(G;X)=0 is the emptyset. The main result of this work is the characterization of immersible graphs via complete antifactor sets, moreover we prove that factorizable graphs are included in the class of immersible graphs.en
dc.description.affiliationUniversidade Estadual Paulista IBILCE Depto. de Ciências de Computação e Estatística
dc.description.affiliationUnespUniversidade Estadual Paulista IBILCE Depto. de Ciências de Computação e Estatística
dc.format.extent1-9
dc.identifierhttp://dx.doi.org/10.1590/S0101-74382005000100001
dc.identifier.citationPesquisa Operacional. Sociedade Brasileira de Pesquisa Operacional, v. 25, n. 1, p. 1-9, 2005.
dc.identifier.doi10.1590/S0101-74382005000100001
dc.identifier.fileS0101-74382005000100001.pdf
dc.identifier.issn0101-7438
dc.identifier.scieloS0101-74382005000100001
dc.identifier.urihttp://hdl.handle.net/11449/21811
dc.language.isopor
dc.publisherSociedade Brasileira de Pesquisa Operacional
dc.relation.ispartofPesquisa Operacional
dc.relation.ispartofsjr0,365
dc.rights.accessRightsAcesso aberto
dc.sourceSciELO
dc.subjectgrafospt
dc.subjectimersívelpt
dc.subjectantifator completopt
dc.subjectfatorávelpt
dc.subjectequação de Tutte-Bergept
dc.subjectgraphsen
dc.subjectimmersibleen
dc.subjectcomplete antifactoren
dc.subjectfactorizableen
dc.subjectTutte-Berge's equationen
dc.titleUma caracterização de grafos imersíveispt
dc.typeArtigo
unesp.campusUniversidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Pretopt

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
S0101-74382005000100001.pdf
Tamanho:
258.97 KB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 2 de 2
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:

Coleções

Artigos - Ciência da Computação e Estatística - IBILCE