Page 18 - bilim_dergisi

Aycan ve Koç Denizli İl Millî Eğitim Müdürlüğü Bilim ve Eğitim Dergisi 1(1), 2025 *Hatice Nur KOÇ

grafı bir alt grafıdır. Aynı zamanda kendisi ve her bir düğümü tek başına da bir alt grafını oluşturur (Şentürk, 2024).

2.4.2. Tanım G bir graf olsun. V, G’nin düğümler kümesi ve E, G’nin kenarlarının kümesi olarak verilsin. ⊆ , G
grafının boş olmayan düğümler kümesinin alt kümesi olsun. G grafında bulunan tüm kenarların en az bir tane uç düğümü
bu H kümesinde bulunuyorsa H kümesine örtü kümesi denilir. Yani, G grafında bulunan kenarların tümü H kümesindeki
düğümler ile ilişkili olursa buna örtü denir. Bir graf için birden fazla örtü tanımlanabilir. Bir G grafının örtü kümelerinin
içinden en az düğüm sayısına G grafının örtü sayısı denilir. Örtü sayısı ( ) şeklinde gösterilir. V sonlu bir küme
olduğundan H örtü kümesi de sonlu bir kümedir (Şentürk, 2024).

Aşağıdaki örnekte basit bir graf yapısı için örtüyü ve örtü sayısını inceleyelim.

Örnek 1 K1,7 grafının örtü sayısını bulunuz.

Şekil 2.4.3. 1,7 Grafı

H1 = {v1} benzer şekilde H2 = {v2, v3, v4, v5, v6, v7} farklı örtü kümeleri bulunabilir. En az düğüm sayısı olan kümeyi
bulduğumuz için α(K1,7) = 1 diyebiliriz (Şentürk, 2024).

Örnek 2 de daha açıklayıcı bir graf modeli geliştirerek bunun üzerinde örtü kavramı ile bu kavramın önemini sunmaya
çalıştık.

Örnek 2 Bir grup insan tarafından, şekilde graf modeli verilen yerleşim alanına geri dönüşüm bilincini artırmak
amacıyla geri dönüşüm için çöp kutuları konulmak isteniyor. Bununla birlikte yerleşim alanının her ana caddesine en
az bir tane geri dönüşüm çöp kutusu koymayı hedefliyorlar. Bu hedefe ulaşabilmek için en az kaç tane geri dönüşüm
kutusu gerekir? (Şentürk, 2024).

Şekil 2.4.4. Yerleşim Alanının Graf Modeli
Örnekte istenilen şartlar doğrultusunda verilen grafın örtü sayısını bulmalıyız. Bunun için ise en az düğüm kümesini
bulmamız yeterli olacaktır.

Graftaki her ana caddeye en az bir geri dönüşüm çöp kutusu yerleştirmeli ve bununla birlikte bunu en az geri dönüşüm
çöp kutusu sayısıyla yapmamız gerekiyor. Seçimlerimizi de bu yönde yapmalıyız.

v1 düğümünü ele alarak başlayalım. düğümü; e1, e9 ve e11 caddelerinin ortak düğümüdür. v1 düğümünü seçebiliriz.
Böylelikle v1 düğümünü seçerek üç cadde için en az bir çöp kutusu koymuş oluruz.
v2 düğümünü ele alalım. v 2 düğümü; e1, e2 ve e7 caddelerinin ortak düğümüdür. v2 düğümünü seçmemizin sebebi ise
sadece üç caddenin ortak düğümü olması değildir. Bu düğümü seçmediğimiz durumunda oluşabilecek düğüm kümesi
sayısı fazlalaşacaktır.

v2’yi de bu yüzden seçiyoruz. Böylelikle e 2 ve e7 caddeleri için de geri dönüşüm çöp kutusu en az bir tane olmuş oldu.

9