Teorema Pernikahan

Sumber: huffpost.com

Sumber: huffpost.com

Mumun adalah seorang mak comblang, dia hendak menjodohkan 4 laki-laki kepada 4 perempuan. Dia bertanya kepada para laki-laki, siapa perempuan yang mereka sukai kemudian Mumun membuat diagram sebagai berikut.

Diagram 1

Diagram 1

Tanda garis adalah kesukaan. Adi dan Galuh sama-sama suka Citra. Bejo menyukai 2 perempuan sekaligus yaitu Ajeng dan Dea, sedangkan Didit naksir Berliana.

Apakah Mumun bisa menjodohkan mereka semua? Apakah terjadi kesesuaian? Yaitu semua laki-laki dan perempuan mendapatkan pasangan tanpa ada satupun yang tertinggal. Mmm… sepertinya tidak mungkin karena Adit dan Galuh menyukai perempuan yang sama. Karena tidak ada kesesuaian, Mumun menyuruh meraka semua kembali berkencan satu-sama lain, Mumun berharap para lelaki mengubah pikirannya. Oh.. stratregi Mumun tepat, dia memperbarui diagramnya sebagai berikut

Diagram 2

Diagram 2

Mmm… sepertinya juga belum ada kesesuaian karena pada diagram 2, Didit dan Galuh sama-sama menyukai Ajeng. Kembali Mumun melakukan strategi yang sama dan kembali dia memperbarui diagramnya.

Diagram 3

Diagram 3

Nah… sepertinya baru terjadi kesesuaian. Mumun bisa menjodohkan Adi – Citra, Bejo – Berliana, Didit – Ajeng dan Galuh – Dea.

Sekarang timbul pertanyaan

Apa syarat suatu digaram sehingga terjadi kesesuaian?

Peranyaan diatas dijawab oleh teorema berikutnya.

Teorema Pernikahan: Diberikan himpunan laki-laki A dan himpunan perempuan B dengan |A| = |B|, kesesuaian hanya akan terjadi jika hanya jika untuk setiap himpunan bagian X ⊆ A terdapat Y ⊆ A yaitu perempuan-perempuan yang disukai para lelaki di X dengan |X| ≤ |Y|.

Teorema Pernikahan dibuktikan oleh Philip Hall (1935) sehingga sering disebut Teorema Pernikahan Hall atau sederhananya cukup disebut Teorema Hall.

Sekarang mari coba kita lihat diagram 1, pada diagaram 1 terlihat Andi dan Galuh sama-sama menyukai Citra.  Dengan kata lain, kita mendapatkan X = {Andi, Galuh} dan Y= {Citra} dengan |x| > |Y|,  bertentangan dengan Teorema perkawinan. Itulah sebabnya tidak terjadi kesesuaian di diagram 1. Hal serupa juga terjadi pada diagram 2.

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in graph theory and tagged , , . Bookmark the permalink.

2 Responses to Teorema Pernikahan

  1. X says:

    Tantangan pak, aturan/pola apa yg mungkin utk membentuk deret ini:
    tak terhingga, 5, 6, 3, 3, 3, 3, 3, …
    petunjuk: ada hubungannya sama geometri

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s