BAB IV PENUTUP

Kesimpulan

Matching pada dekomposisi graf bipartit dapat digunakan untuk pembuktian teorema (Konig’s, 1916), karena proses matching pada dekomposisi graf bipartit dapat digunakan untuk menemukan minimum pewarnaan sisi pada graf bipartit, proses matching pada dekomposisi graf bipartit adalah sebagai berikut :

· Tahapan pertama : Jika G adalah graf bipartit, maka G mempunyai ∆–regular bipartit supergraf dengan menambahkan simpul dan sisi dummy pada G, sehingga graf G menjadi graf bipartit ∆–regular G’.

· Tahapan kedua : Menggunakan tahapan pertama dan jika G’ adalah k–regular graf bipartit dengan k > 0, maka G’ mempunyai 1–factorable.

· Tahapan ketiga : Penghapusan simpul dan sisi dummy pada graf G’ yang telah ditambahkan pada tahapan pertama.

Saran

Dapat mengembangkan matching pada dekomposisi graf bipartit ini dengan cara menggunakan algoritma yang lebih efisien. Sehingga dapat menghasilkan alternatif pembuktian yang lebih baik.