Matching adalah salah satu bagian dari teori graf yang banyak membahas mengenai pemasangan. Matching M merupakan himpunan dari edge dengan tidak ada dua edge dari M yang incident pada satu vertex. Matching dapat menyelesaikan berbagai permasalahan. Salah satu permasalahan tersebut adalah marriage problem, yaitu bagaimanakah menentukan pasangan dari sekumpulan laki-laki dan perempuan dengan syarat bahwa mereka telah saling mengenal.
Tujuan dari penulisan skripsi ini adalah membahas matching dalam bipartite graph dan diaplikasikan untuk menyelesaikan marriage problem. Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur.
Kasus marriage problem dapat diilustrasikan dalam bipartite graph yang kemudian dicari matching awalnya. Dari matching awal ini akan dicari perfect matching. Perfect matching merupakan penyelesaian dari marriage problem dengan mencari alternating path. Alternating path dimulai dari unmatched vartex untuk mendapatkan matching yang lebih besar hingga didapat perfect matching. Berdasarkan pembahasan dapat disimpulkan bahwa matching dalam bipartite graph dapat digunakan untuk menyelesaikan marriage problem dengan mencari perfect matching.
