• Portal do Governo Brasileiro

Plataforma Sucupira

Dados do Trabalhos de Conclusão

UNIVERSIDADE FEDERAL DE CIÊNCIA E INOVAÇÃO DO RIO DE JANEIRO
Engenharia de Produção e Sistemas (31022014001P4)
PERTURBAÇÕES EM GRAFOS E SEUS EFEITOS SOBRE A CONECTIVIDADE ALGÉBRICA
MARCIA BENGIO DE ALBUQUERQUE
DISSERTAÇÃO
24/08/2012

Neste trabalho, determinamos as variações sofridas pela conectividade algébrica de um grafo, um parâmetro espectral, denotado por a(G), ao aplicarmos a operação de remoção de um vértice nos grafos das famílias split completo, abacaxi, caminho completo, dupla estrela e em grafos resultantes das operações 1-soma, 2-soma e ponte de ligação entre grafos completos. A função utilizada para medir esta variação é dada por φ(v) = a(G) – a(G|v), onde G|v é o grafo obtido de G pela remoção do vértice v e de todas as suas arestas incidentes. Um artigo recente de autoria de Kirkland estabeleceu condições necessárias e suficientes para G tal que φ(v) = 1 e, como consequência desse resultado, mostrou que, se G tem um vértice universal v e este vértice é removido, tem-se φ(v) = 1. A partir desse fato, o autor levantou a seguinte questão: "O que podemos dizer sobre φ(v) se o grau do vértice v é (n – 2)?” Nesse estudo, resolvemos parcialmente esta questão e obtivemos condições necessárias para um grafo G tal que φ(v) = 0 quando v tem grau (n – 2). Estabelecemos ainda duas conjecturas acerca da função φ(v) quando v tem grau (n – 2).

Grafos;Conectividade Algébrica;Perturbações
In this work, we consider the operation of a vertex removal and its effects to the algebraic connectivity of a graph, that is a spectral parameter denoted by a(G). That operation is applied to some families of graphs, such that complete split, pineapple, path-complete, double star, 1-sum and 2-sum graphs, and linking bridge between complete graphs. We used the function φ(v) = a(G) – a(G|v) to evaluate the algebraic connectivity variation when G|v is the graph obtained from G by removing the vertex v and all of its incident edges. A recent paper authored by Kirkland establishes necessary and sufficient conditions for G such that φ(v) = 1 and as a consequence of that result, he also shows that if G has a universal vertex v , then φ (v) = 1. From this fact, Kirkland has risen the question: "What can we say about φ(v) if vertex degree of v is (n - 2)?" Here, we partially solve this problem obtaning a necessary condition to a graph G such that φ(v) = 0 when v is of degree (n - 2). Also , we state two conjectures to φ(v) when v is of degree (n - 2).
Graphs;Algebraic Connectivity;Disturbances
1
108
PORTUGUES
UNIVERSIDADE FEDERAL DE CIÊNCIA E INOVAÇÃO DO RIO DE JANEIRO
O trabalho possui divulgação autorizada
336_Marcia Bengio de Albuquerque.pdf

Contexto

TECNOLOGIA, GESTÃO E INOVAÇÃO
DESENVOLVIMENTO DE TECNOLOGIAS INTEGRADAS A PRODUTOS E PROCESSOS
TEORIA ESPECTRAL DE GRAFOS E APLICAÇÕES

Banca Examinadora

CARLA SILVA OLIVEIRA
DOCENTE - PERMANENTE
Sim
Nome Categoria
EDUARDO BEZERRA DA SILVA Participante Externo
LEONARDO SILVA DE LIMA Docente - PERMANENTE
CLAUDIA MARCELA JUSTEL Participante Externo
REINALDO CASTRO SOUZA Participante Externo

Vínculo

Servidor Público
Empresa Pública ou Estatal
Ensino e Pesquisa
Sim
Plataforma Sucupira
Capes UFRN RNP Ministério da Educação Governo Federal
  • Compatibilidade
  • . . .
  • Versão do sistema: 3.88.17
  • Copyright 2022 Capes. Todos os direitos reservados.

Nós usamos cookies para melhorar sua experiência de navegação no portal. Ao utilizar o gov.br, você concorda com a política de monitoramento de cookies. Para ter mais informações sobre como isso é feito, acesse Política de cookies.Se você concorda, clique em ACEITO.

Politica de Cookies

O que são cookies?

Cookies são arquivos salvos em seu computador, tablet ou telefone quando você visita um site.Usamos os cookies necessários para fazer o site funcionar da melhor forma possível e sempre aprimorar os nossos serviços. Alguns cookies são classificados como necessários e permitem a funcionalidade central, como segurança, gerenciamento de rede e acessibilidade. Estes cookies podem ser coletados e armazenados assim que você inicia sua navegação ou quando usa algum recurso que os requer.

Cookies Primários

Alguns cookies serão colocados em seu dispositivo diretamente pelo nosso site - são conhecidos como cookies primários. Eles são essenciais para você navegar no site e usar seus recursos.
Temporários
Nós utilizamos cookies de sessão. Eles são temporários e expiram quando você fecha o navegador ou quando a sessão termina.
Finalidade
Estabelecer controle de idioma e segurança ao tempo da sessão.

Cookies de Terceiros

Outros cookies são colocados no seu dispositivo não pelo site que você está visitando, mas por terceiros, como, por exemplo, os sistemas analíticos.
Temporários
Nós utilizamos cookies de sessão. Eles são temporários e expiram quando você fecha o navegador ou quando a sessão termina.
Finalidade
Coletam informações sobre como você usa o site, como as páginas que você visitou e os links em que clicou. Nenhuma dessas informações pode ser usada para identificá-lo. Seu único objetivo é possibilitar análises e melhorar as funções do site.

Você pode desabilitá-los alterando as configurações do seu navegador, mas saiba que isso pode afetar o funcionamento do site.

Chrome

Firefox

Microsoft Edge

Internet Explorer