1.2 Perumusan Masalah

Graf G (V,E) yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2). Sedangkan pewarnaan sisi adalah cara pemberian warna pada garis sedemikian rupa sehingga setiap garis yang terkait pada titik yang sama diberi warna yang berbeda. Kemudian graf G didekomposisi menjadi kelompok subgraf dimana setiap subgraf hanya memuat sisi di G dengan warna yang sama. Masing – masing subgraf tersebut adalah matching di graf bipartit G. Proses tersebut dinamakan dekomposisi graf bipartit menjadi matching.