Minggu, 26 Juni 2011
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).
Langganan:
Posting Komentar (Atom)
Pemborong Bangunan Karawang
PEMBORONG BANGUNAN DAERAH KARAWANG Pelaksana pemborong bangunan terpercaya siap kerjakan: Renovasi Rumah, Bangun Rumah Baru, ...
-
Teorema (Hall, 1935) Jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai matching sempurna. Bukti....
-
Teorema 2. 2 (Hall, 1935) Misal G adalah graf bipartit dengan partisi ( X,Y ). Maka G mengandung sebuah matching saturates setiap sim...
Tidak ada komentar:
Posting Komentar