Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde kullanılan ispat yöntemlerinden birisidir. Bu yöntemde bir varlığın oluşmasının gösterilmesi hedeflenir. Örneğin aşağıdaki teoriyi inşaa yöntemi ile ispat edelim:
“2’den büyük her çift n sayısı için n düğüm içeren 3-düzenli graf bulunur”
Öncelikle k-düzenli graf tanımını hatırlayalım:
Bir graf üzerindeki her düğümün “k” kadar komşusu bulunması durumuna k-düzenli graf denilir. Örneğin aşağıdaki graf 2-düzenli bir graftır çünkü her düğümün derecesi 2′dir.
Dolayısıyla ispatlanmak istenen nazariyede bize düğüm derecelerinin en az 3 ve daha fazla olabildiği bildirilmiş bir k-düzenli graf isteniyor.
Bir graftaki kenarları aşağıdaki küme ile ifade etmek mümkündür:
K =
{ {i,i+1} | 0 ≤ i ≤ n-2} U { n – 1 , 0 } }
U { {i, i+ n/2 } | 0 ≤ i ≤ n/2 – 1 }
Yukarıda iki satır olarak tanımlanan kenarlar kümesindeki ilk satırı komşu düğümleri gösteren satır ve ikinci satırı karşı düğümleri gösteren satır olarak düşünebiliriz. Buna göre n adet düğüm içeren bir grafta her düğüm içi kendisinden önce ve kendisinden sonraki düğümlere birer kenar olduğu kabul edilirse (ilk satır) ayrıca karşısındaki düğüme de bir kenar olduğu kabul edilirse (alttaki satır) bu durumda her düğümün 3. derece olması mümkündür denilebilir.
Yukarıdaki grafta bu durum tasvir edilmiştir. Grafın bir çember olmasını sonsuz sayıda düğüm içermesi olara düğünebiliriz. Bu çeber üzerindeki bir noktayı komşusu olan 2 noktaya bağlayan birer kenar (mavi ile gösterilmiştir) ve tam karşısında buluna noktaya bağlayan(kırmızı ile gösterilmiştir) birer kenar çizilmesi durumunda n > 2 düğümü bulunan herhangi bir graf için 3-düzenli graf bulunabileceğini tasvir etmiş oluruz.
Yukarıdaki örnekte kullanılan ispat yöntemine bakıldığında bir varlığı oluşturan diğer varlıkların ispatta kullanıldığını görürüz. Örneğin 3-düzenli graf kavramını oluşturan bir düğüm ve 3 kenar varlıklarının ayrı ayrı gösterilmesi ve bu varlıkların üzerine ispatın inşası mümkün olmuştur.