Saya ingin tahu apakah masalah berikut memiliki nama, atau hasil apa pun yang terkait dengannya. Misalkan adalah grafik berbobot di mana menunjukkan bobot tepi antara dan , dan untuk semua , . Masalahnya adalah untuk menemukan subset dari simpul yang memaksimalkan jumlah dari bobot tepi yang...
Salah satu masalah utama dalam penghitungan grafik adalah menentukan 'bentuk' grafik, misalnya kelas isomorfisme dari grafik tertentu. Saya menyadari sepenuhnya bahwa setiap grafik dapat direpresentasikan sebagai matriks simetris. Namun, untuk mendapatkan bentuknya, Anda memerlukan kumpulan...
Definisikan mesh dalam 3D sebagai kumpulan tetrahedra yang terhubung dengan interior terpisah (jadi tetrahedra hanya berbagi k-face, ). Diberikan grafik yang arbitrer, adakah prosedur yang efisien untuk menguji apakah dapat ditanamkan sebagai sebuah mesh?k ≤ 2k≤2k \le 2 Di sini, penyisipan adalah...
Saya ingin memiliki ikatan pada kardinalitas dari set grafik disk unit dengan simpulDiketahui bahwa memeriksa apakah suatu grafik adalah anggota dari set ini adalah NP-hard. Apakah ini mengarah pada batas yang lebih rendah pada kardinalitas, dengan asumsi P NP?≠NNN≠≠\neq Misalnya, anggap ada...
Saya bekerja pada algoritma aproksimasi untuk masalah himpunan dominasi minimum. Secara khusus, saya tertarik pada kelas grafik yang dibatasi oleh subgraph yang diinduksi terlarang. Karena masalah dominasi dan variannya telah dipelajari secara luas, saya kira seseorang mungkin mengerjakan ini...
Masalah Klasik: Biarkan nomor diberikan. Masalah -clique adalah sebagai berikut.kkkkkkk Diberikan grafik , apakah ada subset dari simpul sehingga setiap dua simpul berdekatan?S k SGGGSSSkkkSSS Masalah Hypergraph: Biarkan angka dan diberikan. Masalah -hyperclique adalah sebagai berikut.k ( c , k...
Saya memiliki satu set terbatas , fungsi f : S → S , dan total order < pada S . Saya ingin mencari jumlah siklus yang berbeda di S .SSSf:S→Sf:S→Sf:S\to
Saya ingin tahu apakah masalah berikut ini NP-hard. Input: grafik sederhana, dan pewarnaan pada tepian ( tidak memverifikasi properti spesifik apa pun).f : E → { 1 , 2 , 3 } fG = ( V, E)G=(V,E)G = (V,E)f: E→ { 1 , 2 , 3 }f:E→{1,2,3}f : E \to \{1,2,3\}fff Pertanyaan: apakah mungkin untuk...
Ketika memperkenalkan grafik dekomposisi modular , kebanyakan penulis menggunakan grafik 11-simpul, yang saya salin dari wikipedia. Pertanyaannya adalah siapa desainer asli dari itu. (Saya tidak bertanya siapa yang menggambar grafik ini untuk wikipedia, tetapi sumber aslinya). Halaman wikipedia...
Misalkan kita memiliki grafik pada nnn node. Kami ingin menetapkan ke setiap node baik + 1+1+1 atau . Sebut ini sebagai konfigurasi . Jumlah yang harus kita tetapkan adalah persis (karenanya jumlah dt adalah .) Dengan konfigurasi , kita melihat setiap simpul dan menjumlahkan nilai yang diberikan...
Misalkan GGG dan HHH menjadi dua grafik ukuran- rrr terhubung secara teratur nnn . Biarkan AAA adalah himpunan permutasi PPP sehingga PGP−1=HPGP−1=HPGP^{-1}=H . Jika G=HG=HG=H maka AAA adalah himpunan automorphisms dari GGG . Apa batas atas yang paling dikenal pada ukuran AAA ? Apakah ada...
Biarkan menjadi grafik. Biarkan k ≤ | V | menjadi bilangan bulat. Mari O k menjadi jumlah tepi diinduksi subgraphs dari G memiliki k simpul dan ganjil tepi. Mari E k menjadi jumlah tepi diinduksi subgraphs dari G memiliki k simpul dan jumlah yang lebih dari tepi. Biarkan Δ k = O k - E k . Masalah...
kkk titik yang berbeda dipilih secara acak dari kisi . (Jelas dan merupakan bilangan konstan yang diberikan.) Sebuah grafik berbobot lengkap dibangun dari titik-titik ini sedemikian sehingga bobot tepi antara simpul dan simpul sama dengan jarak Manhattan dari dua simpul pada kisi asli. .p ×...
Saya mengalami masalah pencocokan ini yang saya tidak dapat menuliskan algoritma waktu polinomial. Biarkan menjadi grafik tertimbang lengkap dengan masing-masing set vertex dan , di mana . Juga, biarkan dan menjadi fungsi bobot masing-masing di tepi danP V Q VP, QP,QP, QPVPVP_VQVQVQ_V| PV| = |...
Pertimbangkan grafik dengan semua sisi memiliki kapasitas unit. Satu dapat menemukan potongan min di waktu polinomial. Misalkan saya diizinkan untuk meningkatkan kapasitas setiap tepi hingga tak terbatas (setara dengan menggabungkan node di kedua sisi tepi). Apa cara optimal untuk memilih set tepi...
Diberi bahasa reguler pada alfabet , otomat deterministik minimalnya dapat dilihat sebagai multigraf terhubung langsung dengan out-degree konstandan kondisi awal yang ditandai (dengan melupakan label transisi, status akhir). Kami menjaga keadaan awal karena setiap titik harus dapat diakses...
Saya mencoba menemukan grafik dengan properti-properti itu untuk studi saya, tetapi sayangnya saya tidak dapat menemukan grafik tersebut. Adakah yang tahu kalau ada grafik itu, atau mengapa tidak mungkin
Saya sedang memecahkan masalah "memadukan" set gambar yang tumpang tindih. Set ini dapat diwakili oleh grafik tertimbang yang tidak diarahkan seperti yang ini: Setiap node mewakili gambar. Gambar yang tumpang tindih dihubungkan oleh tepi. Bobot tepi mewakili ukuran area yang tumpang tindih (...
Berapa banyak siklus yang ada dalam grafik vertex sehingga grafik tidak memiliki siklus .CkCkC_k n C m ( m > k )( k ≥ 3 )(k≥3)(k \geq 3)nnn CmCmC_m ( m > k )(m>k)(m>k) Misalnya , , maka grafik akan memiliki paling banyak dua sehingga tidak akan memilikik = 3 C 3 G C k ( k > 3 ) .n =...
Kami memiliki algoritma waktu untuk menentukan apakah grafik memiliki siklus panjang persis . Bagaimana kita dapat menemukan berapa banyak sepeda yang ada di menggunakan algoritma yang sama atau lainnya.f( k ) n3f(k)n3f(k)