Pengertian Bipartisi dalam Teori Graf

Dalam teori graf, bipartisi suatu graf adalah pembagian himpunan simpulnya menjadi dua himpunan yang saling lepas (disebut himpunan partit) sedemikian rupa sehingga semua sisinya menghubungkan simpul-simpul dari himpunan partit yang berbeda. Dengan kata lain, tidak ada sisi di antara simpul-simpul pada himpunan partisit yang sama.

Sebagai contoh, perhatikan sebuah graf dengan 4 simpul {a,b,c,d} dan kita membagi himpunan simpul tersebut menjadi dua bagian : {a,b} dan {CD}. Graf tersebut bersifat bipartit karena semua sisi menghubungkan simpul-simpul dari bagian yang berbeda.

Bipartisi dapat digunakan untuk mengurangi kompleksitas algoritma untuk permasalahan graf seperti traversal graf, pencarian jalur terpendek, dan pencocokan graf.