022-talkOut2

Prévia do material em texto

Aplicações de relações de recorrência em
Teoria Espectral de Grafos.
Vilmar Trevisan
Instituto de Matemática e Estatística, UFRGS, Brasil
Seminários online de Grafos, Algoritmos e Combinatória, 1
de Outubro de 2020
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Belo Horizonte, LAGOS 2019
Que voltem logo tempos como estes!
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Belo Horizonte, LAGOS 2019
Que voltem logo tempos como estes!
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Objetivos da TEG
O que se quer?
Objetivo 1
Associar uma matrix a um grafo e obter informações sobre os
autovalores.
Linear Algebra
Objetivo 2
A partir dos autovalores obter informações estruturais sobre o
grafo.
Spectral Graph Theory
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Objetivos da TEG
O que se quer?
Objetivo 1
Associar uma matrix a um grafo e obter informações sobre os
autovalores.
Linear Algebra
Objetivo 2
A partir dos autovalores obter informações estruturais sobre o
grafo.
Spectral Graph Theory
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Objetivos da TEG
O que se quer?
Objetivo 1
Associar uma matrix a um grafo e obter informações sobre os
autovalores.
Linear Algebra
Objetivo 2
A partir dos autovalores obter informações estruturais sobre o
grafo.
Spectral Graph Theory
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Exemplo
Exemplo 1
A soma dos autovalores ao quadrado é duas vezes o número
de arestas:
n∑
i=1
λ2i = 2m.
Matriz de adjacências
Exemplo 2
O segundo menor autovalor determine a conectividade:
µn−1 > 0 ⇐⇒ G é conexo
Matriz Laplaciana
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Exemplo
Exemplo 1
A soma dos autovalores ao quadrado é duas vezes o número
de arestas:
n∑
i=1
λ2i = 2m.
Matriz de adjacências
Exemplo 2
O segundo menor autovalor determine a conectividade:
µn−1 > 0 ⇐⇒ G é conexo
Matriz Laplaciana
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Contribuição do Grupo de Pesquisa
Temos obtido algoritmos eficientes para matrizes M
associados a um grafos que determinam uma matriz diagonal
que é congruente a M .
Algoritmos que são O(n) e tem importância per se em teoria
de matrizes.
Aplicações não triviais tem sido obtidas em TEG.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Contribuição do Grupo de Pesquisa
Temos obtido algoritmos eficientes para matrizes M
associados a um grafos que determinam uma matriz diagonal
que é congruente a M .
Algoritmos que são O(n) e tem importância per se em teoria
de matrizes.
Aplicações não triviais tem sido obtidas em TEG.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Contribuição do Grupo de Pesquisa
Temos obtido algoritmos eficientes para matrizes M
associados a um grafos que determinam uma matriz diagonal
que é congruente a M .
Algoritmos que são O(n) e tem importância per se em teoria
de matrizes.
Aplicações não triviais tem sido obtidas em TEG.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Tree width
Lembro que Carlos Hoppen no segundo seminário desta série
falou sobre isso
Mas há outros algoritmos especializados para classes de
grafos
Pessoas que fizeram algoritmos de localização:
Rodrigo Braga, Renata Del-Vecchio, Martin Furer, Carlos
Hoppen, David Jacobs, Virginia Rodrigues, Fernando Tura,
Cybele Vinagre.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Nosso objetivo - Our view
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Nosso objetivo - Our view
Vamos falar sobre o avo deste algoritmo.
Árvores
Ver como relações de recorrência aparecem quando o algoritmo
é aplicado a árvores e mostrar algumas aplicações.
Aplicações em TEG
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Nosso objetivo - Our view
Vamos falar sobre o avo deste algoritmo.
Árvores
Ver como relações de recorrência aparecem quando o algoritmo
é aplicado a árvores e mostrar algumas aplicações.
Aplicações em TEG
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Nosso objetivo - Our view
Vamos falar sobre o avo deste algoritmo.
Árvores
Ver como relações de recorrência aparecem quando o algoritmo
é aplicado a árvores e mostrar algumas aplicações.
Aplicações em TEG
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência SecundaRecorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
A is real and symmetric =⇒
{
A is diagonalizable
A has an associated graph
vi adjacent to vj if and only if ai,j 6= 0.
L2 =
 3 −1 0−1 4 −1
0 −1 1
 .
Has an underlying graph
3
4 1
−1
−1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
A is real and symmetric =⇒
{
A is diagonalizable
A has an associated graph
vi adjacent to vj if and only if ai,j 6= 0.
L2 =
 3 −1 0−1 4 −1
0 −1 1
 .
Has an underlying graph
3
4 1
−1
−1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
A is real and symmetric =⇒
{
A is diagonalizable
A has an associated graph
vi adjacent to vj if and only if ai,j 6= 0.
L2 =
 3 −1 0−1 4 −1
0 −1 1
 .
Has an underlying graph
3
4 1
−1
−1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
A is real and symmetric =⇒
{
A is diagonalizable
A has an associated graph
vi adjacent to vj if and only if ai,j 6= 0.
L2 =
 3 −1 0−1 4 −1
0 −1 1
 .
Has an underlying graph
3
4 1
−1
−1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
• Duas matrizes A e B são ditas similares (ou semelhantes)
se existe uma matriz invertível M tal que A = MBM−1.
• Duas matrizes A e B são ditas congruentes se existe uma
matriz invertível N tal que A = NBNT .
Theorem
Matrizes similares têm os mesmos autovalores.
Theorem
(Lei da Inércia de Sylvester1852) Matrizes simétricas
congruentes têm o mesmo número de autovalores positivos, o
mesmo número de autovalores negativos e o mesmo número
de autovalores nulos.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our setting
• Duas matrizes A e B são ditas similares (ou semelhantes)
se existe uma matriz invertível M tal que A = MBM−1.
• Duas matrizes A e B são ditas congruentes se existe uma
matriz invertível N tal que A = NBNT .
Theorem
Matrizes similares têm os mesmos autovalores.
Theorem
(Lei da Inércia de Sylvester1852) Matrizes simétricas
congruentes têm o mesmo número de autovalores positivos, o
mesmo número de autovalores negativos e o mesmo número
de autovalores nulos.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Our goal
Design a O(n) algorithm Diagonalize, so that on input A, an
n× n matrix, and x ∈ R, Diagonalize(A, x) outputs a diagonal
matrix D congruent to Bx = A+ xI.
Let D = Diagonalize(A,−x).
• The number of positive entries of D is the number of
eigenvalues of A greater than x.
• The number of negative entries of D is the number of
eigenvalues of A less than x.
• The number of zero entries of D is the multiplicity of x.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Application
Corollary
The number of eigenvalues in an interval (α, β], counting
multiplicities, is the number of positive entries in the
diagonalization of B−α, minus the number of positive entries in
the diagonalization of B−β.
... in two calls to Diagonalize, we can determine how many
eigenvalues lie in an interval.
We call this locate the eigenvalues of the matrix.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Application
Corollary
The number of eigenvalues in an interval (α, β], counting
multiplicities, is the number of positive entries in the
diagonalization of B−α, minus the number of positive entries in
the diagonalization of B−β.
... in two calls to Diagonalize, we can determine how many
eigenvalues lie in an interval.
We call this locate the eigenvalues of the matrix.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Application
Corollary
The number of eigenvalues in an interval (α, β], counting
multiplicities, is the number of positive entries in the
diagonalization of B−α, minus the number of positive entries in
the diagonalization of B−β.
... in two calls to Diagonalize, we can determine how many
eigenvalues lie in an interval.
We call this locate the eigenvalues of the matrix.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Main features
We Diagonalize A+ xI. Keeping in mind:
WHY
Sylvester’s Law of Inertia’1852: The number of positive, neg-
ative and zero eigenvalues of D is the number of eigenvalues
greater than, less than and equal to x, respectively.
Congruence
HOW
The algorithm performs elementary row operations, immediately
followed by the corresponding column operation.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Main features
We Diagonalize A+ xI. Keeping in mind:
WHY
Sylvester’s Law of Inertia’1852: The number of positive, neg-
ative and zero eigenvalues of D is the number of eigenvalues
greater than, less than and equal to x, respectively.
Congruence
HOW
The algorithm performs elementary row operations, immediately
followed by the corresponding column operation.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Main features
We Diagonalize A+ xI. Keeping in mind:
WHY
Sylvester’s Law of Inertia’1852: The number of positive,neg-
ative and zero eigenvalues of D is the number of eigenvalues
greater than, less than and equal to x, respectively.
Congruence
HOW
The algorithm performs elementary row operations, immediately
followed by the corresponding column operation.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The tree algorithm - 2011
David Jacos
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Usamos ideias de várias algoritmos que obtivemos desde 1995
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The tree algorithm
Let A be a matrix whose underlying tree is such that vertices
are orderedso that if vi is child of vj then i < j.
We store each vertex v, its diagonal value d(v).
Initially, d(v) = d(v) + x, for all v ∈ V .
The algorithm processes the vertices bottom-up, performing
Gaussian elimination.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The tree algorithm
Let A be a matrix whose underlying tree is such that vertices
are orderedso that if vi is child of vj then i < j.
We store each vertex v, its diagonal value d(v).
Initially, d(v) = d(v) + x, for all v ∈ V .
The algorithm processes the vertices bottom-up, performing
Gaussian elimination.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The tree algorithm
Let A be a matrix whose underlying tree is such that vertices
are orderedso that if vi is child of vj then i < j.
We store each vertex v, its diagonal value d(v).
Initially, d(v) = d(v) + x, for all v ∈ V .
The algorithm processes the vertices bottom-up, performing
Gaussian elimination.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The tree algorithm
Let A be a matrix whose underlying tree is such that vertices
are orderedso that if vi is child of vj then i < j.
We store each vertex v, its diagonal value d(v).
Initially, d(v) = d(v) + x, for all v ∈ V .
The algorithm processes the vertices bottom-up, performing
Gaussian elimination.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Matrices of Trees
vi is a child of vj :

...
...
. . . ajj . . . `
...
...
. . . ` . . . aii . . .
...

Perform Rj ← Rj − `aiiRi
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Matrices of Trees
vi is a child of vj :

...
...
. . . ajj . . . `
...
...
. . . ` . . . aii . . .
...

Perform Rj ← Rj − `aiiRi
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
if aii 6= 0, after Rj ← Rj − `aiiRi
...
...
. . . ajj − `
2
aii
. . . 0
...
...
. . . ` . . . aii . . .
...

Perform Cj ← Cj − `aiiCi
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
if aii 6= 0, after Rj ← Rj − `aiiRi
...
...
. . . ajj − `
2
aii
. . . 0
...
...
. . . ` . . . aii . . .
...

Perform Cj ← Cj − `aiiCi
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
After Cj ← Cj − laiiCi
...
...
. . . ajj − `
2
aii
. . . 0
...
...
. . . 0 . . . aii . . .
...

V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
The ordering of the vertices avoids fill-in.
Assuming all children c of node vj have nonzero diagonal
values, then collectively
d(v)−
∑
c∈C
`2c
d(c)
. (1)
A little more work needs to be done when some of the children
have value zero.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
The ordering of the vertices avoids fill-in.
Assuming all children c of node vj have nonzero diagonal
values, then collectively
d(v)−
∑
c∈C
`2c
d(c)
. (1)
A little more work needs to be done when some of the children
have value zero.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
The ordering of the vertices avoids fill-in.
Assuming all children c of node vj have nonzero diagonal
values, then collectively
d(v)−
∑
c∈C
`2c
d(c)
. (1)
A little more work needs to be done when some of the children
have value zero.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
Child with zero value
d(vj) = −12 and d(vi) = 2.
If vj is not the root, then the edge incident to its parent vk is
removed. All other children of vj are unaffected, including those
that might also have zero values.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana:terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Trees
Child with zero value
d(vj) = −12 and d(vi) = 2.
If vj is not the root, then the edge incident to its parent vk is
removed. All other children of vj are unaffected, including those
that might also have zero values.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Diagonalize tree
Algorithm Diagonalize(T, x)
initialize d(v) := d(v) + x, for all vertices v
for i = 1 to n
if vk is a leaf then continue
else if d(c) 6= 0 for all children c of vk then
d(vk) := d(vk)−
∑ `2c
d(c), summing over children
else
select one child vj of vk for which d(vj) = 0
d(vk) := −12
d(vj) := 2
if vk has a parent vl, remove the edge vkvl.
end loop
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example - Adjacency
x = 1, dv = −1
The algorithm is executed the tree.
Diagonal values of D are stored at node values.
Choose an arbitrary node as a root.
-1
-1 -1 -1
-1-1
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example - Adjacency
x = 1, dv = −1
The algorithm is executed the tree.
Diagonal values of D are stored at node values.
Choose an arbitrary node as a root.
-1
-1 -1 -1
-1-1
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example - Adjacency
x = 1, dv = −1
The algorithm is executed the tree.
Diagonal values of D are stored at node values.
Choose an arbitrary node as a root.
-1
-1 -1 -1
-1-1
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example - Adjacency
x = 1, dv = −1
The algorithm is executed the tree.
Diagonal values of D are stored at node values.
Choose an arbitrary node as a root.
-1
-1 -1 -1
-1-1
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Leaves are processed. Nodes whose children are all processed
may be processed.
If all children values of v are different from zero, then
a(v) = a(v)−
∑
c a(c):
-1
-1 -1 -1
-1-1
-1 -1
-1
-1 -1 -1
00
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Leaves are processed. Nodes whose children are all processed
may be processed.
If all children values of v are different from zero, then
a(v) = a(v)−
∑
c a(c):
-1
-1 -1 -1
-1-1
-1 -1
-1
-1 -1 -1
00
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Leaves are processed. Nodes whose children are all processed
may be processed.
If all children values of v are different from zero, then
a(v) = a(v)−
∑
c a(c):
-1
-1 -1 -1
-1-1
-1 -1
-1
-1 -1 -1
00
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Leaves are processed. Nodes whose children are all processed
may be processed.
If all children values of v are different from zero, then
a(v) = a(v)−
∑
c a(c):
-1
-1 -1 -1
-1-1
-1 -1
-1
-1 -1 -1
00
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
If some child of v is zero, then
1. that child gets 2
2.a(v) = −1/2
3. If v has a parent, delete its edge.
-1
-1 -1 -1
00
-1 -1
-1
-1 -1/2 -1/2
22
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
If some child of v is zero, then
1. that child gets 2
2.a(v) = −1/2
3. If v has a parent, delete its edge.
-1
-1 -1 -1
00
-1 -1
-1
-1 -1/2 -1/2
22
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
If some child of v is zero, then
1. that child gets 2
2.a(v) = −1/2
3. If v has a parent, delete its edge.
-1
-1 -1 -1
00
-1 -1
-1
-1 -1/2 -1/2
22
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
If some child of v is zero, then
1. that child gets 2
2.a(v) = −1/2
3. If v has a parent, delete its edge.
-1
-1 -1 -1
00
-1 -1
-1
-1 -1/2 -1/2
22
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
If some child of v is zero, then
1. that child gets 2
2.a(v) = −1/2
3. If v has a parent, delete its edge.
-1
-1 -1 -1
00
-1 -1
-1
-1 -1/2 -1/2
22
-1 -1
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Finally, we process the root:
0
-1 -1/2 -1/2
22
-1 -1
There are 5 eigenvalues smaller than 1, 2 eigenvalues larger
than 1 and 1 is a simple eigenvalue.
V. Trevisan Recorrências emTEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
An example
Finally, we process the root:
0
-1 -1/2 -1/2
22
-1 -1
There are 5 eigenvalues smaller than 1, 2 eigenvalues larger
than 1 and 1 is a simple eigenvalue.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Aplicação
Comparando o índice de duas árvores
Aqui a matriz pode ser qualquer. O índice é o maior autovalor,
que é o raio espectral, que é simples. Considera árvore T e T ′.
Apply the algorithm to T with the index λ1(T )
• All but one value is negative
• There is a zero value
• This happens at the root
Apply the algorithm to T ′ with the same λ = −λ1(T ) of T and
• if all values are negative then λ1(T ′) < λ1(T )
• If all but one value is negative and one is positive, then
λ1(T
′) < λ1(T ).
V. TrevisanRecorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
O desafio é que os índice λ1(T ) ou λ1(T ′) são desconhecidos.
Essa ideia simples pode funcionar se as árvores T e T ′ são
próximas
E se tivermos alguma ferramenta analítica (não numérica)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
O desafio é que os índice λ1(T ) ou λ1(T ′) são desconhecidos.
Essa ideia simples pode funcionar se as árvores T e T ′ são
próximas
E se tivermos alguma ferramenta analítica (não numérica)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
O desafio é que os índice λ1(T ) ou λ1(T ′) são desconhecidos.
Essa ideia simples pode funcionar se as árvores T e T ′ são
próximas
E se tivermos alguma ferramenta analítica (não numérica)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Primeira Recorrência
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Digamos que A seja a matriz de adjacências e λ o raio
espectral de A
z1 z2 zr dvn
Note z1 = −λ, z2 = −λ− 1z1 , z3 = −λ−
1
z2
. Em geral
obtemos a seguinte recorrência:{
z1 = −λ
zi = −λ− 1zi−1 , i = 2, . . . , k.
(2)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Primeira Recorrência
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Digamos que A seja a matriz de adjacências e λ o raio
espectral de A
z1 z2 zr dvn
Note z1 = −λ, z2 = −λ− 1z1 , z3 = −λ−
1
z2
. Em geral
obtemos a seguinte recorrência:{
z1 = −λ
zi = −λ− 1zi−1 , i = 2, . . . , k.
(2)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Primeira Recorrência
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Digamos que A seja a matriz de adjacências e λ o raio
espectral de A
z1 z2 zr dvn
Note z1 = −λ, z2 = −λ− 1z1 , z3 = −λ−
1
z2
. Em geral
obtemos a seguinte recorrência:{
z1 = −λ
zi = −λ− 1zi−1 , i = 2, . . . , k.
(2)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Primeira Recorrência
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Digamos que A seja a matriz de adjacências e λ o raio
espectral de A
z1 z2 zr dvn
Note z1 = −λ, z2 = −λ− 1z1 , z3 = −λ−
1
z2
. Em geral
obtemos a seguinte recorrência:{
z1 = −λ
zi = −λ− 1zi−1 , i = 2, . . . , k.
(2)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
starlikes=partitions
Elismar Oliveira and Dragan Stevanovic
Estudando esta recorrência, conseguimos determinar um
ordenamento total pelo índice das starlikes trees.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
starlikes=partitions
Elismar Oliveira and Dragan Stevanovic
Estudando esta recorrência, conseguimos determinar um
ordenamento total pelo índice das starlikes trees.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
starlike = partition
A starlike with n vertices and r rays may be represented by a
partition of n− 1 in r parts.
c
Uma starlike com 5 raios e 15 vértices.
Pode ser representado por [1, 2, 3, 3, 5]
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
starlike = partition
A starlike with n vertices and r rays may be represented by a
partition of n− 1 in r parts.
c
Uma starlike com 5 raios e 15 vértices.
Pode ser representado por [1, 2, 3, 3, 5]
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
starlike = partition
A starlike with n vertices and r rays may be represented by a
partition of n− 1 in r parts.
c
Uma starlike com 5 raios e 15 vértices.
Pode ser representado por [1, 2, 3, 3, 5]
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The result
The order by index is the same as the lexicographic order of the
partitions
Oliveira, Stevanovic, T., LAMA, 2018
Given n ≥ 3, the smallest partition of n− 1 is [1, 1, n− 3],
whereas the largest is [1, 1, . . . , 1]︸ ︷︷ ︸
n−1
Exemplo: n = 8
[1, 1, 5] ≺ [1, 2, 4] ≺ [1, 3, 3] ≺ [2, 2, 3]
≺ [1, 1, 1, 4] ≺ [1, 1, 2, 3] ≺ [1, 2, 2, 2]
≺ [1, 1, 1, 1, 3] ≺ [1, 1, 1, 2, 2] ≺ [1, 1, 1, 1, 1, 2]
≺ [1, 1, 1, 1, 1, 1, 1]
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The result
The order by index is the same as the lexicographic order of the
partitions
Oliveira, Stevanovic, T., LAMA, 2018
Given n ≥ 3, the smallest partition of n− 1 is [1, 1, n− 3],
whereas the largest is [1, 1, . . . , 1]︸ ︷︷ ︸
n−1
Exemplo: n = 8
[1, 1, 5] ≺ [1, 2, 4] ≺ [1, 3, 3] ≺ [2, 2, 3]
≺ [1, 1, 1, 4] ≺ [1, 1, 2, 3] ≺ [1, 2, 2, 2]
≺ [1, 1, 1, 1, 3] ≺ [1, 1, 1, 2, 2] ≺ [1, 1, 1, 1, 1, 2]
≺ [1, 1, 1, 1, 1, 1, 1]
V. Trevisan Recorrências em TEGIntrodução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The result
The order by index is the same as the lexicographic order of the
partitions
Oliveira, Stevanovic, T., LAMA, 2018
Given n ≥ 3, the smallest partition of n− 1 is [1, 1, n− 3],
whereas the largest is [1, 1, . . . , 1]︸ ︷︷ ︸
n−1
Exemplo: n = 8
[1, 1, 5] ≺ [1, 2, 4] ≺ [1, 3, 3] ≺ [2, 2, 3]
≺ [1, 1, 1, 4] ≺ [1, 1, 2, 3] ≺ [1, 2, 2, 2]
≺ [1, 1, 1, 1, 3] ≺ [1, 1, 1, 2, 2] ≺ [1, 1, 1, 1, 1, 2]
≺ [1, 1, 1, 1, 1, 1, 1]
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Francesco Belardo-Elismar Oliveira
A applicação é comparar os índices de alguns pares de
árvores.
Isso determinaria um ordenamento e resolveria uma conjectura
antiga.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Francesco Belardo-Elismar Oliveira
A applicação é comparar os índices de alguns pares de
árvores.
Isso determinaria um ordenamento e resolveria uma conjectura
antiga.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Francesco Belardo-Elismar Oliveira
A applicação é comparar os índices de alguns pares de
árvores.
Isso determinaria um ordenamento e resolveria uma conjectura
antiga.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Segunda recorrência
z1 z2 zr−1
z1
b1 b2 br br+1 dvn
As recorrências que aparecem agora são a mesma zi das
starlikes
Mas também aparece{
b1 = −λ− 1z1
1
zr−1
= zr +
1
λ ,
bi = −λ− 1bi−1 , 2 ≤ i.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Segunda recorrência
z1 z2 zr−1
z1
b1 b2 br br+1 dvn
As recorrências que aparecem agora são a mesma zi das
starlikes
Mas também aparece{
b1 = −λ− 1z1
1
zr−1
= zr +
1
λ ,
bi = −λ− 1bi−1 , 2 ≤ i.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Segunda recorrência
z1 z2 zr−1
z1
b1 b2 br br+1 dvn
As recorrências que aparecem agora são a mesma zi das
starlikes
Mas também aparece{
b1 = −λ− 1z1
1
zr−1
= zr +
1
λ ,
bi = −λ− 1bi−1 , 2 ≤ i.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The result
Analisando recorrências do tipo{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
e {
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 2 ≤ i.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Mostramos, por exemplo que λ1(T6(r)) < λ(T5(r)), onde T5 e
T6 são as seguintes
2r − 1
r
r − 2
Isso permitiu o ordenamento de árvores que têm índice no
intervalo (2,
√
2 +
√
5). Note que 2.05817102727− 2 < 0.06.
Numericamente nenhum método poderia funcionar.
Belardo, Oliveira, T, LAA, 2019.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Mostramos, por exemplo que λ1(T6(r)) < λ(T5(r)), onde T5 e
T6 são as seguintes
2r − 1
r
r − 2
Isso permitiu o ordenamento de árvores que têm índice no
intervalo (2,
√
2 +
√
5). Note que 2.05817102727− 2 < 0.06.
Numericamente nenhum método poderia funcionar.
Belardo, Oliveira, T, LAA, 2019.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Mostramos, por exemplo que λ1(T6(r)) < λ(T5(r)), onde T5 e
T6 são as seguintes
2r − 1
r
r − 2
Isso permitiu o ordenamento de árvores que têm índice no
intervalo (2,
√
2 +
√
5). Note que 2.05817102727− 2 < 0.06.
Numericamente nenhum método poderia funcionar.
Belardo, Oliveira, T, LAA, 2019.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
terceira recorrência
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
terceira recorrência
Matriz Laplaciana
Essa conjectura foi forjada pela Renata Del-Vecchio no Lagos
2009, em Gramado
Conjectura Renata
Pelo menos a metade dos autovalores laplacianos de qualquer
árvore são menores que a média d = 2− 2n
Poucos autovalores grandes e muito são pequenos.
Distribuição
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
terceira recorrência
Matriz Laplaciana
Essa conjectura foi forjada pela Renata Del-Vecchio no Lagos
2009, em Gramado
Conjectura Renata
Pelo menos a metade dos autovalores laplacianos de qualquer
árvore são menores que a média d = 2− 2n
Poucos autovalores grandes e muito são pequenos.
Distribuição
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Terceira recorrência
Aplicar o algoritmo para uma árvore qualquer com α = d = 2− 2n
e mostrar que pelo menos metade dos valores são negativos.
ideia
Qual recorrência que aparece?
Recorrência
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência SecundaRecorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Terceira recorrência
Aplicar o algoritmo para uma árvore qualquer com α = d = 2− 2n
e mostrar que pelo menos metade dos valores são negativos.
ideia
Qual recorrência que aparece?
Recorrência
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Média dos graus
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Agora a matriz é a Laplaciana L = D −A e λ = 2− 2/n é a
média dos autovalores.
x1 x2 xr dvn
Note x1 = 1− λ = −1 + 2n < 0, x2 = 2− λ−
1
x1
,
x3 = 2− λ− 1x2 . Em geral obtemos a seguinte recorrência:{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
(3)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Média dos graus
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Agora a matriz é a Laplaciana L = D −A e λ = 2− 2/n é a
média dos autovalores.
x1 x2 xr dvn
Note x1 = 1− λ = −1 + 2n < 0, x2 = 2− λ−
1
x1
,
x3 = 2− λ− 1x2 . Em geral obtemos a seguinte recorrência:{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
(3)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Média dos graus
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Agora a matriz é a Laplaciana L = D −A e λ = 2− 2/n é a
média dos autovalores.
x1 x2 xr dvn
Note x1 = 1− λ = −1 + 2n < 0, x2 = 2− λ−
1
x1
,
x3 = 2− λ− 1x2 . Em geral obtemos a seguinte recorrência:{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
(3)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Média dos graus
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Agora a matriz é a Laplaciana L = D −A e λ = 2− 2/n é a
média dos autovalores.
x1 x2 xr dvn
Note x1 = 1− λ = −1 + 2n < 0, x2 = 2− λ−
1
x1
,
x3 = 2− λ− 1x2 . Em geral obtemos a seguinte recorrência:{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
(3)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Média dos graus
Aplica o algoritm em um caminho de uma árvore, começando
na extremidade, caminhando em direção à raiz.
Agora a matriz é a Laplaciana L = D −A e λ = 2− 2/n é a
média dos autovalores.
x1 x2 xr dvn
Note x1 = 1− λ = −1 + 2n < 0, x2 = 2− λ−
1
x1
,
x3 = 2− λ− 1x2 . Em geral obtemos a seguinte recorrência:{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
(3)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
General recursion
Note que as recorrências{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
{
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 1 ≤ i ≤ r + 2.{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
são todas do mesmo tipo:
Transforming these sequences into real function, they are of the
form:
xj+1 = ϕ (xj) ,
where ϕ(t) = α+ γt
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
General recursion
Note que as recorrências{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
{
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 1 ≤ i ≤ r + 2.{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
são todas do mesmo tipo:
Transforming these sequences into real function, they are of the
form:
xj+1 = ϕ (xj) ,
where ϕ(t) = α+ γt
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
General recursion
Note que as recorrências{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
{
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 1 ≤ i ≤ r + 2.{
x1 = 1− λ = −1 + 2n
xi = 2− λ− 1xi−1 , i = 2, . . . , k.
são todas do mesmo tipo:
Transforming these sequences into real function, they are of the
form:
xj+1 = ϕ (xj) ,
where ϕ(t) = α+ γt
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Um teoremão – ocupa 3 slides!!
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
The general formula
Theorem
Given
xj+1 = ϕ(xj), j ≥ 1,
where ϕ(t) = α+ γt , for t 6= 0, α, γ ∈ R are fixed numbers
(γ 6= 0) and x1 is a given initial condition. Then the general
solution is one of three possibilities according the sign of
∆ = α2 + 4γ:
For ∆ = 0 the solution is
xj = θ
(
1 +
1
(β + j)
)
,
where θ = α2 and β ∈ R is defined by the initial point x1 by the
formula β = −1 + θx1−θ .
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Theorem
Given
xj+1 = ϕ(xj), j ≥ 1,
where ϕ(t) = α+ γt , for t 6= 0, α, γ ∈ R are fixed numbers
(γ 6= 0) and x1 is a given initial condition.
∆ = α2 + 4γ > 0 the solution is
xj = θ +
θ′ − θ
β
(
θ
θ′
)j
+ 1
,
where θ = α2 +
1
2
√
α2 + 4γ, θ′ = α2 −
1
2
√
α2 + 4γ and β ∈ R is
defined by the initial point x1 by the formula β = θ
′
θ
(
θ′−θ
x1−θ − 1
)
.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Theorem
Given
xj+1 = ϕ(xj), j ≥ 1,
where ϕ(t) = α+ γt , for t 6= 0, α, γ ∈ R are fixed numbers
(γ 6= 0) and x1 is a given initial condition. Then the general
solution is one of three possibilities according the sign of
∆ = α2 + 4γ:
For ∆ < 0 the solution is
xj = ρ (cos(φ)− sin(φ) tan(jφ+ ω)) ,
where ρ =√
−γ, φ = arctan
(√
−α2−4γ
α
)
if α > 0,
φ = arctan
(√
−α2−4γ
α
)
+ π if α < 0 and ω ∈ [0, 2π) is defined
by the initial point x1 by the formula
ω = −φ+ arctan
(
cot(φ)− x1ρ csc(φ)
)
.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
As recorrências neste Framework
{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
e{
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 1 ≤ i ≤ r + 2.
são do tipo 2: ∆ = α2 + 4γ = (−λ)2 + 4(−1) > 0 Para λ > 2
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
As recorrências neste Framework
{
z1 = −λ
zj+1 = −λ− 1zj , j ≥ 1.
e{
b1 = zr +
1
λ ,
bi = −λ− 1bi−1 , 1 ≤ i ≤ r + 2.
são do tipo 2: ∆ = α2 + 4γ = (−λ)2 + 4(−1) > 0 Para λ > 2
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Analisando as recorrências como funções reais, mostra-se que
para recorrências do tipo 2:
Se z1 < θ = −λ−
√
λ2−4
2 então zi < 0, cresce monotonicamente
para θ
Se θ < z1 < θ′ = −λ+
√
λ2−4
2 então zi < 0 decresce
monotonicamente para θ′
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Analisando as recorrências como funções reais, mostra-se que
para recorrências do tipo 2:
Se z1 < θ = −λ−
√
λ2−4
2 então zi < 0, cresce monotonicamente
para θ
Se θ < z1 < θ′ = −λ+
√
λ2−4
2 então zi < 0 decresce
monotonicamente para θ′
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Analisando as recorrências como funções reais, mostra-se que
para recorrências do tipo 2:
Se z1 < θ = −λ−
√
λ2−4
2 então zi < 0, cresce monotonicamente
para θ
Se θ < z1 < θ′ = −λ+
√
λ2−4
2 então zi < 0 decresce
monotonicamente para θ′
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Analisando as recorrências como funções reais, mostra-se que
para recorrências do tipo 2:
Se z1 < θ = −λ−
√
λ2−4
2 então zi < 0, cresce monotonicamente
para θ
Se θ < z1 < θ′ = −λ+
√
λ2−4
2 então zi < 0 decresce
monotonicamente para θ′
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Analisando as recorrências como funções reais, mostra-se que
para recorrências do tipo 2:
Se z1 < θ = −λ−
√
λ2−4
2 então zi < 0, cresce monotonicamente
para θ
Se θ < z1 < θ′ = −λ+
√
λ2−4
2 então zi < 0 decresce
monotonicamente para θ′
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Exemplo - Pontos limites
Um problema famoso de Hoffman (1972) pede para
caracterizar números que sejam pontos limites de raios
espectrais de matrizes simétricas com entradas positivas
Sabe-se que, neste caso, as matrizes se reduzem a matrizes
com estradas 0,1: adjacências de grafos.
Para matrizes Laplacianas sabe-se muito pouco.
Definition
A real number µ is said to be a limit point of the Laplacian
spectral radii of graphs if there exists a sequence {Gk} of
graphs such that
ρL(Gi) 6= ρL(Gj), i 6= j and lim
k→∞
ρL(Gk) = µ.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Exemplo - Pontos limites
Um problema famoso de Hoffman (1972) pede para
caracterizar números que sejam pontos limites de raios
espectrais de matrizes simétricas com entradas positivas
Sabe-se que, neste caso, as matrizes se reduzem a matrizes
com estradas 0,1: adjacências de grafos.
Para matrizes Laplacianas sabe-se muito pouco.
Definition
A real number µ is said to be a limit point of the Laplacian
spectral radii of graphs if there exists a sequence {Gk} of
graphs such that
ρL(Gi) 6= ρL(Gj), i 6= j and lim
k→∞
ρL(Gk) = µ.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Exemplo - Pontos limites
Um problema famoso de Hoffman (1972) pede para
caracterizar números que sejam pontos limites de raios
espectrais de matrizes simétricas com entradas positivas
Sabe-se que, neste caso, as matrizes se reduzem a matrizes
com estradas 0,1: adjacências de grafos.
Para matrizes Laplacianas sabe-se muito pouco.
Definition
A real number µ is said to be a limit point of the Laplacian
spectral radii of graphs if there exists a sequence {Gk} of
graphs such that
ρL(Gi) 6= ρL(Gj), i 6= j and lim
k→∞
ρL(Gk) = µ.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Ji-Ming Guo - 2008
z1
z1z2zn
z1z2zn
a(v)
Figure: Trees T1,n,n with labels.
Theorem
lim
n→∞
µ(T1,n,n) = 2 + � ≈ 4.382975767,
where � is the real root of x3 − 4x− 4.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Ji-Ming Guo - 2008
z1
z1z2zn
z1z2zn
a(v)
Figure: Trees T1,n,n with labels.
Theorem
lim
n→∞
µ(T1,n,n) = 2 + � ≈ 4.382975767,
where � is the real root of x3 − 4x− 4.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
Ji-Ming Guo - 2008
z1
z1z2zn
z1z2zn
a(v)
Figure: Trees T1,n,n with labels.
Theorem
lim
n→∞
µ(T1,n,n) = 2 + � ≈ 4.382975767,
where � is the real root of x3 − 4x− 4.
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrênciaLaplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
A prova de Guo é difícil. Para nós isso é piece of cake!
z1
z1z2zn
z1z2zn
a(v)
Aplicamos o algoritmo para λn o raio espectral Laplaciano de
T (1, n, n), para um n fixo. A recorrência que obtemos é:
z1 = 1− λn and zi = 2− λn − 1zi−1
Que é do tipo 2(∆ > 0)
θn =
2−λn−
√
λ2n−4λn
2 and θ
′
n =
2−λn+
√
λ2n−4λn
2 .
z1 = 1− λn < θn then zi → θn de forma crescente.
Como λn é limitado, segue λn → λ0 (a ser determinado)
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
z1
z1z2zn
z1z2zn
a(v)
O valor na raiz é: a(v) = 3− λn − 1/z1 − 2/zn = 0, onde
zn → θn = 2−λn− sqrtλ
2
n−4λn
2
Mostre-se que θn → θ0 =
2−λ0−
√
λ20−4λ0
2
Portanto, o valor na raiz é
a(v) = 3− λn − 1/z1 − 2/zn → 3− λ0 −
1
1− λ0
− 2
θ0
= 0
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
z1
z1z2zn
z1z2zn
a(v)
O valor na raiz é: a(v) = 3− λn − 1/z1 − 2/zn = 0, onde
zn → θn = 2−λn− sqrtλ
2
n−4λn
2
Mostre-se que θn → θ0 =
2−λ0−
√
λ20−4λ0
2
Portanto, o valor na raiz é
a(v) = 3− λn − 1/z1 − 2/zn → 3− λ0 −
1
1− λ0
− 2
θ0
= 0
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
z1
z1z2zn
z1z2zn
a(v)
O valor na raiz é: a(v) = 3− λn − 1/z1 − 2/zn = 0, onde
zn → θn = 2−λn− sqrtλ
2
n−4λn
2
Mostre-se que θn → θ0 =
2−λ0−
√
λ20−4λ0
2
Portanto, o valor na raiz é
a(v) = 3− λn − 1/z1 − 2/zn → 3− λ0 −
1
1− λ0
− 2
θ0
= 0
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
z1
z1z2zn
z1z2zn
a(v)
O valor na raiz é: a(v) = 3− λn − 1/z1 − 2/zn = 0, onde
zn → θn = 2−λn− sqrtλ
2
n−4λn
2
Mostre-se que θn → θ0 =
2−λ0−
√
λ20−4λ0
2
Portanto, o valor na raiz é
a(v) = 3− λn − 1/z1 − 2/zn → 3− λ0 −
1
1− λ0
− 2
θ0
= 0
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
z1
z1z2zn
z1z2zn
a(v)
O valor na raiz é: a(v) = 3− λn − 1/z1 − 2/zn = 0, onde
zn → θn = 2−λn− sqrtλ
2
n−4λn
2
Mostre-se que θn → θ0 =
2−λ0−
√
λ20−4λ0
2
Portanto, o valor na raiz é
a(v) = 3− λn − 1/z1 − 2/zn → 3− λ0 −
1
1− λ0
− 2
θ0
= 0
V. Trevisan Recorrências em TEG
Introdução - Histórico Trees Starlike trees Secunda Recorrência Secunda Recorrência Secunda Recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência Laplaciana: terceira recorrência
3− λ0 − 11−λ0 −
2
θ0
= 0 Solving this (Maple!!!) gives
λ0 =
3
√
54 + 6