Saya sedang bekerja untuk mencoba mempartisi grafik triangulasi menjadi subgraph yang terhubung dengan beberapa jaminan pada jumlah tepi antar-partisi. Berikut adalah contoh grafik triangulasi yang telah dipartisi menjadi 4 "cluster": Apa yang saya inginkan pada awalnya adalah algoritma yang dapat...
angka c-chromatic didefinisikan dalam makalah Partisi grafik menjadi cographs . Ia meminta jumlah minimum warna yang digunakan untuk mewarnai simpul sedemikian rupa sehingga setiap kelas warna adalah cograph . Cograf adalah grafik bebas P4 , yaitu tidak ada lintasan panjang 3 yang diinduksi. The...
Saya menduga bahwa jika adalah grafik bebas segitiga sederhana, maka ada satu set paling banyak 2/25 edge yang penghapusannya menghancurkan setiap siklus aneh.n 2 / 25GG G n2/ 25n2/25 n^2/25 Untuk informasi lebih lanjut, lihat makalah 1988 oleh Erdös et al., How to Make a Bipartite Graph...
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...
Ada beberapa teorema, kebanyakan dalam teori grafik dan optimasi kombinatorial, yang sering disebut sebagai penokohan yang baik. Mereka biasanya menempatkan properti di , dengan menunjukkan bahwa suatu properti dapat bertahan, atau ada beberapa kendala yang teridentifikasi dengan baik yang...
Grafik adalah bipartit lokal jika lingkungan terbuka dari setiap simpul menginduksi grafik bipartit. (Menurut penelusuran, nama yang sama dapat digunakan untuk hal lain yang terkait dengan permukaan). NP-hard untuk masalah grafik umum mana yang menjadi polinomial untuk grafik bipartit lokal dan...
Biarkan menjadi masalah grafik NP-complete. Misalkan X dapat dipecahkan dalam waktu polinomial pada grafik dengan diameter terikat. Dengan kata lain, X yang diparameterisasi dengan diameter ada di XP. (Ingat masalah ada di XP jika bisa diselesaikan dalam waktu n f ( k ) ). Apakah ini menyiratkan...
Tentukan sebagai grafik berarah acak ( simpul; kami menempatkan tepi antara dua simpul dengan probabilitas ).n pG(n,p)G(n,p)G(n, p)nnnppp Apa hasil yang diketahui untuk masalah berikut: Perbaiki dua simpul dan . Berapa probabilitas bahwa setidaknya ada jalur (panjang paling banyak ) antara dan ?...
Pathwidth dari grafik bipartit lengkap K3,nK3,nK_{3,n} dengan ukuran partite 333 dan nnn paling banyak 333 . Saya tertarik merencanakan grafik ini dengan proses berikut: Gambarlah di bidang sedemikian rupa sehingga tidak ada tepi yang mengandung simpul di bagian dalamnya, dan sedemikian rupa...
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,...
Diberikan grafik G yang tidak terarah, kita dapat mengatakan bahwa G hampir bipartit jika menghapus tepi k (atau simpul) akan membuatnya menjadi bipartit. Apakah ada algoritma waktu poli untuk menentukan apakah grafik tepat atau kira-kira hampir
Dibandingkan dengan spektrum grafik tidak berarah, yang sesuai dengan matriks simetris, spektrum grafik berarah tidak terlalu dikenal: Diketahui bahwa graf berarah G=(V,E)G=(V,E)G = (V,E) memiliki matriks adjacency A(G)A(G)A(G) yang nilai eigennya adalah biner {0,1}{0,1}\{0,1\} jika GGG adalah...
Diberikan grafik bipartit tanpa bobot . Apakah benar bahwa selalu ada pencocokan non -tyty M ⊆ E (belum tentu maksimal), sehingga untuk setiap ( i , j ) ∈ E dengan saya cocok dan j tidak cocok , ia memegang deg ( i ) > deg ( j ) ? Di sini ( i , j ) tidak dipesan, yaitu, saya bisa berada di kedua...
Dalam tulisan ini , Hajnal menyatakan lemma berikut: Misalkan Gn,mGn,m\mathscr{G}_{n, m} adalah himpunan semua grafik bipartit dengan simpul di bagian kiri dan simpul di bagian kanan. Misalkan adalah nontrivial, monoton, dan invarian terkait dengan isomorfisme grafik bipartit. Pesan rangkaian...
The vertex jumlah isoperimetric dari grafik adalah . Beberapa makalah akademis menyatakan bahwa masalah penghitungan angka verteks isoperimetrik dari grafik adalah NP-hard, tanpa bukti atau referensi.G=(V,E)G=(V,E)G=(V,E) iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}i_V(G)...
Saya tertarik dengan masalah berikut. Diberikan grafik euler , kita harus menemukan partisi dari sisi-sisinya C 1 , C 2 , ... , C k ( ∪ i C i = E dan i ≠ j ↔ C i ∩ C j = ∅ ), sehingga setiap C i membentuk siklus sederhana dalam G dan k semaksimal
Pertanyaan serupa ditanyakan sebelumnya, tetapi ada kesalahan di dalamnya sehingga dibiarkan tidak dijawab kelas Grafik dengan nomor berwarna mudah, tetapi pewarnaan NP-keras Apakah ada rangkaian grafik tak terbatas seperti:CCC Ada algoritma polinomial yang mengenali untuk setiap grafik apakah G...