Misalkan saya memberi Anda grafik tanpa arah dengan tepi tertimbang, dan memberi tahu Anda bahwa setiap node sesuai dengan titik dalam ruang 3d. Setiap kali ada tepi antara dua node, berat tepi adalah jarak antara titik. Tujuan Anda adalah merekonstruksi posisi relatif dari titik-titik tersebut,...
Apakah ada karakterisasi grafik yang himpunan tepi-nya terurai menjadi kesatuan yang serasi dan sempurna? Satu kelas sepele dari grafik tersebut adalah grafik regular ( n , n ) -bipartite. Perangkat edge mereka akan terurai menjadi d disjoint matching sempurna.
Katakanlah saya memiliki grafik jarang hingga tidak terarah, dan harus dapat menjalankan kueri berikut secara efisien: sayas Co n n e c t e d( N1, N2)sayasCHainnected(N1,N2)IsConnected(N_1, N_2) - mengembalikan jika ada jalur antara dan , jika tidakN 1 N 2 FTTTN1N1N_1N2N2N_2FFF Co n n e c t e dNo...
Pertimbangkan masalah berikut. Diberikan: Grafik lengkap dengan bobot non-negatif nyata di tepinya. Tugas: Temukan subgraph planar dengan berat maksimum. ("Maksimum" di antara semua kemungkinan subgraph planar.) Catatan: Subgraph dengan berat maksimum akan menjadi triangulasi; jika grafik...
Saya mengalami masalah berikut: Diberikan grafik asiklik terarah dengan bobot tepi bernilai nyata, dan dua simpul s dan t, menghitung potongan minimum. Untuk grafik umum ini adalah NP-hard, karena orang dapat dengan mudah mengurangi max-cut untuk itu hanya dengan membalik bobot edge (koreksi saya...
Saya menulis sebuah Program, menyelesaikan Masalah Tukang Pos Cina (juga dikenal sebagai masalah inspeksi rute) dalam sebuah draph yang tidak diarahkan dan saat ini menghadapi masalah untuk menemukan tepi tambahan terbaik untuk menghubungkan node dengan derajat ganjil, sehingga saya dapat...
Kami ingin menyelesaikan masalah aliran biaya minimal dengan algoritma pembatalan siklus negatif generik. Artinya, kita mulai dengan aliran acak yang valid, dan kemudian kita tidak memilih siklus negatif "baik" seperti siklus biaya rata-rata minimal, tetapi menggunakan Bellman-Ford untuk menemukan...
Sebuah graf bipartit adalah planar jika dan hanya jika ia tidak memiliki K3,3K3,3K_{3, 3} atau anak di bawah umur.K5K5K_5 Saya mencari kondisi yang diperlukan atau / dan cukup untuk memungkinkan gambar planar tanpa tepi "berkeliling" set simpul. Ini adalah gambar yang memuaskan: Semua simpul...
Apakah saya benar dalam pengamatan saya bahwa kardinalitas maksimum pencocokan dari grafik bipartit selalu sama dengan ?MMMG(U,V,E)G(U,V,E)G(U, V, E)min(|U|,|V|)min(|U|,|V|)\min(|U|,
Jika grafik memiliki siklus Euler, apakah komponen-komponen yang tidak terhubung memiliki siklus Euler
Saya merancang sebuah algoritma untuk kelas yang akan menentukan apakah grafik yang diarahkan adalah unik sehubungan dengan vertex sehingga untuk setiap u ≠ v ada paling banyak satu jalur dari v ke u . Saya sudah mulai dengan menggunakan BFS (pencarian luas-pertama) untuk menemukan jalur terpendek...
Saya sedang mengerjakan masalah yang terkait dengan kotak Latin, dan saya ingin metode untuk apa yang intinya bermuara pada masalah keputusan: Input : Grafis terbatas, sederhana G. Output : YESjika G memiliki automorfisme non-sepele, NOjika tidak. Karenanya... Pertanyaan : Apakah ada algoritma...
Anda dapat memodifikasi grafik apa pun sehingga Dijkstra's menemukan solusinya dengan jumlah tepi minimal sebagai berikut:GGG Lipat gandakan setiap bobot tepi dengan angka aaa , lalu tambahkan 111 ke bobot untuk menghukum setiap tepi tambahan dalam solusi,
Saya mencari makalah yang mudah dan pengantar tentang bukti Teorema Courcelle . Saya juga tertarik dengan hubungannya dengan kompleksitas parameter tentang treewidth . Saya hanya pemula di bidang ini. Ada
Saya menerapkan algoritme pembatalan siklus untuk menemukan solusi optimal untuk masalah aliran biaya minimum. Dengan menemukan dan menghilangkan siklus biaya negatif dalam jaringan residual, total biaya diturunkan di setiap putaran. Untuk menemukan siklus negatif saya menggunakan algoritma...
Pertimbangkan grafik yang tidak diarahkan dengan sumber dan simpul wastafel. Kami ingin menghapus jumlah minimum simpul dalam grafik itu untuk memutuskan jalur apa pun antara sumber dan wastafel. Bisakah kita melakukan ini menggunakan katakanlah algoritma max-flow,
Masalah 3-Warna dapat dibuktikan NP-Complete memanfaatkan pengurangan dari 3SAT Graph Coloring (dari 3SAT) . Sebagai akibatnya, masalah 4-Warna adalah NP-Lengkap menggunakan pengurangan dari 3-Warna: Reduksi dari instance 3-Coloring: menambahkan simpul tambahan ke grafik masalah 3-Coloring, dan...
Diberikan grafik , cari simpul , yang penghapusan akan menghasilkan grafik dengan komponen terkecil terkecil. G=(V,E)G=(V,E)G = (V, E)kkk{v∗1,…,v∗k}{v1∗,…,vk∗}\{v^*_1,\dots,v^*_k\} Saya berasumsi untuk besardan besar masalahnya sulit (NP-keras), tapi saya tertarik pada nilai kecil ( ).n=|V|n=|V|n...
Saat ini saya sedang mengerjakan tesis master saya, dan ini tentang pengelompokan pada grafik. Saya bekerja dengan ide menggunakan semut untuk menyelesaikan masalah. Saat ini saya sedang mengerjakan implementasinya dan saya bertanya-tanya seberapa baik merepresentasikan tepi grafik. Setiap sisi...
Saya mencari algoritme yang menyediakan string kanonik untuk grafik berwarna yang diberikan. Yaitu. sebuah algoritma yang mengembalikan string untuk grafik, sehingga dua grafik mendapatkan string yang sama jika dan hanya jika mereka isomorfik. Secara khusus, saya mencari algoritma sederhana yang...