Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
565 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)

Lisans Matematik kategorisinde (25.4k puan) tarafından  | 565 kez görüntülendi

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

20,237 soru
21,758 cevap
73,397 yorum
2,052,430 kullanıcı