## PENENTUAN MATCHING MAKSIMUM PADA GRAF BIPARTIT BERBOBOT MENGGUNAKAN METODE HUNGARIAN
Muchammad Abrori 1 dan Rina Wahyuningsih 2

## Abstrak:
Matching is a part of graph theory that discuss to make a pair, that can be used to solve  many  problems;  one  of  them  is  the  assignment  problem.  The  assignment problem is to make a pair problem for n as the employees and for n as the duties, therefore  each  employee  gets  one  duty,  and  each  duty  is  given  exactly  for  each employee.  The  assignment  problem  can  be  solved  by  determining  the  matching in  weighted  bipartite  graph  through  Hungarian  Method.  It  can  be  determined from  the  alternating  tree  of  a  formed  edge.  If  there  is  augmenting  path,  that augmenting  path  is  used  to  form  the  more  number  of  matching.  If  the  formed path  is  alternating  path,  therefore  the  process  is  labeling  the  new  node  until finding the augmenting vertices. This matching is called as the perfect matching with  the  number  of  maximum  weighed  side  in  weighted  bipartite  graphs.  The result matching is the solution for the assignment problem by giving an employee with a duty.
Keywords: matching,  graph,  assignment problem,  Hungarian method.

## PENDAHULUAN
Sebuah  matching  merupakan  masalah  mengenai  mengawankan  elemen- elemen  dalam  sebuah  himpunan  dengan  elemen-elemen  dalam  himpunan  yang  lain. Sebuah  matching  merupakan  subset  M  dari  himpunan  edge  E  sedemikian  hingga tidak  ada  dua  edge  yang  incident  ke  suatu  verteks  yang  sama  (Magun:  2000). Matching  dapat  diapliksikan  dalam  banyak  hal,  misalnya  identifikasi  keaslian  tanda tangan, penentuan jadwal, solusi marriage problem atau pemasangan  antara laki-laki dengan perempuan, dan penyelesaian dari masalah penugasan (assignment problem). Penempatan  awal  task-task  ke  dalam  prosessor-prosessor,  dimana  biaya  dari  suatu penugasan  merupakan  fungsi  total  waktu  eksekusi  dan  total  waktu  komunikasi sehingga  diperoleh  penugasan  yang  optimal  yaitu  penugasan  yang  meminimumkan fungsi  kedua  biaya  tersebut  (Venkateswaran:  1993)  merupakan  contoh  lain  aplikasi dari matching.
Masalah penugasan merupakan permasalahan memasangkan n pegawai dan n tugas,  sedemikian  sehingga  setiap  pegawai  mendapatkan  satu  tugas,  dan  tiap  tugas diberikan tepat pada satu pegawai. Masalah penugasan dapat direpresentasikan dalam bentuk graf bipartit. Graf bipartit merupakan graf yang tidak memiliki  cycle  ganjil, loop,  dan  dapat dipartisi  menjadi  dua bagian  himpunan  simpul  yaitu 1 V dan 2 V , dengan 1 V menunjukkan himpunan pegawai, sedangkan himpunan tugas ditunjukkan
1 Jurusan Matematika, Universitas Islam Negeri Sunan Kalijaga Jln. Adi Sucipto no. 1, Jakarta 11440 E-mail : borymuch@yahoo.com
2 Jurusan Matematika, Universitas Islam Negeri Sunan Kalijaga Jln. Adi Sucipto no. 1, Jakarta 11440
Naskah diterima: 21 Desember 2011, direvisi: 20 Maret 2012, disetujui: 15 Mei 2012
dengan 2 V .  Sebuah  sisi  graf  menghubungkan  sebuah  pegawai  dengan  tugas  dapat diberi sebuah bobot yang menunjukkan bobot atau nilai pegawai terhadap tugas.
Masalah  penugasan  dapat  dicari  hasil  optimalnya  dengan  cara  menentukan matching  maksimum  pada  graf  bipartit  berbobot.  Matching  maksimum  pada  suatu graf bipartit berbobot adalah matching yang memiliki jumlah bobot yang maksimum, sehingga  penentuan  matching  maksimum  pada  graf  bipartit  berbobot  bukan  hanya sekedar mencari matching dengan kardinalitas terbanyak, tetapi juga memperhatikan bobot  yang  termuat  pada  sisi  graf  bipartit  tersebut.  Cara  menentukan  matching maksimum  pada  graf  bipartit  berbobot  ini  dapat  diselesaikan  menggunakan  metode Hungarian.  Sehingga  tujuan  dari  penelitian  ini  adalah  untuk  mendapatkan  matching maksimum pada graf bipartit berbobot menggunakan metode Hungarian
Metode  Hungarian  merupakan  salah  satu  metode  yang  digunakan  untuk menyelesaikan masalah penugasan. Ada dua macam intrepretasi dari metode ini, yaitu dengan menggunakan matrik dan graf bipartit berbobot.

