Kose ortusu ve minimum kose ortu sayisi nedir?

0 beğenilme 0 beğenilmeme
68 kez görüntülendi

Kose ortusu ve minimum kose ortu sayisi nedir? (vertex cover, minimum vertex cover)

Asagidaki cizgeler icin minimum kose ortu sayisini bulunuz ($n,m$ pozitif tamsayi):

$K_n, K_{n,m},C_n$   (tam cizge, iki parcali tam cizge, dongusel cizge)

7, Ağustos, 2015 Lisans Matematik kategorisinde Sercan (23,218 puan) tarafından  soruldu

Kn complete graphları temsil ediyordu yanlış hatırlamıyorsam ve n(n-1)/2 kenar içeriyordu. Cn cycles idi galiba ve n kenar n düğüm içeriyordu. Kn,m complete Bipartite, m+n düğüm, m*n kenar içeriyordu. 

Secilen koselerin kenarlarinin cizgeyi tamamen ortmesi. Bu sarti saglayan minimum da, minimum sayi yapiyor. Yani kose sayisi ile ilgili degil bu soru.

Ayrica soruyu okuyan ve bilgili (/bilgisiz) arkadaslar daha iyi bir ceviri sunabilirlerse.. kose ortusu icime pek sinmedi..

...