Çızgelerde döngü sıfır zorlama

Bir çizgenin döngü sıfır zorlama sayısı, döngü renk degi¸stirme kuralına dayanır. Bu ˘ kuralda eger beyaz renkli ˘ v kö¸se noktası, u siyah kö¸se noktasının tek beyaz kom¸susu ise, v kö¸se noktasının rengi siyah olarak degi¸stirilir. Ayrıca, beyaz bir ˘ v kö¸se noktasının tüm kom¸suları siyah ise, v kö¸se noktasının rengi siyah olarak degi¸stirilir. Minimum döngü sıfır ˘ zorlama kümesi, çizgenin tüm kö¸se noktalarını siyah renge dönü¸stüren minimum sayıda elemana sahip siyah renkteki kö¸se noktaların kümesidir. Bir çizgenin döngü sıfır zorlama sayısı, minimum döngü sıfır zorlama kümesinin eleman sayısıdır. Döngü yayılım süresi, çizgenin tüm kö¸se noktalarını siyaha dönü¸stürmek için minimum döngü sıfır zorlama kümelerine kar¸sılık gelen tur sayılarının minimumudur. Ba¸sarısız döngü sıfır zorlama sayısı, çizgenin tüm kö¸se noktalarını siyah renge dönü¸stüremeyen en geni¸s kö¸se noktalar kümesidir. Döngü kısma sayısı ise bir döngü sıfır zorlama kümesinin eleman sayısı ile döngü yayılma süresinin toplamını minimize eder. Bu çalı¸smada, çizgenin döngü sıfır zorlama sayısı, döngü yayılım süresi, döngü kısma sayısı ve ba¸sarısız döngü sıfır zorlama sayısının çe¸sitli özellikleri incelenmi¸stir. Ayrıca, bu kavramların ekstrem degerlerini veren çizgeler karakterize edilmi¸stir.