Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima
leonardo.delima@ufpr.br
Universidade Federal do Paraná
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Grafo G
Matrizes associadas
ao grafo G
Informações
estruturais
do grafo
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Teoria Espectral de Grafos
Área de pesquisa que objetiva obter informações sobre a estrutura da rede a partir dos autovalores e autovetores de matrizes associadas a grafos.
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Aplicações
Page Rank
The PageRank Citation Ranking: Bringing Order to the Web, Technical Report Stanford University, 1998.
Larry Page e Sergey Brin
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Particionamento de grafos é um tema importante da
otimização combinatória que surge de muitos problemas
práticos.
Colocação de comerciais de televisão em intervalos de
programa (Bollapragada, S., Garbiras, M.: Scheduling
commercials on broadcast television.
Oper. Res. 52(3), 337– 345 (2004))
Aplicações
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Matriz de Adjacência do grafo G
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima | UFPR
Autoequação
autovetor
autovalor
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Propriedades de A(G)
Autovalores são reais
Ortogonalmente diagonalizável
Matriz de Adjacência
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Polinômio Característico de A(G)
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Polinômio característico de A(G):
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Consiste em determinar a k-partição do conjunto de vértices V tal que a soma dos pesos de arestas que conectam vértices em diferentes partes seja o maior possível.
Problema do k-corte máximo (PkCM)
Problema do k-corte
máximo (PkCM)
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Problema do k-corte máximo (PkCM)
Formulação Matemática
Variáveis de decisão
Dados de Entrada
Grafo: G com os pesos das arestas
Número de partições: k
Restrição
Cada vértice deve estar em somente
uma partição
Função Objetivo
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Problema do k-corte máximo (PkCM)
Formulação Matemática
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Cota Espectral para o PkCM
Vladimir Nikiforov
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Cota Espectral para o PkCM
número de
arestas
número de
vértices
Menor autovalor da matrix de adjacência
Problema do k-corte
máximo (PkCM)
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Considerações Finais
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
frutífera área com vários problemas em aberto
conexão com problemas combinatórios
Obrigado!
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Explorando conexões entre a
Álgebra Linear e a Teoria de Grafos
Leonardo de Lima
leonardo.delima@ufpr.br
Universidade Federal do Paraná