Latihan 3.

Salah satu cara untuk memeriksa apakah suatu pencocokan parsial sudah maksimum adalah dengan membentuk lintasan berselang-seling. Lintasan ini merupakan urutan sisi-sisi yang bertetangga, yang secara bergantian terdiri atas sisi dalam pencocokan dan sisi di luar pencocokan (tidak ada sisi yang boleh digunakan lebih dari satu kali). Jika sebuah lintasan berselang-seling berawal dan berakhir dengan sisi yang tidak berada dalam pencocokan, lintasan itu disebut lintasan augmentasi.
  1. Temukan lintasan berselang-seling terpanjang yang mungkin untuk pencocokan parsial pada graf teman Anda. Apakah lintasan tersebut merupakan lintasan augmentasi? Bagaimana lintasan ini membantu Anda menemukan pencocokan yang lebih besar?
    Sebuah graf bipartit dengan sepuluh simpul yang terbagi ke dalam dua himpunan beranggotakan lima simpul. Namai simpul-simpul atas a, b, c, d, e dan simpul-simpul bawah 1, 2, 3, 4, 5. Graf tersebut memiliki sisi-sisi berikut: a-1, a-3, b-1, b-2, c-1, c-2, c-4, d-5, e-4, dan e-5. Di antaranya, sisi a-1, b-2, c-4, dan e-5 ditampilkan dengan garis tebal.
  2. Temukan lintasan berselang-seling terpanjang yang mungkin untuk pencocokan parsial berikut. Apakah terdapat lintasan augmentasi? Apakah pencocokan parsial tersebut merupakan pencocokan parsial maksimum dalam graf ini?
    Sebuah graf bipartit dengan 12 simpul yang terbagi ke dalam dua himpunan beranggotakan enam simpul. Namai simpul-simpul atas a sampai f dan simpul-simpul bawah 1 sampai 6. Graf tersebut memiliki sisi-sisi berikut: a-2, a-3, b-1, b-3, c-1, c-2, c-4, c-5, d-3, d-5, e-3, e-4, e-5, e-6, f-5, dan f-6. Di antaranya, sisi a-3, b-1, c-2, e-4, dan f-5 ditampilkan dengan garis tebal.
dalam konteks