## METODE PENELITIAN
Penelitian  dimulai  dengan  mempelajari  konsep  dasar  yang  berkaitan  dengan matching  pada  graf  bipartit  berbobot,  metode  Hungarian,  dan  masalah  penugasan. Selanjutnya  merumuskan  masalah  penugasan  dalam  bentuk  graf  bipartit  berbobot, sehingga dapat diselesaikan menggunakan metode Hungarian. Sebuah matrik ukuran 5x5  disajikan  sebagai  contoh  kasus  penelitian  (Howard  Anton,  1987:  84).  Matrik tersebut  dibawa  menjadi  matrik  penugasan  dan  direpresentasikan  ke  dalam  bentuk graf  bipartit  berbobot,  kemudian  dicari  matching  berbobot  maksimumnya menggunakan  metode  Hungarian.

## MATCHING

## Definisi : Matching (Kocay dan Kreher, 2004: 139)
Matching M adalah himpunan sisi sedemikian sehingga tidak terdapat dua sisi pada  M    yang  bertemu  pada  simpul  yang  sama.  Banyaknya  matching  yang  terdapat pada  suatu  graf  disebut  kardinalitas  matching,    dan    dilambangkan  dengan M . Contoh: Sisi matching 4 M pada graf 4 G adalah sisi ( ) ( ) 6 4 3 2 , , , v v v v dan ( ) . , 7 5 v v
Terdapat dua istilah simpul pada matching:
1. Simpul    Saturated.  Simpul  saturated  adalah  simpul  yang  incident  dengan  sisi pada matching M.  (Gondran dan Minoux, 1984: 280)
Contoh : simpul 6 4 3 2 , , , v v v v
2. Simpul  Unsaturated.  Simpul  unsaturated  adalah  simpul  yang  tidak  incident dengan setiap sisi pada matching  M.  (Gondran dan Minoux, 1984: 280)
Contoh : simpul 8 v dan 1 v 2 v 3 v 4 v 5 v 6 v 7 v 1 v 8 v
2 v 3 v 5 v 1 v 7 v 8 v 7 v 8 v 5 v 4 v 6 v
Selain simpul terdapat dua istilah lintasan pada matching, yakni:
1. Lintasan Alternating. Lintasan alternating adalah lintasan pada graf G yang sisi- sisinya  bergantian  antara  matching  dan  bukan  matching.  (Gondran  dan  Minoux,
1984: 281). Contoh: lintasan 6 4 5 7 8 v v v v v − − − − 2. Lintasan  Augmenting.  Lintasan  augmenting  adalah  lintasan  alternating  yang simpul  pangkal  dan  simpul  ujungnya  adalah  simpul  unsaturated  (Gondran  dan Minoux, 1984: 281). Contoh : lintasan
8 7 5 3 2 1 v v v v v v − − − − −

## Matching  Maksimum
M disebut matching maksimum jika G tidak memuat matching  M ′ yang lain dengan
M M > ′ . (Bondy dan Murty, 1976: 70)
Contoh:
Graf dengan matching yang belum
maksimum Graf dengan matching yang maksimum

