Page 13 - bilim_dergisi

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

Şekil 1.7. Dört Küp Problemi

2. Graf Yapılarda Temel Kavramlar

Bu bölümde Graf çeşitleri, Graf yapıların temel tanım ve özellikleri verilmiştir.

2.1.1. Tanım G grafı, nokta ve kenarlardan oluşan bir yapıdır. Şöyle ki, elemanları düğüm (nokta) olarak adlandırılan
sonlu ve boş olmayan ( ) = {v1, v2, v3, … , vn} kümesi ile sonlu ve boş olmayan elemanları ise kenar olarak
adlandırılan ( ) = { , , , , … , } kümesinden oluşur.
1
2
3
= ( ( ), ( )) şeklinde tanımlanır. Daha kısa bir gösterim ile = ( , ) ya da sadece ile gösterilir. Bir grafı
çizmek için düğüm(nokta) ile bu düğümler arasında geçişi sağlayan kenarlar gereklidir. Fakat bu düğüm ve kenarlar ile
oluşturulabilecek graflar tek değildir (Demir,2021).
2.1.2. Tanım Bir = ( , ) grafında, aşağıdaki özelliği sağlayan iki noktaya komşu denir.

• G grafına ait olan iki noktayı birleştiren en az bir kenar vardır. G grafından alınan bir noktasına komşu olan

tüm noktalara , noktasının bir komşuluğu denir.

Şekil 2.1.1. G grafı
Şekil 2.1.1 deki graftaki komşulukları;

=
1
1 2
=
2
2 3
olduğundan noktaları ile ve noktaları komşudur. ile noktaları arasında bu noktaları
2
3
3
1
2
1
birleştiren bir kenar bulunmadığından ile noktaları komşu değildir (Şentürk, 2024).
3
1
2.1.3. Tanım Bir grafta ortak noktaya sahip olan kenarlara bitişik kenarlar denir. Ayrıca herhangi bir = ( , )
grafında herhangi bir kenardan çizilebilen kenar sayısı, o noktanın derecesi olarak adlandırılır. Bu kenara dersek ( )
ile gösterilir. Bir grafın derecesi en küçük olan noktasına minimum dereceli nokta denir ve bir grafının minimum
dereceli noktasının derecesi ( ) ile gösterilir. Bir grafın derecesi en büyük olan noktasına maksimum dereceli nokta
denir ve bir grafının maksimum dereceli noktasının derecesi ∆( ) ile gösterilir. = ( , ) bir graf olsun. Grafta bir
noktanın derecesi 0 ise bu noktaya izole nokta denir. ∈ için ( ) = 1 ise ya sarkık nokta denir (West, 2001;
Sunar, 2021).
2.1.4. Tanım Bir grafına ait iki nokta arasına birden çok kenar çizilebiliyor ise, buna katlı kenarlar denir. G grafında
bir kenarın uç noktaları aynı olursa bu kenar ilmek adını alır (Sunar, 2021; Vasudev,2006).
2.1.5. Tanım Bir grafın nokta sayısı; | | ve kenar sayısı; | | şeklinde gösterilir ve bir grafının nokta sayısı ve kenar
sayısı sonlu (| | < ∞ | | < ∞) ise sonlu graf denir (Sunar, 2021; Vasudev,2006).

4