Algoritma Hungarian

Teorema Algoritma Hungarian membentuk matching maximum pada graf bipartit.

Misalkan G adalah graf bipartit dengan partisi (X,Y). Dalam algoritma jika saturates setiap simpul di X, maka matching maximum. Jika tidak, kita pilih sebuah M–unsaturated simpul u di X dan secara sistematik mencari lintasan M–augmenting P yang bermula di u, harus alternate diantara X dan Y. Selama G adalah graf bipartit. Algoritma membentuk himpunan S dan N(S), terdiri dari semua simpul X dan Y, yang membentuk lintasan alternating. Jadi P akan ditemukan jika ada. Jika u bukan saturated, maka │S│= │N(S)│+1. Setiap simpul di S selain u adalah matched. S dan N(S) kemudian dihapus dari graf. Penghapusan simpul mengakibatkan algoritma berhenti? Pada Teorema Hall’s, tidak ada sisi [S, Y – N(S)]. Misalkan lintasan alternating dari simpul z є X terbentuk. Jika lintasan dimana simpul y pada penghapusan N(S) hanya bisa menyatukan ke simpul yang lain di S dan N(S). Sehingga tidak menyatukan ke lintasan augmenting. Oleh karena itu simpul dihapus. Setelah selesai, algoritma akan mempunyai hasil matching M tidak terdapat lintasan augmenting pada graf. Oleh teorema (Berge, 1957) M adalah matching maximum.