## Pohon Alternating
Pohon  adalah  sebuah  graf  terhubung  yang  mempunyai  n  buah  simpul,  (n-1) sisi dan tidak mempunyai cycle (Samuel, 2008: 159). Sedangkan pohon alternating T merupakan  pohon  berakar  di  simpul  v,  jika  setiap  lintasan  yang  berawal  di  v  adalah lintasan alternating-M (Chartrand dan Oellerman, 1993:169).
Terdapat 2 bentuk pohon alternating dengan akar v, yakni:
1. Semua simpul  pada  T  kecuali v adalah simpul saturated-M.
2. Pohon  T  memuat sebuah simpul unsaturated-M  selain simpul v

## Masalah Penugasan
Masalah penugasan dapat dikelompokkan menjadi dua, yaitu :
1. Masalah  minimisasi,  yaitu  masalah  penugasan  yang  mencari  total  kerugian minimum.
2. Masalah  maksimasi,  yaitu  masalah  penugasan  yang  mencari  total  keuntungan maksimum.
1 v 2 v 3 v 4 v 1 v 2 v 3 v 4 v
1 v 2 v 3 v 4 v 8 v 7 v 6 v 1 e 2 e 3 e 4 e 5 e 6 e 7 e 5 v 1 v 2 v 3 v 4 v 8 v 7 v 6 v 1 e 2 e 3 e 4 e 5 e 6 e 7 e 5 v
Penyelesaian masalah penugasan sama  artinya dengan menentukan 1-regular subgraf  pada  graf  bipartit  G  dengan  kardinalitas  maksimum.  (Chatrand  dan Oellerman, 1993: 162)
Pada  kondisi  dimana  penilaian  menjadi  pertimbangan,  maka  hal  ini  dapat diselesaikan dengan menentukan sebuah 1-regular subgraf  H  pada graf  berbobot G dengan penjumlahan bobot sisi-sisi pada H  sehingga G  juga maksimum. (Chatrand dan Oellerman, 1993: 162)

