Perkiraan jumlah pewarnaan tampaknya mudah pada grafik dengan pengecualian kecil menggunakan algoritma oleh Jung / Shah. Apa contoh lain dari masalah yang sulit pada grafik umum tetapi mudah pada grafik kecil-dikecualikan? Pembaruan 10/24 Tampaknya mengikuti hasil Grohe bahwa rumus yang FPT untuk...
Di bawah ini, MSO menunjukkan logika urutan kedua monadik dari grafik dengan kuantifikasi himpunan sudut dan himpunan tepi. Biarkan menjadi kelompok kecil grafik tertutup. Ini mengikuti dari teori minor minor Robertson dan Seymour bahwa ditandai dengan daftar berhingga dari anak di bawah umur...
Saya ingin tahu apakah ada perpustakaan grafik gratis untuk menguji apakah ada sekelompok anak di bawah umur yang ada dalam grafik
Treewidth memainkan peran penting dalam algoritma FPT, sebagian karena banyak masalah yang FPT parameter oleh treewidth. Gagasan terkait, lebih terbatas, adalah pathwidth. Jika grafik memiliki pathwidth , grafik juga memiliki treewidth paling banyak k , sedangkan pada arah sebaliknya, treewidth k...
Pertanyaan ini mirip dengan salah satu pertanyaan saya sebelumnya. Hal ini diketahui bahwa adalah minor dilarang untuk grafik dari treewidth paling t .Kt + 2Kt+2K_{t+2}ttt Adakah keluarga yang dibangun dengan baik, parameter, dan tak terbatas grafik (selain grafik lengkap dan grafik kisi) yang...
Hal ini juga diketahui bahwa dan K 3 , 3 dilarang anak di bawah umur untuk grafik planar. Ada ratusan anak di bawah umur yang terlarang untuk grafik yang dapat disematkan pada torus. Jumlah anak di bawah umur yang terlarang untuk grafik yang dapat disematkan pada permukaan genus g adalah fungsi...
Grafik planar adalah -gratis. Grafik tersebut dapat didekomposisi menjadi komponen tri-terhubung, yang dikenal sebagai komponen planar atau .K3 , 3K3,3K_{3,3}K5K5K_5 Apakah ada dekomposisi grafik genus satu yang "bagus"? Dalam karya seminal mereka pada grafik anak di bawah umur, Roberston dan...
Pertimbangkan masalah berikut. Input: Grafik tidak berarah . Output: Grafik H yang merupakan minor G dengan kepadatan tepi tertinggi di antara semua anak di bawah umur G , yaitu, dengan rasio tertinggi | E ( H ) | / | V ( H ) |
Jika adalah grafik dengan derajat 3 maksimum dan merupakan minor , maka adalah minor topologiH G HGGGHHHGGGHHH . Wikipedia mengutip hasil ini dari "Grafik Theory" Diestel. Itu terdaftar sebagai Prop 1.7.4 di versi terbaru buku. Buku ini tidak memiliki bukti atau kutipan. Apakah keberadaannya...
Biarkan C4C4C_4 menjadi siklus dengan empat simpul. Untuk grafik sembarang GGG dengan nnn simpul dan tepi m, ucapkan m>nn−−√m>nnm>n\sqrt n , berapa banyakC4C4C_4yang ada? Apakah ada batas bawah untuk
Biarkan kkk diperbaiki, dan biarkan GGG menjadi grafik (terhubung). Jika saya tidak salah, itu berasal dari karya Bodlaender [1, Teorema 3.11] bahwa jika treewidth GGG kira-kira setidaknya 2k32k32k^3 , maka GGG berisi bintang K1,kK1,kK_{1,k} sebagai minor. Bisakah kita membuat istilah 2k32k32k^3...
Teorema Courcelle menyatakan bahwa setiap properti grafik yang dapat didefinisikan dalam logika urutan kedua monadik dapat diputuskan dalam waktu linier pada grafik treewidth terikat . Ini adalah salah satu meta-teorema algoritmik yang paling terkenal. Termotivasi oleh teorema Courcelle, saya...
The Robertson-Seymour teorema mengatakan bahwa setiap keluarga kecil-tertutup grafik dapat dicirikan oleh finitely banyak anak di bawah umur dilarang.GG\mathcal G Apakah ada algoritma yang untuk input GG\mathcal G menghasilkan anak di bawah umur terlarang atau apakah ini tidak dapat...
Saya diberi grafik dengan treewidth dan derajat sewenang-wenang, dan saya ingin menemukan subgraf dari (belum tentu merupakan subgraf yang diinduksi) sedemikian rupa sehingga memiliki derajat yang konstan dan treewidth-nya setinggi mungkin. Secara resmi masalah saya adalah sebagai berikut: telah...
Pertanyaan ini dua kali lipat, dan terutama berorientasi pada referensi: Apakah ada suatu tempat di mana intuisi utama untuk membuktikan teorema minor diberikan, tanpa terlalu banyak detail? Saya tahu buktinya panjang dan sulit, tetapi pasti harus ada ide-ide kunci yang dapat dikomunikasikan...
Mari menjadi parameter grafik (ex. Diameter, jumlah dominasi, dll)sss Keluarga dari grafik memiliki properti s -treewidth jika ada fungsi f sehingga untuk setiap grafik G ∈ F , treewidth G paling banyak adalah f ( s ) .FF\mathcal{F}sssfffG∈FG∈FG\in \mathcal{F}GGGf(s)f(s)f(s) Sebagai contoh,...
Definisi: A "kkk -chain" adalah multi-grafik yang diperoleh dari lintasan panjangdengan menduplikasi setiap sisi.kkk Perhatikan bahwa jumlah jalur antara dua titik akhir dari rantai adalahkkk2k.2k.2^k. Pertanyaan: Misalkan adalah graf sederhana pada n node dan biarkan dan menjadi dua node dari...
Thor Johnson, et al, dalam makalah mereka: Sutradara Pohon Lebar , memperkenalkan definisi untuk diarahkan jaringan , dan mereka menduga:JkJkJ_k Untuk setiap bilangan bulat k terdapat bilangan bulat N sehingga setiap digraph dengan pohon-lebar N atau lebih memiliki minor isomorfik ke J k...