Pengaruh operasi grafik yang berbeda pada konektivitas aljabar grafik laplacian?

8

The konektivitas aljabar dari graf G adalah nilai eigen kedua terkecil dari matriks Laplacian dari G. eigenvalue ini lebih besar dari 0 jika dan hanya jika G adalah graf terhubung. Besarnya nilai ini mencerminkan seberapa baik grafik keseluruhan terhubung.

misalnya, " menambahkan loop otomatis " tidak mengubah nilai eigen laplacian (khususnya konektivitas aljabar) grafik. Karena, laplacian (G) = DA adalah invarian sehubungan dengan menambahkan loop-diri.

Pertanyaanku adalah:

Apakah ada yang telah mempelajari efek dari operasi yang berbeda (seperti kontraksi tepi) pada spektrum laplacian? apakah anda tahu referensi yang bagus?

Catatan: definisi pasti dari konektivitas aljabar tergantung pada jenis Laplacian yang digunakan. Untuk pertanyaan ini saya lebih suka menggunakan definisi Fan Chung dalam TEORI GAMBAR SPECTRAL . Dalam buku ini Fan Chung telah membuat versi ulang dari Laplacian, menghilangkan ketergantungan pada jumlah simpul.

graph-theory co.combinatorics spectral-graph-theory js
sumber
4
Akan sangat membantu jika Anda memberikan motivasi dan latar belakang. Silakan lihat Bagaimana cara mengajukan pertanyaan yang bagus? dan FAQ situs .
Kaveh
Saya juga tertarik pada kasus kontraksi tepi. Saya telah menghabiskan waktu sebelumnya mencoba mencari referensi tentang hubungan antara nilai eigen dan operasi kecil, tanpa hasil.
Hsien-Chih Chang 張顯 之
4
Bagi saya, motivasinya tampak cukup jelas.
Suresh Venkat
2
Saya kedua Suresh, mengetahui bagaimana berbagai operasi mempengaruhi Laplacian menarik dalam dirinya sendiri dan masalah ini muncul dalam berbagai konteks.
Marcin Kotowski

Jawaban:

5

Operasi intuitif yang menjaga konektivitas tidak akan menurunkan nilai eigen. Misalnya, menambahkan tepian pada grafik tidak mengurangi konektivitas.

Secara umum, jika H adalah subgraf dari grafik G, dengan menjalin kita tahu bahwa nilai eigen Laplacian terbesar ke-H dari H tidak lebih besar dari nilai eigen Laplacian terbesar ke-i dari G. Bukti dapat ditemukan dalam Proposisi 3.2. 1 dari buku " Spectra of graphs " oleh Brouwer dan Haemers. Perhatikan bahwa definisi Laplacian yang digunakan dalam buku ini tidak dinormalisasi; ia memiliki derajat simpul pada diagonal dan -1 (atau 0 jika tidak ada tepi) pada entri diagonal.

Hsien-Chih Chang 張顯 之
sumber
Terima kasih Chang. Jawaban Anda sangat berguna bagi saya. Tetapi jika kita menggunakan definisi Laplacian yang tidak dinormalisasi, maka banyak perbandingan tampaknya tidak ada artinya. Misalnya kita memiliki Konektivitas Aljabar (K10) = 10 dan Konektivitas Aljabar (K20) = 20. namun, kedua grafik tersebut sepenuhnya terhubung dengan grafik sederhana. Tetapi jika kita menggunakan Laplacian yang dinormalisasi, maka NormalizedAlgebraicConnectivity (K10) = NormalalizedAlgebraicConnectivity (K20) = 1 dan oleh karena itu perbandingan versi yang dinormalkan tampaknya lebih rasional dan alami.
js
@behnam: Saya setuju dengan Anda. Tetapi setelah normalisasi, beberapa properti nondecreasing mungkin berbeda. (Katakanlah seseorang dapat memastikan pengurangan ketat pada Laplacian terbesar ketika menghapus tepi untuk yang tidak normal, tetapi tidak untuk yang normal).
Hsien-Chih Chang 張顯 之
@ Hsien-Chih Chang "Operasi intuitif yang menjaga konektivitas tidak akan menurunkan nilai eigen. Misalnya, menambahkan tepian pada grafik tidak mengurangi konektivitas." Apakah kamu yakin Apakah Anda punya bukti? Apakah contoh berikut adalah contoh? Mulailah dengan grafik jalur dan tambahkan tepi untuk membentuk grafik Lollipop . Waktu cover menjadi lebih buruk; mulai dari ke . Apa yang terjadi pada nilai eigen dalam contoh ini? Θ ( n 3 )Θ(n2)Θ(n3)
Tyson Williams
@TysonWilliams Anda benar sekali. Ini adalah salah satu aspek teoretis di mana orang Laplasia yang dinormalisasi dan tidak normal memiliki perbedaan. Dengan menambahkan edge, konektivitas aljabar yang tidak dinormalisasi selalu naik (Fiedler), tetapi ada (bahkan tidak terlalu rumit) contoh yang menunjukkan bahwa edge yang ditambahkan di tempat yang salah dapat mengurangi konektivitas. Ini sangat mudah dilihat jika Anda mengizinkan bobot tepi.
Delio M.