1-factorable

Jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai 1–factorable :

Misal graf G adalah k–regular graf bipartit dengan k > 0. Sesuai teorema 2.2 (Hall, 1935), kondisi matching pada G, karena menurut corollary 2.1 jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai matching sempurna. Warnai semua sisi pada matching sempurna dengan satu warna, kemudian memindahkannya dari G, kita memperoleh (k–1)–regular graf bipartit. Ulangi proses ini k kali dan selesai.

Sistematika Penulisan

Sistematika penulisan dalam skripsi ini adalah sebagai berikut :

BAB I Pendahuluan. Bab ini menjelaskan latar belakang permasalahan, perumusan masalah, batasan masalah, tujuan penulisan, manfaat penulisan, kerangka berpikir dan sistematika penulisan.

BAB II Landasan Teori. Bab ini menguraikan teori yang menjadi dasar dan penunjang dalam matching pada dekomposisi graf bipartit.

BAB III Pembahasan. Bab ini menjelaskan tentang proses matching pada dekomposisi graf bipartit yang digunakan untuk pembuktian teorema (Konig’s, 1916).

BAB IV Kesimpulan dan Saran. Bab ini berisikan tentang kesimpulan dan saran yang telah diperoleh dari bab – bab sebelumnya.

Kerangka Berpikir

Suatu graf bipartit G=(V,E) terdiri dari dua partisi V(G), yaitu X(G) dan Y(G). Setiap sisi di E(G) mempunyai simpul di X(G) dan simpul lainnya di Y(G). 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’. Kedua, menggunakan tahapan pertama dan jika G’ adalah k–regular graf bipartit dengan k > 0, maka G’ mempunyai 1–factorable. Terakhir, penghapusan simpul dan sisi dummy pada G’ yang telah ditambahkan pada tahapan pertama. Tahapan – tahapan tersebut merupakan proses matching pada dekomposisi graf bipartit untuk pembuktian teorema (Konig’s, 1916).

Manfaat Penulisan

Manfaat bagi penulis adalah untuk mengetahui dan memahami lebih dalam tentang teorema (Konig’s, 1916).

Tujuan Penulisan

Tujuan dari penulisan skripsi ini adalah untuk alternatif pembuktian teorema (Konig’s, 1916).

Batasan Masalah

Pembahasan skripsi ini dibatasi hanya pada graf bipartit.