Laplace matrisi
Olarak grafik teorisi , bir Laplace matris veya Laplace matrisi , bir grafik temsil eden bir matristir.
Tanım
Bir grafik Laplace matris G yönlenimsiz ve yansıtıcı olmayan tanımlanır: burada bir matris derecesi arasında G ve bitişiklik matrisi arasında G . Resmi olarak:
L=D-AT{\ görüntü stili L = DA}
D{\ görüntü stili D}
AT{\ görüntü stili A}![AT](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Lben,j: ={derece(sben)Eğer ben=j-x Eğer ben≠j x ile i'yi j'ye doğrudan bağlayan kenarların sayısı0değilse{\ displaystyle L_ {i, j}: = \ sol \ {{\ başlangıç {matrix} \ derece (s_ {i}) & {\ mbox {si}} i = j \\ - x & {\ mbox {si } } i \ neq j {\ mbox {i ile j'yi doğrudan bağlayan kenarların sayısı}} \\ 0 & {\ mbox {aksi halde}} \ end {matris}} \ sağ.}
Sezgi
Bir grafiğin bitişik matrisinden farklı olarak, Laplacian matrisi, spektral analizini verimli kılan cebirsel bir yoruma sahiptir .
Daha doğrusu matris , grafikteki difüzyon operatörüne karşılık gelir . Grafiğin köşelerinin her birinde bir gazın parçacıklarının yoğunluğuna karşılık geliyorsa , bunun, her parçacığın köşesinden rastgele seçilen bir komşuya hareket ettiği bir difüzyon yinelemesinden sonraki yoğunluğa karşılık geldiğini not etmek kolaydır .
D-1AT{\ displaystyle D ^ {- 1} A}
x∈$değil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
değil{\ görüntü stili n}
D-1ATx{\ displaystyle D ^ {- 1} Balta}![{\ displaystyle D ^ {- 1} Balta}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd35433ee10d9971c05991eeefd71ba5ec850d39)
Ayrıca, Laplacian matrisi , grafik tarafından tanımlanan mesafeye göre bir vektörün düzenliliğini karakterize eden ikinci dereceden bir form olarak görülebilir . Aslında, aşağıdaki formüle sahibiz: .
x∈$değil{\ displaystyle x \ in \ mathbb {R} ^ {n}}
xTLx=∑(sen,v)∈E(x(sen)-x(v))2{\ displaystyle x ^ {T} Lx = \ toplam _ {(u, v) \ E} (x (u) -x (v)) ^ {2}}![{\ displaystyle x ^ {T} Lx = \ toplam _ {(u, v) \ E} (x (u) -x (v)) ^ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c43498e53f60b8bcde5583a637ddef92f587114)
Misal
yönsüz grafik
|
Derece matrisi
|
komşuluk matrisi
|
Laplace matrisi
|
---|
|
(200000030000002000000300000030000001){\ displaystyle \ sol ({\ başlangıç {dizi} {rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0) {son
|
(010010101010010100001011110100000100){\ displaystyle \ sol ({\ başlangıç {dizi} {rrrrrr} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0}) {
|
(2-100-10-13-10-100-12-10000-13-1-1-1-10-130000-101){\ displaystyle \ sol ({\ başlangıç {dizi} {rrrrrr} 2 & -1 & 0 & 0 & -1 & 0 \\ - 1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & -1 \\ - 1 & -1 & 0 & -1 & 3 & 0 \\ 0 & 0 & 0 & - 1 & 0 & 1 \\\ bitiş {dizi}} \ sağ)}
|
Uygulamalar
Laplacian matrisi, Kirchhoff teoremi tarafından bir grafiğin yayılan ağaçlarının sayısını hesaplamak için kullanılır .
Tayfı Laplace matrisin in incelenmiştir grafikler spektral teorisi . Bu çalışma, diğer şeylerin yanı sıra, grafik bölümleme için spektral yöntemleri tanımlamaya izin verir .
Özdeğerler sıralanırsa Örneğin, ancak ve ancak grafiğin en az bağlantılı bileşenler içerdiğini fark edebiliriz .
0≤λ1≤...≤λdeğil{\ displaystyle 0 \ leq \ lambda _ {1} \ leq ... \ leq \ lambda _ {n}}
λr=0{\ displaystyle \ lambda _ {r} = 0}
r{\ görüntü stili r}![r](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
Varyantlar
ağırlıklı grafik
Daha genel olarak, ağırlığını herhangi bir kenarla ilişkilendiren ağırlık fonksiyonu ile ağırlıklandırılmış, n köşeli, yönsüz ve yansıtıcı olmayan bir G = ( S , A ) grafiği olsun . G'nin Laplacian matrisi şunları sağlar:
(sben,sj){\ görüntü stili (s_ {i}, s_ {j})}
p(sben,sj){\ displaystyle p (s_ {i}, s_ {j})}![p (s_ {i}, s_ {j})](https://wikimedia.org/api/rest_v1/media/math/render/svg/b68ce5c78a6668d09dc6ba8390426dd0919f37c1)
(L)ben,j: ={derece(sben)=∑k=1değilp(sben,sk)Eğer ben=j-p(sben,sj)Eğer ben≠j ve (sben,sj)∈AT0değilse{\ displaystyle (L) _ {i, j}: = \ sol \ {{\ başlangıç {matris} \ derece (s_ {i}) = \ toplam _ {k = 1} ^ {n} p (s_ {i }, s_ {k}) & {\ mbox {si}} i = j \\ - p (s_ {i}, s_ {j}) & {\ mbox {si}} i \ neq j {\ mbox {ve }} (s_ {i}, s_ {j}) \ A \\ 0 & {\ mbox {aksi halde}} \ bitiş {matris}} \ sağda.}
Yönlendirilmiş grafik
Bu tanımlar yönlendirilmiş grafiklere genelleştirilebilir; bu durumda, Laplacian matrisi artık simetrik değildir.
Notlar ve referanslar
-
Laurent ve Pierre Beauguitte, Matrix işlemleri ve grafik analizi , sonbahar 2011
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">