Havel Hakimi Algorithm in C#
Anlatıma başlamadan önce kodumuzu verelim :)
https://github.com/muhammedtanriverdi/Havel_Hakimi_C_Sharp
Havel Hakimi algoritması verilen özelliklerden bir graph(çizge) oluşup oluşmadığını bulmaya yarayan algoritmadır. (Türkçe karşılıklarını tam bilmediğim için yanlış olabilir, affola)
Verilen özelliklerden kastımız tanımlanan vertexler (köşe) ve her vertex için tanımlanan edgeler(kenar ya da derece)dir. Bunlara uygun graph var mı yok mu bunun kontrolünü yapacağız.
Örnek ile başlayalım :
2 tane vertex olsun A ve B
A'nın 2 tane edge'i olsun
B'nin de 2 tane edge olsun
gözle görülebilen problem oldu, verilen özelliklere uygun graph oluşmaz, çünkü 2 vertex arasında 1 edge olur ve her iki vertex de 1 edge'e sahip olabilir en fazla.
gördüğümüz gibi özelliklere uygun graph vardır diyebiliriz.
Peki havel hakimi teoremi bu olayı nasıl çözümlemiş :
En büyükten en küçüğe doğru edge sayılarını sıralamış ve degree (derece) demiş
yukarıdaki örnek ile gösterelim 3 vertex ve her biri 2 edge sahip.
O zaman;
S : 2, 2, 2 diye sıralanır.
Buradan anlaşılıyor ki 3 tane vertex var.
1. adım = eğer herhangi bir derece büyük eşitse toplam derece sayısından => Başarısız.
( yani eğer herhangi bir vertexe ait edge sayısı büyükse ya da eşitse toplam vertex sayısından => Başarısız. )
mesela ilk örnekteki S : 2, 2 başarısız. Çünkü vertex sayısı 2, herhangi bir vertexe ait edge sayısı da 2.
2. adım = eğer tek derecelerin toplam sayısı tek ise => Başarısız.
mesela S : 3, 2, 1, 1 başarısız. Çünkü tek olanlar (3, 1 ve 1 ; teklerin toplamı tek sayı) toplam 3 tane.
3. adım = eğer herhangi bir derece 0 dan küçükse => Başarısız.
4. adım = eğer bütün dereceler 0 ise => BAŞARILI
5. adım = dereceleri sırala
6. adım = ilk sıradaki dereceyi tut
7. adım = ilk sıradaki dereceyi sil
8. adım = ilk sıradaki derece sayısı kadar, sıradaki derecelerden 1 tane eksilt.
Yani mesela S : 3, 2, 2, 2, 2 örneğinde ilk sıradaki 3'ü tuttuk ve sildik. Bu adımda elimizde kalan S : 2, 2, 2, 2 kümesindeki ilk 3 dereceyi (BİR) eksiltiyoruz. Oluşan sonuç S : 1, 1, 1, 2
9. adım = 3. adıma geri dön
Örneğimize geçelim, kimyadan bir örnek yapalım, C2H6 bir graph mıdır ? (C, 4 bağ / H, 1 bağ.... bu bilgi lazım :)
C2H6 ne demek oluyor. Toplamda 8 tane verteximiz var. Ve karbonlar 4 edge, hidrojenler 1 edge sahip olacaklar. Yani
A - 4
B - 4
C - 1
D - 1
E - 1
F - 1
G - 1
H - 1
diyebiliriz.
O zaman
S : 4 4 1 1 1 1 1 1
ile başlayalım
kontroller
1. adım (en buyuk derece 4 >=? toplam vertex 8 / HAYIR )
2. adm (tek derecelerin toplamı 6 tane =? tek sayı / HAYIR)
3. adım ( herhangi bir derece <? 0 / HAYIR)
ilk derece olan 4'ü tuttuk sildik
k = 4
S : 4 1 1 1 1 1 1
ve geri kalan sıradaki 4 dereceden (BİR) çıkardık
S : 3 0 0 0 1 1 1
adım 3'e geri döndük. 0'dan küçük derece var mı? YOK gibi kontrolleri yazmıyorum artık :)
S : 3 1 1 1
3 ü tuttuk ve sildik
k = 3
S : 1 1 1
geri kalan sıradaki (k = 3) taneden (BİR) çıkardık
S : 0 0 0
adım 3
adım 4 (Hepsi 0 BAŞARILI :)
Umarım yardımcı olabilmişimdir....
Anlatıma başlamadan önce kodumuzu verelim :)
https://github.com/muhammedtanriverdi/Havel_Hakimi_C_Sharp
Havel Hakimi algoritması verilen özelliklerden bir graph(çizge) oluşup oluşmadığını bulmaya yarayan algoritmadır. (Türkçe karşılıklarını tam bilmediğim için yanlış olabilir, affola)
Verilen özelliklerden kastımız tanımlanan vertexler (köşe) ve her vertex için tanımlanan edgeler(kenar ya da derece)dir. Bunlara uygun graph var mı yok mu bunun kontrolünü yapacağız.
Örnek ile başlayalım :
2 tane vertex olsun A ve B
A'nın 2 tane edge'i olsun
B'nin de 2 tane edge olsun
gözle görülebilen problem oldu, verilen özelliklere uygun graph oluşmaz, çünkü 2 vertex arasında 1 edge olur ve her iki vertex de 1 edge'e sahip olabilir en fazla.
Bunun yerine 3. vertexi de ekleyip her vertex 2 edge sahiptir desek, ve bu özelliklere uygun graph var mıdır diye sorarsak
Peki havel hakimi teoremi bu olayı nasıl çözümlemiş :
En büyükten en küçüğe doğru edge sayılarını sıralamış ve degree (derece) demiş
yukarıdaki örnek ile gösterelim 3 vertex ve her biri 2 edge sahip.
O zaman;
S : 2, 2, 2 diye sıralanır.
Buradan anlaşılıyor ki 3 tane vertex var.
1. adım = eğer herhangi bir derece büyük eşitse toplam derece sayısından => Başarısız.
( yani eğer herhangi bir vertexe ait edge sayısı büyükse ya da eşitse toplam vertex sayısından => Başarısız. )
mesela ilk örnekteki S : 2, 2 başarısız. Çünkü vertex sayısı 2, herhangi bir vertexe ait edge sayısı da 2.
2. adım = eğer tek derecelerin toplam sayısı tek ise => Başarısız.
mesela S : 3, 2, 1, 1 başarısız. Çünkü tek olanlar (3, 1 ve 1 ; teklerin toplamı tek sayı) toplam 3 tane.
3. adım = eğer herhangi bir derece 0 dan küçükse => Başarısız.
4. adım = eğer bütün dereceler 0 ise => BAŞARILI
5. adım = dereceleri sırala
6. adım = ilk sıradaki dereceyi tut
7. adım = ilk sıradaki dereceyi sil
8. adım = ilk sıradaki derece sayısı kadar, sıradaki derecelerden 1 tane eksilt.
Yani mesela S : 3, 2, 2, 2, 2 örneğinde ilk sıradaki 3'ü tuttuk ve sildik. Bu adımda elimizde kalan S : 2, 2, 2, 2 kümesindeki ilk 3 dereceyi (BİR) eksiltiyoruz. Oluşan sonuç S : 1, 1, 1, 2
9. adım = 3. adıma geri dön
Örneğimize geçelim, kimyadan bir örnek yapalım, C2H6 bir graph mıdır ? (C, 4 bağ / H, 1 bağ.... bu bilgi lazım :)
C2H6 ne demek oluyor. Toplamda 8 tane verteximiz var. Ve karbonlar 4 edge, hidrojenler 1 edge sahip olacaklar. Yani
A - 4
B - 4
C - 1
D - 1
E - 1
F - 1
G - 1
H - 1
diyebiliriz.
O zaman
S : 4 4 1 1 1 1 1 1
ile başlayalım
kontroller
1. adım (en buyuk derece 4 >=? toplam vertex 8 / HAYIR )
2. adm (tek derecelerin toplamı 6 tane =? tek sayı / HAYIR)
3. adım ( herhangi bir derece <? 0 / HAYIR)
ilk derece olan 4'ü tuttuk sildik
k = 4
S : 4 1 1 1 1 1 1
ve geri kalan sıradaki 4 dereceden (BİR) çıkardık
S : 3 0 0 0 1 1 1
adım 3'e geri döndük. 0'dan küçük derece var mı? YOK gibi kontrolleri yazmıyorum artık :)
S : 3 1 1 1
3 ü tuttuk ve sildik
k = 3
S : 1 1 1
geri kalan sıradaki (k = 3) taneden (BİR) çıkardık
S : 0 0 0
adım 3
adım 4 (Hepsi 0 BAŞARILI :)
Umarım yardımcı olabilmişimdir....
