A conectividade algébrica de um gráfico G é o segundo menor valor próprio da matriz laplaciana de G. Esse valor próprio é maior que 0 se e somente se G for um gráfico conectado. A magnitude desse valor reflete o quão bem conectado o gráfico geral está.
por exemplo, " adicionar auto-loops " não altera os autovalores laplacianos (especialmente a conectividade algébrica) do gráfico. Porque laplaciano (G) = DA é invariável em relação à adição de auto-loops.
Alguém estudou o efeito de diferentes operações (como a contração da borda) no espectro de laplaciano? você conhece boas referências?
Observação: a definição exata da conectividade algébrica depende do tipo de Laplaciano usado. Para esta pergunta, prefiro usar a definição de Fan Chung na TEORIA DO GRÁFICO ESPECTRAL . Neste livro, Fan Chung utilizou uma versão redimensionada do Laplaciano, eliminando a dependência do número de vértices.
Ajudaria se você fornecer alguma motivação e experiência. Por favor, consulte Como fazer uma boa pergunta? e as perguntas frequentes do site .
Também estou interessado no caso de contração de borda. Passei algum tempo tentando encontrar referências sobre a relação entre autovalores e operações menores, sem sucesso.
— Hsien-Chih Chang # 16/11
Para mim, a motivação parece bastante clara.
Eu segundo Suresh, sabendo como várias operações influenciam o Laplaciano é interessante por si só e esses problemas aparecem em vários contextos.
Operações intuitivas que preservam a conectividade não diminuirão os valores próprios. Por exemplo, adicionar arestas ao gráfico não diminui a conectividade.
Em geral, se H é um subgráfico de um gráfico G, entrelaçando, sabemos que o i-ésimo maior autovalor de Laplaciano de H não é maior que o i-ésimo maior autovalor de Laplacian de G. Uma prova pode ser encontrada na Proposição 3.2. 1 do livro " Spectra of graphs " de Brouwer e Haemers. Observe que a definição de Laplaciano usada no livro não é normalizada; possui graus de nó na diagonal e -1 (ou 0 se não houver aresta) nas entradas fora da diagonal.
Obrigado Chang. Sua resposta é realmente útil para mim. Mas se usarmos a definição de Laplaciano que não é normalizada, muitas das comparações parecem não ter sentido. Por exemplo, temos conectividade algébrica (K10) = 10 e conectividade algébrica (K20) = 20. no entanto, ambos os gráficos são gráficos simples totalmente conectados. Mas se usarmos o Laplaciano normalizado, então NormalizedAlgebraicConnectivity (K10) = NormalizedAlgebraicConnectivity (K20) = 1 e, portanto, a comparação da versão normalizada parece ser mais racional e natural.
@behnam: Eu concordo com você. Mas após a normalização, algumas das propriedades não decrescentes podem diferir. (Say pode-se garantir um rigoroso diminuindo em maiores Laplaciano bordas quando exclusão para os não normalizadas, mas não para os normalizados.)
Θ ( n2)Θ(n2)Θ ( n3)Θ(n3)
@TysonWilliams Você está muito certo. Esse é um dos aspectos teóricos em que os laplacianos normalizados e não normalizados diferem. Ao adicionar arestas, a conectividade algébrica não normalizada sempre aumenta (Fiedler), mas há exemplos (nem muito complicados) que mostram que as arestas adicionadas nos lugares errados podem diminuir a conectividade. Isso é particularmente fácil de ver se você permite pesos na borda.