Edge cover

Dalam Teori graf, edge cover merupakan himpunan busur (edge) sehingga tiap simpul (vertex) pada graf insiden dengan setidaknya satu busur dari himpunan. Dalam pengetahuan komputer, masalah minimum edge cover merupakan masalah untuk menemukan edge cover dengan ukuran yang paling minimal. Ini merupakan masalah optimasi yang bisa didudukkan dalam waktu polinomial. Secara formal, sebuah edge cover dari graf G merupakan himpunan busur C sehingga tiap simpul insiden dengan setidaknya satu busur dalam himpunan busur C. Dengan ujar lain, tiap 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)}
Tiap 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 merupakan 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) tetapi tiap simpul dalam V insiden dengan setidaknya satu busur di C.