## Penyelesaian Matching Maksimum dengan Metode Hungarian
Teorema-teorema  yang  menjadi  dasar  dalam  penentuan  matching  maksimum pada graf bipartit berbobot menggunakan metode Hungarian. (Berge, 1984: 122)
Misal 1 M dan 2 M adalah   matching  di  graf  G. Jika  H  adalah  subgraf perentang dari G dengan himpunan sisi ( ) ( ) 1 2 2 1 2 1 ) ( M M M M M M H E − ∪ − = ⊗ =
maka setiap komponen dari H akan mengikuti salah satu dari tipe berikut:
1. Sebuah simpul terasing.
2. Sebuah cycle genap dengan sisi bergantian antara M 1 dan M 2
3. Sebuah  lintasan  dengan  sisi  saling  bergantian  antara  M 1 dan  M 2 ,  sedemikian sehingga setiap simpul terakhir dari lintasan adalah simpul unsaturated  di M 1 dan M 2, tetapi bukan di keduanya. Ilustrasinya sebagai berikut:
1 H dan 2 H adalah  subgraf  perentang G

## Teorema: (Bondy dan Murty, 1976: 70)
Matching  M  di  G  adalah  matching  maksimum  jika  dan  hanya  jika  G  tidak memuat lintasan augmenting. Sebagai ilustrasi dari teorema ini diberikan graf G pada Gambar  di  bawah  ini.  Misalkan
{ } 6 4 2 , , e e e M = ′ adalah  matching  di  G  dan
8 7 6 5 4 3 2 1 , , , , , , , : v v v v v v v v P merupakan lintasan augmenting-M maka
{ } 7 5 3 1 , , , e e e e
M = adalah matching yang diperoleh dengan augmenting-M  sepanjang P,  dengan 1 4 + ′ = = M M Contoh : Augmenting-M sepanjang P (a) (b) 1 v 2 v 5 v 6 v 7 v 4 v 3 v 5 e 6 e 7 e 3 e 2 e 4 e : 2 H 1 v 2 v 5 v 6 v 7 v 4 v 3 v 1 e 3 e 7 e 6 e 4 e 5 e : 1 H 1 v 2 v 6 v 7 v 4 v 3 v : G 1 e 2 e 3 e 4 e 5 e 6 e 7 e 5 v

## Matching  Maksimum pada Graf Bipartit
Matching  maksimum  pada  graf  bipartit  adalah  banyaknya  matching  yang termuat pada suatu graf bipartit dengan kardinalitas yang maksimum.
Misalkan G merupakan graf bipartit dengan partisi ( ) Y X , . Jika X S ⊆ maka
persekitaran S adalah ( ) S N yaitu simpul-simpul yang adjacent dengan simpul di S.
Teorema (Kocay dan Kreher, 2004: 141)
Misalkan  G  adalah  graf  bipartit  dengan  partisi ( ) Y X , maka  G  memuat sebuah  matching  yang  memenuhi  setiap  simpul  X   jika  dan  hanya  jika
S S N ≥ ) ( untuk setiap
X S ⊆ .
Teorema  ini  membantu  dalam  penyusunan  pohon  alternating.  Chartrand  dan Oellermann (1993: 163) memberikan cara menyusun pohon alternating yang berakar pada v ,  yaitu  dengan  menempatkan  v  pada  tingkatan  0  dan  semua  simpul
k u u u , , , 2 1 K yang adjacent dengan v di G ditempatkan pada tingkatan 1, dan simpul v dihubungkan  pada  simpul ( ) . 1 k i u i ≤ ≤ Misal i v u 1 untuk k i ≤ ≤ 1 .  Simpul
k v v v , , , 2 1 K ditempatkan  pada  tingkatan  2,  dan  simpul  u  dihubungkan  pada  simpul
( ) . 1 k i v i ≤ ≤ Jika pohon alternating sudah tersusun pada tingkatan genap (m genap) maka setiap simpul ada tingkat m digunakan untuk menguji simpul  y  adjacent.
Simpul   y  adalah simpul di T Y − yang adjacent pada sebuah simpul x di S .  Jika  y  adalah simpul saturated dengan M yz ∈ dimana z bukan  termasuk  pohon alternating, sehingga simpul  y  ditempatkan pada tingkatan
1 + m dan z ditempatkan pada 2 + m ,  dengan  demikian    adjacent  dengan  y   dan  y   adjacent  dengan z ,  dan akan  terbentuk  pohon  alternating  seperti  gambar  (a)  di  bawah  ini.  Jika  y   adalah simpul unsaturated, maka pohon alternating dibangun dengan menambahkan simpul y   dan  sisi  xy ,  sehingga  didapat  lintasan  augmenting  dari  simpul v ke  simpul  y seperti  gambar  (b)  di  bawah  ini.  Dengan  lintasan  augmenting  ini  dapat  dibentuk matching baru yang lebih besar.
Contoh proses membangun pohon alternating
(a) Tingkatan (b)
Susunan  pohon  alternating  berhenti  jika  tidak  bisa  menambah  tingkatan pohon alternating atau lintasan augmenting telah ditemukan.
M L L L v x z y 2 + m 1 + m L 1 2 m M L L L v x y 0
1 v 2 v 3 v 4 v 5 v 6 v 6 8 3 3 3
Setiap  k-regular  graf  bipartit  mempunyai  matching sempurna  jika k > 0.
Matching  sempurna  pada  graf  bipartit  menghasilkan  kardinalitasnya  sebanyak ( ) 2 G V (Kocay dan Kreher, 2004: 143)

## Matching  Maksimum  pada  Graf  Berbobot
Matching maksimum pada graf berbobot merupakan matching yang memiliki jumlah bobot sisi yang maksimum. (Chartrand dan Oellermann, 1993: 163). Matching dengan  bobot  maksimum  belum  tentu  memiliki  kardinalitas  maksimum.  Contoh Matching berbobot maksimum dan  matching maksimum:

## .

## Matching  Maksimum  pada  Graf  Bipartit  Berbobot
Matching  maksimum  pada  graf  bipartit  berbobot  merupakan  matching sempurna dengan  jumlah  bobot  sisi  yang  maksimum  pada  graf bipartit  berbobot.
Misalkan G adalah graf bipartit berbobot dengan partisi himpunan 1 V dan 2 V . Graf G ′ adalah  graf  bipartit  lengkap  berbobot  yang  memuat  G  sebagai  subgraf.
Misalkan G ′ memiliki partisi
himpunan
1 U dan 2 U dengan
{ } 2 1 2 1 , maksimum V V U
U = = dan i V  termuat di i U  , untuk 2 , 1 = i . Misal 1 U x ∈ dan 2 U y ∈ ,    jika ( ) ( ) xy w xy w G G = ′ maka ( ) G E xy ∈ dan  jika ( ) 0 = ′ xy w G ,  maka
( ) G E xy ∈ .
Jika  M  adalah  matching  sempurna  dengan  jumlah  bobot  maksimum  di G ′ , maka ( ) G E M ∩ adalah matching maksimum di G dengan kardinalitas ( )
2 G V .
Pelabelan simpul atau ( ) x l adalah fungsi nilai real l dari himpunan simpul
2 1 V V ∪ untuk setiap
1 V v ∈ dan 2 V u ∈ ; ( ) ( ) ( ) u v w u v , ≥ + l l
dimisalkan ( ) ( ) u v w v V u , max 2 ∈ = l untuk setiap
1 V v ∈
0 ) ( = u l untuk setiap 2 V u ∈ maka  adalah  pelabelan  simpul  di         dengan
( ) ( ) ( ) ( ) { } vu w u v V u V v G vuE E = + ∈ ∈ ′ = l l l dan dan 2 1 l G ′

## Teorema (Chartrand dan Oellermann, 1993: 174)
Jika l adalah  pelabelan  simpul  pada  graf  bipartit  lengkap  berbobot  G ′ . Misal l H  adalah subgraf perentang dari   G ′ . Jika l E  memuat matching sempurna M ′ , maka  M ′ merupakan matching berbobot maksimum di  G ′

## Metode Hungarian
Berikut  adalah  metode  hungarian  untuk  menentukan  matching  maksimum pada graf biparti berbobot. Misalkan G ′ adalah  graf bipartit berbobot dengan partisi himpunan simpul 1 V dan 2 V .
1. Langkah pertama adalah melakukan pelabelan simpul l
1.1. Untuk 1 V v ∈ ∀ , misal ( ) ( ) u v w v V u , max 2 ∈ = l 1.2. Untuk 2 V u ∈ ∀ , misal ( ) 0 = v l
1.3. H l adalah subgraf perentang dari G l dengan himpunan sisi E l . 1.4. Misal G l adalah graf dasar dari H l.
2. Pilih sembarang matching M di l G
3. Jika  mendapatkan  matching  maksimum  di l G ,  dicari  apakah l G merupakan matching  sempurna  maka  menurut  teorema  di  atas  matching  sempurna  tersebut adalah matching maksimum di G ′ . Jika matching maksimum di l G  tersebut bukan matching sempurna, maka susun sebuah  pohon  alternating  T  yang  berakar  di  simpul  unsaturated  untuk menentukan pelabelan simpul baru l ′ .
Berikut  merupakan  langkah-langkah  untuk  menentukan  sebuah  pelabelan  simpul baru l ′ .
3.1. Jika setiap simpul di 1 V merupakan simpul saturated di M, maka M adalah matching maksimum di G ′ dan  proses berhenti. Jika tidak maka lanjutkan.
3.2. Misal x adalah simpul unsaturated di 1 V .
3.3. Susun pohon alternating dari M  yang berakar di  x.
Jika  terdapat  lintasan  augmenting-P  di l G ,  maka  gantikan  M    dengan
( ) P E M M ⊗ = ′ untuk mendapatkan matching baru.
Jika  tidak  memuat  lintasan  augmenting  P,  dan  T  adalah  pohon  alternating dari  M    dengan  akar    x    yang  tidak  dapat  diperluas  lagi  di l G ,  maka pelabelan simpul l diganti dengan sebuah pelabelan simpul baru l ′ dengan sifat bahwa M  dan T  termuat di graf dasar l G dari l ′ H .
4. Menghitung pelabelan simpul baru l ′ Misalkan:
= l m minimal ( ) ( ) ( )
) ( { 1 T V V v vu w u v ∩ ∈ − + l l dan )} ( 2 T V V u − ∈
Maka berlaku untuk l ′ :
( ) ( ) ( ) ( )      ∩ ∈ + ∩ ∈ − = ′ lainnya yang v T V V v untuk m v
T V V v untuk m v v l l l l l l ) ( ) ( 2 1
5. Jika pelabelan simpul yang baru belum memuat semua simpul di 1 V , maka ulang ke langkah 3.3.

## Contoh Kasus
Misal seorang manager sebuah perusahaan melakukan seleksi terdapat 5 calon pegawai ( ) 5 , , 2 , 1 K = i v i untuk  5  posisi  jabatan ( ) 5 , , 2 , 1 K = i u i .  Seleksi  dilakukan untuk  mengetahui  kemampuan  setiap  pelamar  untuk  setiap  posisi.  Kemampuan pelamar  kerja  merupakan  bobot  sisi  yang  menghubungkan  pelamar  kerja  dengan jabatan. Bentuk matrik
[ ] ij m M = dengan
( ) j i ij u v w m = 3 3 3 0 0 2 2 2 1 1 4 6 4 3 0 2 4 2 3 0 2 9 1 3 4 5 4 3 2 1 5 4 3 2 1 v v v v v u u u u u M =
G adalah graf bipartit berbobot dengan partisi himpunan simpul dengan partisi himpunan ( ) 5 4 3 2 1 1 , , , , v v v v v V = dan ( ) 5 4 3 2 1 2 , , , , u u u u u
V = dengan  mengikuti
langkah-langkah pada metode Hungarian diperoleh hasil sebagai berikut:
Langkah 1.a    Untuk
1 V v ∈ ∀ ,  misal ( ) ( ) u v w v V u , max 2 ∈ = l Sehingga diperoleh ( ) ( ) 3 , 2 , 6 , 4 , 9 = v l Untuk 2 V u ∈ ∀ ,  misal ( ) 0 = u l maka nilai pelabelan ( ) ( ) 0 , 0 , 0 , 0 , 0 = u l 1.b Misal l H adalah subgraf perentang dari G ′ dengan himpunan sisi l E 1.c Misal l G  adalah graf dasar dari l H
Langkah 2.    Pilih sembarang matching M di l G Misal dipilih ( ) ( ) ( ) 3 5 5 4 4 2 0 , , , , , u v u v u v M =
: G 2 v 3 v 4 v 5 v 1 v 1 u 3 u 4 u 5 u 2 v 1 v 3 v 4 v 5 v 1 u 2 u 3 u 4 u 5 u 1 v 4 v 5 v 3 v 1 u 2 u 3 u 4 u 5 u 2 v 2 u
Langkah 3.a   Terdapat  simpul  pada 1 V yang  merupakan  simpul  unsaturated  di  M, maka lanjutkan.
3.b 1 v adalah  simpul  unsaturated  di 1 V sehingga 1 v digunakan  sebagai simpul akar.
3.c  Susun pohon alternating dari M  yang berakar di 1 v . Diperoleh pohon
alternating  T  dengan ( ) { } 2 4 1 , , v u v T V = ,  karena  tidak  ditemukan lintasan  augmenting  dan  pohon  alternating  T   tidak  dapat  diperluas lagi di l G , maka pelabelan simpul l diganti dengan sebuah pelabelan simpul baru l ′ .
Pohon alternating pertama
Langkah 4. Menghitung pelabelan baru l ′
= l m minimal ( ) ( ) ( ) ) ( { 1 T V V v vu w u v ∩ ∈ − + l l dan )} ( 2 T V V u − ∈ { } 2 1 1 , ) ( v v T V V v = ∩ ∈ dan { } 5 3 2 1 2 , , , ) ( u u u u T V V u = − ∈ diperoleh 1 = l m yakni  pada  sisi ( ) 2 2 u v sehingga  pelabelan  simpul
baru ( ) v l ′ yang terbentuk adalah: ( ) ( ) { } ( ) { } ( )      ∩ ∈ = + ∩ ∈ = − = ′ lainnya yang untuk v T V V u untuk m u T V V v untuk m v v
l l l l l l ) ( 0 , 1 , 0 , 0 , 0 ) ( 3 , 2 , 6 , 3 , 8 2 1 Matching 0 M dan sisi l m
Langkah 5. Karena pelabelan simpul l ′ yang baru belum memuat semua   simpul l , maka ulang  ke langkah 3.c
Langkah  3.c  Susun  pohon  alternating  dari  M  yang  berakar  di 1 v .  Diperoleh  pohon
alternating  T  dengan ( ) { } 2 2 4 1 , , , u v u v T V = ,  karena    ditemukan lintasan  augmenting-M  yakni ( ) ( ) ( ) { } 2 2 4 2 4 1 0 , , , , , u v u v u v P = maka
lintasan  augmenting 0 P   digunakan  untuk  membentuk  matching    baru dan kembali ke langkah 3.a.
1 v 2 v 3 v 4 v 5 v 4 u 3 u 2 u 1 u 5 u 1 v 4 u 2 v
1 v 2 u 4 u 2 v Pohon alternating kedua ( ) ( ) ( ) { } 3 5 5 4 4 2 0 , , , , , u v u v u v M = ( ) ( ) ( ) { } 2 2 4 2 4 1 0 , , , , , u v u v u v P = maka ( ) ( )( ) ( ) { } 2 2 4 1 3 5 5 4 0 0 1 , , , , , , u v u v u v u v P M M = ⊗ = Matching 1 M
Langkah 3.a   Terdapat  simpul  pada 1 V yang  merupakan  simpul  unsaturated  di  M, maka lanjutkan.
Langkah 3.b 3 v   adalah  simpul  unsaturated  di 1 V sehingga 3 v   digunakan  sebagai simpul akar.
Langkah 3.c   Susun pohon alternating dari M  yang berakar di
3 v . Diperoleh pohon alternating  T  dengan ( ) { } 4 5 5 3 1 4 3 , , , , , , v u v u v u v T V =
,  karena  tidak ditemukan  lintasan  augmenting,  dan  pohon  alternating  T  tidak  dapat diperluas lagi di l G , maka pelabelan simpul l diganti dengan sebuah pelabelan simpul baru l ′ Pohon alternating ketiga
Langkah 4. Menghitung pelabelan baru l ′ = l m minimal ( ) ( ) ( ) ) ( { 1 T V V v vu w u v ∩ ∈ − + l l dan )} ( 2 T V V u − ∈ { } 5 4 3 1 1 , , , ) ( v v v v T V V v = ∩ ∈ dan { } 2 1 2 , ) ( u u T V V u = − ∈
dari  perhitungan  diperoleh
1 = l m yakni  pada  sisi ( ) 1 4 u v dan  sisi
( ) 2 4 u v , pelabelan baru yang terbentuk  adalah :
3 u 5 v 5 u 4 v 4 v 1 u 3 v 1 v 2 v 3 v 4 v 5 v 4 u 3 u 2 u 1 u 5 u
( ) ( ) { } ( ) { } ( )      ∩ ∈ = + ∩ ∈ = − = ′ lainnya yang untuk v T V V u untuk m u T V V v untuk m v v
l l l l l l ) ( 1 , 2 , 1 , 0 , 0 ) ( 2 , 1 , 5 , 3 , 7 2 1
Langkah 5. Karena pelabelan simpul l ′ yang baru belum memuat semua   simpul l , maka ulang  ke langkah 3.c.
Matching 1 M dan sisi l m
Langkah 3.c Susun pohon alternating dari M  yang berakar di
3 v .   Diperoleh pohon alternating  T  dengan ( ) { } 1 4 5 5 3 1 4 3 , , , , , , , u v u v u v u v T V = ,  karena diperoleh lintasan augmenting i ( ) ( ) ( ) ( ) ( ) { } 1 4 5 4 5 5 3 5 3 3 1 , , , , , , , , , u v u v u v u v u v
P = maka lintasan augmenting 1 P digunakan  untuk  membentuk  matching  baru  dan kembali pada langkah 3.a
Pohon alternating keempat ( ) ( )( ) ( ) { } 2 2 4 1 3 5 5 4 1 , , , , , , u v u v u v u v M = ( ) ( ) ( ) ( ) ( ) { } 1 4 5 4 5 5 3 5 3 3 1 , , , , , , , , , u v u v u v u v u v P = maka ( ) ( ) ( ) ( ) ( ) { } 1 4 4 1 5 5 2 2 3 3 1 1 2 , , , , , , , , , u v u v u v u v u v P M M = ⊗ = Matching 2 M 3 u 5 v 5 u 4 v 4 v 1 u 1 u 3 v 1 v 2 v 3 v 4 v 5 v 4 u 5 u 1 u 2 u 3 u 1 v 2 v 3 v 4 v 5 v 4 u 5 u 1 u 2 u 3 u
( ) 1 2 1 0 0 5 4 3 2 1 5 4 3 2 1 i u v v v v v u u u u u M l = Langkah 3.a  Setiap  simpul  di 1 V merupakan  simpul  saturated  di 2 M maka matching adalah matching maksimum di G ′ dan proses berhenti. Jadi ( ) ( ) ( ) ( ) ( ) ( ) { } 1 4 4 1 5 5 2 2 3 3 2 , , , , , , , , , u v u v u v u v u v G E
M = ∩
adalah matching maksimum di G.
Dari  langkah-langkah  di  atas  diperoleh  matching  sempurna  dengan  bobot maksimum sebesar 20. dan kardinalitas matching M adalah 5. Jadi penempatan calon pegawai pada posisi jabatan adalah sebagai berikut:
calon pegawai 1 v pada jabatan 4 u , calon pegawai 2 v pada jabatan 2 v , calon pegawai 3 v  pada jabatan 3 u ,
calon pegawai 4 v pada jabatan 1 u , dan, calon pegawai 5 v  pada jabatan 5 u .

## Solusi penempatan pegawai

## E. Kesimpulan
Matching  maksimum  pada  graf  bipartit  berbobot  dapat  ditentukan menggunakan metode Hungarian. Matching tersebut merupakan matching  sempurna dengan    dengan    kardinalitas  dan  jumlah    bobot    sisi    yang    maksimum    pada    graf bipartit  berbobot.
Matching  maksimum  yang  diperoleh  pada  graf  bipartit  berbobot  merupakan solusi optimal dari masalah penugasan yakni memasangkan seorang pegawai dengan sebuah tugas.
Metode  Hungarian  dapat  membantu  perusahaan  atau  institusi  dalam mengambil keputusan terutama menyangkut pemberian pekerjaan, penempatan posisi pegawai,  pembuatan jadwal dan lain sebagainya.
( ) 2 1 5 3 7 i v l        
        3 3 3 0 0 2 2 2 1 1 4 6 4 3 0 2 4 2 3 0 2 9 1 3 4 1 v 2 v 3 v 4 v 5 v 4 u 5 u 1 u 2 u 3 u

## Daftar Pustaka
Anton, Howard, 1987, Aljabar Linear Elementer: Jakarta. Berge, Coulde, 1970, Graph and Hypergraph, Dunod: Netherlands. Bondy,  J.A dan  Murty,  U.S.R.,  1976,  Graph  Theory  with  Applications,  Mac  Millan  Press: New York.
Chartrand, Gary dan Oellermann, Ortrud, 1993,  Applied and Algoritmic Graph Theory, Mc Graw  Hill  International  Edition: New York.
Gondran, M. dan Minoux, M., 1984, Graphs and Algorithms. John Wiley & Sons, Ltd.:
Chichester, Inggris.
Kocay, William dan Kreher, Donald, 2005, Graph Theory and Optimization, Chapman & Hall / CRC.
Magun,  J.,  2000.  Greedy  Matching  Algorithms,  an  Experimental  Study.  Schweizerischer Nationalfond, Grant NF 2000-422 44.94. Z ű rich, Switzerland.
Venkateswaran,  R.,  Obranivic,  Z.,  Raghavendra,  C.S.,  1993.  Cooperative  Genetic  for Optimization Problem in Distributed Computer System. Technical report TR-EECS-93- 018. School of EECS. Washington State University. Wibisono, Samuel, 2008, Matematika Diskrit. Edisi Kedua, Graha Ilmu: Yogyakarta.