Matching Graf

  • June 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Matching Graf as PDF for free.

More details

  • Words: 352
  • Pages: 2
KELOMPOK: INAYATUL AINI JAUHARI

0607258 0607096

MILKI M. FAISAL

0607212

PIPIN FITRIADI

0607173

RAIFA MUKTI

0607564

TEORI GRAF MATCHING Definisi: Subset M dalam E disebut Matching di G jika elemen-elemennya adalah sisi yang bukan loop dan setiap dua sisinya tidak saling ajasen di G. Ujung-ujung sisi di M dikatakan Matched di bawah M. Sebuah Matching M Saturates terhadap titik v, dan v disebut M-saturated, jika ada sisi dalam M insiden dengan v. Jika tidak ada, v disebut M-unsaturated. Jika setiap titik dalam G M-saturated, maka Matching M Sempurna. M adalah Maximum Matching jika G tidak memiliki Matching M’ dengan |M’| >|M|, sehingga setiap Matching Sempurna adalah Maximum Matching.

Misal M Matching di G, sebuah lintasan M-alternating di G adalah lintasan yang sisi-sisinya bergantian di E \ M dan M. Contoh: Lintasan v5v8v1v7v6 di gambar (Maximum Matching) adalah sebuah lintasan M-alternating. Lintasan M-augmenting adalah lintasan M-alternating yang pangkal dan ujungnya M-unsaturated.

Teorema 5.1( Berge,

1957)

Matching M di G adalah Maximum Matching jika hanya jika G tidak memuat lintasan M-augmenting. Bukti (→) Misalkan M Matching di G, dan misalkan bahwa G memuat lintasan Maugmenting v0v1 . . . v2m+1. Definisikan M’ ⊆ E dengan M’=(M\{ v1v2, v3v4, . . ., v2m-1v2m}) ∪ { v0v1, v2v3, . . ., v2mv2m+1} Maka M’ adalah Matching di G, dan |M’|=|M|+1. Sehingga M bukan Maximum Matching. (←) Misalkan M bukan Maximum Matching, dan misalkan M’ Maximum Matching di G, maka |M’|>|M|. H=G[M ∆ M’] dimana M ∆ M’ menotasikan perbedaan simetris M dan M’. Setiap titik dalam H memiliki derajat 1 atau 2 di H, karena setiap titik hanya bisa berinsiden dengan paling banyak 1 sisi dalam M, dan 1 sisi dalam M’. Jadi setiap komponen dalam H adalah siklus genap dengan sisi-sisi yang bergantian di M dan M’, atau lintasan dengan sisi-sisi yang bergantian di M dan M’. H memuat lebih banyak sisi dalam M’ daripada M, dan terdapat komponen lintasan P dalam H yang sisi awal dan akhirnya dalam M’. Dikarenakan pangkal dan ujung lintasan P merupakan M’-saturated di H, maka pangkal dan ujung tersebut Munsaturated di G. sehingga P adalah lintasan M-augmenting di G.

Related Documents

Matching Graf
June 2020 12
Graf
May 2020 26
Matching Colours
October 2019 58
Graf Garis
May 2020 16
Para Graf
May 2020 16