Bir köşenin iç ve dış derecesini anlamak için öncelikle köşenin derecesi kavramını öğrenmemiz gerekir. Bundan sonra bir köşenin iç ve dış derecelerini kolaylıkla anlayabiliriz. İç derece ve dış derecenin ancak yönlendirilmiş grafikte belirlenebileceğini bilmeliyiz. Yönsüz bir grafik yardımıyla bir tepe noktasının derecesini hesaplayabiliriz. Yönsüz grafikte bir tepe noktasının iç ve dış derecesini hesaplayamayız.
Bir tepe noktasının derecesi
Bir grafikte her bir köşenin derecesini bulmak istiyorsak, bu durumda belirli bir köşenin diğer köşeyle kurduğu ilişkilerin sayısını saymamız gerekir. Yani bir köşenin derecesini o köşeye bağlanan kenar sayısını hesaplayarak belirleyebiliriz. Bir tepe noktasının derecesi derece(v) yardımıyla gösterilir. Eğer n sayıda köşe içeren basit bir grafik varsa, bu durumda herhangi bir köşenin derecesi şöyle olacaktır:
Deg(v) = n-1 ∀ v ∈ G
Bir köşe, kendisi dışında bir grafikteki diğer tüm köşelerle bir kenar oluşturma yeteneğine sahiptir. Yani basit bir grafikte, bir tepe noktasının derecesi, bir grafikteki köşe sayısı eksi 1 ile bulunacaktır. Burada kendi tepe noktası için 1 kullanılmıştır, çünkü kendi başına bir döngü oluşturmaz. Eğer grafik kendi kendine döngüye sahip köşeleri içeriyorsa, bu tür bir grafik basit bir grafik olmayacaktır.
Örnek:
string'i int'ye dönüştürme
Bu örnekte 6 köşesi olan bir grafiğimiz var; yani a, b, c, d, e ve f. 'a' köşesinin derecesi 5'tir ve diğer tüm köşelerin derecesi 1'dir. Eğer herhangi bir köşe 1. dereceye sahipse, o zaman bu tür köşe 'son köşe' olarak bilinecektir.
Bir tepe noktasının derecesini dikkate alabileceğimiz, aşağıda açıklanan iki grafik durumu vardır:
- Yönlendirilmemiş grafik
- Yönlendirilmiş grafik
Şimdi yönlendirilmiş bir grafikte bir tepe noktasının derecesini ve yönsüz bir grafikte bir tepe noktasının derecesini ayrıntılı olarak öğreneceğiz.
Yönlendirilmemiş bir grafikte bir tepe noktasının derecesi
Yönsüz bir grafik varsa, bu tür grafikte yönlü kenar olmayacaktır. Yönsüz bir grafikte bir tepe noktasının derecesini belirlemeye yönelik örnekler aşağıda açıklanmaktadır:
Örnek 1: Bu örnekte yönsüz bir grafiği ele alacağız. Şimdi bu grafikteki her köşenin derecesini öğreneceğiz.
Çözüm: Yukarıdaki yönsüz grafikte toplam 5 adet köşe noktası vardır, yani a, b, c, d ve e. Her köşenin derecesi şu şekilde tanımlanır:
- Yukarıdaki grafik 'a' köşesinde buluşan 2 kenar içermektedir. Dolayısıyla Derece(a) = 2
- Bu grafik 'b' köşesinde buluşan 3 kenar içerir. Dolayısıyla Derece(b) = 3
- Yukarıdaki grafik 'c' köşesinde kesişen 1 kenar içermektedir. Dolayısıyla Deg(c) = 1. c köşesi aynı zamanda sarkık köşe olarak da bilinir.
- Yukarıdaki grafik 'd' köşesinde buluşan 2 kenar içermektedir. Dolayısıyla Derece(d) = 2.
- Yukarıdaki grafik 'e' köşesinde buluşan 0 kenar içermektedir. Dolayısıyla Deg(a) = 0. E köşesine izole edilmiş köşe de denilebilir.
Örnek 2: Bu örnekte yönsüz bir grafiği ele alacağız. Şimdi bu grafikteki her köşenin derecesini öğreneceğiz.
Çözüm: Yukarıdaki yönsüz grafikte toplam 5 adet köşe noktası vardır; yani a, b, c, d ve e. Her köşenin derecesi şu şekilde tanımlanır:
Köşe derecesi a = derece(a) = 2
Köşe derecesi b = derece(b) = 2
Köşe derecesi c = derece(c) = 2
Köşe derecesi d = derece(d) = 2
Köşe derecesi e = derece(e) = 0
Bu grafikte asılı bir tepe noktası yoktur ve 'e' tepe noktası izole bir tepe noktasıdır.
Yönlendirilmiş grafikte tepe noktası derecesi
Grafik yönlendirilmiş bir grafikse, bu grafikte her köşenin bir iç derece ve bir dış derece olması gerekir. Yönlendirilmiş bir grafiğin olduğunu varsayalım. Bu grafikte bir tepe noktasının iç derecesini, dış derecesini ve derecesini bulmak için aşağıdaki adımları kullanabiliriz.
Bir tepe noktasının derecesi
Bir tepe noktasının derecesi, v ile birlikte kenarların sayısı olarak tanımlanabilir; burada v, terminal tepe noktasını belirtmek için kullanılır. Yani köşeye gelen kenar sayısı olarak tanımlayabiliriz. Sözdizimi deg yardımıyla-(v), bir tepe noktasının derecesini yazabiliriz. Bir tepe noktasının derecesini belirlemek istiyorsak bunun için tepe noktasında biten kenar sayısını saymamız gerekir.
Bir tepe noktasının dış derecesi
Bir tepe noktasının dış derecesi, v ile birlikte bir dizi kenar olarak tanımlanabilir; burada v, başlangıç tepe noktasını belirtmek için kullanılır. Yani tepe noktasından çıkan bir takım kenarlar olarak tanımlayabiliriz. Sözdizimi deg yardımıyla+(v), bir tepe noktasının dış derecesini yazabiliriz. Bir köşenin dış derecesini belirlemek istiyorsak bunun için köşeden başlayan kenar sayısını saymamız gerekir.
Bir tepe noktasının derecesi
Bir tepe noktasının derecesi, bir tepe noktasının iç derecesi ve bir tepe noktasının dış derecesinin toplamına eşit olan derece(v) yardımıyla gösterilir. Bir tepe noktasının derecesinin sembolik gösterimi şu şekilde tanımlanır:
Deg(v) = deg-(v) + deg+(v)
Örnek 1: Bu örnekte bir grafiğimiz var ve her köşenin derecesini belirlememiz gerekiyor.
Çözüm: Bunun için öncelikle bir köşenin derecesini, bir köşenin iç derecesini ve daha sonra bir köşenin dış derecesini bulacağız.
Yukarıdaki grafiğin toplam 6 köşeyi içerdiğini görebildiğimiz gibi, yani v1, v2, v3, v4, v5 ve v6.
Derecede:
Bir tepe noktasının derecesi v1 = derece(v1) = 1
Bir tepe noktasının derecesi v2 = derece(v2) = 1
Bir tepe noktasının derecesi v3 = derece(v3) = 1
Bir tepe noktasının derecesi v4 = derece(v4) = 5
Bir tepe noktasının derecesi v5 = derece(v5) = 1
Bir tepe noktasının derecesi v6 = derece(v6) = 0
Dış derece:
Bir tepe noktasının dış derecesi v1 = derece(v1) = 2
Bir tepe noktasının dış derecesi v2 = derece(v2) = 3
Bir tepe noktasının dış derecesi v3 = derece(v3) = 2
Bir tepe noktasının dış derecesi v4 = derece(v4) = 0
Bir tepe noktasının dış derecesi v5 = derece(v5) = 2
Bir tepe noktasının dış derecesi v6 = derece(v6) = 0
Bir tepe noktasının derecesi
Yukarıda açıklanan tanımın yardımıyla bir köşe noktasının derecesinin Deg(v) = derece olduğunu biliyoruz.-(v) + sen+(v). Şimdi bu formülün yardımıyla şu şekilde hesaplayacağız:
Tepe noktasının derecesi v1 = derece(v1) = 1+2 = 3
Tepe noktasının derecesi v2 = derece(v2) = 1+3 = 4
Tepe noktasının derecesi v3 = derece(v3) = 1+2 = 3
Tepe noktasının derecesi v4 = derece(v4) = 5+0 = 5
Tepe noktasının derecesi v5 = derece(v5) = 1+2 = 3
Tepe noktasının derecesi v6 = derece(v6) = 0+0 = 0
Örnek 2:
Bu örnekte 7 köşeli yönlendirilmiş bir grafiğimiz var. 'a' köşesi, dışarı doğru uzanan 'ad' ve 'ab' olmak üzere 2 kenar içerir. Dolayısıyla, 'a' köşesi dış dereceyi içerir, yani 2. Benzer şekilde, 'a' köşesinin de bu 'a' köşesine doğru gelen bir 'ga' kenarı vardır. Dolayısıyla 'a' köşesi 1 olan dereceyi içerir.
Çözüm: Yukarıdaki köşelerin tümünün iç derecesi ve dış derecesi şu şekilde tanımlanır:
Derecede:
Bir tepe noktasının derecesi a = derece(a) = 1
Bir tepe noktasının derecesi b = derece(b) = 2
Bir tepe noktasının derecesi c = derece(c) = 2
Bir tepe noktasının derecesi d = derece(d) = 1
Bir tepe noktasının derecesi e = derece(e) = 1
Bir tepe noktasının derecesi f = derece(f) = 1
Bir tepe noktasının derecesi g = derece(g) = 0
'mason' formülü'
Dış derece:
Bir tepe noktasının dış derecesi a = derece(a) = 2
Bir tepe noktasının dış derecesi b = derece(b) = 0
Bir tepe noktasının dış derecesi c = derece(c) = 1
Bir tepe noktasının dış derecesi d = derece(d) = 1
Bir tepe noktasının dış derecesi e = derece(e) = 1
Bir tepe noktasının dış derecesi f = derece(f) = 1
Bir tepe noktasının dış derecesi g = derece(g) = 2
Her köşenin derecesi:
Bir tepe noktasının derecesinin Deg(v) = derece olduğunu biliyorduk.-(v) + sen+(v). Şimdi bu formülün yardımıyla şu şekilde hesaplayacağız:
Tepe noktasının derecesi a = derece(a) = 1+2 = 3
Bir tepe noktasının derecesi b = derece(b) = 2+0 = 2
Tepe noktasının derecesi c = derece(c) = 2+1 = 3
Tepe noktasının derecesi d = derece(d) = 1+1 = 2
Tepe noktasının derecesi e = derece(e) = 1+1 = 2
Tepe noktasının derecesi f = derece(f) = 1+1 = 2
Tepe noktasının derecesi g = derece(g) = 0+2 = 2
mysql kullanıcı oluştur
Örnek 3: Bu örnekte 5 köşeli yönlendirilmiş bir grafiğimiz var. 'a' köşesi, dışarı doğru giden 1 kenar, yani 'ae' içerir. Dolayısıyla 'a' köşesi 1 olan bir dış derece içerir. Benzer şekilde, 'a' köşesinin de bu 'a' köşesine doğru gelen bir 'ba' kenarı vardır. Dolayısıyla 'a' köşesi 1 olan dereceyi içerir.
Çözüm: Yukarıdaki köşelerin tümünün iç derecesi ve dış derecesi şu şekilde tanımlanır:
Derecede
Bir tepe noktasının derecesi a = derece(a) = 1
Bir tepe noktasının derecesi b = derece(b) = 0
Bir tepe noktasının derecesi c = derece(c) = 2
Bir tepe noktasının derecesi d = derece(d) = 1
Bir tepe noktasının derecesi e = derece(e) = 1
Dış derece:
Bir tepe noktasının dış derecesi a = derece(a) = 1
Bir tepe noktasının dış derecesi b = derece(b) = 2
Bir tepe noktasının dış derecesi c = derece(c) = 0
Bir tepe noktasının dış derecesi d = derece(d) = 1
Bir tepe noktasının dış derecesi e = derece(e) = 1
Her köşenin derecesi:
Bir tepe noktasının derecesinin Deg(v) = derece olduğunu biliyorduk.-(v) + sen+(v). Şimdi bu formülün yardımıyla şu şekilde hesaplayacağız:
Tepe noktasının derecesi a = derece(a) = 1+1 = 2
Bir tepe noktasının derecesi b = derece(b) = 0+2 = 2
Tepe noktasının derecesi c = derece(c) = 2+0 = 2
Tepe noktasının derecesi d = derece(d) = 1+1 = 2
Tepe noktasının derecesi e = derece(e) = 1+1 = 2
Örnek 4: Bu örnekte bir grafiğimiz var ve her köşenin derecesini, iç derecesini ve dış derecesini belirlememiz gerekiyor.
Çözüm: Bunun için önce bir köşenin iç derecesini, sonra da dış derecesini bulacağız.
Yukarıdaki grafiğin toplam 8 köşeyi içerdiğini görebildiğimiz gibi, yani 0, 1, 2, 3, 4, 5 ve 6.
Derecede:
Bir tepe noktasının derecesi 0 = derece(0) = 1
Bir tepe noktasının derecesi 1 = derece(1) = 2
Bir tepe noktasının derecesi 2 = derece(2) = 2
Bir tepe noktasının derecesi 3 = derece(3) = 2
Bir tepe noktasının derecesi 4 = derece(4) = 2
Bir tepe noktasının derecesi 5 = derece(5) = 2
Bir tepe noktasının derecesi 6 = derece(6) = 2
Dış derece:
Bir tepe noktasının dış derecesi 0 = derece(0) = 2
Bir tepe noktasının dış derecesi 1 = derece(1) = 1
Bir tepe noktasının dış derecesi 2 = derece(2) = 3
Bir tepe noktasının dış derecesi 3 = derece(3) = 2
Bir tepe noktasının dış derecesi 4 = derece(4) = 2
Bir tepe noktasının dış derecesi 5 = derece(5) = 2
Bir tepe noktasının dış derecesi 6 = derece(6) = 1
javascript'e tıkla
Her köşenin derecesi:
Bir tepe noktasının derecesinin Deg(v) = derece olduğunu biliyorduk.-(v) + sen+(v). Şimdi bu formülün yardımıyla şu şekilde hesaplayacağız:
Tepe noktasının derecesi 0 = derece(0) = 1+2 = 3
Tepe noktasının derecesi 1 = derece(1) = 2+1 = 3
Tepe noktasının derecesi 2 = derece(2) = 2+3 = 5
Tepe noktasının derecesi 3 = derece(3) = 2+2 = 4
Tepe noktasının derecesi 4 = derece(4) = 2+2 = 4
Tepe noktasının derecesi 5 = derece(5) = 2+2 = 4
Tepe noktasının derecesi 6 = derece(5) = 2+1 = 3
Bir Grafiğin derece dizisi
Bir grafiğin derece sırasını belirlemek için öncelikle grafikteki her köşenin derecesini belirlememiz gerekir. Daha sonra bu dereceleri artan sırada yazacağız. Bu sıraya/sıraya bir grafiğin derece dizisi denilebilir.
Örneğin: Bu örnekte 3, 4 ve 5 köşeli üç grafiğimiz var ve tüm grafiklerin derece sırası 3'tür.
Yukarıdaki grafikte 3 köşe bulunmaktadır. Bu grafiğin dizisinin derecesi şu şekilde açıklanmaktadır:
Yukarıdaki grafikte 4 köşe bulunmaktadır. Bu grafiğin derece dizisi şu şekilde açıklanmaktadır:
Yukarıdaki grafikte 5 köşe bulunmaktadır. Bu grafiğin derece dizisi şu şekilde açıklanmaktadır: