Edge cover: Perbedaan antara revisi
k Maximum matching harus dibuat dalam topik tersendiri. Sebaliknya informasi tentang edge cover masih kurang memadai, bdk. dengan versi bahasa Inggris |
|||
| Baris 10: | Baris 10: | ||
C = {(2,3),(1,4),(1,5),(1,6)}<br /> |
C = {(2,3),(1,4),(1,5),(1,6)}<br /> |
||
Disini bisa dipilih busur (2,3) untuk menggantikan busur (1,2) dan busur (1,3) namun setiap simpul dalam V insiden dengan setidaknya satu busur di C. |
Disini bisa dipilih busur (2,3) untuk menggantikan busur (1,2) dan busur (1,3) namun setiap simpul dalam V insiden dengan setidaknya satu busur di C. |
||
== ''Maximum Matching'' == |
|||
''Maximum matching'' adalah himpunan busur M dimana tiap simpul insiden dengan hanya satu busur dalam M. Dengan kata lain, M adalah himpunan busur dimana ujung-ujung dari tiap busurnya tidak saling berbagi. |
|||
(a,b), (c,d) € M, dimana: a != c, a != d, b != c, b != d |
|||
Gambar berikut menunjukkan contoh ''maximum matching'' dari graf G |
|||
<br />[[Berkas:G3.PNG]]<br /> |
|||
M = {(2,3), (1,6)}<br /> |
|||
''Maximum matching'' ini digunakan untuk mencari ''edge cover''. Kita lihat kasus graf G, terlihat bahwa ''edge cover'' C adalah M digabung dengan busur (1,5) dan busur (1,6). |
|||
Revisi per 14 April 2012 03.21
Definisi
Dalam Teori graf, edge cover adalah himpunan busur (edge) sehingga setiap simpul (vertex) pada graf insiden dengan setidaknya satu busur dari himpunan. Dalam ilmu komputer, masalah minimum edge cover adalah masalah untuk menemukan edge cover dengan ukuran yang paling minimal. Ini adalah masalah optimasi yang dapat diselesaikan dalam waktu polinomial. Secara formal, sebuah edge cover dari graf G adalah himpunan busur C sehingga setiap simpul insiden dengan setidaknya satu busur dalam himpunan busur C. Dengan kata lain, setiap simpul merupakan ujung dari salahsatu atau lebih busur dalam C. Gambar berikut menunjukkan menunjukkan contoh edge cover dari graf G.
C = {(1,2),(1,3),(1,4),(1,5),(1,6)}
Setiap simpul dalam V = {1,2,3,4,5,6} insiden dengan setidaknya satu busur di C. Simpul 1 insiden (merupakan ujung) dengan busur (1,2), (1,3), (1,4), (1,5), dan (1,6). Simpul 2 insiden dengan busur (1,2). Simpul 3 insiden dengan busur (1,3). Simpul 4 insiden dengan busur (1,4). Simpul 5 insiden dengan busur (1,5). Dan simpul 6 insiden dengan busur (1,6).
Minimum Edge Cover
Minimum edge cover adalah edge cover dengan ukuran seminimal mungkin. Gambar berikut menunjukkan contoh minimum edge cover dari graf G.
C = {(2,3),(1,4),(1,5),(1,6)}
Disini bisa dipilih busur (2,3) untuk menggantikan busur (1,2) dan busur (1,3) namun setiap simpul dalam V insiden dengan setidaknya satu busur di C.