Edge cover

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 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).