matching

M ⊆E(G) dikatakan suatu matching di G jika tidak ada sisi dari M yang saling adjacent di G. Simpul ujung dari sisi di M disebut matched di bawah M. Misalkan M suatu matching di G jika suatu simpul di v terkait dengan sisi di M, maka v dikatakan M–saturated sebaliknya, jika suatu simpul v tidak terkait dengan sisi di M, maka v dikatakan M–unsaturated. Jika setiap simpul di G adalah M–saturated, matching M adalah sempurna. Matching Sempurna adalah matching dengan semua simpul matched pada graf. Matching M pada G dengan jumlah terbesar sisi dibandingkan dengan matching lainnya pada G disebut matching maksimum. Jelas, setiap matching sempurna adalah maksimum.

Misalkan M suatu matching di G Suatu lintasan M–alternating di G adalah lintasan yang melewati simpul dan sisi yang berbeda dimana sisi – sisinya berselang – seling di E\M dan M. Suatu lintasan M–augmenting di G adalah lintasan M–alternating yang simpul awal dan simpul akhirnya M–unsaturated, karena kita akan gunakan untuk membangun matching yang lebih besar dari M.

Teorema (Berge, 1957) Matching M pada graf G akan maksimum jika dan hanya jika G tidak mengandung lintasan M–Augmenting.

Bukti : Asumsikan M merupakan matching pada G. misal G mengandung lintasan M–Augmenting P = v₀v₁, . . . , v_2m+1. Akan dibuktikan M bukan matching maksimum. (perhatikan bahwa _2m+1 jumlah sisi pada P) harus berjumlah ganjil karena setiap sisi lain melewati M, dan v₀v₁ dan v_2mv_2m+1 keduanya tidak melewati M.

Didefinisikan himpunan sisi – sisi M' ⊆E dimana

M' = (M \ { v₁v_2, v₃v_{4, ... ,} v_2m-1v_2m }) ∪{ v₀v_1, v₂v_{3, ... ,} v_2mv_2m+1 }.

Maka, M' merupakan matching pada G dengan nilai │M'│ =│M│+ 1. Karena │M'│ >│M│terbukti M bukan matching maksimum.

Kebalikannya, tentukan bahwa M bukan matching maksimum. Misal M' matching maksimum di G, maka│M'│>│M│ (2.1)

Himpunan H = G[ M ∆ M' ], dengan M ∆ M' menunjukkan beda simetrik di M dan M'.

Setiap simpul di H berderajat 1 atau 2, karena setiap simpul di H insident dengan paling banyak satu sisi di M dan satu sisi di M’. Dengan demikian, komponen H adalah lintasan yang sisi nya bergantian di M dan M’ atau siklus dengan banyak sisi nya adalah genap. Karena M’ dimisalkan sebagai matching maksimum, dari penjelasan sebelumnya diperoleh |M’| > |M|. Akibatnya, H mempunyai lebih banyak sisi di M’ dibandingkan sisi di M. Sehingga lintasan P di H yang sisi awal dan sisi akhirnya adalah anggota dari M’. Dengan kata lain simpul awal serta simpul akhir dari lintasan P merupakan M’–saturated di H, M–unsaturated di G. Maka lintasan P adalah lintasan M–augmenting.