Tentang properti matriks adjacency ketika grafik planar

21

1- Apakah ada properti khusus untuk matriks kedekatan ketika grafik planar?
2- Apakah ada hal khusus untuk menghitung matriks adjacency permanen ketika grafik planar?

graph-theory co.combinatorics permanent marjoonjan
sumber
8
Harap setidaknya jalankan periksa ejaan sebelum menulis pertanyaan Anda. Ini bukan tandu, itu planar
Suresh Venkat
:)) OK Tentu, saya berjanji untuk melakukannya! :)
marjoonjan
Bagaimana dengan grafik planar bipartit?
Mohammad Al-Turkistany
Saya pribadi tidak peduli tentang grafik planar bipartit, tetapi jika ada hal dalam pikiran Anda, itu disambut baik! tolong bagikan!
marjoonjan
Apakah komputasi grafik planar bipartit permanen mudah?
T ....

Jawaban:

25

Komputasi determinan dan permanen grafik planar sama sulitnya dengan menghitungnya dalam grafik umum. Keduanya lengkap untuk GapL dan #P . Lihat makalah ini oleh Datta, Kulkarni, Limaye, Mahajan untuk lebih jelasnya.

Siwa Kintali
sumber
Apakah menghitung grafik planar bipartit permanen mudah?
T ....
@Arul Ya, oleh algoritme FKT en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
15

Ini lebih merupakan properti dari matriks kejadian daripada matriks adjacency, tetapi salah satu properti penting dari grafik planar adalah bahwa mereka persis grafik yang matroid grafisnya adalah ganda dari matroid grafis lain. Relasi dengan matriks kejadian adalah bahwa matroid grafis menggambarkan set kolom independen dalam matriks.

David Eppstein
sumber
9

Ada properti dari matriks jarak (dan bukan matriks kedekatan) dari grafik planar terbatas yang mungkin menarik, properti Monge . Properti Monge (karena Gaspard Monge) untuk grafik planar pada dasarnya berarti bahwa jalur terpendek tertentu tidak dapat dilintasi. Lihat Wikipedia: Monge Array untuk deskripsi formal tentang properti Monge. Djidjev (WG 1996) ( makalah di situs web Djidjev ) dan Fakcharoenphol dan Rao (FOCS 2001) ( Video ) menunjukkan bagaimana cara mengeksploitasi properti non-persimpangan dalam algoritma jalur terpendek.

Christian Sommer
sumber
6

Saya tidak yakin jenis properti apa yang Anda cari tetapi jari-jari spektral grafik planar adalah salah satu dari jumlah tersebut (nilai absolut maksimum nilai eigen dari matriks adjaceny). Lihat misalnya makalah ini .

Suresh Venkat
sumber
6

Meskipun tidak terkait langsung dengan pertanyaan Anda, Anda mungkin ingin melihat karya pada urutan derajat grafik planar. Tidak ada penokohan yang diketahui tentang kapan deret derajat adalah deret derajat grafik planar. Namun, ada berbagai makalah menarik tentang hal-hal tersebut termasuk:

http://www.jstor.org/pss/2100346

Joseph Malkevitch
sumber