Memahami Dwipartition dalam Teori Graf
Dalam teori graf, pembahagian dua graf ialah pembahagian set bucunya kepada dua set bercapah (dipanggil set partit) supaya semua tepi menyambung bucu daripada set partit yang berbeza. Dalam erti kata lain, tiada tepi antara bucu dalam set partit yang sama.
Sebagai contoh, pertimbangkan graf dengan 4 bucu {a,b,c,d} dan kami membahagikan set bucu kepada dua bahagian : {a,b} dan {c,d}. Graf adalah dwipartit kerana semua tepi menyambung bucu dari bahagian yang berbeza.
Dwipartition boleh digunakan untuk mengurangkan kerumitan algoritma untuk masalah graf seperti traversal graf, pencarian laluan terpendek dan padanan graf.
Saya menyukainya
Saya tidak menyukainya
Laporkan ralat kandungan
Kongsi
