OMEGA İNVARYANTI Sadık DELEN T. C. BURSA ULUDAĞ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ OMEGA İNVARYANTI Sadık DELEN Prof. Dr. İ. Naci CANGÜL (Danışman) DOKTORA TEZİ MATEMATİK ANABİLİM DALI BURSA–2019 Her Hakkı Saklıdır TEZ ONAYI Sadık DELEN tarafından hazırlanan “Omega İnvaryantı” adlı tez çalışması aşağıdaki jüri tarafından oy birliği/oy çokluğu ile Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı’nda DOKTORA TEZİ olarak kabul edilmiştir. Danışman : Prof. Dr. İ. Naci CANGÜL Üye: Prof. Dr. İ. Naci CANGÜL İmza Bursa Uludağ Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Üye: Doç. Dr. Musa DEMİRCİ İmza Bursa Uludağ Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Üye: Prof. Dr. İlker KÜÇÜK İmza Bursa Uludağ Üniversitesi Fen-Edebiyat Fakültesi Fizik Anabilim Dalı Üye: Prof. Dr. Recep ŞAHİN İmza Balıkesir Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Üye: Prof. Dr. Sebahattin İKİKARDEŞ İmza Balıkesir Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Yukarıdaki sonucu onaylarım Prof. Dr. Ali BAYRAM Enstitü Müdürü U.Ü. Fen Bilimleri Enstitüsü, tez yazım kurallarına uygun olarak hazırladığım bu tez çalışmasında;  tez içindeki bütün bilgi ve belgeleri akademik kurallar çerçevesinde elde ettiğimi,  görsel, işitsel ve yazılı tüm bilgi ve sonuçları bilimsel ahlak kurallarına uygun olarak sunduğumu,  başkalarının eserlerinden yararlanılması durumunda ilgili eserlere bilimsel normlara uygun olarak atıfta bulunduğumu,  atıfta bulunduğum eserlerin tümünü kaynak olarak gösterdiğimi,  kullanılan verilerde herhangi bir tahrifat yapmadığımı,  bu tezin herhangi bir bölümünü bu üniversite veya başka bir üniversitede başka bir tez çalışması olarak sunmadığımı beyan ederim. 01/02/2019 İmza Sadık DELEN ÖZET Doktora Tezi OMEGA İNVARYANTI Sadık DELEN Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı Danışman: Prof. Dr. İ. Naci CANGÜL Bu çalışmada, verilen çizilebilir bir derece dizisinin mümkün olan çizimlerinin graf teorik, topolojik ve kombinatorik özellikleri hakkında bilgi veren ve adına omega invaryantı denilen bir graf invaryantı tanımlanmış ve çeşitli uygulamaları ve özellikleri incelenmiştir. Topolojide 250 yılı aşkın bir süredir bilinen ve yüzeylerle ilgili çok sayıda uygulamalara sahip olan Euler karakteristiği ile ve grafın devir sayısı ile de ilgili olan bu invaryantın bir çok özelliğin çalışılmasında faydalı olduğu gözlenmiştir. Bu tez 6 bölümden oluşmaktadır. Birinci bölüm giriş bölümü olup bu bölümde graflarla ilgili temel kavramlar hatırlatılmış ve tezin ilerleyen bölümlerinde kullanılacak olan bazı sonuçlar verilmiştir. Ayrıca sık kullanılan graf türleri ve temel özellikleri hatırlatılmıştır. İkinci bölümde omega invaryantının tanımına temel oluşturan derece dizisi kavramı hatırlatılacaktır. Ayrıca bazı graf sınıflarının derece dizileri ifade edilecektir. Üçüncü bölümde omega invaryantı tanımlanacaktır. Bu tanım için nelerden esinlenildiği açıklanarak temel bazı özellikleri incelenmiştir. Bazı özel graf sınıfları için omega invaryantının aldığı değerler formülleştirilmiş ve tüm omega değerlerinin bir çok açıdan üç farklı kümeye ayrılabildiği gösterilmiştir. Ayrıca omega invaryantı ile Euler karakteristiği arasındaki ilişki ortaya konmuştur. Dördüncü bölümde derece dizilerinin çok sayıda olası çizimi arasında özel bir yere sahip olan temel çizimler; beşinci bölümde bir graftan kenar ve köşe silmenin omega invaryantına etkisi ele alınmıştır. Altıncı ve son bölümde graflarla ilgili bazı uç problemler ele alınmıştır. Anahtar Kelimeler: Graf, Omega invaryant, graf invaryant, derece dizisi, Euler karakteristiği 2019, xi + 117 sayfa. i ABSTRACT PhD Thesis OMEGA INVARIANT Sadik DELEN Bursa Uludag University Graduate School of Natural and Applied Sciences Department of Mathematics Supervisor: Prof. Dr. I. Naci CANGUL In this thesis, omega invariant which gives information about the graph theoretical, topological and combinatorial properties of all realizations of a given degree sequence is defined and several applications and properties of it are studied. It is observed that this invariant which is related to the Euler characteristics known in topology for more than 250 years and has many applications related to surfaces and also to the cyclomatic number of graphs, is useful in the study of many properties. This thesis consists of 6 chapters. The first chapter is the introductory chapter and the fundamental notions are recalled here together with the results which will be needed in later chapters. Also some frequently used graph classes and their fundamental properties are given. In the second chapter, the notion of degree sequence which forms the basis of the definition of the omega invariant is studied. Also the degree sequences of some graph classes will be given. In the third chapter, omega invariant will be defined. The motivation for defining it and some main properties will be given. It will be calculated for some graph classes and it is shown that the values of omega invariant can be grouped into three sets which appears to be very useful. Also the relation between omega invariant and Euler characteristic is established. In the fourth chapter, the fundamental realizations which have an important place amongst all realizations of a given degree sequence; in the fifth chapter, the effect of edge and vertex deletion from a graph on omega are studied. In the sixth and last chapter, some extremal problems are studied. Key words: Graph, Omega invariant, graph invariant, degree sequence, Euler characteristic 2019, xi + 117 pages. ii ÖNSÖZ VE TEŞEKKÜR Eğitim hayatım da emeği geçen bütün öğretmenlerime bu vesileyle teşekkür ederim. Doktora öğrenimim de emeği geçen, başta Prof. Dr. İsmail Naci CANGÜL hocam olmak üzere matematik bölümündeki birbirinden değerli bütün hocalarıma teşekkür ederim. Sonrasında da bu yoğun çalışma temposunda sabrını ve hoşgörüsünü esirgemeyen değerli aileme teşekkürü bir borç bilirim. Sadık DELEN 01/02/2019 iii İÇİNDEKİLER Sayfa ÖZET.................................................................................................................................. i ABSTRACT ...................................................................................................................... ii ÖNSÖZ VE TEŞEKKÜR ................................................................................................ iii İÇİNDEKİLER ................................................................................................................ iv SİMGELER DİZİNİ......................................................................................................... vi ŞEKİLLER DİZİNİ ........................................................................................................ viii ÇİZELGELER DİZİNİ .................................................................................................... xi 1. GİRİŞ ............................................................................................................................ 1 1.1. Temel kavramlar ........................................................................................................ 2 1.2. Graf türleri ................................................................................................................ 14 2. DERECE DİZİLERİ ................................................................................................... 19 2.1. Bazı graf türlerinin derece dizileri ........................................................................... 19 2.2. Mertebeye göre derece dizileri ................................................................................. 20 3.OMEGA İNVARYANTI ............................................................................................. 24 3.1. Giriş .......................................................................................................................... 24 3.2. Omega invaryantının temel özellikleri ..................................................................... 26 3.3. Omega invaryantının Euler karakteristiği ile ilgisi .................................................. 35 4. DERECE DİZİLERİNİN TEMEL ÇİZİMLERİ ......................................................... 40 4.1. Giriş .......................................................................................................................... 40 4.2.  ≥ 0 durumu .......................................................................................................... 41 4.3.  = -2 durumu ........................................................................................................ 69 4.4.  ≤ -4 durumu ........................................................................................................ 71 5. KENAR VE KÖŞE SİLMENİN OMEGA DEĞERİ ÜZERİNDEKİ ETKİSİ ........... 78 5.1. Giriş .......................................................................................................................... 78 5.2. Kenar silmenin omega değerine etkisi ..................................................................... 80 5.3. Köşe silmenin omega değerine etkisi ....................................................................... 85 6. UÇ PROBLEMLER .................................................................................................... 95 6.1. Giriş .......................................................................................................................... 95 6.2. Maksimum döngü sayısı .......................................................................................... 98 6.3.  ≥ 0 durumu .......................................................................................................... 99 6.4.  = -2 durumu ...................................................................................................... 106 iv 6.5.  ≤ -4 durumu ...................................................................................................... 106 7. SONUÇ …………………………………………………………….………………109 KAYNAKLAR ............................................................................................................. 110 ÖZGEÇMİŞ .................................................................................................................. 112 v SİMGELER DİZİNİ Simge Açıklama 𝐺 graf 𝑉(𝐺) 𝐺 grafının köşe kümesi 𝐸(𝐺) 𝐺 grafının kenar kümesi 𝑑𝑣, 𝑑(𝑣) v köşesinin derecesi ∆𝐺, ∆ 𝐺 grafının maksimum köşe derecesi 𝛿𝐺 𝐺 grafının minimum köşe derecesi ?̅? 𝐺 grafının tümleyeni 𝐾𝑛 n köşeli tam graf 𝐶𝑛 n köşeli devir graf 𝑃𝑛 n köşeli yol graf 𝑆𝑛 n köşeli yıldız graf 𝑇𝑛 n köşeli ağaç graf 𝐾𝑡,𝑠 iki parçalı tam graf 𝑇𝑡,𝑠 larva graf 𝑐(𝐺) veya 𝑐 𝐺 grafının bileşen sayısı 𝑑𝑢 ya da 𝑑𝐺(𝑢) 𝐺 grafında u köşesinin derecesi ∆𝐺 𝐺 grafının maksimum derecesi 𝛿𝐺 𝐺 grafının minimum derecesi 𝐷 derece dizisi △ (𝐺, 𝑣1, 𝑣2, … , 𝑣𝑘) 𝑣1, 𝑣2, … , 𝑣𝑘 köşelerini silmenin omegaya etkisi △ (𝐺, 𝑒1, 𝑒2, … , 𝑒𝑡) 𝑒1, 𝑒2, … , 𝑒𝑡 kenarlarını silmenin omegaya etkisi 𝑎𝑖 derece dizisinde 𝑑𝑖 derecesinin katlılığı (𝐺) 𝐺 grafının omega değeri (𝐷) 𝐷 derece dizisinin omega değeri vi 𝑐𝑎 devire sahip olmayan bileşen sayısı 𝑐𝑐 devire sahip bileşen sayısı 𝐶𝑖 devir bulunduran bileşenler 𝐴𝑖 devir bulundurmayan bileşenler 𝑏𝑟(𝐺) köprü 𝑐𝑣(𝐺) kopma noktası (𝑆) Euler karakteristiği 𝑟 bölge sayısı ℓ döngü sayısı 𝑐ℎ kiriş sayısı 𝑚𝑒 katlılık sayısı η silinen ortak kenar sayısı vii ŞEKİLLER DİZİNİ Sayfa Şekil 1.1. Bir 𝐺 grafı ....................................................................................... 3 Şekil 1.2. Basit ve basit olmayan graflar......................................................... 5 Şekil 1.3. {1(1), 2(3), 3(1)} derece dizisinin iki farklı çizimi ........................... 8 Şekil 1.4. 𝐺 grafı ve ?̅? tümleyeni .................................................................... 9 Şekil 1.5. 𝐺 ve 𝐺 − 𝑣 ...................................................................................... 10 Şekil 1.6. 𝐺 ve 𝐺 − 𝑒 ....................................................................................... 11 Şekil 1.7. 𝐺 ve 𝐺 + 𝑣 ...................................................................................... 11 Şekil 1.8. 𝐺, 𝐺 + {𝑢𝑤} ve 𝐺 + {𝑢𝑣} ............................................................... 12 Şekil 1.9. İki basit ve bağlantılı grafı birleştirme ............................................ 13 Şekil 1.10. 𝑁3 boş grafı ................................................................................... 14 Şekil 1.11. 𝑃4 yol grafı .................................................................................... 14 Şekil 1.12. 𝐶5 devir grafı ................................................................................. 15 Şekil 1.13. 𝑆7 yıldız grafı ................................................................................ 15 Şekil 1.14. 𝐾6 tam grafı ................................................................................... 16 Şekil 1.15. 𝐾2,4 iki parçalı tam grafı ............................................................... 16 Şekil 1.16. 𝑇4,2 tadpole grafı ........................................................................... 17 Şekil 1.17. 𝑇1,3 ağaç grafı ................................................................................ 18 Şekil 2.1. 𝑁1 boş grafı ..................................................................................... 20 Şekil 2.2. 𝑁1 ve 𝐾2 .......................................................................................... 20 Şekil 2.3. 3 köşeli graflar ve derece dizileri .................................................... 20 Şekil 2.4. 4 köşeli graflar ve derece dizileri .................................................... 21 Şekil 2.5. 5 köşeli graflar ve derece dizileri .................................................... 23 Şekil 3.1. {1(2)} derece dizisine sahip 𝑃2 yol grafı ......................................... 35 Şekil 3.2. Tırtıl graf ......................................................................................... 35 Şekil 3.3. Bölge sayısı kolay belirlenemeyen bir graf .................................... 37 Şekil 3.4. Bölge sayısı kolayca belirlenebilen bir graf.................................... 37 Şekil 3.5. {1(1), 2(3), 3(3), 4(4), 5(2)} derece dizisinin bağlantılı bir çizimi ..... 38 Şekil 4.1. {1(3), 3(1), 4(2)} derece dizisine ait iki farklı çizim ......................... 40 Şekil 4.2. {2(2), 3(3), 4(1), 5(1)}’in herhangi bir çizimi ve bir temel çizimi ..... 42 Şekil 4.3. İki temel çizim ................................................................................ 47 Şekil 4.4. {2(3), 4(1)} derece dizisinin bir diğer çizimi ................................... 47 Şekil 4.5. 𝐶6 ..................................................................................................... 48 Şekil 4.6. {2(2), 3(4)} ....................................................................................... 48 Şekil 4.7. {2(2), 3(2), 4(2)} ............................................................................... 48 Şekil 4.8. 𝐶6..................................................................................................... 49 Şekil 4.9. {2(2), 3(4)} ....................................................................................... 49 Şekil 4.10. {1(1), 2(1), 3(5)} ............................................................................. 49 Şekil 4.11. {1(3), 2(1), 3(3), 4(2)} derece dizisinin bir temel çizimi ................. 50 Şekil 4.12. {2(3)} ............................................................................................. 50 Şekil 4.13. {2(1), 3(2)} ..................................................................................... 50 Şekil 4.14. {3(2), 4(1)} derece dizisinin bir temel çizimi ................................. 51 Şekil 4.15. {2(3)} ............................................................................................. 51 viii Şekil 4.16. {2(1), 3(2)} ..................................................................................... 51 Şekil 4.17. {1(1), 3(3)} ..................................................................................... 52 Şekil 4.18. {1(2), 3(2), 4(1)} derece dizisinin bir temel çizimi ......................... 52 Şekil 4.19. 2(1)} ............................................................................................... 53 Şekil 4.20. {1(1), 3(1)} derece dizisinin bir temel çizimi ................................. 53 Şekil 4.21. {2(2)} ............................................................................................. 53 Şekil 4.22. {1(1), 2(1), 3(1)} derece dizisinin bir temel çizimi ......................... 54 Şekil 4.23. Algoritmada belirtilen {2(8)}’e karşı gelen bağlantılı graf 54 Şekil 4.24. {2(2), 3(6)} ..................................................................................... 54 Şekil 4.25. {1(1), 2(1), 3(7)} ............................................................................. 55 Şekil 4.26. {1(1), 2(1), 3(3), 4(4)} derece dizisinin bir temel çizimi ................. 55 Şekil 4.27. {2(1)} derece dizisinin bir temel çizimi ........................................ 55 Şekil 4.28. {2(8)} sekizgeni ............................................................................. 58 Şekil 4.29. {1(11), 2(2), 3(3), 4(1), 5(2)} ............................................................ 59 Şekil 4.30. 𝐺(𝑎 +𝑎 +⋯+𝑎 −1) = {1 (11), 2(2), 3(3), 4(1), 5(2)} ........................... 59 2 3 △ Şekil 4.31. 6-genli çizim ................................................................................. 60 Şekil 4.32. 5-genli çizim ................................................................................. 60 Şekil 4.33. 4-genli çizim ................................................................................. 61 Şekil 4.34. 3-genli çizim ................................................................................. 61 Şekil 4.35. 2-genli çizim ................................................................................. 61 Şekil 4.36. 1-genli çizim ................................................................................. 62 Şekil 4.37. 𝐷 derece dizisinin bir temel çizimi ............................................... 65 Şekil 4.38. Basit graf olamayan {1(4), 6(1)} derece dizisinin bir çizimi ......... 67 Şekil 4.39. Basit graf olamayan {1(8), 5(1), 6(1), 7(1), 9(2)}’nin bir çizimi 67 Şekil 4.40. {1(2), 2(𝑎2+𝑎3+⋯+𝑎)} derece dizisinin yol grafı ........................... 70 Şekil 4.41. Bir tırtıl graf .................................................................................. 70 Şekil 4.42. {1(9), 2(2), 3(2), 4(1), 5(1)}’nin herhangi bir çizimi ve bir temel çizimi 71 Şekil 4.43. 𝐷 = {1(6)} bağlantısız grafı .......................................................... 72 Şekil 4.44. 𝐷 derece dizisinin bir karma temel çizimi .................................... 72 Şekil 4.45. 𝐷 derece dizisinin 2 −gen ana devirli bir çizimi .......................... 73 Şekil 4.46. 𝐷 derece dizisinin 1 −gen ana devirli bir çizimi .......................... 73 Şekil 4.47. 𝐷 derece dizisinin devir içermeyen ana bileşenli bir çizimi ......... 74 Şekil 4.48. 𝐷 derece dizisine ait 𝐾2 bileşeni olmayan bir herhangi bir çizim 74 Şekil 4.49. 𝐷 derece dizisinin bir çizimi ......................................................... 75 Şekil 4.50. Karma bir temel çizim formu (ana bileşeni maksimum döngülü) 76 Şekil 4.51. Karma bir temel çizim (ana bileşeni maksimum sallanan kenarlı) 77 Şekil 5.1. İzole köşe bulunduran bazı graflar .................................................. 80 Şekil 5.2. Graftan bir kenar silme ................................................................... 81 Şekil 5.3. Graftan bir döngü silme .................................................................. 82 Şekil 5.4. Bağlantılı bir graf ............................................................................ 82 Şekil 5.5. Verilen derece dizisine sahip graftan bir kenar silme ..................... 83 Şekil 5.6. Verilen derece dizisine sahip graftan iki kenar silme ..................... 83 Şekil 5.7. Graftan iki tane döngü silmek ......................................................... 84 Şekil 5.8. 𝐺 grafına bir ağaç eklemek ............................................................. 85 Şekil 5.9. Aynı köşede ℓ tane döngüye sahip bir 𝐺 grafı ................................ 86 ix Şekil 5.10. 𝑣 köşesi silinmiş 𝐺 grafı ............................................................... 87 Şekil 5.11. Bir graftan döngüye sahip bir köşe silmek ................................... 87 Şekil 5.12. 𝑣 köşesi ve komşuları ................................................................... 88 Şekil 5.13. Bir graftan bir köşe silmek ............................................................ 89 Şekil 5.14. {1(3), 2(1), 3(4), 4(2), 5(1), 7(2)} derece dizisinin bir 𝐺 çizimi ....... 91 Şekil 5.15. Bir graftan bir köşe silmek ............................................................ 91 Şekil 5.16. Bir graftan bir köşe silmek ............................................................ 92 Şekil 5.17. Bir graftan iki komşu köşe silmek ................................................ 93 Şekil 5.18. Bir graftan komşu olmayan iki köşe silmek ................................. 93 Şekil 6.1. {1(8), 5(1), 6(1), 7(1), 9(2)} derece dizisine sahip 5 graf ................... 96 Şekil 6.2. Bazı 𝐵𝑟,𝑠 grafları ............................................................................. 96 Şekil 6.3. Bazı 𝐿𝑞 grafları ............................................................................... 97 Şekil 6.4. 𝐷’nin temel formdaki bir çizimi ..................................................... 98 Şekil 6.5. Verilen derece dizisinin maksimum bileşenli bir çizimi................. 98 Şekil 6.6. {1(4), 3(4), 4(2)} derece dizisinin maksimum döngülü bir temel çizimi 102 Şekil 6.7. {1(4), 3(2), 4(4)} derece dizisinin maksimum döngülü bir temel çizimi 102 Şekil 6.8. {2(2), 4(3), 6(1)}’in maksimum döngülü bağlantılı bir çizimi 105 Şekil 6.9. {1(4), 3(2), 4(4)} derece dizisinin maksimum döngülü bir temel çizimi.106 Şekil 6.10. {1(4), 3(4), 4(2)}’nin maksimum döngülü bağlantılı bir çizimi…. 106 Şekil 6.11. 𝐷’ye karşılık gelen bir karma temel çizim………..……………….. 108 Şekil 6.12. {1(45), 2(1), 3(2), 5(2), 9(3), 10(1)}’in maksimum döngülü bir çizimi 109 x ÇİZELGELER DİZİNİ Sayfa Çizelge 2.1. Bazı iyi bilinen graf türlerinin derece dizileri .............................. 19 xi 1. GİRİŞ 1736 yılında Leonhard Euler tarafından Königsberg'in yedi köprüsü olarak bilinen problemden hareketle yazılmış olan bir makale, modern graf teorinin kesin başlangıç tarihi olarak kabul edilmektedir. Aslında graflar, çok daha eski yıllarda çeşitli bilim insanlarınca farklı isimler verilerek kullanılmıştır. Örneğin Platonik cisimler adı verilen ve her biri bir graf olan beş adet üç boyutlu cisim (düzgün 4 yüzlü, düzgün 6 yüzlü, düzgün 8 yüzlü, düzgün 12 yüzlü, düzgün 20 yüzlü) çok eski çağlarda bilim insanlarınca astronomik hesaplamalarda kullanılmıştır. En basit tarifiyle bir graf noktalardan ve bunları birleştiren çizgilerden oluşur. Bu noktalara grafın köşeleri; çizgilere de grafın kenarları adı verilir. Bir kenar iki köşeyi birleştiren düz bir çizgi olabileceği gibi bazen bir eğri de olabilir. Hatta bu eğri bir köşeden başlayıp yine aynı köşeye dönebilir. Bir graf, düzlemde çizilebileceği gibi yönlendirilebilen veya yönlendirilemeyen farklı yüzeyler üzerinde de çizilebilir. Grafların bu şekilde farklı yüzeyler üzerinde çalışılmasıyla Topolojik Graf Teori ortaya çıkmıştır. Bu tezde tanımlanan yeni graf invaryantı omega (), bu teoriyle yakından ilgilidir. Uzun yıllar birkaç klasik problem dışında çok fazla uygulama alanı bulamamış olsa da 1947 yılında H. Wiener’in bir makalesinde bugün Wiener indeksi olarak bilinen ve alkanlar denilen kimyasal molekül sınıfının izomerlerinin kaynama noktalarının karşılaştırılmasında kullanılan bir formül vermesiyle graflar ilgi çekmeye ve yeni uygulama alanları bulmaya başlamıştır. Bu uygulama alanlarının başında kimyasal uygulamalar gelmektedir. Bunun sebebi her bir atomu bir köşe olarak, her bir kimyasal bağı da bir kenar olarak düşünerek bir kimyasal molekülün bir graf ile modelleyebileceği gerçeğidir. Köşe ve kenarlardan oluşan bu matematiksel modelin matematiksel ve benzeri yollarla sadece kombinatorik hesaplamalara dayalı olarak çalışılmasıyla karşılık gelen molekülün kimyasal ve fiziksel bir çok özellikleri hakkında bilgi edinmek mümkün olmaktadır. Dolayısıyla kimyacıların laboratuvarda büyük masraflar yaparak uzun zamanda elde edebildiği sonuçları basit matematiksel yöntemlerle elde edebilmek mümkün hale gelmiştir. Bu da kimyaya dayalı farmakoloji, biyoloji, fizik gibi dallarda da grafların uygulama alanlarının çoğalmasına ve sonuç olarak da graf teoriye olan ilginin artmasına sebep olmuştur. 1 Graf teorinin yukarıda bahsedilen uygulama alanları dışında bilgisayar ve matematikte de bir çok uygulaması mevcuttur. Mesela, "minimum geren ağaç problemi", "en kısa yol problemi" ve "network akış problemi" gibi birçok problem graf teorisi yardımıyla çözülmüştür. Biyolojide, popülasyonların ifadesi, hastalıkların yayılma alanlarının gösterilmesi, hayvanların yaşadığı ortamların belirtilmesi yine graf teorisinin uygulama alanları arasındadır. Diller arasındaki parçalı yapılardan ve yapı farklılıklarından dolayı graf teorinin dil bilimde dahi uygulamaları ortaya çıkmıştır. Yani graf teorinin hem fen dallarında hem de sosyal dallarda çok sayıda uygulaması mevcuttur ve bu uygulamalara her gün yenileri eklenmektedir. Grafların moleküllerin çalışılmasındaki avantajları, zamanla kullanılan matematiksel formül ve yöntemlerde çeşitliliğe yol açmıştır. Bu tür formüllere graf teorik değişmezler adı verilir. Kimyasal graf teoride bu değişmezler, topolojik indeksler olarak da bilinirler. Topolojik indeksler, sayısal yapı-aktivite ilişkisi modellerinde (QSPR/QSAR) kullanılırlar. Günümüzde bazıları çok önemli uygulamalara sahip, bazıları ise sadece matematiksel bir ifade olarak kalan çok sayıda graf indeksi mevcuttur. Bu tezde yer alan graflar aksi belirtilmedikçe yönlendirilmemiş, ağırlıksız, bağlantılı, döngüsüz ve katlı kenar içermeyen graflar olacaktır. Bu özelliklerden herhangi birisine veya birkaçına sahip graflar da graf teorinin farklı uygulama alanlarında çalışılmaktadır ve bu tezin kapsamı dışında bırakılmıştır. 1.1. Temel kavramlar Bu bölümde tezin diğer bölümlerinde kullanılacak olan bazı temel kavramlar tanımlanacak ve graflarla ilgili bazı özellikler verilecektir. Daha ayrıntılı bilgi için Aldous ve Wilson (2004), Benjamin ve ark. (2015), Bondy ve Murty (1982), Bondy ve Murty (2008), Capobianco ve Molluzo (1978), Chartrand (1985), Chartrand ve Zhang (2012), Clark ve Holton (1995), Deo (1974), Diestel (2010), Foulds (1992), Gross ve Yellen (2006), Hartsfield ve Ringel (2003), Skiena (1990), Thulasiraman (1992), Trudeau (1993), Tutte (1998), Vasudev (2006), Vasudev (2007), Wallis (2007), West (2001), Wilson (1998), Wilson ve Watkins (1990) veya diğer temel graf teorisi kitapları incelenebilir. 2 1.1.1. Tanım. Köşe (vertex) olarak adlandıran noktalar ile köşeleri birleştiren ve kenar (edge) olarak adlandırılan çizgilerden oluşan bir şekle graf (graph) denilir. Türkçe literatürde graf yerine zaman zaman çizge kelimesi de kullanılmaktadır. Genelde 𝐺 bir graf olmak üzere, 𝐺 grafının köşe kümesi 𝑉(𝐺) ile kenar kümesi ise 𝐸(𝐺) ile gösterilir. Buna göre bir 𝐺 grafı, 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) şeklinde de gösterilir. Bir 𝐺 grafında köşe kümesinin eleman sayısı 𝑛 ve kenar kümesinin eleman sayısı 𝑚 ile gösterilir. Yani |𝑉(𝐺)| = 𝑛 ve |𝐸(𝐺)| = 𝑚’dir. 1.1.2. Tanım. Bir 𝐺 grafının köşe sayısına 𝐺’nin mertebesi (order); kenar sayısına da 𝐺’nin boyutu (size) denilir. Mertebe ve boyut, grafların kombinatorik metodlar yardımıyla çalışılmasında sıkça kullanılan kavramlardır. 1.1.3. Tanım. 𝑢, 𝑣 ∈ 𝑉(𝐺), 𝐺 grafının iki köşesi olsun. Eğer bu iki köşe arasında bir kenar mevcutsa 𝑢 ve 𝑣 köşelerine komşu (adjacent) köşeler denir. a 𝑒1 𝑒5 𝑒6 b e g 𝑒 𝑒 10 7 𝑒 𝑒 2 9 𝑒4 𝑒8 f c 𝑒 d 3 Şekil 1.1. Bir 𝑮 grafı 3 Şekil 1.1’de verilen 𝐺 grafının köşe kümesi 𝑉(𝐺) = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔} ve kenar kümesi 𝐸(𝐺) = {𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8, 𝑒9, 𝑒10}’dur. Örneğin Şekil 1.1’de 𝑏 ve 𝑒 köşeleri arasında bu iki köşeyi birleştiren 𝑒6 kenarı mevcuttur ve bu iki köşe birbirine komşu köşelerdir. 1.1.4. Tanım. Bir 𝐺 grafında 𝐺’nin kenarlarının aynı köşeden iki kez geçmeyen ab, bc, cd, …, fg şeklindeki bir sıralanışına bir yol (path) denir. Eğer 𝑎 = 𝑔 ise bu yola kapalı yol (closed path) adı verilir. Bir yolun tüm kenarları farklı ise bu yola iz (trace) adı verilir. Ayrıca ilk ve son köşeleri hariç, tüm köşeleri farklı olan en az üç köşeli kapalı bir ize bir devir (cycle) denir. Özel olarak 𝑑 uzunluğundaki bir devire 𝑑 − 𝑑𝑒𝑣𝑖𝑟 denilir. 1.1.5. Tanım. 𝑢 ve 𝑣, bir devirin komşu olmayan iki köşesi olsun. 𝑢 ve 𝑣 köşelerini birleştiren bir kenara kiriş (chord) adı verilir. 1.1.6. Tanım. Bir grafta herhangi iki köşe arasında en az bir yol bulunabiliyorsa bu grafa bağlantılı (connected) graf, aksi halde bağlantısız (disconnected) graf denilir. Yani bağlantılı bir grafta verilen her köşe çifti için köşelerden birinden başlayarak diğerine kenarlar boyunca ulaşılabilmektedir. 1.1.7. Tanım. Bir 𝐺 grafının bağlantılı olan her bir alt grafına 𝐺 grafının bir bileşeni (component) adı verilir. Bir grafın bileşen sayısı 𝑐(𝐺) ile ya da karışıklık söz konusu değilse kısaca 𝑐 ile gösterilir. Bağlantılı bir 𝐺 grafı için 𝑐(𝐺) = 1 olup bu tek bileşen grafın tamamıdır. Bir grafın bağlantısız olması için gerek ve yeter şartın 𝑐 > 1 olması olduğu aşikârdır. Aşağıdaki oldukça faydalı sonuç, kenar ve köşe sayıları verildiğinde bu grafın bileşen sayısı hakkında bir alt sınır vermektedir. 1.1.8. Lemma. 𝐺, 𝑐 bileşene sahip bir graf olsun. 𝑐 ≥ 𝑛 − 𝑚 eşitsizliği sağlanır. Bu sonuca göre bir grafta köşe sayısı kenar sayısından en az 2 fazla ise bu grafın bağlantısız olacağı açıktır. 4 1.1.9. Tanım. Bir grafta verilen iki köşeyi birleştiren birden fazla kenar varsa bunlara katlı (çoklu) kenar (multiple edges) denilir. Bir köşeyi kendine birleştiren bir kenara da döngü (loop) adı verilir. Bu iki tür kenarı olmayan graflara basit graf (simple graph) denilir. 𝑒3 𝑒2 𝑒1 Şekil A Şekil B Şekil C Şekil 1.2 Basit ve basit olmayan graflar Şekil 1.2.A’daki graf, döngü veya katlı kenar bulundurmadığından bir basit graftır. Ancak Şekil 1.2.B’deki 𝑒1 ve 𝑒2 kenarları katlı kenarlar; Şekil 1.2.C’deki 𝑒3 kenarı da bir döngü olduğundan her iki graf da basit graf değildir. Graflar, en az bir döngüye sahip olup olmamalarına göre sınıflandırlır. Döngü içeren ve döngü içermeyen bu graflara örnek olarak tüm ağaçlar döngü içermeyen graflardır. Diğerleri döngü içeren graflardır. Kenar ve köşe sayıları arasında bağlantılı bir basit grafta 𝑛 𝑛 − 1 ≤ 𝑚 ≤ ( ) 2 bağıntısı; bağlantısız bir grafta ise 𝑛 0 ≤ 𝑚 ≤ ( ) 2 bağıntısı geçerlidir. 5 1.1.10. Tanım. 𝐺 bir graf ve 𝑢𝑣 ∈ 𝐸(𝐺) olsun. uv kenarına 𝑢 ve 𝑣 köşelerine bitişiktir (incident) denilir. Komşuluk ve bitişiklik kavramları, başta graf enerjisi olmak üzere bir çok alanda uygulamalara sahiptir. Özellikle günümüzde sayıları yüz elliyi bulan graf matrisleri arasında en önemlilerinden ikisi komşuluk ve bitişiklik matrisleridir. Bu matrislerdeki ve ayrıca bu matrislerin kuvvetlerindeki her bir girdi, grafla ilgili bir özelliğe karşılık gelmektedir. Bu nedenle bir 𝐺 grafında bir 𝑢 köşesine bitişik olan kenarların sayısı, graf teoride önemli bir kavramdır: 1.1.11. Tanım. 𝐺 bir graf ve 𝑢 ∈ 𝑉(𝐺) olsun. 𝑢 köşesine bitişik olan kenar sayısına 𝑢 köşesinin derecesi (multiplicity) denilir ve deg(u), 𝑑𝑢 ya da 𝑑𝐺(𝑢) ile gösterilir. Bir grafta derecelerden iki tanesi özellikle önemlidir: 1.1.12. Tanım. 𝐺 grafının maksimum ve minimum derecesi sırasıyla Δ(𝐺) = 𝑚𝑎𝑥{𝑑𝐺(𝑣)|𝑣 ∈ 𝐺} ve δ(𝐺) = 𝑚𝑖𝑛{𝑑𝐺(𝑣)|𝑣 ∈ 𝐺} olarak tanımlanır. Maksimum ve minimum dereceler dışında derecesi 1 olan köşeler de özellikle moleküler grafları çalışırken ortaya çıkacaktır: 1.1.13. Tanım. Derecesi 1 olan bir köşeye sallanan (pendant) köşe, bu köşeye bitişik olan kenara da sallanan kenar (pendant edge) denilir. Bu özel derece çeşitleri kadar olmasa da bağlantısız graflarda karşılaşılabilen bir köşe çeşidi de izole köşelerdir: 1.1.14. Tanım. Derecesi 0 olan bir köşeye izole (isolated) köşe denilir. Bu tezin ana konusunu oluşturan omega invaryantı, derece dizisi yardımıyla tanımlanacağından burada bu kavramı tanımlamak uygun olacaktır. 1.1.15. Tanım. Bir 𝐺 grafının köşe derecelerinin oluşturduğu kümeye bu grafın derece dizisi (degree sequence) adı verilir. 6 Literatürde bir derece dizisindeki tamsayılar ya küçükten büyüğe ya da büyükten küçüğe sıralanmaktadır. Bu tezde küçükten büyüğe olan sıralama tercih edilecektir. Dolayısıyla bir derece dizisi en genel haliyle 0 ≤ 𝑖 ≤ △ için 𝑎𝑖 ≥ 0 olmak üzere 𝐷 = {0(𝑎0), 1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} şeklinde olacaktır. Eğer 𝑎0 > 0 ise bu durumda grafın en az bir izole noktası olacak demektir. Ancak eğer 𝑎0 = 0 ise bu durumda hiçbir izole nokta olmayacağından bu grafın derece dizisi de 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} şeklinde olur. Bu gösterimlerde 𝐷’nin elemanlarının küçükten büyüğe doğru sıralandığına dikkat ediniz. Bir küme sıralı olmak zorunda olmadığından bir derece dizisi de sıralı olmak zorunda değildir. Ancak kolaylık sağlaması amacıyla bir derece dizisi her zaman küçükten büyüğe, katlılıkları belirtilerek yazılacaktır. Nadiren de olsa Havel- Hakimi gibi bazı yöntemlerde, yöntemin yapısı gereği derece dizisinin büyükten küçüğe dizilmesi istenecektir. Bir graf verildiğinde köşelerin derecelerini tek tek sayarak bu grafın derece dizisi kolayca belirlenebilir. Tersine, yukarıdaki gibi herhangi bir 𝐷 kümesi verildiğinde bu kümenin bir grafın derece dizisi olup olmadığı, yani köşe dereceleri tamamen bu kümede kalan tamsayılar olan bir grafın var olup olmadığı, graf teorinin önemli problemlerinden birisidir. Bu konuda çok sayıda sonuç mevcuttur. 1.1.16. Tanım. 𝐷 negatif olmayan tamsayılardan oluşan bir küme olsun. 𝐷 kümesi, bir 𝐺 grafının derece dizisine eşit ise 𝐷’ye bir çizilebilir (realizable) derece kümesi denilir. Literatürde çizilebilir kelimesi yerine grafik kelimesi de kullanılmaktadır. Tanımdan, çizilebilir bir derece dizisi için, bu derece dizisine sahip en az bir graf olduğu açıktır. Örneğin Şekil 1.3’deki graflar tamamen farklı olmasına rağmen aynı derece dizisine sahiptir. 7 veya Şekil 1.3. {1(1), 2(3), 3(1)} derece dizisinin iki farklı çizimi Bu tezde aksi belirtilmedikçe “derece dizisi” denildiğinde bu derece dizisinin çizilebilir olduğu varsayılacaktır. Negatif olmayan tam sayılardan oluşan belirli bir kümenin bir graf olarak çizilip çizilemeyeceğini belirlemek için bir çok sonuç ve algoritma vardır. Bunlardan en ünlüsü Havel-Hakimi tarafından verilen sonuçtur, bkz. Havel (1955), Hakimi (1962). Elbette, bu bölümde görülecek olan ve graf teorinin en temel sonuçları arasında yer alan el sıkışma lemmasından ortaya çıkan en bariz kriter, tüm köşe derecelerinin toplamının kenar sayısının iki katına eşit olması, yani bir çift tamsayı olması gerektiğini ifade eder. Havel- Hakimi dışında çizilebilirlik ile ilgili kriterler için Ivanyi ve ark. (2013), Kim ve ark. (2009), Miller (2013), Skiena (1990), Triphati ve ark. (2010), Triphati ve Tyagi (2008) Tyshkevich ve ark. (1981), Tyshkevich ve ark. 2 (1987) ve Zverovich ve Zverovich (1992) kaynaklarına bakılabilir. Derece dizisi kavramı, bu tezde ilk kez tanımlanan omega invaryantının tanımlanmasında kullanıldığından ikinci bölümde detaylı olarak ele alınacaktır. Yine de burada zaman zaman bahsi geçeceğinden dolayı kısa bir tanımını vermek faydalı olacaktır: 1.1.17. Tanım. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} bir derece dizisi olsun ve 𝐺, bu derece dizisine sahip bir graf olsun. O halde 𝐺 grafının omega invaryantı (𝐺) ile gösterilir ve (𝐺) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 = ∑△𝑖=1(𝑖 − 2) 𝑎𝑖 şeklinde tanımlanır. 8 1.1.18. Tanım. Bir 𝐺 grafının tümleyeni (complement), 𝐺 grafıyla aynı köşe kümesine sahip olan ve 𝐺 grafında kenar oluşturmayan tüm köşelerin birleştirilmesiyle elde edilen bir graftır ve bu graf ?̅? ya da 𝐺𝑐 ile gösterilir, bkz. Şekil 1.4. 𝐺 ?̅? Şekil 1.4. 𝐺 grafı ve ?̅? tümleyeni Yani 𝑉(𝐺) köşe kümesindeki herhangi iki köşeyi birleştiren bir kenar, ya 𝐺 grafına ya da ?̅? grafına aittir. 1.1.19. Tanım. Bir 𝐺 grafında köşe dereceleri birbirine eşit ise 𝐺 grafına regüler (regular) graf denilir. Özel olarak her bir köşenin derecesi r ise 𝐺’ye r-regüler graf denilir. Regüler bir grafın kenar sayısı, köşe sayısı ve regülerlik derecesine bağlı olarak ifade edilebilir: 𝑛𝑟 1.1.20. Teorem. 𝐺 grafı 𝑛 köşeli ve 𝑟-regüler olsun. Bu takdirde 𝐺 grafının kenarı 2 vardır. Graf teorinin en temel sonuçlarından biri şu şekildedir: 1.1.21. Lemma (El Sıkışma (Hand-shaking) Lemması). Bir 𝐺 grafında kenar sayısının iki katı, tüm köşe derecelerinin toplamına eşittir. Yani, 𝑛 köşeli ve 𝑚 kenarlı bir 𝐺 grafında 𝑛 ∑ 𝑑𝑣 = 2𝑚 𝑖 𝑖=1 dir. 9 Dereceler toplamı hesaplanırken her bir kenarda iki köşe bulunduğundan bir kenar iki kez sayılmış olur ve sonuç aşikârdır. Bu sonuç herhangi bir grafta köşe derecelerinin toplamının çift olduğunu belirtir. Bu nedenle negatif olmayan tamsayılardan oluşan bir küme verildiğinde bu kümedeki elemanları toplayıp eğer bu toplam tek sayı çıkıyorsa bu kümenin çizilebilir bir derece kümesi olmadığı kolayca söylenebilir. Bu anlamda El Sıkışma Lemması, çizilebilirlik kriterleri arasında en pratik olanıdır. Bu lemmanın bir sonucu olarak herhangi bir 𝐺 grafında derecesi tek olan köşelerin sayısının çift olması gerektiği söylenebilir. Graflarla yapılan bir çok hesaplamada grafa bir kenar veya köşe eklemenin veya çıkarmanın etkisinden sıklıkla faydalanılır. Bu sayede daha kolay hesaplamalar yapılarak daha büyük graflarla ilgili sonuçlar daha küçük graflar yardımıyla elde edilebilir. Şimdi bu kavramlar kısaca tanımlanacaktır: 1.1.22. Tanım (Köşe çıkarma). 𝐺 bir graf ve 𝑣  𝑉(𝐺), 𝐺 grafının herhangi bir köşesi olsun. 𝐺 grafından 𝑣 köşesinin ve bu köşeye bağlı olan tüm kenarların silinmesiyle elde edilen yeni grafa 𝑣 köşesi çıkarılmış 𝐺 grafı adı verilir ve 𝐺 − {𝑣} ile gösterilir. Buradaki silme işlemine de köşe çıkarma denilir. Eğer 𝐺 grafından birden fazla 𝑣1, 𝑣2, … , 𝑣𝑛 köşesi çıkarılıyorsa elde edilen graf 𝐺 − {𝑣1, 𝑣2, … , 𝑣𝑛} ile gösterilir. Bazı kaynaklarda 𝐺 − {𝑣} gösterimi yerine 𝐺 − 𝑣 de kullanılmaktadır, bkz. Şekil 1.5. 𝑣 𝐺 𝐺 − 𝑣 Şekil 1.5. 𝐺 ve 𝐺 − 𝑣 1.1.23. Tanım (Kenar çıkarma). 𝐺 bir graf ve 𝑒  𝐸(𝐺), 𝐺 grafının herhangi bir kenarı olsun. 𝐺 grafından 𝑒 kenarının silinmesiyle elde edilen yeni grafa 𝑒 kenarı silinmiş 𝐺 10 grafı adı verilir ve 𝐺 − {𝑒} ile gösterilir. Buradaki silme işlemine de kenar silme denilir. Eğer 𝐺 grafından birden fazla 𝑒1, 𝑒2, … , 𝑒𝑛 kenarı siliniyorsa (çıkarılıyorsa) elde edilen graf 𝐺 − {𝑒1, 𝑒2, … , 𝑒𝑛} ile gösterilir. Bazı kaynaklarda 𝐺 − {𝑒} gösterimi yerine 𝐺 − 𝑒 gösterimi de kullanılmaktadır, bkz. Şekil 1.6. 𝑒 𝐺 𝐺 − 𝑒 Şekil 1.6. 𝐺 ve 𝐺 − 𝑒 Köşe ve kenar çıkarma işlemlerini kullanarak karmaşık graflarla ilgili bir çok özelliği daha küçük grafların daha kolay elde edilebilecek özelliklerinden faydalanarak elde edebilir. Bu işlemlere benzer olarak bu maksatla kullanılan iki işlem de köşe ve kenar ekleme işlemleridir. Çıkarma işlemleri kadar standart bir tanımlamaya sahip olmayan bu iki işlem, bazı özel durumlarda aşağıdaki şekilde kullanılır: 1.1.24. Tanım (Köşe ekleme). 𝐺 bir graf olsun. 𝐺 grafının bir 𝑒 kenarına yeni bir 𝑣 köşesinin eklenmesiyle elde edilen yeni grafa v köşesi eklenmiş G grafı adı verilir ve 𝐺 + {𝑣} ile gösterilir. Buradaki ekleme işlemine de köşe ekleme denilir, bkz. Şekil 1.7. 𝑣 𝐺 𝐺 + 𝑣 Şekil 1.7. 𝐺 ve 𝐺 + 𝑣 11 Bu kavram özellikle bir grafın doğru grafı veya alt grafı çalışıldığında ortaya çıkmaktadır. Bazı kaynaklarda eklenen yeni köşenin var olan bir kenar üzerine değil de graf dışında bir köşe olarak eklendiği de görülebilir. 1.1.25. Tanım (Kenar ekleme). 𝐺 bir graf olsun. 𝐺 grafının bir 𝑢 köşesine, 𝑣 köşesi 𝐺 grafına ait olmayan bir köşe olmak üzere yeni bir 𝑒 = 𝑢𝑣 kenarının eklenmesiyle elde edilen yeni grafa 𝑒 kenarı eklenmiş 𝐺 grafı adı verilir ve 𝐺 + {𝑒} ile gösterilir. Benzer şekilde 𝐺 grafının mevcut iki 𝑢, 𝑣 köşesini birleştiren bir 𝑒 = 𝑢𝑣 kenarı da eklenerek kenar ekleme işlemi tanımlanabilir. Buradaki her iki ekleme işlemine de kenar ekleme denili, bkz. Şekil 1.8.. 𝑤 𝑢 𝑣 𝐺 + {𝑢𝑤} 𝑢 𝑣 𝐺 𝑢 𝐺 + {𝑢𝑣} Şekil 1.8. 𝐺, 𝐺 + {𝑢𝑤} ve 𝐺 + {𝑢𝑣} Birden fazla kenar ve köşe eklendiğinde gösterim, kenar ve köşe çıkarmadakine benzer şekilde ayarlanabilir. Aşağıda verilecek olan kavram da kenar çıkarma işleminin en önemli uygulamalarından birisidir ve grafların başta bağlantılılık olmak üzere bir çok özelliğinin çalışılmasında faydalıdır: 12 1.1.26. Tanım. 𝐺 bağlantılı bir graf ve 𝑒 = 𝑢𝑣, 𝐺 grafının bir kenarı olsun. Eğer 𝑒 kenarı silindiğinde 𝐺 − 𝑒 grafı bağlantısız bir graf haline geliyorsa 𝑒 kenarına 𝐺 grafının bir köprüsü (bridge) denilir. Aşağıdaki verilecek olan sonuç ilerleyen bölümlerde sıklıkla kullanılacaktır: 1.1.27. Teorem. Basit ve bağlantılı olan bir 𝐺 grafının herhangi bir köşesine devir içermeyen bir graf eklemek veya herhangi bir kenara yeni bir köşe eklemekle elde edilen yeni graf da basit ve bağlantılıdır. İspat. Sallanan bir kenar katlı kenar olamayacağından ve ayrıca bir döngü oluşturamayacağından böyle bir kenar eklemenin basitliği bozmayacağı açıktır. Bağlantılılığın bozulmayacağı kenar ekleme tanımından aşikârdır. Benzer şekilde (derecesi 2 olan) yeni bir köşeyi herhangi bir kenara eklemek de ne grafın basitliğini ne de bağlantılılığını bozmayacağından sonuç aşikârdır. Bu teorem genelleştirilerek iki basit ve bağlantılı grafı birer köşelerinden 𝑑 ≥ 0 uzunluklu bir patika yardımıyla birleştirmenin de basit ve bağlantılı olan bir graf vereceği ifade edilebilir, bkz. Şekil 1.9. 𝑑 ≥ 0 uzunluk Şekil 1.9. İki basit ve bağlantılı grafı birleştirme 13 1.2. Graf türleri 1.2.1. Tanım. Hiç bir kenara sahip olmayan graflara boş (null) graf adı verilir ve n köşeli bir boş graf 𝑁𝑛 ile gösterilir. Bazı kaynaklarda boş graf yerine sıfır grafı da kullanılmaktadır. 𝑁𝑛 boş grafının köşe sayısı 𝑛 ve kenar sayısı 𝑚 = 0’dır. Dolayısıyla 𝑁𝑛 boş grafının derece dizisi {0 (𝑛)} şeklindedir. Derecesi 0 olan köşelere izole (isolated) köşeler denilir, bkz. Şekil 1.10. Şekil 1.10. 𝑁3 boş grafı Graf teoride ve uygulamalarında iki graf türü oldukça önemli bir yer tutmaktadır. Bunlar şimdi tanımlanacak olan yol grafları ve devir graflarıdır. 1.2.2. Tanım. Devir içermeyen ve bir tek yoldan oluşan bir grafa yol grafı (path graph) denir ve n köşeli bir yol grafı 𝑃𝑛 ile gösterilir. 𝑃𝑛 grafı 𝑛 − 1 kenara sahiptir. 𝑃𝑛 grafının derece dizisi 𝑃 = {1(2), 2(𝑛−2)𝑛 } şeklindedir, bkz. Şekil 1.11. Şekil 1.11. 𝑃4 yol grafı 1.2.3. Tanım. Tek bir devirden oluşan grafa devir grafı (cycle graph) denir. n köşeli bir devir grafı 𝐶𝑛 ile gösterilir. Köşe sayısı 𝑛 ve kenar sayısı 𝑚 = 𝑛’dir. Yani bir devir grafında köşe ve kenar sayıları birbirine eşittir. Ayrıca devir graflar 2-regüler graflardır. 𝐶𝑛 devir grafından bir kenar silindiğinde (çıkarıldığında) 𝑃𝑛−1 yol grafı elde edilir. 𝐶𝑛 devir grafının derece dizisi 14 𝐶 = {2(𝑛)𝑛 } şeklindedir, bkz. Şekil 1.12. Şekil 1.12. 𝐶5 devir grafı Graflar ile çalışırken devir, devir graf, devirli, devirsiz, devir bulunduran, ana devir, vb. gibi kavramlarla karşılaşılabilir. “Devir” ve “devir grafı” ile 𝐶𝑛 grafını; “devirli” veya “devir bulunduran” ifadesini görünce grafın en az bir devir bulundurduğu; “devirsiz” ifadesinden de grafta hiçbir devir bulunmadığı anlaşılacaktır. “Ana devir” ifadesiyle de verilen bir derece dizisinin bu tezde tanımlanacak ve adına temel çizim denilecek olan çizimindeki en uzun uzunluğa sahip devirin bulunduğu bileşen kastedilecektir. 1.2.4. Tanım. Adına merkez köşesi denilecek olan bir köşe ile her biri sadece merkez köşesine komşu olan 𝑛 − 1 tane köşeden oluşan bir grafa yıldız (star) graf denilir. n köşeli bir yıldız graf 𝑆𝑛 ile gösterilir. Dolayısıyla bir 𝑆𝑛 yıldız grafının köşe ve kenar sayıları sırasıyla 𝑛 ve 𝑚 = 𝑛 − 1’dir. Derece dizisi ise 𝑆𝑛 = {1 (𝑛−1), 𝑛(1)} şeklindedir, bkz. Şekil 1.13. Şekil 1.13. 𝑆7 yıldız grafı 15 1.2.5. Tanım. Bir grafta her köşe kendisinden başka bütün köşelere birer kenar ile bağlanıyorsa bu grafa tam (complete) graf denir ve n köşeli bir tam graf 𝐾𝑛 ile gösterilir. 𝑛(𝑛−1) 𝐾𝑛 tam grafının köşe sayısı 𝑛 ve kenar sayısı 𝑚 = şeklindedir. 𝐾𝑛 tam grafının 2 derece dizisi ise 𝐾 = {(𝑛 − 1)(𝑛)𝑛 } şeklindedir. 𝐾𝑛 tam grafı (𝑛 − 1)-regüler bir graftır, bkz. Şekil 1.14. Şekil 1.14. 𝑲𝟔 tam grafı 1.2.6. Tanım. Bir graftaki köşeler iki gruba ayrılıp bir gruptaki köşelerin bazıları diğer gruptaki köşeler ile kenarlar vasıtasıyla birleşiyorsa bu grafa iki parçalı (bipartite) graf denir. Eğer iki parçalı grafta birinci gruptaki her bir köşe ikinci grubun her bir köşesiyle kenarlar yardımıyla birleştirilmiş ise bu grafa iki parçalı tam (complete bipartite) graf denir. Bu gruplarda 𝑟 ve s tane köşe varsa böyle bir graf 𝐾𝑟,𝑠 ile gösterilir. 𝐾𝑟,𝑠 iki parçalı tam grafının köşe sayısı 𝑛 = 𝑟 + 𝑠 ve kenar sayısı 𝑚 = 𝑟. 𝑠’dir. Bu grafın derece dizisi ise 𝐾 = {𝑟(𝑠)𝑟,𝑠 , 𝑠 (𝑟)} şeklindedir. Örneğin 𝐾2,4 iki parçalı tam grafı Şekil 1.15’de görülmektedir: Şekil 1.15. 𝐾2,4 iki parçalı tam grafı 16 𝑆𝑛 yıldız grafındaki merkez köşe bir küme, diğer köşeler ikinci bir küme olarak alınırsa 𝑆𝑛 yıldız grafının aslında 𝐾1,𝑛 iki parçalı tam grafı olduğu da söylenebilir. Yani 𝑆𝑛 = 𝐾1,𝑛 dir. Uygulamada önemli bir yer tutan fakat yukarıdaki graf türleri kadar iyi bilinmeyen bir graf türü de larva graflarıdır: 1.2.7. Tanım. 𝑃𝑠+1 yol grafının bir köşesinin 𝐶𝑟 devir grafının bir köşesiyle özdeşlenmesiyle oluşan bir grafa larva (tadpole) graf denilir. Bu graf türü 𝑇𝑟,𝑠 ile gösterilir. Ayrıca 𝑇𝑟,𝑠 larva grafının köşe sayısı 𝑛 = 𝑟 + 𝑠 ve kenar sayısı da 𝑚 = 𝑟 + 𝑠’dir. Derece dizisi ise 𝑇 = {1(1), 2(𝑟+𝑠−2)𝑟,𝑠 , 3 (1)} şeklindedir, bkz. Şekil 1.16. Şekil 1.16. 𝑇4,2 tadpole grafı Şimdi tanımlanılacak olan graf türü, diğer graflardan önemli bir farka sahiptir. Şimdiye kadar tanımlanan graf türlerinin özellikleri hakkında belli miktarda bilgi mevcuttur. Ağaç adı verilen graf türü ise kontrol edilemeyen ve çok farklılık gösteren yapısı nedeniyle çalışılması en zor olan graf türüdür. Ağaçlarla ilgili hesaba dayalı çalışmalarda diğer graf türlerinde olduğu gibi birkaç durumu değil, köşe sayısına göre artan çok sayıda durumu incelemek gereklidir. Örneğin yukarıdaki graf türlerinde köşe derecelerinin tümü ve dolayısıyla grafın derece dizisi bilinmekteyken, 𝑛 köşeli bir ağacın köşe dereceleri çok farklı şekillerde ifade edilebilmektedir. Buna rağmen bu tezin konusunu oluşturan omega 17 invaryantının tanımının tamamen derece dizilerine bağlı olması nedeniyle ağaçların omega invaryantlarının da diğer özelliklerde olduğu gibi farklılık gösterebileceği düşünülse de ilginç bir şekilde tüm ağaçların omega invaryantının −2 olduğu görülecektir. 1.2.8. Tanım. Bağlantılı bir grafta hiçbir devir bulunmuyorsa bu grafa ağaç (tree) graf veya kısaca ağaç denir. n köşeli bir ağaç 𝑇𝑛 ile gösterilir. Bağlantılılık şartı kaldırıldığında bu grafa orman (forest) adı verilir. Köşe sayısı, graftaki di köşesinin derece dizisindeki katlılığı ai olmak üzere 𝑛 = ∑△𝑖=1 𝑎𝑖, kenar sayısı ise 𝑚 = 𝑛 − 1 şeklindedir. 𝑇𝑛 ağacının derece dizisi 𝑇 = {1(𝑎1)𝑛 , 2 (𝑎2), 3(𝑎3), … ,△(𝑎△)} şeklindedir. Dikkat edilirse bu genel bir grafın derece dizisidir. Bunun sebebi ise yukarıdaki paragrafta açıklandığı gibi ağaçların derecelerinin çok değişik olabilmesidir. Şekil 1.17’de 13 köşeli bir ağaç görülmektedir. Şekil 1.17. 𝑇1,3 ağaç grafı Aşikâr olmayan tüm ağaçlar için 𝑎1 ≥ 2 olduğu kolayca görülebilir. Aynı zamanda △= 2 olan ağaç 𝑃𝑛 yol grafı; △= 𝑑2 = 𝑛 − 1 olan ağaç ise 𝑆𝑛 yıldız grafıdır. Bir orman, gerçek hayatta olduğu gibi ağaçlardan oluşmaktadır. 18 2. DERECE DİZİLERİ 2.1. Bazı graf türlerinin derece dizileri Giriş bölümünde belirtildiği gibi bu tezde tanımlanan ve bu tezin konusunu oluşturan omega invaryantı, tamamen verilen bir grafın derece dizisi yardımıyla tanımlanmaktadır. Dolayısıyla tezin başlığına uygun olarak bu bölümden itibaren bu çalışmada elde edilecek tüm sonuçların da derece dizileriyle ilişkili olacağı tahmin edilebilir. Bu nedenle bu bölümde grafların derece dizileri kavramı detaylı olarak incelenecektir. Birinci bölümde sekiz farklı graf türü tanımlanmıştı ve bunların çok temel bazı özelliklerinden bahsedilmişti. İlk olarak bu graf türlerinin derece dizileri toplu olarak Çizelge 2.1’de verilmiştir. Çizelge 2.1. Bazı iyi bilinen graf türlerinin derece dizileri GRAF DERECE DİZİSİ 𝑁 (𝑛)𝑛 {0 } 𝑃 {1(2), 2(𝑛−2)𝑛 } 𝐶 {2(𝑛)𝑛 } 𝑆 = 𝐾 {1(𝑛−1)𝑛 1,𝑛 , 𝑛 (1)} 𝐾𝑛 {(𝑛 − 1) (𝑛)} 𝐾 {𝑟(𝑠), 𝑠(𝑟)𝑟,𝑠 } 𝑇 (1) (𝑟+𝑠−2) (1)𝑟,𝑠 {1 , 2 , 3 } 𝑇 {1(𝑎1)𝑛 , 2 (𝑎2), 3(𝑎3), … ,△(𝑎△)} 19 2.2. Mertebeye göre derece dizileri Bu kısımda grafları mertebelerine göre küçükten büyüğe sınıflandırarak tüm olası derece dizileri listelenecektir. İlerleyen bölümlerde yapılacak olan hesaplamalarda bu derece dizilerine sıklıkla ihtiyaç duyulacaktır. Bu bölümde ele alınacak graflar basit graflardır. 2.2.1. 𝒏 = 𝟏 olan basit grafların derece dizileri 𝑛 = 1 olan tek bir graf vardır: 𝑁 (1)1 = {0 }, bkz. Şekil 2.1. Şekil 2.1. 𝑁1 boş grafı 2.2.2. 𝒏 = 𝟐 olan basit grafların derece dizileri 𝑛 = 2 olan iki adet graf vardır: 𝑁 = {0(2)2 } ve 𝐾2 = {1 (2)}, bkz. Şekil 2.2. 𝑁 = {0(2)2 } 𝐾2 = {1 (2)} Şekil 2.2. 𝑁2 ve 𝐾2 2.2.3. 𝒏 = 𝟑 olan basit grafların derece dizileri 𝑛 = 3 olan dört adet graf vardır. Bunların derece dizileri 𝑃3 = {1 (2), 2(1)}, 𝑁3 = {0 (3)}, {0(1), 1(2)} ve 𝐶3 = {2 (3)} şeklindedir, bkz. Şekil 2.3. 𝑃 = {1(2), 2(1)3 } 𝑁3 = {0 (3)} {0(1), 1(2)} 𝐶3 = {2 (3)} Şekil 2.3. 3 köşeli graflar ve derece dizileri 20 2.2.4. 𝒏 = 𝟒 olan basit grafların derece dizileri 𝑛 = 4 olan on bir adet graf vardır, bkz. Şekil 2.4: {0(4)} {0(2), 1(2)} {0(1), 1(2), 2(1)} {1(4)} {1(2), 2(2)} {0(1), 2(3)} {1(3), 3(1)} {2(4)} {1(1), 2(2), 3(1)} {2(2), 3(2)} {3(4)} Şekil 2.4. 4 köşeli graflar ve derece dizileri 2.2.5. 𝒏 = 𝟓 olan basit grafların derece dizileri 𝑛 = 5 olan otuz dört adet graf vardır, bkz. Şekil 2.5. 21 (5) {0(3), 1(2)} {0(2), 1(2), 2( 1){0 } } {0 (1), 1(4)} ( ) ( ) {0(2), 2(3)} {0(1), 1(3), 3(1)} {0 (1), 1(2), 2(2)} {1 4 , 2 1 } {0(1), 1(1), 2(2), 3(1)} {0(1), 2(4) (4) (1) (3) (1) (1) } {1 , 4 } {1 , 2 , 3 } {1(2), 2(3)} {1(2), 2(3)} {0(1), 2(2), 3(2)} {1(2), 2(2), 4(1)} {1(2), 2(1), 3(2)} {1(1), 2(3), 3(1) {1 (1), 2(3), 3(1) ( } {2 5 ) } } {0(1), 3(4)} {1(1), 2(1), 3(3)} {1(1), 2(2), 3(1), 4(1)} {2 (4), 4(1)} 22 {2(3), 3(2)} {2(3), 3(2)} {1(1), 3( 3), 4(1)} {2(3), 4(2)} {2(2), 3(2), 4(1)} {2(1), 3(4)} {3(4), 4(1)} {2(1), 3(2), 4(2)} {3(2), 4(3)} {4(5)} Şekil 2.5. 5 köşeli graflar ve derece dizileri 23 3. OMEGA İNVARYANTI 3.1. Giriş Bu bölümde teze adını veren omega invaryantı tanımlanıp temel özellikleri incelenecektir. Çalışmaların başlangıcında bir derece dizisinin çizilebilirliğinin yanı sıra bu çizimlerdeki döngü, katlı kenar, kiriş, sallanan kenar ve köprü gibi çeşitli graf bileşenlerinin sayı ve durumlarını da incelemek amaçlanmıştı. Gözlem aşamasında çizilen çok sayıda grafın bazı ortak özelliklerinin varlığı farkedilince bu özelliklerden hangilerinin her zaman doğru olduğu ve hangilerinin de bazı graf sınıfları için doğru olduğu tespit edilmeye çalışılmıştır. İlk olarak ele alınan moleküler graflardan faydalanılarak bazı toplamların her zaman sabit kaldığı tespit edilmiştir. Buradan hareketle en genel derece dizileri için bu sayının sabit bir sayı olup olmadığı araştırılmış ve yapılan çok sayıda çizimden ortaya çıkan gözlemler sonucunda omega invaryantı olarak adlandırılan ve verilen bir derece dizisi veya birbirine izomorfik tüm graflar için sabit olan bir sayı belirlenmiştir. Bu sayının graflarla ilgili, başta 250 yıldır bilinen Euler karakteristiği olmak üzere bir çok sayı ve kavramla yakın ilgisi olduğu görülmüştür. Derece dizilerinin en önemli özelliği olan çizilebilirlik kavramıyla ilgili başta Havel- Hakimi yöntemi olmak üzere bir çok yöntem bilinmektedir. Burada tanımlanan omega invaryantı, verilen bir derece dizisinin çizilebilir olup olmadığının belirlenmesinde bilinen en basit ve yeni yöntem olarak kullanılabilir: Hesaplanan omega invaryantı tek sayı oluyorsa bu derece dizisi çizilebilir değildir. İleride omega invaryantının her bir çift sayı değeri için en az bir çizimin var olduğu gösterilecektir. Omega invaryantının bir grafın devir sayısı ile de doğrudan bağlantılı olduğu görülünce verilen bir çizilebilir derece dizisinin tüm çizimlerinin kaç tane kapalı bölge bulunduracağı da omega invaryantı sayesinde bir bağıntı ile verilmiştir. Bir grafın bağlantılılığını grafı çizmeden sadece derece dizisine bakıp küçük bir hesaplama yardımıyla tespit etmek omega invaryantı ile yapılabilir. Burada çizilebilir bir derece dizisi için bu derece dizisinin tüm çizimlerinin kaç bileşene sahip olacağını veren bir eşitsizlik elde edilecektir. Bu eşitsizlik sayesinde bileşen sayısı birden büyük çıktığında, ki bu durum omeganın −4’den küçük ya da eşit olması durumuna karşılık gelmektedir, bu durumda olan çizilecek tüm grafların bağlantısız olacağı söylenebilir. 24 Omeganın üç farklı durumunun olduğunu ve bu üç durumun birbirinden farklı özellikler gösterdiği belirlenmiştir. Bu üç durumun her birisinde bu çalışmada adına temel çizim denilecek bir çizim algoritması geliştirildi ve bu çizimler yardımıyla bir çok probleme çözüm bulundu. Verilen tüm çizilebilir derece dizilerinin bir temel çizime sahip oldukları gösterildi. Graflarla ilgili bir çok normal ya da uç (extremal) problemin çözümünde de omega invaryantı faydalıdır. Örneğin bağlantılı olarak çizilebilen bir derece dizisinin aynı zamanda bağlantısız bir halde de çizilebildiği veya bunun tam tersi omega invaryantının değerine göre söylenebilir. Çizilebilir bir derece dizisine karşılık gelen muhtemel graflar çizildiğinde bu graflarda en çok (en az) kaç tane döngü, katlı kenar, köprü, sallanan kenar bulunduğu omega invaryantı yardımıyla söylenebilir. Hatırlanacağı gibi |𝑉(𝐺)| = 𝑛 köşeye ve |𝐸(𝐺)| = 𝑚 kenara sahip bir graf 𝐺 = (𝑉, 𝐸) ile gösterilmektedir. Bir 𝐺 grafının derece dizisi 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … , △(𝑎△)} şeklinde gösterilir. 1.1.17.Tanımda, verilen bir 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisi için bu derece dizisine sahip bir graf 𝐺 olmak üzere 𝐺 grafının  invaryantı (𝐺) ile gösterilmiş ve (𝐺) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 = ∑△𝑖=1(𝑖 − 2) 𝑎𝑖 şeklinde tanımlanmıştı. Daha sonra bu sayının özel bir değerinin önemli bir graf sınıfı olan ağaçların yaprak sayısını (sallanan kenar sayısı) veren bir bağıntı olduğunun bilindiği görüldü. Bir ağacın yapraklarının sayısını veren formül 𝑎1 = 2 + 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ şeklindedir. 𝑎1 sayısı bir ağaç grafında ki yaprakları yani sallanan kenar sayısını vermektedir. Bu formülde 𝑎𝑖’ler eşitliğin diğer tarafına alınırsa, 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 = −2 şeklinde bir sabit elde edilir. Bir 𝐷 derece dizisinin veya bir 𝐺 grafının omega invaryantı sırasıyla (𝐷) ve (𝐺) ile gösterilecektir. Bir çok yerde derece dizisi ve bu derece dizisi yardımıyla çizilen grafın 25 ayırt edilmesi önemsiz olacağından bu iki notasyonu birbirinden ayırt etmeye çok ihtiyaç duyulmayacaktır. Her derece dizisine ait bir omega değerinin varlığı tanımdan aşikârdır. Ama her omega değerine karşılık bir tek grafın varlığı garanti değildir. Aslında her bir omega değeri için sonsuz çoklukta graf olduğu zamanla gözlemlenecektir. Bazı sık karşılaşılan graf türlerinin omega değerleri aşağıdaki gibidir: (𝐶𝑛) = 0 (𝑃𝑛) = −2 (𝑆𝑛) = −2 (𝑇𝑛) = −2 (𝐾𝑛) = 𝑛(𝑛 − 3) (𝐾𝑟,𝑠) = 2[𝑟𝑠 − (𝑟 + 𝑠)] (𝑇𝑟,𝑠) = 0. Dikkat edilirse 𝑃𝑛, 𝑆𝑛 ve 𝑇𝑛 graflarının hepsinin omega değerlerinin −2 olduğu görülür. Genelleştirme yoluyla bu sonuç ileride (𝐺) = −2 olan bir grafın bağlantılı iken devir bulundurmadığını yani bir ağaç graf olduğunu, bağlantısız iken de bileşenlerinden en az bir tanesinin ağaç olduğunu gösterecektir. 3.2. Omega invaryantının temel özellikleri Bu bölümde omega invaryantının bazı temel özelliklerinden bahsedilecektir. Bir 𝐺 grafındaki kapalı bölgelerin (devirlerin) sayısı 𝑟 olsun. Burada grafın dışında kalan bölge hesaba katılmayacaktır. Örneğin bir devir graf için 𝑟 = 1, bir ağaç için 𝑟 = 0, 𝐾4 tam grafı için 𝑟 = 3 olarak alınacaktır. Bazı kaynaklarda, özellikle topolojik çalışmalarda bazen grafın dışında kalan bölgenin de hesaba katıldığı görülmektedir. Yani yukarıdaki üç örnek bu anlamda düşünüldüğünde 𝑟 değerleri sırasıyla 2, 1 ve 4 olacaktır. Devir bulunduran graflar için genel olarak 𝑛 ≥ 3 olacaktır. Ancak bu tezde 1 bölgeli ve 2 bölgeli 26 graf kavramları da kabul edilecek ve bunlar sırasıyla bir döngü ve bir katlı kenar çifti olarak alınacaktır. Aşağıdaki bağıntı omega invaryantının aslında kenar ve köşe sayılarına doğrudan bağlı olduğunu gösterir: 3.2.1. Teorem. m kenar ve n köşeye sahip bir 𝐺 grafı için (𝐺) = 2(𝑚 − 𝑛) bağıntısı sağlanır. İspat. El sıkışma lemması gereği 2𝑚 = 𝑎1 + 2𝑎2 + 3𝑎3 + ⋯ +△ 𝑎△ = (𝑎3 + 2𝑎4 + ⋯ + (△ −2)𝑎△ − 𝑎1) + 2(𝑎1 + 𝑎2 + 𝑎3 + ⋯ + 𝑎△) elde edilir. Burada 𝑎1 + 𝑎2 + 𝑎3 + ⋯ + 𝑎△ = 𝑛 olduğundan 2𝑚 = (𝐺) + 2𝑛 ve buradan da (𝐺) = 2(𝑚 − 𝑛) olur. Aşağıdaki sonuç bilinen tüm çizilebilirlik testlerinden daha kısa bir şekilde, verilen bir derece dizisinin çizilebilir olup olmadığını belirleyebilir: 3.2.2. Teorem. Herhangi bir 𝐷 derece dizisinin çizilebilir olması için (𝐷)’nin çift sayı olması gerekir. İspat. (𝐷) = 2(𝑚 − 𝑛) olduğundan omeganın 2’nin bir katı olduğu ve dolayısıyla da çift olması gerektiği aşikârdır. Örneğin derece dizisi 𝐷 = {1(3), 2(1), 5(5), 8(7)} olan bir graf için (𝐷) = 54 çift sayı olduğundan çizilebilir bir graftır. Bu teoreme dayanarak verilen bir derece dizisinin omega değerinin tek sayı çıkması durumunda bu derece dizisinin çizilebilir olmadığı söylenebilir. Örneğin derece dizisi 𝐷 = {1(10), 2(1), 6(5), 15(7)} olan bir graf için (𝐷) = 101 tek sayı olduğundan bu derece dizisine karşılık herhangi bir graf çizilemez. 27 3.2.3. Teorem. 𝐺 grafı 𝑐 tane 𝐺1, 𝐺2, 𝐺3, … , 𝐺𝑐 bileşenine sahip bağlantısız bir graf olsun. 𝑐 (𝐺) = ∑(𝐺𝑖) 𝑖=1 dir. Bir başka deyişle  toplamsal bir fonksiyondur. İspat. 𝐺 grafının bileşenleri 𝐺1, 𝐺2, 𝐺3, … , 𝐺𝑐 olduğundan 𝐷(𝐺) kümesi, 𝐷(𝐺𝑖) kümelerinin birleşiminden oluşur. Omeganın tanımından sonuç kolayca görülür. Örneğin, bir 𝐺 bağlantısız grafı; derece dizisi 𝐷1 = {1 (3), 3(1)} olan 𝐺1, derece dizisi 𝐷2 = {2(1), 7(2)} olan 𝐺2 ve derece dizisi 𝐷 (2) (2) 3 = {2 , 3 } olan 𝐺3 bileşenlerinden oluşsun. O halde (𝐺1) = −2, (𝐺2) = 10 ve (𝐺3) = 2 olur. Buradan da (𝐺) = −2 + 10 + 2 = 10 elde edilir. Gerçekten de 𝐺 grafının derece dizisi 𝐷 = {1(3), 2(3), 3(3), 7(2)} olduğundan (𝐺) = 10 olduğu açıktır. 3.2.4. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … , △(𝑎△)} derece dizisine sahip bağlantılı bir graf olsun. 𝐺 grafının yüz (kapalı bölge veya devir) sayısı (𝐺) 𝑟 = + 1 2 dir. İspat. Euler karakteristiği gereği 𝑛 − 𝑚 + 𝑟 = 1 olduğundan verilen bir 𝐷 derece dizisi için 𝑛 = 𝑎1 + 𝑎2 + 𝑎3 + ⋯ + 𝑎△ ve 2𝑚 = 𝑎1 + 2𝑎2 + 3𝑎3 + ⋯ +△ 𝑎△ olduğu (G) hatırlanır ve bu değerler yukarıdaki denklemde yerine yazılırsa 𝑟 = + 1 sonucu elde 2 edilir. Euler karakteristiğinin topolojideki kullanımında bölge sayısına grafın dışı da katılmaktadır. Bu nedenle bu tür kaynaklarda yukarıdaki bağıntı ufak bir değişiklikle 𝑛 − 𝑚 + 𝑟 = 2 şeklinde verilmektedir. 28 𝐺 grafının bağlantısız olma durumunda omeganın toplamsallık özelliğinden faydalanarak aşağıdaki daha genel sonuç elde edilebilir: 3.2.5. Sonuç. 𝐺, 𝐷 = {0(𝑎0), 1(𝑎1), 2(𝑎2), 3(𝑎3), … , △(𝑎△)} derece dizisine sahip 𝑐 tane bileşenden oluşan bağlantısız bir graf olsun. Aşağıdaki eşitlik doğrudur: (𝐺) 𝑟 = + 𝑐 2 İspat. (𝐺) toplamsal özelliğe sahip olduğundan ve 𝑐 sabit bir sayı olduğundan 𝑟 de toplamsaldır. Yani 𝑖 = 1,2,3, … , 𝑐 için (𝐺𝑖) r(𝐺𝑖) = + 1 2 olduğu söylenebilir. Yukarıdaki denklemler taraf tarafa toplanırsa, c c (G ) c r(G )  ii 1 i1 i1 2 i1 (𝐺) ve böylece 𝑟 = + 𝑐 sonucu elde edilir. Buradan bağlantılılıkla ilgili aşağıdaki önemli 2 sonuç elde edilir: 3.2.6. Sonuç. Bütün graflar için (𝐺) 𝑐 ≥ − 2 olur. Denk olarak 𝑐 ≥ 𝑛 − 𝑚 eşitsizliği geçerlidir. Aşağıdaki özellik, 3.2.5. Sonucun bir özel durumunu vermektedir: 3.2.7. Sonuç. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … , △(𝑎△)} derece dizisine sahip 𝑐 tane bileşenden oluşan bağlantısız bir graf olsun. (𝐺) = −2 ise 𝑐 − 𝑟 = 1 dir. 29 3.2.8. Teorem. G, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bağlantılı bir graf ve (𝐺) ≥ 0 olsun. Bu durumda 𝐺 grafı en az bir devir bulundurmak zorundadır. İspat. 3.2.4. Teorem gereği 𝐺 grafının kapsadığı kapalı bölge sayısı (𝐺) 𝑟 = + 1 2 olup bu denklemde (𝐺) ≥ 0 yerine yazılırsa 𝑟 ≥ 1 olacaktır. Bu da, en az bir devir olduğunu gösterir. Bu teoremde bağlantılılık şartı kaldırıldığında yani graf bağlantısız olduğunda en az iki devir bulundurmak zorundadır: 3.2.9. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bağlantısız bir graf ve (𝐺) ≥ 0 olsun. Bu durumda 𝐺 grafı en az iki devir bulundurmak zorundadır. İspat. 3.2.5. Sonuç gereği 𝐺 grafının kapsadığı kapalı bölge sayısı (𝐺) 𝑟 = + 𝑐 2 olup bu denklemde (𝐺) ≥ 0 şartını ve bağlantısız olduğundan 𝑐 ≥ 2 şartı kullanıldığında 𝑟 ≥ 2 olacaktır. 3.2.10. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bağlantılı bir graf (𝐺) = −2⬄𝐺 bir ağaçtır. Birinci ispat. (𝐺) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 = −2 olsun. 3.2.4. Teorem gereği G grafının kapsadığı kapalı bölge sayısı, (𝐺) 𝑟 = + 1 2 denkleminde (𝐺) = −2 değeri yerine yazılırsa 𝑟 = 0 olur. Yani bir devire sahip değildir. Dolayısıyla bu bir ağaçtır. 30 İkinci ispat. (𝐺) = 2(𝑚 − 𝑛) = −2 olduğundan 𝑛 − 𝑚 = 1 bulunur. Bu değer Euler karakteristiğinin 𝑛 − 𝑚 + 𝑟 = 1 formülünde yerine konulursa 𝑟 = 0 bulunur. Üçüncü ispat. 3.2.7. Sonuç gereği c − r = 1 olduğu hatırlanırsa bağlantılılık gereği c = 1 olduğundan r = 0 elde edilir. Bu da grafın bir ağaç olduğunu gösterir. 3.2.11. Teorem. Eğer (𝐺) ≤ −4 ise G kesinlikle bağlantısızdır. (𝐺) İspat. Yukarıda verilen 3.2.6. Sonuçdaki 𝑐 ≥ − denkleminde (𝐺) ≤ −4 olduğu 2 kullanılırsa bileşen sayısı 𝑐 ≥ 2 olur. Yani 𝐺 grafı en az iki bileşenden oluşmaktadır. Bu da G’nin bağlantısız olduğunu gösterir. 3.2.12. Teorem. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisi verilsin. Eğer (𝐷) ≥ −2 ise 𝐷 potansiyel bağlantılıdır. Yani 𝐷 derece dizisinin çizimlerinden en az biri bağlantılıdır. Bu teoreme göre 𝐺 bağlantılı bir graf ve (𝐺) ≥ −2 ise 𝐺 grafı ya bir devir içeren graftır ya da bir ağaçtır. Bir 𝐺 grafındaki ağaç olan bileşenlerin sayısı 𝑐𝑎 ve devir bulunduran bileşenlerin sayısı da 𝑐𝑐 olsun. Bu durumda 𝑐 = 𝑐𝑎 + 𝑐𝑐 olur. Aşağıdaki sonuç 𝑐𝑐 sayısının çeşitli değerleri için 𝑐𝑎 sayısının alacağı olası değerleri verecektir: 3.2.13. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bir graf ve 𝑟(𝐺), 𝐺 grafındaki devir sayısı olsun. Eğer 𝑘 negatif olmayan bir tamsayı olmak üzere (𝐷) = −2𝑘  − 4 ise i. 𝑐𝑎 ≥ 𝑘’dır. ii. Eğer 𝑐𝑐 = 0 ise 𝑐𝑎 = 𝑘 olur. iii. Eğer 𝑐𝑐 = 1 ise 𝑐𝑎 = 𝑟(𝐶1) − 1 + 𝑘’dır. Burada 𝐶1, devir bulunduran tek bileşendir. iv. 𝑐𝑐 ≥ 2 ise 𝑐𝑎 = ∑𝑟(𝐶𝑖) − 𝑐𝑐 + 𝑘’dır. Burada 𝐶𝑖 devir bulunduran bileşenlerdir. İspat. i. Devir bulundurmayan bileşenlerin, yani ağaç olan bileşenlerin her biri için  = −2 olduğu ve her bir devir bulunduran bileşen için  ≥ 0 olduğu bilinmektedir. Eğer (𝐷) = −2𝑘 ≤ −4 ise ve tüm bileşenler devir içermiyorsa ’nın toplamsallığı gereği 31 tam 𝑘 tane devir içermeyen bileşen mevcuttur, yani 𝑐𝑎 = 𝑘 olur. Eğer (𝐷) = −2𝑘 ≤ −4 ise ve en az bir bileşen devir içeriyorsa bu durumda devir içermeyen bileşen sayısının 𝑐𝑎 ≥ 𝑘 olacağı açıktır. ii. 𝑐𝑐 = 0 olduğundan devir bulunduran bir bileşene sahip değildir. Dolayısıyla bütün bileşenler birer ağaçtır. Ağaçların  değeri −2 olduğundan her bir devir bulundurmayan (𝐺) 𝐶𝑖 bileşeni için (𝐶𝑖) = −2 olur. Ağaç olan bileşenlerin sayısı olan 𝑐𝑎 için 𝑐𝑎 = =−2 −2k = 𝑘 elde edilir. −2 iii. 𝑐𝑐 = 1 olduğundan tek devir bulunduran bir tane bileşen mevcuttur. Bu bileşen 𝐶1 (𝐶 )−(𝐺) 2𝑟(𝐶 )−2+2𝑘 olsun. 𝑐𝑎 = 1 olur. Buradan 3.2.4. Teorem gereği 𝑐 = 1𝑎 elde edilir. 2 2 Bu da istenen sonuçtur. iv. 𝑐𝑐 ≥ 2 olsun ve bu devir içeren bileşenleri 𝐶𝑖 ile gösterilsin. Böylece 𝑐𝑎 = ∑(𝐶𝑖)−(𝐺) ∑(2𝑟(𝐶𝑖)−2)+2𝑘= = ∑𝑟(𝐶𝑖) − 𝑐𝑐 + 𝑘 olur. 2 2 3.2.14. Teorem. 𝐷, çizilebilir bir derece dizisi olsun. 𝑐 ve 𝑐𝑎, sırasıyla 𝐷’nin bir 𝐺 çiziminin tüm bileşenlerinin ve devir içermeyen bileşenlerinin sayılarını; 𝐶𝑖 ve 𝐴𝑖 ise sırasıyla devir bulunduran ve bulundurmayan bileşenleri göstersin. Hatırlanacağı gibi (𝐴𝑖) = −2 idi. (𝐶𝑖) = 𝑘𝑖 olsun. Bu durumda i. eğer (𝐷) ≤ −4 ise 𝐷’nin tüm çizimleri bağlantısızdır ve  cca   ca  G   Ci   Ai   i1   i1  dir. Ayrıca (𝐺) = 𝑘1 + 𝑘2 + ⋯ + 𝑘𝑐−𝑐 − 2𝑐𝑎 ≤ −4 olur. 𝑎 ii. eğer (𝐷) = −2 ise 𝐷’nin herhangi bir çizimi bağlantılı da bağlantısız da olabilir. Böyle bir 𝐺 çizimi bağlantılı ise 𝐺 devir bulundurmaz ve 𝐺 = 𝐴1 şeklindedir. Böyle bir 𝐺 çizimi bağlantısız ise  cca   ca  G   Ci   Ai   i1   i1  32 dir. Ayrıca (𝐺) = 𝑘1 + 𝑘2 + ⋯ + 𝑘𝑐−𝑐 − 2𝑐 = −2 olur. 𝑎 𝑎 iii. Eğer (𝐷) ≥ 0 ise 𝐷’nin herhangi bir çizimi bağlantılı da bağlantısız da olabilir. Ayrıca tüm çizimler devir içerir. Böyle bir 𝐺 çizimi bağlantılı ise 𝐺 devir bulundurur ve 𝐺 = 𝐶1 şeklindedir. Böyle bir 𝐺 çizimi bağlantısız ise yine 𝐺 devir bulundurur ve  cca   ca  G   Ci   Ai   i1   i1  dir. Ayrıca (𝐺) = 𝑘1 + 𝑘2 + ⋯ + 𝑘𝑐−𝑐 − 2𝑐𝑎 ≥ 0 olur. Bu teoremin aşikâr sonuçları 𝑎 aşağıdaki gibidir: 3.2.15. Sonuç. i. Eğer bir 𝐺 grafı sadece devir içeren bileşenlerden oluşuyorsa (𝐺) ≥ 0 olur. ii. Eğer bir 𝐺 grafının tüm bileşenleri ağaçlardan oluşuyorsa (𝐺) ≤ −2 olur. 3.2.16. Sonuç. 𝑘 ∈ ℕ olmak üzere (𝐷) = −2𝑘 ise 𝐺 grafını oluşturan bileşenlerin en az 𝑘 tanesi ağaçtır. İspat. 𝐺’yi oluşturan bileşenlerde hiç ağaç olmadığı varsayılırsa 3.2.13. Teorem gereği bütün bileşenler devirden oluşmalıdır. Bütün bileşenler devirden oluştuğu için ve 3.2.3. Teorem gereği omeganın toplamsal özelliğinden dolayı (𝐷) ≥ 0 olmak zorundadır. Demek ki 𝐺’yi oluşturan bileşenlerin tümü devirden oluşamaz. Yani varsayımla çelişir. Bu çalışmada bir 𝐺 grafındaki köprülerin sayısı 𝑏𝑟(𝐺) ile; kopma noktalarının sayısı da 𝑐𝑣(𝐺) ile gösterilecektir. Buna göre 3.2.17. Teorem. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} ve 𝐺, 𝐷’nin bir çizimi olsun. 𝐺 bağlantılı ve (𝐷) = −2 ise (𝐺) = 2(𝑏𝑟(𝐺) − 𝑐𝑣(𝐺) − 𝑎1) ve böylece 𝑐𝑣(𝐺) + 𝑎1 − 𝑏𝑟(𝐺) = 1 olur. 33 İspat. (𝐷) = −2 ve bağlantılı olduğundan 𝐷’nin tüm çizimleri devir içermeyen çizimlerdir. Böyle bir grafta tüm kenarlar birer köprü, tüm köşeler birer kopma noktası veya birer sallanan köşedir. Dolayısıyla 3.2.10. Teorem gereği sonuç görülür. Aşağıdaki sonuç 3.2.13. Teoremin özel bir hali olup sık kullanıldığından ayrıca verilmesi uygun görülmüştür: 3.2.18. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bir graf ve (𝐷) = −2 olsun. 𝐺 grafının toplam devir sayısı (kapalı bölge sayısı) 𝑟(𝐺) olsun. 𝐺’nin ağaç şeklindeki bileşenlerinin sayısı 𝑐𝑎 ve devir içeren bileşenlerinin sayısı da 𝑐𝑐 ile gösterilsin. Aşağıdaki özellikler sağlanır. i. 𝑐𝑎 ≥ 1’dir. ii. Eğer 𝑐𝑐 = 0 ise 𝑐𝑎 = 1 olur. iii. Eğer 𝑐𝑐 = 1 ise 𝐶1 devir bulunduran tek bileşen olmak üzere (𝐶 ) 𝑐𝑎 = 1 + 1 = 𝑟(𝐶1) 2 olur. iv. 𝑐𝑐 ≥ 2 ise 𝐶𝑖’ler devir bulunduran bileşenler olmak üzere 𝑐𝑐 𝑐𝑎 = ∑ 𝑟(𝐶𝑖) − 𝑐𝑐 + 1 𝑖=1 olur. İspat. Sadece sonuncu iddiayı ispatlayacağız. Diğerleri benzer şekilde önceki sonuçlar yardımıyla ispatlanabilir. 3.2.4. Teorem ve 𝑐 = 𝑐𝑎 + 𝑐𝑐 olduğu kullanılırsa 𝑐 ∑ 𝑐 (𝐶𝑖) 𝑐 = 𝑖=1𝑎 + 1 2 𝑐𝑐 =∑ (𝑟(𝐶 ) − 1) + 1 𝑖=1 𝑖 𝑐𝑐 =∑ 𝑟(𝐶𝑖) − 𝑐𝑐 + 1 𝑖=1 olduğu açıktır. 34 Örnek olarak {1(2)} derece dizisine sahip 𝑃2 yol grafı ele alınsın, bkz. Şekil 3.1. Şekil 3.1. {1(2)} derece dizisine sahip 𝑃2 yol grafı (𝑃2) = −2, 𝑐𝑣(𝑃2) = 0, 𝑎1 = 2 ve 𝑏𝑟(𝑃2) = 1 olduğu açıktır ve bu değerler 3.2.17. Teorem’i sağlar. 3.2.19. Tanım. Bir graftaki tüm köşelerin merkezi bir yola olan uzaklıkları 0 veya 1 ise böyle bir grafa tırtıl graf (caterpillar tree) adı verilir. Bir tırtıl grafın aynı zamanda bir ağaç olduğuna dikkat ediniz. Örneğin 𝐶 = {1(5), 2(2), 3(1), 4(1)} derece dizisi düşünülsün. 𝐶’nin bağlantılı her bir çizimi (𝐶) = −2 olduğundan bir tırtıl graftır. Bkz. Şekil 3.2. {1(5), 2(2), 3(1), 4(1)} Şekil 3.2. Tırtıl graf Burada 𝑐𝑣(𝐶) = 4, 𝑎1 = 5 ve 𝑏𝑟(𝐶) = 8 olduğuna ve 3.2.17. Teoremi sağladığına dikkat ediniz. 3.2.20. Sonuç. Bağlantılı olan graflar için (𝐺) = 𝑟(𝐺) − 𝑐(𝐺) 2 dir. Burada grafın dışındaki bölgenin sayılmadığı bir kez daha hatırlanmalıdır. 3.3. Omega invaryantının Euler karakteristiği ile ilgisi Kompakt yönlendirilebilir yüzeylerin sınıflandırılması bu yüzeylerin cinsi adı verilen ve genellikle 𝑔 ile gösterilen bir sabit sayıya bağlıdır. Cins, bir anlamda yüzeyin delik sayısıdır. Her bir kompakt yönlendirilebilir yüzey ya cinsi 0 olan küreye, ya cinsi 1 olan 35 tora, ya da cinsi birden büyük bir tamsayı olan torların bağlantılı toplamına homeomorfiktir. Bir 𝑆 yüzeyinin (𝑆) ile gösterilen Euler karakteristiği, o yüzey üzerine çizilebilen 𝑛 köşeli, 𝑚 kenarlı ve 𝑟 bölgeli her bir grafta 𝑛 − 𝑚 + 𝑟 sayısının bir değişmez (invaryant) oluşundan hareketle (𝑆) = 𝑛 − 𝑚 + 𝑟 şeklinde tanımlanmıştır. Cinsi 𝑔 olan kompakt ve yönlendirilebilir bir yüzeyde bu sayı (𝑆) = 2 − 2𝑔 şeklindedir. (𝑆) sayısının verilen herhangi bir yüzey için bir invaryant olması da bu sebeptendir. 𝑆 yüzeyi üzerine hangi büyüklükte bir graf çizilirse çizilsin 𝑛 − 𝑚 + 𝑟 sayısı hep aynı çıkacaktır. Genellikle bir yüzeyin Euler karakteristiği için (𝑆) sembolünü kullanıldığı gibi bu yüzey üzerine çizilebilen bir 𝐺 grafının Euler karakteristiği için de (𝐺) gösterimi tercih edilir. Burada dikkat edilmesi gereken husus şudur: Bir graf cinsi 𝑔 olan bir yüzeye çizilebiliyorsa cinsi daha büyük olan her bir yüzeye de çizilebilir. Bu sebeple bir grafın cinsinden ve Euler karakteristiğinden bahsederken bu grafın çizilebildiği en düşük cinsli yüzey dikkate alınır. Girişte de belirttildiği gibi tanımlanılan omega invaryantının Topolojide ikiyüzelli yıldır bilinen Euler karakteristiği ile yakın ilgisi vardır. Bu kısımda bu ilişki belirlenecektir. 3.3.1. Teorem. Herhangi bir 𝐺 grafı için (𝐺) = 2(𝑟 − (𝐺)) bağıntısı geçerlidir. İspat. 𝐺 grafı, köşe sayısı 𝑛, kenar sayısı 𝑚 ve devir sayısı (kapalı bölge sayısı) 𝑟 olan bir graf olsun. Hatırlanacağı üzere (𝐺) Euler karakteristiği, (𝐺) = 𝑛 − 𝑚 + 𝑟 (𝐺) bağıntısını sağlar. 3.2.1. Teorem gereği = 𝑚 − 𝑛 olduğu da biliniyor. Dolayısıyla 2 sonuç görülür. Grafların çeşitli özelliklerinin çalışılması sırasında grafları farklı özelliklere göre sınıflandırmak oldukça faydalı olmaktadır. Bunlar arasında köşe ve kenar sayıları, bölge sayısı, kiriş, sallanan kenar, köprü sayıları vs. yer almaktadır. Bölge sayısına göre yapılan 36 bir sınıflandırmada hiçbir bölgeye sahip olmayan graflar, tek devir bulunduran graflar, iki devir bulunduran graflar, üç devir bulunduran graflar, vs. sırasıyla devirsiz (acyclic), tek devirli (unicyclic), iki devirli (bicyclic), üç devirli (tricyclic) vs. olarak adlandırılır. Bir grafın bağımsız devir sayısına grafın devir sayısı (cyclomatic number) denilir. Bu tür sınıflandırma problemleriyle uğraşırken graftaki bölge (devir) sayısını belirlemek doğal olarak oldukça önemlidir. Tabii ki bazı karmaşık graflarda kapalı bölgeleri, özellikle de üst üste geldiği durumlarda saymak hiç de kolay olmayabilir. Bu duruma örnek olarak Şekil 3.3’deki graf verilebilir. F E A B C D H G Şekil 3.3. Bölge sayısı kolay belirlenemeyen bir graf Bu grafta bölgeleri birbirine bağlayan köprüler veya kopma noktaları olmadığından bölgeler hemen belirlenemez. Bu yüzden sadece kirişlerin sayılması gerekir. Şekil 3.3’ün içerisinde 7 tane kiriş vardır. 7 kirişin olması 8 tane kapalı bölge olduğunu ifade eder. Şekil 3.4’de yukarıdaki şeklin farklı bir çizimi verilmiştir ve bu çizimdeki bölgelerin sayısının 8 olduğu bölgeler ayrık olduğundan kolayca sayılabilir. A B E G F H C D Şekil 3.4. Bölge sayısı kolayca belirlenebilen bir graf 37 Bu örnek gösteriyor ki bir çizilebilir derece dizisi verildiğinde bu derece dizisinin herhangi bir çiziminin kaç adet bölge bulundurduğu ilk bakışta söylenemeyebilir. Bu çizim farklı şekillerde çizilebilir ve bu sayım yukarıdaki örnekte olduğu gibi daha kolay bir şekilde gerçekleştirilebilir. Ya da verilen bir grafı yeniden çizerek bu çizim gerçekleştirilebilir. Ancak her örnekte bunu yapabilmek o kadar da kolay değildir. Özetlenecek olursa verilen bir derece dizisinin tüm çizimlerinin bölge sayısı veya verilen bir grafın bölge sayısı klasik yöntemle her zaman kolayca bulunamayabilir. Tanımlanılan omega invaryantı bu konuda da yardımcı olacaktır. Verilen örnekteki 𝐺 grafının derece dizisi 𝐷 = {3(4), 4(2), 5(2)} olup (𝐷) = 14’tür. 3.2.4. Teorem gereği aranılan bölge (𝐺) 14 sayısı 𝑟 = + 1 = + 1 = 8 olarak bulunur. 2 2 Dikkat edilirse omega invaryantından faydalanarak bölge sayısı hesaplandığında grafı çizmeye dahi gerek olmamaktadır.  bir graf invaryantı olduğundan 3.2.4. Teorem gereği bölge sayısını veren 𝑟 de bir graf invaryantıdır. Bir başka deyişle verilen bir derece dizisinin eşit bileşen sayısına sahip tüm çizimlerinde aynı sayıda kapalı bölge bulunmak zorundadır. Daha önce de belirtildiği gibi kapalı bölge denince genelde 𝑛 ≥ 3 olmak üzere 𝐶𝑛 devirleri anlaşılsa da burada bunlara ek olarak döngüleri (1 − gen) ve iki katlı kenar arasında kalan bölgeler (2 − gen) de alınacaktır. 3.3.2. Örnek. İkinci bir örnek olarak 𝐷 = {1(1), 2(3), 3(3), 4(4), 5(2)} derece dizisi ele alınsın. Bu derece dizisinin bağlantılı bir çizimi Şekil 3.5’deki gibidir. Şekil 3.5. {1(1), 2(3), 3(3), 4(4), 5(2)} derece dizisinin bağlantılı bir çizimi 38 Burada (𝐷) = 16 olduğu kolayca görülür. Dolayısıyla bu graftaki bağımsız bölge sayısı 16 𝑟 = + 1 = 9 2 olur. Dolayısıyla bağlantılı tüm çizimlerde 9 adet bölge bulunacağı açıktır. 39 4. DERECE DİZİLERİNİN TEMEL ÇİZİMLERİ 4.1. Giriş Hatırlanacağı gibi bu tezin ana hedefi, verilen bir çizilebilir derece dizisinin genellikle çok sayıda olan çizilmiş halleri ve bunların özellikleri hakkında çeşitli bilgiler elde etmektir. Bu hedefe yönelik çalışmalar sonucunda adına omega invaryantı (kısaca omega) denilen ve her bir derece dizisi için sabit olan bir sayı tanımlanmıştır. Bu omega invaryantı sayesinde derece dizisinin çizimlerinin ortak özelliklerini belirlemek bu tezin sonuçlarını zenginleştirmiştir. Derece dizilerine karşılık gelen graflar üzerinde yapılan tüm çalışmalarda belirtildiği gibi çizilebilir derece dizileri bazen bir tek şekilde çizilebildiği gibi bazen de birden fazla şekilde çizilebilir. Örneğin Şekil 4.1’de 𝐷 = {1(3), 3(1), 4(2)} derece dizisine karşılık olarak çizilebilen iki farklı graf görülmektedir. veya Şekil 4.1. {1(3), 3(1), 4(2)} derece dizisine ait iki farklı çizim Verilen bir çizilebilir derece dizisinin farklı şekillerde çizilebilmesi bunlardan hangisi ya da hangilerinin daha avantajlı olduğu sorusunu akla getirecektir. Tabii ki bu sorunun cevabı, hedeflenilen özelliklere bağlı olarak değişecektir. Bazen verilen derece dizisinin çizimlerinin belli bir özelliğine dair bir sayı belirlemek istenebilir, bazen de böyle bir sayı değişken olduğunda onun en küçük ve en büyük değerlerini bulmak gerekebilir. Graf teoride bu tür problemlere uç (extremal) problemler denilmektedir. Bu bölümde referans noktası olarak seçilen ve adına temel çizim formu denilen bir form tanımlanacaktır. Derece dizilerinin üç farklı olası durumu için farklı bir temel çizim formu verilecektir. Bir derece dizisinin temel çizim formu bilindiğinde, diğer çizimleri hakkında 40 bilgiler elde etmek mümkün olmaktadır. Yani bir anlamda temel çizim formu bir referans noktası olarak kullanılacaktır. Mümkün olduğunda bir grafın bağlantılı çizilebilmesinin birçok avantajları vardır. (𝐷) ≥ 0 ve (𝐷) = −2 durumlarında verilen derece dizisi potansiyel bağlantılıdır. Bir başka deyişle en az bir bağlantılı çizime sahiptir. Bu nedenle bu iki durumda kalan derece dizilerinin temel çizimlerinin bağlantılı olarak tercih edilmesi de gayet doğaldır. Ancak (𝐷) ≤ −4 olması durumunda verilen derece dizisi potansiyel bağlantılı değildir. Yani hiçbir şekilde bağlantılı olarak çizilemez. Bu nedenle incelenilecek bu üçüncü durumda tanımlanacak olan temel çizim formunun da bağlantılı olması beklenmemelidir. Bu bölümde derece dizilerinin olası üç durumunun her birisi için temel çizim adı verilen çizimlerinin nasıl yapılacağı incelenecektir. Bu durumlar (𝐷) ≥ 0, (𝐷) = −2 ve (𝐷) ≤ −4 şeklindedir. İlk durumda elde edilen temel çizimlere devirli temel çizim adı verilecektir. Bu durumda verilen derece dizisinin nasıl bir yöntemle çizileceğine ilişkin bir algoritma tanımlanacaktır. Tabii ki basit graflarla çalışmak amaçlandığından döngü ve katlı kenarlardan kaçınmak gerektiğini unutmamak gerekir. Daha sonra (𝐷) = −2 durumunda adına devir bulundurmayan (veya devirsiz) temel çizim denilecek bazı temel çizimler elde edilecektir. Bu durum için de bir algoritma tanımlanacaktır. Son olarak adına karma tipli temel çizim denilen (𝐷) ≤ −4 durumundaki temel çizimler için bir algoritma verilecektir. 4.2. (𝑫) ≥ 𝟎 durumu 4.2.1. (𝑫) ≥ 𝟎 olma durumunda temel çizim Buraya kadar olan çalışmalar neticesinde, çizilebilen, bağlantılı ve en az bir devir bulunduran tüm derece dizilerinin bir 𝐶𝑎 +𝑎 +⋯+𝑎 = 𝐶𝑛−𝑎 deviri etrafında çizilebilir 2 3 △ 1 olduğu gözlemlenmiştir. Burada 𝑛 − 𝑎1 sayısı, böyle bir derece dizisinin herhangi bir çiziminin sahip olabileceği en büyük devirin uzunluğunu göstermektedir. 4.2.1.1. Tanım. (𝐷) ≥ 0 bir çift sayı olsun. 𝐷 derece dizisinin, bir (𝑛 − 𝑎1) −genin köşelerine 𝑎1 tane sallanan kenar ve elde edilen bu çizime toplam (𝐷)/2 tane kiriş, 41 döngü ve katlı kenar eklenerek bulunan bağlantılı bir çizimine 𝐷 derece dizisinin bir devirli temel çizimi (cyclic fundamental form) adı verilir. Tanımdan da görüleceği üzere, (𝐷) ≥ 0 özelliğindeki bir 𝐷 derece dizisinin temel çizimi bağlantılıdır ve tek değildir. Amaca uygun olarak kiriş, döngü ve katlı kenar sayıları değiştirildiğinde farklı temel çizimler elde edilecektir. 4.2.2.17 Teoremde görüleceği gibi bu üç tür kenarın toplam sayısı (𝐷)/2’dir. Eğer grafın basit graf olması isteniyorsa döngü ve katlı kenarların mevcut olamayacağı gerçeğinden hareketle (𝐷)/2 tane kirişe sahip bir temel çizim bulunması gerekecektir. Örneğin eğer döngü olmaması veya sayısının en az olması isteniyorsa bu durumda maksimum sayıda kiriş ve katlı kenar kullanarak elde edilen bir temel çizim kullanılmalıdır. 4.2.1.2. Örnek. {2(2), 3(3), 4(1), 5(1)} derece dizisi için (𝐷) = 8 ≥ 0 olup bu derece dizisinin çok sayıda çiziminden iki tanesi Şekil 4.2’de görülmektedir. Bunlardan sağdaki bir 7 −gen olup derece dizisinde hiç derecesi 1 olan köşe olmadığından sallanan kenara ihtiyaç duyulmayan bir temel çizimdir. 7 −gen üzerindeki köşelerin yerleri değiştirilerek daha birçok farklı temel çizim yapılabilir. Soldaki ise temel çizim formunda olmayan herhangi bir çizimdir. Bu derece dizisi verildiğinde ve bu derece dizisine karşılık gelen bir temel çizim elde edilmesi istendiğinde doğrudan sağdaki çizim yapılır. Ya da soldaki graf verilip bunun temel formda çizilmiş hali istendiğinde yine sağdaki çizim yapılabilir. Bir temel çizim Şekil 4.2. {2(2), 3(3), 4(1), 5(1)} derece dizisinin herhangi bir çizimi ve bir temel çizimi 42 4.2.2. (𝑫) ≥ 𝟎 durumunda temel çizim algoritması Bu kısımda (𝐷) ≥ 0 ve bir çift sayı olması durumunda bir temel çizimin nasıl elde edileceğine, yani varlığına, dair bir algoritma geliştirilecektir. Hatırlanacağı gibi bu durumdaki bir temel çizim bağlantılı olacaktır. 4.2.2.1. Teorem. (𝐷) ≥ 0 ve bir çift sayı olsun. 𝐷 derece dizisinin en az bir devirli temel çizimi mevcuttur. İspat. Bu devirli temel çizimi genel hatlarıyla aşağıdaki temel prensiplere dayanan bir algoritma yardımıyla oluşturulacaktır. 1) 𝑎2 + 𝑎3 + ⋯ + 𝑎△ uzunluklu bir 𝐶 deviri çiziniz. Elde edilen grafın derece dizisi {2(𝑎2+𝑎3+⋯+𝑎△)} şeklindedir. 2) Eğer 𝑎1 > 0 ise 𝐶 deviri üzerinde katlı kenardan mümkün olduğunca kaçınabilmek adına birbirinden mümkün olduğunca uzak olan köşelere 𝑎1 tane sallanan kenar ekleyiniz. Elde edilen grafın derece dizisi {1(𝑎1), 2(𝑎2+𝑎3+⋯+𝑎△−𝑎1), 3(𝑎1)} şeklindedir. 3) Eğer (𝐷) = 0 ise algoritma sona erer. Değilse toplam (𝐷)/2 tane kiriş, döngü ve/veya katlı kenar ekleyiniz. Bu son durumda elde edilen grafın derece dizisi {1(𝑎1), 2(𝑎2), 3(𝑎3), … , △(𝑎△)} şeklindedir ve algoritma sona erer. Derece dizisi △ ≤ 4 olan moleküler graflara kısıtlanırsa daha detaylı bir ispat verilebilir: Burada çeşitli alt durumlar mevcuttur. İlk olarak 𝒂𝟑 + 𝒂𝟒 çift ise i. 𝑎 (𝑎2) (𝑎3) (𝑎4)1 = 0 için derece dizisi 𝐷 = {2 , 3 , 4 } şekline dönüşür. 1. adım: 𝐶 (𝑎2+𝑎3+𝑎4)𝑎 +𝑎 +𝑎 çizilir ve 𝐷 = {2 } elde edilir. 2 3 4 𝑎3+𝑎4 2. adım: tane kiriş yardımı ile 𝑎3 + 𝑎4 tane derecesi 2 olan köşe mümkünse katlılık 2 olmayacak şekilde birleştirilir. Böylelikle yeni derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−( 𝑎3+𝑎4), 3(𝑎3+𝑎4)} = {2(𝑎2), 3(𝑎3+𝑎4)} olur. Burada el sıkışma lemması gereği 𝑎3 + 𝑎4 toplamının çift olması gerektiğine dikkat ediniz. 43 𝑎 43. adım: tane kiriş yardımı ile mümkünse katlılık olmadan 𝑎4 tane derecesi 3 olan 2 köşe birleştirilir. Bu durumda 𝐷 = {2(𝑎2), 3(𝑎3+𝑎4)−𝑎4 , 4(𝑎4)} = {2(𝑎2), 3(𝑎3), 4(𝑎4)} elde edilmiş olur. Bu da aranan çizimdir. ii. 𝑎1 ≠ 0 için derece dizisi 𝐷 = {1 (𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} şekline dönüşür. 𝒂𝟏 < 𝒂𝟒 ise 1. adım: 𝐶𝑎 +𝑎 +𝑎 çizilir ve 𝐷 = {2 (𝑎2+𝑎3+𝑎4)} elde edilir. 2 3 4 𝑎3+𝑎4 2. adım: tane kiriş ile 𝑎3 + 𝑎4 tane derecesi 2 olan köşe mümkünse katlılık 2 olmayacak şekilde birleştirilir. Böylelikle yeni derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−(𝑎3+𝑎4), 3(𝑎3+𝑎4)} = {2(𝑎2), 3(𝑎3+𝑎4)} olur. 3. adım: 𝑎1 tane derecesi 3 olan köşeye birer tane sallanan kenar eklenir. Bu durumda yeni derece dizisi {1(𝑎1), 2(𝑎2), 3(𝑎3+𝑎4−𝑎1), 4(𝑎1)} olur. 4. adım: 𝑎4 − 𝑎1 tane derecesi 3 olan köşe mümkünse katlılık olmadan birleştirilir. Bu durumda derece dizisi 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3+𝑎4−𝑎1)−(𝑎4−𝑎1), 4(𝑎1)+(𝑎4−𝑎1)} = {1(𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} olarak elde edilmiş olur. Bu da aranan çizimdir. 𝒂𝟏 > 𝒂𝟒 ise 1. adım: 𝐶𝑎 +𝑎 +𝑎 deviri çizilir ve 𝐷 = {2 (𝑎2+𝑎3+𝑎4)} elde edilir. 2 3 4 𝑎 +2𝑎 −𝑎 2. adım: Devir üzerinde 3 4 1 tane kiriş yardımı ile 𝑎3 + 2𝑎4 − 𝑎1 tane derecesi 2 2 olan köşe mümkünse katlılık olmayacak şekilde birleştirilir. Böylelikle yeni 𝐷 = {2(𝑎2+𝑎3+𝑎4)−(𝑎3+2𝑎4−𝑎1) , 3(𝑎3+2𝑎4−𝑎1)} = {2(𝑎1+𝑎2−𝑎4), 3(𝑎3+2𝑎4−𝑎1)} olur. Burada el sıkışma lemması gereği 𝑎3 + 2𝑎4 − 𝑎1 sayısının tek olması gerekir. 3. adım: Derecesi 2 olan 𝑎1 − 𝑎4 tane köşeye birer tane sallanan kenar eklenir. Bu durumda derece dizisi 𝐷 = {1(𝑎1−𝑎4), 2(𝑎1+𝑎2−𝑎4)−(𝑎1−𝑎4), 3(𝑎3+2𝑎4−𝑎1+(𝑎1−𝑎4))} = {1(𝑎1−𝑎4), 2(𝑎2), 3(𝑎3+𝑎4)} olur. 44 4. adım: Derecesi 3 olan 𝑎4 tane köşeye birer tane sallanan kenar eklenir. Böylece 𝐷 = {1(𝑎1−𝑎4+𝑎4), 2(𝑎2), 3(𝑎3+𝑎4−𝑎4), 4(𝑎4)} = {1(𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} olur. 𝒂𝟏 = 𝒂𝟒 ise 1. adım: 𝐶 (𝑎2+𝑎3+𝑎4)𝑎 +𝑎 +𝑎 çizilir ve 𝐷 = {2 } elde edilir. 2 3 4 𝑎3+𝑎4 2. adım: tane kiriş yardımı ile derecesi 2 olan 𝑎3 + 𝑎4 tane köşe mümkünse katlılık 2 olmayacak şekilde birleştirilir. Böylelikle yeni derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−(𝑎3+𝑎4) , 3(𝑎3+𝑎4)} = {2(𝑎2), 3(𝑎3+𝑎4)} olur. 3. adım: Derecesi 3 olan 𝑎1 tane köşeye birer tane sallanan kenar eklenir. Bu durumda 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3+𝑎4−𝑎1), 4(𝑎1)} olur. Ayrıca 𝑎1 = 𝑎4 olduğundan derece dizisi 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎1)} olarak elde edilir. İkinci olarak 𝒂𝟑 + 𝒂𝟒 tek ise i. 𝑎1 = 0 için derece dizisi 𝐷 = {2 (𝑎2), 3(𝑎3), 4(𝑎4)} şeklinde olacaktır. 1. adım: 𝐶𝑎 +𝑎 +𝑎 deviri çizilir ve 𝐷 = {2 (𝑎2+𝑎3+𝑎4)} elde edilir. 2 3 4 𝑎3+𝑎4−1 2. adım: tane kiriş ile 𝑎3 + 𝑎4 − 1 tane derecesi 2 olan köşe mümkünse katlılık 2 olmayacak şekilde birleştirilir. Böylelikle yeni derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−( 𝑎3+𝑎4−1), 3(𝑎3+𝑎4−1)} = {2(𝑎2+1), 3(𝑎3+𝑎4−1)} olur. 3. adım: Bir tane derecesi 2 olan köşe ile bir tane derecesi 3 olan köşe birleştirilir. Bu durumda 𝐷 = {2(𝑎2+1−1), 3(𝑎3+𝑎4−1)+1−1, 4(1)} = {2(𝑎2), 3(𝑎3+𝑎4−1), 4(1)} derece dizisi elde edilmiş olur. 4. adım: Derecesi 3 olan 𝑎4 − 1 tane köşe mümkünse katlılık olmayacak şekilde birleştirilir. Böylece 𝐷 = {2(𝑎2), 3(𝑎3+𝑎4−1)−(𝑎4−1), 4(1+ 𝑎4−1)} = {2(𝑎2), 3(𝑎3), 4(𝑎4)} elde edilir. ii. 𝑎1 ≠ 0 için 𝐷 = {1 (𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} şeklinde bir derece dizisi mevcuttur. 𝒂𝟏 < 𝒂𝟒 ise 45 1. adım: 𝐶 çizilir ve 𝐷 = {2(𝑎2+𝑎3+𝑎4)𝑎 +𝑎 +𝑎 } elde edilir. 2 3 4 𝑎 +𝑎 −1 2. adım: 3 4 tane kiriş ile 𝑎3 + 𝑎4 − 1 tane derecesi 2 olan köşe mümkünse katlılık 2 olmayacak şekilde birleştirilir. Böylelikle derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−( 𝑎3+𝑎4−1), 3(𝑎3+𝑎4−1)} = {2(𝑎2+1), 3(𝑎3+𝑎4−1)} olur. 3. adım: Bir tane derecesi 2 olan köşeye bir tane sallanan kenar eklenir. Yani 𝐷 = {1(1), 2(𝑎2+1−1), 3(𝑎3+𝑎4−1)+1} = {1(1), 2(𝑎2), 3(𝑎3+𝑎4)} elde edilmiş olur. 4. adım: Derecesi 3 olan 𝑎1 − 1 tane köşeye birer tane sallanan kenar eklenir. 𝐷 = {1(1+𝑎1−1), 2(𝑎2), 3(𝑎3+𝑎4)−(𝑎1−1), 4(𝑎1−1)} = {1(𝑎1), 2(𝑎2), 3(𝑎3+𝑎4−𝑎1+1), 4(𝑎1−1)} olur. 𝑎4−𝑎1+1 5. adım: Eğer 𝑎4 − 𝑎1 + 1 = 0 ise algoritma biter. Aksi taktirde tane kiriş ile 2 𝑎4 − 𝑎1 + 1 tane derecesi 3 olan köşe mümkünse katlılık olmayacak şekilde birleştirilir. Bu durumda derece dizisinin son hali 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3+𝑎4−𝑎1+1)−(𝑎4−𝑎1+1), 4(𝑎1−1)+𝑎4−𝑎1+1} = {1(𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} şeklinde elde edilir ve böylece istenen çizim elde edilmiş olur. 𝒂𝟏 > 𝒂𝟒 ise 1. adım: 𝐶 çizilir ve 𝐷 = {2(𝑎2+𝑎3+𝑎4)𝑎 +𝑎 +𝑎 } elde edilir. 2 3 4 𝑎3+2𝑎4−𝑎1 2. adım: tane kiriş ile 𝑎3 + 2𝑎4 − 𝑎1 tane derecesi 2 olan köşe mümkünse 2 katlılık olmayacak şekilde birleştirilir. Böylelikle elde edilen derece dizisi 𝐷 = {2(𝑎2+𝑎3+𝑎4)−( 𝑎3+2𝑎4−𝑎1 ), 3(𝑎3+2𝑎4−𝑎1 )} = {2(𝑎2−𝑎4+𝑎1), 3(𝑎3+2𝑎4−𝑎1)} olur. 3. adım: 𝑎1 − 𝑎4 tane derecesi 2 olan köşeye birer tane sallanan kenar eklenir. Yani 𝐷 = {1(𝑎1−𝑎4 ), 2(𝑎2−𝑎4+𝑎1)−(𝑎1−𝑎4 ), 3(𝑎3+2𝑎4−𝑎1)+(𝑎1−𝑎4 )} = {1(𝑎1−𝑎4 ), 2(𝑎2), 3(𝑎3+𝑎4)} elde edilmiş olur. 4. adım: Derecesi 3 olan 𝑎4 tane köşeye birer tane sallanan kenar eklenir. 𝐷 = {1(𝑎1−𝑎4)+(𝑎4), 2(𝑎2), 3(𝑎3+𝑎4)−(𝑎4), 4(𝑎4)} = {1(𝑎1), 2(𝑎2), 3(𝑎3), 4(𝑎4)} olur. 𝒂𝟏 = 𝒂𝟒 ise 46 𝑎3 + 𝑎4 tek olma şartına uymadığı için bu ihtimal yoktur. Çünkü el sıkışma lemması gereği 𝑎1 ile 𝑎3 aynı anda tek ya da aynı anda çift olması gerektiğinden, 𝑎4 çift olduğunda eşitlikten dolayı 𝑎1 de çift olacaktır. 𝑎1 çift olması gerektiğinden, el sıkışma lemması gereği 𝑎3 de çift olmak zorunda olacaktır. Bu da 𝑎1, 𝑎3 ve 𝑎4 sayılarının aynı anda tek veya aynı anda çift olacağını gösterdiğinden en baştaki şarta uymaz. Böylelikle 𝑎3 + 𝑎4 tek iken 𝑎1 = 𝑎4 olamaz. Not: “Derecesi 2 olan bir köşeyi derecesi 3 olan bir köşe ile birleştirin” denilen adımlarda eğer derecesi 3 olan hiçbir köşe yoksa derecesi 2 olan mevcut bir köşeden çıkan ve yine aynı köşeye dönen bir döngü eklenir. (Çıkılan 2 dereceli köşenin derecesi artık 3 olduğundan kurala uyulmuş olur.) 4.2.2.2. Örnek. 𝐷 = {4(1)} ve 𝐷 = {2(3), 4(1)} derece dizileri ele alınsın, bkz. Şekil 4.3. {4(1)} {2(3), 4(1)} Şekil 4.3. İki temel çizim Yukarıdaki iki çizim de (𝐷) ≥ 0 durumundaki temel çizim yöntemine uygun olarak çizilmiştir. Soldaki şekilde en büyük devir 1 −gen olduğundan başka bir çizim yapılamaz. Ancak sağdaki çizimde bir dörtgen bulunduğundan 4.2.2.1. Teorem gereği bu çizim aynı zamanda bir 3 −gen ve bir 2 −gen kullanılarak da yapılabilir, bkz. Şekil 4.4. Şekil 4.4. {2(3), 4(1)} derece dizisinin bir diğer çizimi 47 4.2.2.3. Örnek. 𝐷 = {2(2), 3(2), 4(2)} derece dizisi verilsin. 𝑎3 + 𝑎4 = 4 çift ve 𝑎1 = 0 olduğundan 1. adım: 𝐶𝑎 +𝑎 +𝑎 çizilir. Yani 𝐶2+2+2 = 𝐶6 = {2 (6)} çizilir. Bkz. Şekil 4.5. 2 3 4 Şekil 4.5. 𝐶6 𝑎3+𝑎 2. adım: 4 = 2 tane kiriş yardımı ile 𝑎3 + 𝑎4 = 4 tane derecesi 2 olan köşe 2 birleştirilir. Bkz. Şekil 4.6. Şekil 4.6. {2(2), 3(4)} 𝑎4 3. adım: = 1 tane kiriş ile 𝑎4 = 2 tane derecesi 3 olan köşe birleştirilir, bkz. Şekil 4.7. 2 Şekil 4.7. {2(2), 3(2), 4(2)} Elde edilen son şekil, aranan çizimdir. 48 4.2.2.4. Örnek. 𝐷 = {1(3), 2(1), 3(3), 4(2)} derece dizisi verilsin. O halde 𝑎3 + 𝑎4 tek, 𝑎1 ≠ 0 ve 𝑎1 > 𝑎4 olduğundan aşağıdaki adımlar atılır: 1. adım: 𝐶𝑎 +𝑎 +𝑎 = 𝐶1+3+2 = 𝐶6 çizilir, bkz. Şekil 4.8. 2 3 4 Şekil.4.8. 𝐶6 𝑎 +2𝑎 −𝑎 2. adım: 3 4 1 = 2 tane kiriş ile 𝑎3 + 2𝑎4 − 𝑎1 = 4 tane derecesi 2 olan köşe 2 birleştirilir. Bkz. Şekil 4.9. Şekil 4.9. {2(2), 3(4)} 3. adım: 𝑎1 − 𝑎4 = 1 tane derecesi 2 olan köşeye birer tane sallanan kenar eklenir, bkz Şekil 4.10. Şekil 4.10. {1(1), 2(1), 3(5)} 4. adım: 𝑎4 = 2 tane derecesi 3 olan köşeye birer tane sallanan kenar eklenir, bkz. Şekil 4.11. 49 Şekil 4.11. {1(3), 2(1), 3(3), 4(2)} derece dizisinin bir temel çizimi 4.2.2.5. Örnek. 𝐷 = {3(2), 4(1)} derece dizisi verilsin. 𝑎3 + 𝑎4 tek ve 𝑎1 = 0 olduğundan aşağıdaki adımlarla aranan çizime ulaşılır: 1. adım: 𝐶𝑎 +𝑎 +𝑎 = 𝐶2+1 = 𝐶3 çizilir ve 𝐷 = {2 (3)} elde edilir, bkz. Şekil 4.12. 2 3 4 Şekil 4.12. {2(3)} 𝑎3+𝑎4−1 2. adım: = 1 tane kiriş ile 𝑎3 + 𝑎4 − 1 = 2 tane derecesi 2 olan köşenin 2 mümkünse katlılık olmayacak şekilde birleştirilmesi gerekir, ancak hangi köşeler seçilirse seçilsin katlılıktan kaçınılamayacağı açıktır, bkz. Şekil 4.13. Şekil 4.13. {2(1), 3(2)} 3. adım: Derecesi 2 olan bir köşe derecesi 3 olan bir köşeye birleştirilir, bkz. Şekil 4.14. 50 Şekil 4.14. {3(2), 4(1)} derece dizisinin bir temel çizimi 4. adım: 𝑎4 − 1 = 0 olduğundan işlem sona erer. 4.2.2.6. Örnek. 𝐷 = {1(2), 3(2), 4(1)} derece dizisi verilsin. 𝑎3 + 𝑎4 tek, 𝑎1 ≠ 0 ve 𝑎1 > 𝑎4 olduğundan aşağıdaki adımlar atılır: 1. adım: 𝐶𝑎 +𝑎 +𝑎 = 𝐶2+1 = 𝐶3 çizilir ve 𝐷 = {2 (3)} elde edilir, bkz. Şekil 4.15. 2 3 4 Şekil 4.15. {2(3)} 𝑎3+2𝑎4−𝑎1 2. adım: = 1 tane kiriş ile 𝑎3 + 2𝑎4 − 𝑎1 = 2 tane derecesi 2 olan köşe, 2 mümkünse katlılık olmayacak şekilde birleştirilir, bkz. Şekil 4.16. Şekil 4.16. {2(1), 3(2)} 51 3. adım: 𝑎1 − 𝑎4 = 1 tane derecesi 2 olan köşeye birer tane sallanan kenar eklenir, bkz. Şekil 4.17. Şekil 4.17. {1(1), 3(3)} 4. adım: 𝑎4 = 1 tane derecesi 3 olan köşeye birer tane sallanan kenar eklenir, bkz. Şekil 4.18. Şekil 4.18. {1(2), 3(2), 4(1)} derece dizisinin bir temel çizimi 4.2.2.7. Örnek. 𝐷 = {1(1), 3(1)} derece dizisi verilsin. 𝑎3 + 𝑎4 tek, 𝑎1 ≠ 0 ve 𝑎1 > 𝑎4 olduğundan, 1. adım: 𝐶𝑎 +𝑎 +𝑎 çizilir. Yani 𝐶1+0 = 𝐶1 çizilir. Hatırlanacağı gibi 𝐶1 1 −geni, bir 2 3 4 döngü olarak alınmalıdır, bkz. Şekil 4.19. 52 Şekil 4.19. {2(1)} 𝑎3+2𝑎 −𝑎 4 12. adım: = 0 tane kiriş ile 𝑎3 + 2𝑎4 − 𝑎1 = 0 tane derecesi 2 olan köşeyi 2 mümkünse katlılık olmayacak şekilde birleştirmek gerekir ama açıktır ki bu adım gereksizdir. 3. adım: 𝑎1 − 𝑎4 = 1 tane derecesi 2 olan köşeye bir tane sallanan kenar eklenir, bkz. Şekil 4.20. Şekil 4.20. {1(1), 3(1)} derece dizisinin bir temel çizimi 4. adım: 𝑎4 = 0 tane derecesi 3 olan köşeye birer tane sallanan kenar eklenir. Yani bu adımı gerçekleştirilemez. 4.2.2.8. Örnek. 𝐷 = {1(1), 2(1), 3(1)} derece dizisi ele alınsın. 𝑎3 + 𝑎4 tek, 𝑎1 ≠ 0 ve 𝑎1 > 𝑎4 olduğundan aşağıdaki adımlar takip edilir: 1. adım: 𝐶𝑎 +𝑎 +𝑎 çizilir. Yani 𝐶1+1 = 𝐶2 çizilir, bkz. Şekil 4.21. 2 3 4 Şekil 4.21. {2(2)} 53 𝑎3+2𝑎4−𝑎 12. adım: = 0 tane kiriş ile 𝑎3 + 2𝑎4 − 𝑎1 = 0 tane derecesi 2 olan köşe 2 mümkünse katlılık olmayacak şekilde birleştirilir, ancak bu adım gerçekleştirilemez. 3. adım: 𝑎1 − 𝑎4 = 1 tane derecesi 2 olan köşeye birer tane sallanan kenar eklenir, bkz. Şekil 4.22. Şekil 4.22. {1(1), 2(1), 3(1)} derece dizisinin bir temel çizimi 4. adım: 𝑎4 = 0 tane derecesi 3 olan köşeye birer tane sallanan kenar eklemek gerekir ancak bu işlem de yapılamaz. 4.2.2.9. Örnek. 𝐷 = {1(1), 2(1), 3(3), 4(4)} derece dizisi verilsin. 𝑎3 + 𝑎4 tek, 𝑎1 ≠ 0 ve 𝑎1 < 𝑎4 olduğundan aşağıdaki adımlar takip edilmelidir: 1. adım: 𝐶𝑎 +𝑎 +𝑎 çizilir. Yani 𝐶2 3 4 1+3+4 = 𝐶8 çizilir, bkz. Şekil 4.23. Şekil 4.23. Algoritmada belirtilen {2(8)} derece dizisine karşılık gelen tek bağlantılı graf 𝑎 +𝑎 3 4 −1 2. adım: = 3 tane kiriş ile 𝑎3 + 𝑎4 − 1 = 6 tane derecesi 2 olan köşe mümkünse 2 katlılık olmayacak şekilde birleştirilir, bkz. Şekil 4.24. Şekil 4.24. {2(2), 3(6)} 54 3. adım: 1 tane derecesi 2 olan köşeye bir tane sallanan kenar eklenir, bkz. Şekil 4.25. Şekil 4.25. {1(1), 2(1), 3(7)} 4. adım: 𝑎1 − 1 = 0 tane derecesi 3 olan köşeye birer tane sallanan kenar eklemek gerekir ancak bu işlem de yapılamaz. 5. adım: 𝑎4 − 𝑎1 + 1 = 4 tane derecesi 3 olan köşe mümkünse katlılık olmayacak şekilde birleştirilir, bkz. Şekil 4.26. Şekil 4.26. {1(1), 2(1), 3(3), 4(4)} derece dizisinin bir temel çizimi 4.2.2.10. Örnek. 𝐷 = {2(1)} derece dizisi verilsin. 𝑎3 + 𝑎4 çift ve 𝑎1 = 0 olduğundan aşağıdaki adımlar takip edilmelidir: 1. adım: 𝐶 çizilir. Yani 𝐶 = 𝐶 = {2(1)𝑎 +𝑎 +𝑎 1+0+0 1 } çizilir, bkz. Şekil 4.27. 2 3 4 Şekil 4.27. {2(1)} derece dizisinin bir temel çizimi 55 𝑎3+𝑎4 2. adım: = 0 tane kiriş ile 𝑎3 + 𝑎4 = 0 tane derecesi 2 olan köşeyi mümkünse 2 katlılık olmayacak şekilde birleştirmek gerekir ki bu da yapılamaz. 𝑎4 3. adım: = 0 tane kiriş ile mümkünse katlılık olmadan 𝑎4 = 0 tane derecesi 3 olan 2 köşeyi birleştirmek gerekir ve bu da mümkün değildir. Yani aranan çizim Şekil 4.27’deki çizimdir. 4.2.2.11. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bir graf olsun. 𝑎1 > 0 ve 𝑖 = 2, 3, 4, … , △ için 𝑎𝑖 ≥ 0 olsun. Eğer (D) = 0 ise G grafı potansiyel bağlantılıdır ve en az bir devire sahiptir. Bağlantılı olma durumunda bu çizim tek devire sahiptir ve bu tek devirin uzunluğu 1 ile 𝑎2 + 𝑎3 + ⋯ + 𝑎△ arasındaki herhangi bir sayı olabilir. Bağlantısız olma durumunda ise en az iki devir mevcuttur. Bu teoremde belirtilen tek devirin uzunluğunun 𝑎2 + 𝑎3 + ⋯ + 𝑎△ olduğu çizimin yukarıda tanımlanan devir içeren temel çizim olduğuna ve diğer çizimlerin birer temel çizim olmadığına dikkat ediniz. İspat. (D) = 0 olsun. İlk olarak 𝐷’nin çizimlerinden en az birisinin bağlantılı olduğunu göstermek gerekir. Bu bağlantılı çizim adım adım oluşturulur: (𝑎2 + 𝑎3 + ⋯ + 𝑎△) −gen çizerek başlanır. Bu çokgen 𝐶(𝑎 +𝑎 +⋯+𝑎 ) ile gösterilsin. Bir devir oluşturulduğu için 2 3 △ deviri oluşturan her köşenin derecesi 2 olduğundan 𝑎2 tane derecesi 2 olan köşeyi ayırarak başlanabilir. Derecesi 3 olan köşeleri elde etmek için 𝑎3 tane köşenin her birine birer sallanan kenar eklenir. Derecesi 4 olan köşeleri elde etmek için 𝑎4 tane köşenin her birine 2’şer tane sallanan kenar eklenir. Derecesi 5 olan köşeleri elde etmek için 𝑎5 tane köşenin her birine 3’er tane sallanan kenar eklenir. Bu adımları △’ya kadar devam ettirilirse, derecesi △ olan köşeleri elde etmek için 𝑎△ tane köşenin her birine △ −2’şer tane sallanan kenar eklenir. Böylelikle 𝑎2 + 𝑎3 + ⋯ + 𝑎△ uzunluklu devire eklenen sallanan kenarların toplam sayısı, 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ olarak elde edilir. Yani elde edilen çizimin, ki buna da 𝐺(𝑎 +𝑎 +⋯+𝑎 ) denilsin, derece 2 3 △ dizisi 𝐷 = {1(𝑎3 + 2𝑎4+3𝑎5+⋯+(△ −2)𝑎△ ), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} 56 olur. (D) = 0 olduğundan dolayı 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 = 0 olur. Buradan 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ = 𝑎1 bulunur. Bu da verilen 𝑎1 tane sallanan kenarın tam olarak tümünün kullanıldığını gösterir ve elde edilen 𝐺(𝑎 +𝑎 +⋯+𝑎 ) çiziminin derece dizisi 𝐷 = {1 (𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} 2 3 △ şeklindedir. Bir tek devire sallanan kenarlar eklenerek elde edilen bu çizim aranan bağlantılı çizimdir. İkinci olarak 𝐷’nin bağlantılı bir çiziminde mevcut olan bir tek devirin uzunluğunun 1 ile 𝑛 − 𝑎1 = 𝑎2 + 𝑎3 + ⋯ + 𝑎△ arasında kalan her bir tamsayı olabileceği gösterilecektir: İspatın tamamlanan kısmında böyle bir bağlantılı çizimin, adına 𝐶(𝑎 +𝑎 +⋯+𝑎 ) denilen 2 3 △ bir (𝑛 − 𝑎1) −gen yardımıyla elde edilebildiği gösterildi ve bu çizime 𝐺(𝑎 +𝑎 +⋯+𝑎 ) adı 2 3 △ verildi. Şimdi de adım adım bu devirin uzunluğunun 1’e varana dek birer birer düşürebileceği gösterilecektir. 𝑖 = 1, 2, … , 𝑎2 + 𝑎3 + ⋯ + 𝑎△ için 𝑑𝑖, 𝑣𝑖 köşesinin derecesi olsun. 𝐺(𝑎 +𝑎 +⋯+𝑎 ) grafının derece dizisi 𝐷 = {𝑑1, 𝑑2, … , 𝑑𝑎 +𝑎 +⋯+𝑎 } 2 3 △ 2 3 △ küçükten büyüğe sıralanmış olsun. 𝐺(𝑎 +𝑎 +⋯+𝑎 ) üzerinde derecesi en düşük 𝑑1 sayısı 2 3 △ olan 𝑣1 köşesini, varsa kendisine bitişik olan tüm sallanan kenarlar ve kendisine komşu olan tüm sallanan köşeler ile birlikte silinsin ve derece dizisinin değişmemesi için adına tekrar 𝑣1 denilecek olan yeni bir köşe, mevcut sallanan kenarlardan herhangi birine, diyelim ki 𝑢𝑣𝑎 +𝑎 +⋯+𝑎 kenarı üzerine, eklensin. (Burada neden 𝑎1 > 0 şartının alındığı 2 3 △ anlaşılabilir. Eğer 𝑎1 = 0 olsaydı hiçbir sallanan kenar olmayacağından 𝑣1 köşesini taşımak mümkün olamayacaktı). Bu işlem sonucunda 𝐺(𝑎 +𝑎 +⋯+𝑎 ) grafındaki tek 2 3 △ devirin uzunluğunu 1 azaltarak bir (𝑎2 + 𝑎3 + ⋯ + 𝑎△ − 1) −gene dönüştürülen ve adına 𝐺(𝑎 +𝑎 +⋯+𝑎 −1) denilecek olan yeni bir graf elde edilir. İkinci adımda ilkine 2 3 △ benzer şekilde 𝐺(𝑎2+𝑎 +⋯+𝑎 −1) grafındaki en küçük 𝑑2 derecesine sahip 𝑣2 köşesi, yine 3 △ kendisine bitişik olan tüm sallanan kenarlar ve kendisine komşu olan tüm sallanan köşeler ile birlikte silinir ve adına yine 𝑣2 denilecek olan yeni bir köşe, bu kez 𝑢𝑣2 kenarı üzerine eklenir. Bu işlem sonucunda 𝐺(𝑎 +𝑎 +⋯+𝑎 −1) grafındaki tek devirin uzunluğu yine 1 2 3 △ 57 azaltarak bir (𝑎2 + 𝑎3 + ⋯ + 𝑎△ − 2) −gene dönüşen ve adına 𝐺(𝑎 +𝑎 2 3+⋯+𝑎△−2) denilecek yeni bir graf elde edilir. Bu şekilde devam edilerek 𝑣3, 𝑣4, … , 𝑣𝑎 2+𝑎3+⋯+𝑎△−1 köşeleri bir ucu 𝑢 köşesi olan kenar üzerine taşındığında sırasıyla adına 𝐺(𝑎 , 2+𝑎3+⋯+𝑎△−3) 𝐺(𝑎 +𝑎 +⋯+𝑎 −4), …, 𝐺2 ve 𝐺1 denilecek olan graflar elde edilir. Bu da istenen sonuçtur. 2 3 △ Buradaki işlemleri tam anlamıyla anlayabilmek için 4.2.2.12. Örnek’e bakınız. Çizimin bağlantısız olması durumunda ise en az iki devir bulunduğunu göstermek için omeganın toplamsallık özelliğinden faydalanılır. 𝐷’nin bağlantısız bir çizimi 𝐺 ve (𝐷) = 0 olsun. Bu durumda (𝐺) = 0 olduğu açıktır. 𝐺’nin en az iki bileşeni olduğundan iki durum söz konusudur. Ya tüm bileşenlerin omega değerleri sıfırdır, ki bu durumda her bir bileşen, 3.2.4. Teorem gereği 0/2+1 = 1 devire sahip olur ve bu da 𝐺’nin en az iki devire sahip olduğunu gösterir, ya da bazı bileşenlerin omega değerleri pozitif bazılarının da negatiftir ve bu durumda da pozitif omega değerine sahip olan her bir 𝐺𝑖 (𝐺 bileşenindeki devir sayısı 𝑖 ) + 1 ≥ 2 olur ki bu da istenen sonucu verir. 2 4.2.2.12. Örnek. 𝐷 = {1(11 ), 2(2), 3(3), 4(1), 5(2)} derece dizisi verilsin. (𝐷) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + ( − 2)𝑎 − 𝑎1 = 3 + 2 + 6 − 11 = 0 olur. İlk olarak (2 + 3 + 1 + 2) −gen çizilir, bkz. Şekil 4.28. v v 1 2 v v 8 3 v v 4 7 v v 5 6 Şekil 4.28. {2(8)} sekizgeni 58 İkinci olarak, derecesi 3 olan köşelere birer tane, derecesi 4 olan köşelere ikişer tane ve derecesi 5 olan köşelere üçer tane sallanan kenar eklenir. Derecesi en büyük olan köşelerden birisindeki sallanan kenarın diğer ucundaki sallanan köşe 𝑢 ile gösterilsin, bkz. Şekil 4.29. v v 1 2 u v v 8 3 v v 4 7 v v 5 6 Şekil 4.29. {1(11), 2(2), 3(3), 4(1), 5(2)} Üçüncü olarak, 𝑣1 köşesini silinir ve herhangi bir sallanan kenara sahip olmadığından 𝑢𝑣8 kenarı üzerine adına yine 𝑣1 denilebilecek bir köşe eklenir, bkz. Şekil 4.30. v 2 v v 3u v 8 1 v 4 v 7 v v 6 5 Şekil 4.30. 𝐺 (11) (2) (3) (1) (2)(𝑎2+𝑎3+⋯+𝑎△−1) = {1 , 2 , 3 , 4 , 5 } Dördüncü olarak, 2 dereceli 𝑣2 köşesi silinip 𝑢𝑣1 kenarı üzerine taşınır. 59 v 3 u v v 8 v 2 v 1 4 v v 7 5 v 6 Şekil 4.31. 6-genli çizim Bu şekilde devam edilerek en büyük devirin uzunluğu 1’e düşene kadar Şekil 4.29- Şekil 4.36’da görülen tüm çizimler elde edilebilir. u v 3 v 2 v 4 v 1 v v 8 5 v 7 v 6 Şekil 4.32. 5-genli çizim 60 u v 4 v 3 v 2 v 1 v v 8 5 v 7 v 6 Şekil 4.33. 4-genli çizim u v 5 v 4 v 3 v 2 v 1 v v 6 8 v 7 Şekil 4.34. 3-genli çizim u v v 8 7 v v v v 6 5 4 3 v v 2 1 Şekil 4.35. 2-genli çizim 61 u v v v v v 87 v v v 6 5 4 3 2 1 Şekil 4.36. 1-genli çizim Dikkat edilirse tüm bu graflar aynı derece dizisine ve dolayısıyla da aynı omega değerine sahiptirler ve sadece bunlardan Şekil 4.29’daki temel çizim kuralına uygun olan çizimdir. 4.2.2.11. Teorem göre (𝐷) = 0 olan bir 𝐷 derece dizisi bağlantılı bir graf olarak çizilebiliyorsa bu çizim tek bir devire sahiptir. Eğer bu devirin uzunluğu en az 3 olarak alınırsa bu çizim kiriş, katlı kenar veya döngü içeremez. Eğer bu devirin uzunluğu 2 ise, bu çizim döngü ve kiriş içeremez, sadece bir çift katlı kenara sahip olur. Eğer bu devirin uzunluğu 1 ise, bu çizim katlı kenarlar ve kiriş içeremez, sadece bir döngüye sahip olur. Yukarıda zaman zaman derece dizisinde bulunan 2’lerin derece dizisinin çizilebilirliğini etkilemediği belirtildi. Aynı zamanda çizilebilir bir derece dizisinde bulunan 2’lerin de bu derece dizisinin çizimlerinin sahip olduğu özellikleri etkilemediği bilinir. Örneğin (𝐷) = 0 olan bir derece dizisinin bağlantılı çizimlerinin tümü tek devire sahiptir ve bu derece dizisine eklenecek veya silinecek 2’lerin bu çizimlerin tek devire sahip olmasına bir etkileri olmaz. Bu nedenle 4.2.2.11. Teorem yerine 𝑎2 = 0 alarak aşağıdaki sonuç da verilebilir: 4.2.2.13. Sonuç. 𝐺, 𝐷 = {1(𝑎1), 3(𝑎3), 4(𝑎4), … ,△(𝑎△)} derece dizisine sahip bağlantılı bir graf olsun. 𝑎1 > 0 ve 𝑖 = 3, 4, … , △ için 𝑎𝑖 ≥ 0 olsun. Eğer (𝐷) = 0 ise 𝐺 grafı potansiyel bağlantılıdır ve en az bir devire sahiptir. Bağlantılı olma durumunda bu çizim tek devire sahiptir ve bu tek devirin uzunluğu 1 ile 𝑎3 + ⋯ + 𝑎△ arasındaki herhangi bir sayı olabilir. Bağlantısız olma durumunda ise en az iki devir mevcuttur. Buraya kadar olan kısımda zaman zaman potansiyel bağlantılılıktan bahsedildi. Bu kavramla ilgili aşağıdaki test, Edmonds (1964)’de verilmiştir: 62 4.2.2.14. Lemma. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} bir derece dizisi olsun. 𝐷’nin potansiyel bağlantılı olması için gerek ve yeter şart ∑𝑛𝑖=1 𝑑𝑖 ≥ 2(𝑛 − 1) olmasıdır. Bu test, omega yardımıyla da ifade edilebilir: 4.2.2.15. Teorem. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} bir derece dizisi olsun. 𝐷’nin potansiyel bağlantılı olması için gerek ve yeter şart (D) ≥ −2 olmasıdır. İspat. Önceden bilindiği üzere el sıkışma lemması gereği 2𝑚 = ∑𝑛𝑖=1 𝑑𝑖 olduğundan bu eşitlik 4.2.2.14. Lemmada yerine konulursa, 2𝑚 ≥ 2(𝑛 − 1) elde edilir. 3.2.1. Teorem gereği (𝐷) = 2(𝑚 − 𝑛) olur. Dolayısıyla, 2𝑚 − 2𝑛 ≥ −2 2(𝑚 − 𝑛) ≥ −2 (D) ≥ −2 elde edilir. 4.2.2.16. Teorem. 𝐺 bağlantılı bir graf olsun. 𝐺 devire sahiptir  (𝐺) ≥ 0’dır. İspat. 𝐺 devirlidir  r ≥ 1’dir (𝐺)  + 1 ≥ 1’dir 2  (𝐺) ≥ 0’dır. Alternatif olarak bu sonuç başka yoldan da ispat edilebilir: (𝐺) = 2(𝑚 − 𝑛) ve (𝐺) ≥ 0 olduğu kullanılırsa r = 1 + 𝑚 − 𝑛 ≥ 1 sonucuna ulaşılır. Bir 𝐺 grafında döngülerin sayısı ℓ ile, kirişlerin sayısı 𝑐ℎ ile, katlı kenarların sayısı da 𝑚𝑒 ile gösterilsin. Buna göre, 63 4.2.2.17. Teorem. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip olan bir graf ve (𝐷) ≥ 0 olsun. Bu derece dizisinin bağlantılı her bir 𝐺 çizimi için (𝐺) = ℓ + 𝑐ℎ + 𝑚 2 𝑒 dir. İspat. (𝐷) = 0 durumunda elde edilecek olan bağlantılı çizimin kiriş ve döngüye sahip olmadığı 4.2.2.11. Teoremden bilinmektedir. Ayrıca bu durumda 3.2.4. Teorem gereği bölge sayısı 1 olduğundan katlı kenar da bulunmaz. Dolayısıyla sonuç aşikârdır. O halde (𝐷) > 0 durumu incelenmelidir. İlk olarak bir (𝑎2 + 𝑎3 + ⋯ + 𝑎△) −gen çizilir. 𝑎1 tane sallanan kenarı bu devir üzerindeki köşelere 4.2.2.11. Teorem’deki yöntemle eklemek için bu devir üzerindeki 𝑎3 tane derecesi 2 olan köşelere birer tane sallanan kenar, 𝑎4 tane köşeye 2’şer tane sallanan kenar, 𝑎5 tane köşeye 3’er tane sallanan kenar, ve bu şekilde devam edilerek 𝑎△ tane köşeye △ −2’şer tane sallanan kenar eklemeye kalkıldığında elde yeterli sayıda sallanan kenar olmadığı fark edilir. Çünkü (𝐷) > 0 kabul edildiğinden 𝑎1 < 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ olur ve sol taraftaki 𝑎1, eklenebilecek tüm sallanan kenarların sayısını, sağ taraftaki toplam ise eklemeye çalışılan sallanan kenarların toplam sayısını göstermektedir. Bir başka deyişle 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 tane sallanan kenar eklenememiş olur. Bu da devir üzerindeki bazı köşelerin derecelerine ulaşılamayacağı anlamına gelir. Bu dereceleri olmaları gereken hale ulaştırabilmek için kiriş, döngü veya katlı kenarlardan faydalanmak mümkündür. Bir köşeyi 2 derece artırmak için 2 tane sallanan kenar yerine bir döngü de çizilebilir. Ya da bu köşeden derecesi 2 eksik olan bir başka köşeye 2 adet katlı kenar çizilerek de bu gerçekleştirilebilir. Üçüncü bir ihtimal de derecesi eksik olan iki köşe arasına yeterli sayıda kiriş çizmektir. Her bir döngünün, her bir kirişin ve her bir katlı kenarın derece toplamına katkısı 2 olacağından eklenmesi gereken kiriş, döngü ve katlı kenarların toplam sayısı 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 (𝐺) = 2 2 kadardır. 64 Yukarıda da belirtildiği gibi eksik dereceleri tamamlamak için döngü, kiriş ve katlı kenarların hangilerinin kaçar tane kullanılacağının standart bir yolu mevcut değildir. Bu tamamen verilen derece dizisinin ne şekilde çizilmek istendiğiyle ilgilidir. 6. Bölümdeki bir çok problem, bu amaca yöneliktir. 4.2.2.18. Örnek. 𝐷 = {1(3), 3(1), 4(2), 5(2), 6(1) (𝐷) } olsun. Buradan = ℓ + 𝑐ℎ + 𝑚 2 𝑒 = 6 elde edilir, bkz. Şekil 4.37. 𝑒𝑚 𝑐ℎ _ ℓ 𝑐ℎ m 𝑐ℎ_ 𝑒𝑚 _ h _ h m Şekil 4.37. 𝐷’nin derece dizisinin bir temel çizimi ve bir basit çizimi O halde Euler karakteristiği ile ilgili aşağıdaki sonuç verilebilir: 4.2.2.19. Sonuç. Eğer (𝐷) ≥ 0 ise, 𝐷 derece dizisine sahip çizilebilir bir 𝐺 grafının Euler karakteristiği (𝐺) = 𝑟 − ℓ − 𝑐ℎ − 𝑚𝑒 dir. Bu sonuç 3.3.1. Teorem ve 4.2.2.17. Teoremden kolayca elde edilebilir. 4.2.2.20. Örnek. 4.2.2.18. Örnekteki graf için (D) = 𝑟 − ℓ − 𝑐ℎ − 𝑚𝑒 = 7 − 1 − 3 − 2 = 1 eşitliği sağlanır. 65 4.2.2.21. Teorem. 𝐺, (𝐷) ≥ 0 özelliğinde bir 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip olan ve temel çizim formunda çizilebilen basit bir graf olsun. 𝑘 = 𝑎2 + 𝑎3 + ⋯ + 𝑎△ için (𝐷) = (𝐺) ≤ 𝑘(𝑘 − 3) olur. İspat. Hatırlanacağı üzere 𝑘 = 𝑎2 + 𝑎3 + ⋯ + 𝑎△ sayısı, 𝐺 grafının sahip olduğu en uzun devirin uzunluğudur. Ayrıca bir 𝑘 −gende çizilebilecek maksimum kiriş sayısı 𝑘(𝑘−3) olabilir. 4.2.2.17. Teorem gereği 2 (𝐺) = 2(ℓ(𝐺) + 𝑐ℎ(𝐺) + 𝑚𝑒(𝐺)) olduğu bilinmektedir. 𝐺’ nin basit graf olması ℓ(𝐺) = 𝑚𝑒(𝐺) = 0 olduğu anlamına gelir. O halde (𝐺) = 2𝑐ℎ(𝐺) elde edilir. Böylece 𝑘(𝑘 − 3) 𝑐ℎ(𝐺) ≤ 2 ve buradan da (𝐺) 𝑘(𝑘 − 3) ≤ 2 2 sonucuna ulaşılır. 𝑘 = 𝑛 − 𝑎1 değeri yerine yazıldığında (G) (𝑛 − 𝑎1)(𝑛 − 𝑎1 − 3) ≤ 2 2 elde edilir. Dikkat edilirse temel çizim formunda bulunan en uzun devir olan (𝑛 − 𝑎1) −genin maksimum köşegen sayısı, aynı zamanda (𝑛 − 𝑎1) −genin içine çizilebilecek maksimum kiriş sayısının doğal bir üst sınırıdır. 4.2.2.22. Örnek. 4.2.2.18. Örnekteki graf için (G) (9 − 3)(9 − 3 − 3) ≤ 2 2 ve böylece 66 (G) = 12 ≤ 18 elde edilir, bkz. Şekil 4.37. Denk olarak aşağıdaki test verilebilir: 4.2.2.23. Sonuç. Eğer 𝑘 = 𝑎2 + 𝑎3 + ⋯ + 𝑎△ için (𝐷) > 𝑘(𝑘 − 3) ise 𝐷 derece dizisi hiçbir şekilde bir basit graf olarak çizilemez. 4.2.2.24. Örnek. 𝐷 = {1(4), 6(1)} olsun. (𝐷) = 0 > 1(−2) olduğundan (𝐷) > 𝑘(𝑘 − 3) şartı sağlanır ve 𝐷 derece dizisi bir basit graf olarak çizilemez, bkz. Şekil 4.38. Şekil 4.38. Basit graf olamayan 𝐷 = {1(4), 6(1)} derece dizisinin bir çizimi İkinci olarak 𝐷 = {1(8), 5(1), 6(1), 7(1), 9(2)} derece dizisi için (𝐷) = 18 ve 𝑘 = 5 olduğundan (𝐷) = 18 > 52 olur ve bu durumda yine (𝐷) > 𝑘(𝑘 − 3) şartı sağlanacağından 𝐷 derece dizisi bir basit graf olarak çizilemez, bkz. Şekil 4.39: Şekil 4.39. Basit graf olamayan 𝐷 = {1(8), 5(1), 6(1), 7(1), 9(2)} derece dizisinin bir çizimi 67 4.2.12. Sonuçtan faydalanarak aşağıdaki kullanışlı sonuca ulaşılabilir: 4.2.2.25. Sonuç. 𝑟 ve 𝑘, yukarıdaki gibi olsun. Eğer (𝑘 − 1)(𝑘 − 2) 𝑟 > 2 ise 𝐺 grafı basit graf değildir. İspat. 4.2.2.23. Sonuçta (𝐺) = 2𝑟 − 2 değeri yerine yazılırsa 2r − 2 > 𝑘(𝑘 − 3) iken 𝐺 grafının bir basit graf olamayacağı söylenebilir. Bu eşitsizlik düzenlendiğinde (𝑘 − 1)(𝑘 − 2) 𝑟 > 2 iken 𝐺 grafının bir basit graf olamayacağı bulunur. Denk olarak olmayana ergi yöntemiyle ispatlanabilecek olan şu sonuç verilebilir: 4.2.2.26. Sonuç. 𝑟 ve 𝑘, yukarıdaki gibi olsun. 𝐺 grafı basit graf ise (𝑘 − 1)(𝑘 − 2) 𝑟 ≤ 2 dir. 4.2.2.27. Sonuç. 𝐺, 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip olan ve temel çizim formunda çizilebilen bir basit graf olsun. 𝑘 = 𝑎2 + 𝑎3 + ⋯ + 𝑎△ için 𝑘(𝑘 − 3) 𝑐ℎ(𝐺) ≤ 2 dir. İspat. 4.2.2.17. Teorem gereği (𝐺) = 2(ℓ(𝐺) + 𝑐ℎ(𝐺) + 𝑚𝑒(𝐺)) (𝐺) 𝑐ℎ(𝐺) = − ℓ(𝐺) − 𝑚 (𝐺) 2 𝑒 68 (𝐺) ≤ 2 𝑘(𝑘−3) ≤ 2 elde edilir. 4.3. (𝑫) = −𝟐 durumu 4.3.1. (𝑫) = −𝟐 olma durumunda temel çizim Şimdi de (𝐷) ≥ 0 (ve bir çift sayı) durumuna benzer olarak (𝐷) = −2 durumunda 𝐷 derece dizisinin temel çizimi tanımlanacaktır. Tabii bu yeni durumda elde edilebilecek tüm bağlantılı çizimler devir bulundurmayacağından (𝐷) ≥ 0 durumuyla farklı olan birçok özellik olması beklenebilir. 4.3.1.1. Tanım. (𝐷) = −2 olsun. 𝐷 derece dizisinin 𝑎2 + 𝑎3 + ⋯ + 𝑎△ + 2 uzunluğundaki bir 𝑃𝑎 +𝑎 +⋯+𝑎 +2 = 𝑃𝑛−𝑎 +2 yol grafı üzerindeki derecesi 2 olan 2 3 △ 1 köşelere 𝑎1 − 2 tane sallanan kenar eklenerek elde edilebilen bir çizimine 𝐷 derece dizisinin devir içermeyen bir temel çizimi adı verilir. Burada elde edilen bu temel çizime literatürde tırtıl graf da denilmektedir. (𝐷) = −2 durumunda tanımlanan temel bir çizimin bağlantılı olması ve devir içermemesi gerektiğine dikkat ediniz. 4.3.2. Temel çizim algoritması Şimdi de (𝐷) = −2 durumunda tanımlanan temel çizimin varlığını garantileyen ve bu çizimin nasıl oluşturulacağını gösteren bir algoritma verilecektir: 4.3.2.1. Teorem. (𝐷) = −2 olsun. a) 𝐷 derece dizisinin devir içermeyen en az bir tane temel çizimi mevcuttur. b) Çizimin bağlantılı olması durumunda bu çizim sadece bir ağaç olabilir. c) Çizimin bağlantısız olma durumunda en az bir tane devir içermeyen bileşen ve en az bir tane devir içeren bileşen vardır. Daha net ifade etmek gerekirse, bir tek devir içeren bileşen varsa devir içermeyen bileşenlerin sayısı, çizimdeki bölge sayısına eşittir, yani 69 𝑐𝑎 = 𝑟’dir ve 𝑠 tane devir içeren bileşen varsa devir içermeyen bileşenlerin sayısı 𝑟 − 𝑠 + 1’dir. İspat. a) i. 𝑃𝑎 +𝑎 +⋯+𝑎 +2 yol grafı çizilirse 𝐷 = {1 (2), 2(𝑎2+𝑎3+⋯+𝑎△)} derece dizisine 2 3  sahip bir yol graf elde edilir, bkz. Şekil 4.40. … Şekil 4.40. {1(2), 2(𝑎2+𝑎3+⋯+𝑎)} derece dizisinin yol grafı ii. Elde edilen 𝑃𝑎 +𝑎 +⋯+𝑎 +2 yolu üzerinde derecesi 1 olan köşelere hiçbir işlem 2 3 △ yapılmaz. Derecesi 2 olan köşelere ise, 2 ≤ i ≤△ olmak üzere 𝑎𝑖 tanesine 𝑖 − 2 büyükten küçüğe doğru (sıralamanın önemi yok) tane sallanan kenar eklenir, bkz. Şekil 4.41. 𝑎2 tane 𝑎3 tane 𝑎4 tane 𝑎△ tane … … … … … 1’er tane 2’şer tane △ −2’şer tane Şekil 4.41. Bir tırtıl graf b) Çizim bağlantılı ise sonuç, 3.2.10. Teorem gereği aşikârdır. c) Önceki sonuçlardan kolayca görülür. 4.3.2.2. Örnek. 𝐺, derece dizisi {1(9), 2(2), 3(2), 4(1), 5(1)} olan bağlantılı bir graf olsun. (𝐺) = −2 olduğundan 𝐺 bir ağaçtır. Şekil 4.42’de 𝐺 grafının farklı iki çizimi verilmiştir. Bunlardan sağda kalanı temel çizim formundaki çizim olup soldaki ise bağlantılılık dışında herhangi bir özelliğe sahip olmayan bir çizimdir. 70 𝐺’nin bir temel çizimi 𝐺 Şekil 4.42. {1(9), 2(2), 3(2), 4(1), 5(1)} derece dizisinin herhangi bir çizimi ve bir temel çizimi 4.4. (𝑫) ≤ −𝟒 durumu 4.4.1. (𝑫) ≤ −𝟒 olma durumunda temel çizim Son olarak (𝐷) ≤ −4 (ve bir çift sayı) olması durumunda ilk iki duruma benzer şekilde bir temel çizim tanımlamak istenecek olursa ilk iki durumdaki temel çizim tanımlarına bakıldığında her iki çizimin de bağlantılı olarak tanımlandığına dikkat ediniz. (𝐷) ≤ −4 durumunda tanımlanacak olan temel çizim için farklı bir durum söz konusudur. Hatırlanacağı gibi 3.2.11. Teorem gereği (𝐷) ≤ −4 olduğunda 𝐷 derece dizisinin tüm çizimlerinin kesinlikle bağlantısız olduğu ispatlanmıştı. Bu nedenle burada tanımlanacak olan temel çizimin de bağlantısız olması mecburiyeti vardır. 4.4.1.1.Tanım. 𝐺, (𝐷) ≤ −4 özelliğinde bir 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisine sahip bir graf olsun. 𝐷 derece dizisinin −(𝐷)/2 tane 𝐾2 tam grafı şeklindeki bileşenden ve 4.2.1.1. Tanımda verilen devirli temel forma sahip ancak kiriş, döngü ve katlı kenar bulundurmayan (dolayısıyla omega değeri sıfır olan ve 𝑎2 + 𝑎3 + 𝑎4 + … + 𝑎△ uzunluklu bir tek devir içeren) bir bileşenden oluşan çizimine karma temel çizim (mixed type fundamental form) adı verilir. Burada devirli temel forma sahip bileşene ana bileşen adı verilir ve sadece ana bileşenin özel bazı durumlarda bir döngü veya katlı kenar olmasına müsaade edilir. Burada 𝑎2, 𝑎3, 𝑎4, … , 𝑎△ sayılarından en az birisinin pozitif olması durumunda ana bileşen tanımda belirtilen özelliklere sahip bir devir bulundurur. Aslında ana bileşen 4.4.1.1. Tanımda olduğu gibi bir devire sahip olarak çizilebileceği gibi devirsiz bir şekilde de çizilebilir. Özel olarak tüm 𝑎2, 𝑎3, 𝑎4, … , 𝑎△ sayıları sıfır ise derece dizisi 𝐷 = {1 (𝑎1)} 71 şeklinde olacağından devirli bir ana bileşene sahip olamaz. Sadece 𝐾2’lerden oluşur. Temel çizimin ve bu çizimdeki ana bileşenin, hedeflenen özellik ya da özelliklere göre değişik şekiller alabileceğine dikkat ediniz. Bu nedenle belli bir niteliğe sahip olan temel çizimi adlandırırken o niteliğe sahip temel çizim olduğunu belirtmekte fayda vardır. Şimdi bu durum örneklerle incelenecektir: 4.4.1.2. Örnek. 𝐷 = {1(6)} bir derece dizisi olsun. O halde (𝐷) = −6 olur. Buna göre 𝐷’nin tek olası çizimi üç bileşene sahip olan aşağıdaki çizimdir, bkz. Şekil 4.43. 3 tane 𝐾2 Şekil 4.43. 𝐷 = {1(6)} bağlantısız grafı Derece dizisinde izole köşelere karşılık gelen sıfırların olması durumunda temel çizimi elde etmek için 4.4.1.1. Tanımda verilen temel çizime sıfırların sayısı (𝑎0) kadar izole köşe eklemek yeterli olur. 4.4.1.3. Örnek. 𝐷 = {1(16), 6(3)} ise (𝐷) = −4 olur. 𝐷 derece dizisine ait, en uzun devir içeren karma bir temel çizim aşağıda verilmiştir, bkz. Şekil 4.44. En büyük devire sahip 2 tane 𝐾2 olan ana bileşen Şekil 4.44. 𝐷 derece dizisinin bir karma temel çizimi 72 Aynı 𝐷 derece dizisine sahip devir içeren başka bir çizim aşağıda verilmiştir. Bu çizim, en uzun devirinin uzunluğu 2 olup bu derece dizisinin sahip olabileceği maksimum devir uzunluğu olan 𝑎2 + 𝑎3 + 𝑎4 + … + 𝑎△ = 3’den az olduğundan bir temel çizim değildir, bkz. Şekil 4.45. 2-gen devirli ana bileşen 4 tane 𝐾2 Şekil 4.45. 𝐷 derece dizisinin 2 −gen ana devirli bir çizimi Aynı 𝐷 derece dizisine sahip devir içeren üçüncü bir çizim de, bkz. Şekil 4.46, 1 −gen devirli 6 tane 𝐾2 ana bileşen Şekil 4.46. 𝐷 derece dizisinin 1 −gen ana devirli bir çizimi şeklindedir ve aynı sebepten bu da bir temel çizim değildir. Bu 𝐷 derece dizisine sahip devir içermeyen başka bir çizim aşağıda verilmiştir, bkz. Şekil 4.47. 73 Devir içermeyen ana bileşen 1 tane 𝐾2 Şekil 4.47. 𝐷 derece dizisinin devir içermeyen ana bileşenli bir çizimi Son olarak 𝐷 derece dizisine ait, devir içeren ve hiçbir 𝐾2 bileşeni olmayan başka bir çizim de aşağıda verilmiştir, bkz. Şekil 4.48. 1 −gen devirli ana bileşen Devir içermeyen bileşenler Şekil 4.48. 𝐾2 bileşeni olmayan bir herhangi bir çizim Bu örneklerden görüleceği gibi bir karma temel çizimde devir içermeyen her bir bileşenin, her zaman bir 𝐾2 tam grafı olması gerekirken diğer çizimlerde bu bileşenler birer 𝐾2 tam grafı veya birer ağaç olabilir. Bu kısımda (𝐷) ≤ −4 olan derece dizileriyle çalışılıyor olunsa da aşağıdaki sonuç, (𝐷) = −2 olan derece dizilerini de kapsadığından (𝐷) ≤ −2 şartına bağlı olarak ifade edilmiştir. 4.4.1.4. Sonuç. 𝐷, (𝐷) ≤ −2 çift bir sayı olacak şekilde bir derece dizisi olsun. 𝐷 derece dizisinin en az bileşene sahip çizimi 4.3.2.1. Teoremde oluşturulan tırtıl grafı şeklindeki bir bileşenle her biri birer 𝐾2 tam grafı olan (−2 − (𝐷))/2 tane devir içermeyen bileşenden oluşur. Buradaki çizime devirsiz ana bileşenli bir temel çizim adı verilir. 74 4.4.1.5. Sonuç. (𝐷) ≤ −2 çift bir sayı olacak şekilde bir derece dizisi olsun. 𝐷 derece dizisinin en az bileşene sahip çizimi −(𝐷)/2 tane bileşene sahiptir ve bu bileşenlerin tümü devir içermeyen bileşenlerdir. 4.4.1.6. Örnek. 𝐷 = {1(16), 6(3)} için (𝐷) = −4 olur. 𝐷 derece dizisinin en az bileşene sahip çizimi elde edilmek istendiğinde tüm bileşenlerin devir içermeyen graflar olması gerekir ve bu durumda 4.4.1.4. Sonuç gereği bu bileşenlerden birisi tırtıl grafı şeklinde olup diğerleri 𝐾2 tam graflarıdır, bkz. Şekil 4.49. Devir içermeyen ana bileşen 1 tane 𝐾2 Şekil 4.49. 𝐷 derece dizisinin bir çizimi −(𝐷) −(−4) Gerçekten de bu çizim = = 2 adet devir içermeyen bileşene sahiptir. 2 2 4.4.2. Temel çizim algoritması Buraya kadar olan kısımda temel çizim yaparken, hedeflenen özelliklere uygun olan temel çizimi oluşturmanın mümkün olduğu gösterildi. Bu kısımda (𝐷) ≤ −4 halinde elde edilebilecek iki temel çizim verilecektir. Bu çizimlerin hedeflenen özelliği ana bileşenin maksimum sayıda döngüye sahip olması ve ana bileşenin maksimum sayıda sallanan kenara sahip olmasıdır. Bu iki temel çizim tercihi sırayla incelenecektir: İlk olarak ana bileşenin maksimum sayıda döngüye sahip olması durumu ele alınsın. i. 𝐶𝑎 +𝑎 +⋯+𝑎 = 𝐶𝑛−𝑎 çizilir. 2 3  1 ii. Tek dereceli olan köşelere birer tane sallanan kenar çizilir. Burada kiriş sayısını minimum sayıda tutacak şekilde bir yöntem izlenmelidir. Bunun yerine farklı tercihler de yapılabilir. Sonrasında bu tek dereceli köşelerin her 𝑖−3 birine, 𝑘 ∈ ℤ+ için 𝑖 = 2𝑘 + 1 olmak üzere tane döngü çizilir. 2 75 𝑖−2 iii. Çift dereceli olan köşelerin her birine, 𝑘 ∈ ℤ+ için 𝑖 = 2𝑘 olmak üzere 2 tane döngü çizilir. Böylelikle karma temel çizimin devir kısmı çizilmiş oldu. Şimdi diğer bileşenler + 𝑎1−∑ 𝑎𝑘=1 2𝑘+1çizilmelidir. 𝑖 = 2𝑘 + 1, 𝑘 ∈ ℤ , olmak üzere tane 𝐾 çizilir. Böylece 2 2 karma temel çizim formunun ağaçlardan oluşan kısmı da çizilmiş oldu ve şekil tamamlanmış oldu. 4.4.2.1. Örnek. 𝐷 = {1(46), 2(1), 3(3), 5(2), 9(3), 10(1)} derece dizisi olsun. (D) = −8 ≤ −4 olduğundan, 𝐷 derece dizisine sahip olan bu graf bağlantısız olmak zorundadır. O halde uzunluğu maksimum olan bir tane devir içeren ana bileşen ile 𝐾2’lerden oluşmaktadır, bkz. Şekil 4.50. Gerçekten de, … 19 tane 𝐾2 times Şekil 4.50. Karma bir temel çizim formu (ana bileşeni maksimum döngülü) İkinci olarak ana bileşenin maksimum sayıda sallanan kenara sahip olması durumu ele alınacaktır. i. (𝑎2 + 𝑎3 + ⋯ + 𝑎△) −gen çizilir. ii. Bir devir oluşturulduğu için deviri oluşturan her köşenin derecesi 2 olduğundan 𝑎2 tane derecesi 2 olan köşe ayırılır ve bunlara hiçbir işlem yapılmaz. iii. Derecesi 3 olan köşeleri elde etmek için 𝑎3 tane köşenin her birine birer sallanan kenar eklenir. Derecesi 4 olan köşeleri elde etmek için 𝑎4 tane köşenin her birine 2’şer tane sallanan kenar eklenir. Derecesi 5 olan köşeleri elde etmek için 𝑎5 tane köşenin her birine 3’er tane sallanan kenar eklenir. Bu adımları △’ya kadar devam ettirilirse, derecesi △ olan köşeleri elde etmek için 𝑎△ tane köşenin her birine △ −2’şer tane sallanan kenar 76 eklenir. Böylelikle 𝐶(𝑎 +𝑎 +⋯+𝑎 ) ile gösterilecek olan 𝑎2 + 𝑎3 + ⋯ + 𝑎△ uzunluklu 2 3 △ devire eklenen sallanan kenarların toplam sayısı 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ olur. 𝑎1−(𝑎3 + 2𝑎4+3𝑎5+⋯+(△ −2)𝑎△) iv. Ana devirin yanına tane 𝐾2 çizilir. 2 Böylelikle (𝐷) ≤ −4 durumuna sahip tüm derece dizileri için ikinci bir karma temel çizimin algoritması verilmiş oldu. 4.4.2.2. Örnek. 𝐷 = {1(45), 2(1), 3(2), 5(2), 8(1), 9(3)} derece dizisi olsun. (𝐷) = −10 ≤ −4 olduğundan, 𝐷 derece dizisine sahip olan her bir graf bağlantısız olmak zorundadır. O halde karma temel çizim formunda çizildiğinde bir tane maksimum uzunluklu devir içeren ana bileşenden ve 𝐾2’lerden oluşacaktır, bkz. Şekil 4.51. Gerçekten de, 5 tane 𝐾2 Şekil 4.51. Karma bir temel çizim (ana bileşeni maksimum sallanan kenarlı) elde edilir. 77 5. KENAR VE KÖŞE SİLMENİN OMEGA ÜZERİNDEKİ ETKİSİ 5.1. Giriş Küçük olan objeler üzerinde yapılan çalışmaların daha büyük objeler hakkında fikirler vermesi matematikte sıkça kullanılan metotlardandır. Bu düşünceden hareketle bu bölümde kenar silme ve köşe silme işlemlerinin omega üzerindeki etkileri incenecektir. 1.1.22 ve 1.1.23.Tanımlarda bir 𝐺 grafından köşe ve kenar silinmesi (çıkarılması) işlemleri tanımlanmıştı. Bu bölümün ana amacı bu işlemlerin etkisini araştırmak olduğundan bu kavramları kısaca hatırlatmakta fayda vardır: 𝐺’nin bazı köşeleri 𝑢, 𝑢1, 𝑢2, … , 𝑢𝑘 ve bazı kenarları da 𝑒, 𝑒1, 𝑒2, … , 𝑒𝑡 olsun. Hatırlanacağı gibi bir 𝐺 grafından bir 𝑢 köşesi silindiğinde bu köşeye bitişik tüm kenarlar da silinmekteydi. Bu işlemin sonucunda elde edilen graf 𝐺 − 𝑢 ile gösterilmişti. Benzer şekilde bir 𝐺 grafından 𝑢1, 𝑢2, … , 𝑢𝑘 köşeleri ve bunlara bitişik tüm kenarlar silindiğinde elde edilen graf da 𝐺 − {𝑢1, 𝑢2, … , 𝑢𝑘} ile gösterilmişti. Bir 𝐺 grafından bir 𝑒 kenarı silindiğinde bu işlemin 𝐺 − 𝑒 ile; 𝑒1, 𝑒2, … , 𝑒𝑡 kenarları silindiğinde de 𝐺 − {𝑒1, 𝑒2, … , 𝑒𝑡} ile gösterildiğini hatırlayınız. Bu işlemlere köşe ve kenar silme (çıkarma) işlemleri denilir. 𝐺 grafına ait derece dizisinin elemanlarının, 𝐺’nin köşe dereceleri olan ve negatif olmayan tam sayıların azalmayan bir şekilde sıralanışları olarak tanımlandığını hatırlayınız. 𝐺 grafından kenar ve köşe silindiğinde (çıkarıldığında) grafın bağlantısız hale dönüşebileceği ve elde edilen yeni grafın bazı bileşenlerinin izole köşeler olabileceği açıktır. İzole köşeler hiç bir kenara bitişik olmadıklarından derece dizisi tanımını biraz daha genişletmek gerekir. Bir izole köşenin derecesi sıfırdır. Örneğin 𝑁𝑛 sıfır grafının tüm köşeleri izoledir, yani hiçbir kenara bitişik değildir. Ya da bir sallanan kenar silindiğinde, bu kenarın bağlı olduğu köşe yine 𝐺 grafına aittir, fakat izole bir köşe olarak kalır. Bu nedenle birçok grafta izole edilmiş köşelerle karşılaşılabilir. Eğer bu köşelerin omegaya etkisi olmasaydı bu köşeler kolayca göz ardı edilebilirdi. Her bir izole köşenin omega değeri −2 olduğundan izole köşeler aynı zamanda birer ağaç olarak da düşünülebilir. 78 5.1.1. Lemma. 𝐺 = {𝑣} grafı herhangi bir kenarı olmayan sadece bir köşeye sahip bir graf olsun. (𝐺) = ({𝑣} ) = −2 dir. İspat. 1.1.14.Tanımdan dolayı bir izole köşenin derece dizisi {0(1)} olarak gösterilir. Yani 𝐷(𝐺) = 𝐷({𝑣}) = {0(1)} (1) olur ve  ({0 } ) = −2 olduğu görülür. Hatırlanacağı üzere bağlantılı bir graf için (𝐺) = −2 ise bu grafın bir ağaç olduğu, yani hiçbir devir bulundurmadığı gösterilmişti. Bu nedenle izole köşelerin her biri bir ağaçtır denilebilir. Bu genelleme sonrasında bir derece dizisinin en genel hali verilecek olunursa 𝐷 = {0(𝑎0), 1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} yazılabilir. 𝐺 grafının omega değeri ise 𝑎0 da katılarak (𝐺) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯ + (△ −2)𝑎△ − 𝑎1 − 2𝑎0 △ = ∑(𝑖 − 2) 𝑎𝑖 𝑖=0 olarak ifade edilir. Bu tanımlamanın daha önce verilen ve 𝑎0 içermeyen omega tanımıyla uyumlu olduğuna dikkat ediniz. 𝑎0 > 0 olduğunda en az bir izole köşe mevcut olacağından 𝐺 grafının bağlantılı olamayacağı açıktır. Bu nedenle bağlantılı graflarla çalışılırken, derece dizisinde sıfırlara ihtiyaç duyulmaz. Birçok makalede derece dizilerinin tanımında sıfırın yazılmamasının nedeni budur. 5.1.2. Örnek. 𝐷 = {0(1), 1(8), 4(2)} derece dizisi verilsin. (𝐷) = −6 olarak hesaplanır. Bu derece dizisinin çok sayıda çiziminden dördü Şekil 5.1’de verilmiştir. Tüm bu çizimlerin ortak özelliği birer izole köşe bulundurmaları ve dolayısıyla bağlantısız olmalarıdır. Bu durum (𝐷) = −6 olduğundan (𝐷) ≤ −4 olması durumunda grafın bağlantısız oluşuyla da uyumludur. 79 G G 1 2 G G 3 4 Şekil 5.1. İzole köşe bulunduran bazı graflar 5.2. Kenar silmenin omega değerine etkisi 5.2.1. Tanım. 𝐺 bir graf ve 𝑡 ≤ 𝑚 için 𝑒1, 𝑒2, … , 𝑒𝑡 ∈ 𝐸(𝐺) olsun. 𝐺 grafından bir 𝑒𝑖 kenarının silinmesi sonucunda ’da oluşan değişim △ (𝐺, 𝑒𝑖) = (𝐺) − (𝐺 − 𝑒𝑖) ile; 𝐺 grafından 𝑒1, 𝑒2, … , 𝑒𝑡 kenarlarının silinmesi sonucunda ’da oluşan değişim ise △ (𝐺, 𝑒1, 𝑒2, … , 𝑒𝑡) = (𝐺) − (𝐺 − {𝑒1, 𝑒2, … , 𝑒𝑡}) ile gösterilecektir. Aşağıdaki sonuçta bir graftan kenar(lar) silmenin omega değerine etkisi ele alınacaktır: 5.2.2. Teorem. 𝐺 bir graf olsun. 𝐺 grafından bir kenarın silinmesi (𝐺) değerini 2 azaltır. Birinci ispat. 𝑒 = 𝑢𝑣, 𝐺 grafının bir kenarı olsun ve 𝑑𝑢 ve 𝑑𝑣, sırasıyla 𝑢 ve 𝑣 köşelerinin dereceleri olsun. 𝑒 kenarı silindiğinde 𝐷(𝐺)’deki 𝑑𝑢 ve 𝑑𝑣 sayıları birer tane azalır ve 𝑑𝑢 − 1 ve 𝑑𝑣 − 1 sayıları da birer tane artar. Bu nedenle (𝐺) değeri 2 azalır. İkinci ispat. 𝐷, çizilebilir bir derece dizisi ise omega değerinin (𝐷) = 2(𝑚 − 𝑛) olduğu bilinmektedir. Özel olarak 𝐷 derece dizisine ait graftan bir kenar silindiğinde yeni derecce dizisi 𝐷′ ise (𝐷′) = 2(𝑚 − 1 − 𝑛) (𝐷′) = 2(𝑚 − 𝑛) − 2 80 olur. Böylelikle omega değeri, △= (𝐷) − (𝐷′) = 2 kadar azalmış olur. Daha genel olarak ifade edilirse, 𝑚 kenar sayısına sahip bir graftan 0 ≤ 𝑒 ≤ 𝑚 olmak üzere 𝑒 tane kenar silindiğinde yeni derece dizisi 𝐷′ ve bu derece dizisine ait omega değeri de (𝐷′) olur. Böylece (𝐷′) = 2(𝑚 − 𝑒 − 𝑛) (𝐷′) = 2(𝑚 − 𝑛) − 2 𝑒 olur. Böylelikle omega değeri △= (𝐷) − (𝐷′) = 2𝑒 kadar azalmış olur. Burada silinen kenarın bir döngü, sallanan kenar, köprü, vs. olmasının hiçbir farkı yoktur. Silinen her bir kenara karşı omega 2 azalır. Hatta silinen kenarların komşu olmasının da bir önemi yoktur. Ancak aşağıda köşe silme konusunu incelerken komşu köşeleri silmeyle komşu olmayan köşeleri silmenin farklı etkileri olduğu görülecektir. 5.2.3. Örnek. 𝐷 = {1(3), 3(1), 4(2), 5(2), 6(1)} olsun. 𝐺 de bu derece dizisine ait graf olsun. O halde (𝐺) = 12 olur. Bu derece dizisine ait grafdaki 𝑒 kenarı silindiğinde, yeni derece dizisi 𝐷′ = {1(3), 2(1), 4(3), 5(1), 6(1)} ′ elde edilir.  (𝐺 ) = 10 olur, bkz. Şekil 5.2. 𝑒 _ h 𝐺 𝐺′ _ _ h Şekil 5.2. Graftan bir kenar silme h (𝐺) − 𝐺′Görüldüğü gibi gerçekten de   ( ) = 2 olmaktadır. 81 5.2.2. Teorem, silinen kenarın bir döngü olması durumunda da geçerlidir: 5.2.4. Sonuç. 𝐺 bir graf olsun. 𝐺 grafından bir döngü silmek (𝐺) değerini 2 azaltır. İspat. 𝐿, 𝐺 grafında bir döngü olsun ve bu döngünün sahip olduğu tek 𝑢 köşesinin derecesi 𝑑 olsun. 𝐿 döngüsünü silmek, 𝐷(𝐺)’deki 𝑑’lerin sayısını 1 azaltır ve 𝐷(𝐺)’deki 𝑑 − 2’lerin sayısını da 1 arttırır. Sonuç olarak (𝐺) değeri 2 azalır. 5.2.5. Örnek. 𝐷 = {1(3), 3(1), 4(2), 5(2), 6(1)}, 𝐺 grafı da bu derece dizisine sahip bir graf olsun. O halde (𝐺) = 12 olur. Şekil 5.3’deki graftan 𝐿 döngüsünün silinmesiyle elde edilen graf 𝐺′ olsun. Bu durumda yeni derece dizisi 𝐷′ = {1(3), 3(1), 4(3), 5(2)} olarak ′ ′ elde edilir ve  (𝐺 ) = 10 olur. Görüldüğü gibi gerçekten de (𝐺) −  (𝐺 ) = 2 olur. 𝐿 _m _m ′ 𝐺 𝐺 Şekil 5.3. Graftan bir döngü silme 5.2.6. Örnek. (𝐷) = 18 olan 𝐷 = {1(3), 2(1), 3(4), 4(2), 5(1), 7(2)} ye ait graf Şekil 5.4’deki gibi olsun. 𝑢1 𝐿2 𝑢3 1 𝐿 _1 1 𝑢6 𝑢4 𝑢2 _ _2 _3 𝑢5 4 _3 _1 _4 Şekil 5.4. Bağlantılı bir g_r2af 82 i. 𝑒1 = 𝑢1𝑢4 kenarı silinsin. Bu durumda yeni derece dizisi 𝐷 ′ = {1(3), 2(2), 3(4), 4(1), 5(1), 7(2)} (𝐷′ olduğundan  ) = 16 olarak hesaplanır. 𝐺 grafından 𝑒 = 1 tane kenarı silmek omega değerini △ (𝐺, 𝑢1𝑢4) = 2(1) = 2 kadar azaltır. Gerçekten de △ (G, 𝑢 𝑢 ′1 4) = (𝐷) − (𝐷 ) = 18 − 16 = 2 olduğu görülür, bkz. Şekil 5.5. 𝑢1 𝐿2 𝑢3 _ 1 _ 𝐿1 1 _ 𝑢6 𝑢4 𝑢2 1 _4 _ _3 𝑢5 2 _2 _1 _4 _2 Şekil 5.5. Verilen derece dizisine sahip graftan bir kenar silme ii. 𝑒1 = 𝑢2𝑢4 ve 𝑒2 = 𝑢4𝑢6 kenarları silinsin. Bu durumda yeni derece dizisi 𝐷′ = {1(3), 2(4), 3(2), 4(1), 5(1), 7(2)} ′ olduğundan  (𝐷 ) = 14 olarak bulunur. 𝐺 grafından 𝑒 = 2 tane kenarı silindiğinden dolayı omega değerindeki azalma △ (𝐺, {𝑢1𝑢4,𝑢4𝑢6}) = 2. (2) = 4 olur. Gerçekten de △ (𝐺, {𝑢1𝑢4,𝑢4𝑢6}) = (𝐷) − (𝐷′) = 18 − 14 = 4 olduğu görülür, bkz. Şekil 5.6. 𝑢1 𝐿2 𝑢3 _1 𝐿1 _ 1 _1 𝑢6 𝑢4 𝑢2 _ _2 _3 𝑢5 4 _3 _1 _4 Şekil 5.6. Verilen derece dizisine sahip graf_ta2n iki kenar silm 83 iii. Şimdi de 𝑒1 = 𝐿1 ve 𝑒2 = 𝐿2 döngüleri silinsin. Bu durumda yeni derece dizisi 𝐷′ = {1(3), 2(1), 3(4), 4(2), 5(3)} ′ olduğundan  (𝐷 ) = 14 olarak hesaplanır. 𝐺 grafından 𝑒 = 2 tane döngü olan kenar silindiğinden dolayı omega değeri △ (𝐺, {𝑒1, 𝑒2}) = 2(2) = 4 kadar azalır. Gerçekten de bu durumda da △ (𝐺, {𝑒1, 𝑒2}) = (𝐷) − (𝐷 ′) = 18 − 14 = 4 olduğu görülür, bkz. Şekil 5.7. 𝑢1 𝑢3 _ 1 𝑢6 𝑢4 𝑢2 _ _ _ 𝑢5 4 2 3 _ 4 Şekil 5.7. Graftan iki tane döngü silmek 5.2.7. Teorem. Bir 𝐺 grafı üzerindeki bir köşeye ağaç eklemek (𝐺) değerini değiştirmez. Birinci ispat. Bir 𝐺 grafı üzerindeki bir köşeye herhangi büyüklükte bir ağaç eklemek, 𝐺 grafının bölge sayısını yani r(𝐺)’yi değiştirmez. Böylece c(𝐺), 𝐺 grafındaki bileşenlerin sayısı olmak üzere (𝐺) = 2(r(𝐺) − c(𝐺)) sayısı değişmez. İkinci ispat. (𝐺) = 2(𝑚 − 𝑛) olduğunu hatırlayınız. Her ne kadar ağaç graflarda köşe sayısı kenar sayısından her zaman 1 fazla olsa da, buradaki eklemede var olan grafın herhangi bir köşesine bir ağaç eklendiğinden ve eklenen köşe, zaten 𝐺 grafında mevcut olduğundan grafa ağaç eklenirken eşit sayıda köşe ve kenar eklenmiş olur. Bundan dolayı omega değerindeki 2(𝑚 − 𝑛) değeri değişmeyecektir. Netice itibariyle bir grafın üzerindeki herhangi bir köşeye ağaç eklemek omega değerini değiştirmez. 5.2.8. Örnek. 𝐷 = {1(3), 3(1), 4(2), 5(2), 6(1)} ve 𝐺, bu derece dizisine sahip bir graf olsun. O halde (𝐺) = 12 olur, bkz. Şekil 5.8. 84 𝐺 𝐺 ′ _ _ h hŞekil 5.8. 𝐺 grafına bir ağaç eklemek 𝐷 derece dizisine sahip 𝐺 grafındaki bir köşeye şekildeki gibi bir ağaç eklendiğinde yeni derece dizisi 𝐷′ = {1(8), 4(5), 5(2), 6(1)} haline gelir. Bu derece dizisine sahip grafa 𝐺′ ′ denilirse  (𝐺 ) = 12 bulunur ve böylece omega değerinin değişmediği görülür. 5.2.2. Teorem, 5.2.4. Sonuç ve 5.2.7. Teorem gereği karmaşık bir grafın omega değerini hesaplamak için bu graftan tüm sallanan kenarlar ve bunun sonucu olarak grafa bir kopma noktası veya köprü ile bağlı olan tüm patikalar, yıldız graflar ve ağaçlar silinir ve elde edilen bu daha küçük grafın omega değeri ilkine göre silinen kenar sayısının iki katı kadar azalmış olur. Yani problem çok daha küçük bir grafın ya da grafların omegalarını hesaplama problemine indirgenmiş olur. Bu sonuçların bir başka uygulama alanı da bilinen graf sınıflarına yakın bir çizime sahip olan grafların omega değerlerinin hesaplanmasıdır. Örneğin bir 𝐾6 tam grafından iki kenarı eksik olan bir graf verildiğinde bu grafın omegasını bulmak için çok iyi bilinen (𝐾6) = 63 = 18 sayısından 4 çıkararak 14 bulmak yeterlidir. 5.3. Köşe silmenin omega değerine etkisi Bu kısımda verilen bir graftan köşe veya köşeler silmenin omega değerine olan etkisi ele alınacaktır. İzole köşeler silmek yukarıda da açıklandığı gibi omega değerini sadece 2 düşürdüğünden sildiğimiz köşelerin derecelerinin en az 1 olduğunu varsayabiliriz. 5.3.1. Tanım. 𝐺 bir graf ve 𝑘 ≤ 𝑛 için 𝑣1, 𝑣2, … , 𝑣𝑘 ∈ 𝑉(𝐺) olsun. 𝐺 grafından bir 𝑣𝑖 köşesinin silinmesi sonucunda ’da oluşan değişim 85 △ (𝐺, 𝑣𝑖) = (𝐺) − (𝐺 − 𝑣𝑖) ile; 𝐺 grafından 𝑣1, 𝑣2, … , 𝑣𝑘 köşelerinin silinmesi sonucunda ’da oluşan değişim ise △ (𝐺, 𝑣1, 𝑣2, … , 𝑣𝑘) = (𝐺) − (𝐺 − {𝑣1, 𝑣2, … , 𝑣𝑘}) ile gösterilir. 5.3.2. Teorem. 𝑣, 𝐺 grafında ℓ ≥ 0 tane döngüye bitişik olan 𝑑𝑣 = 𝑘 dereceli bir köşe olsun. 𝑣 köşesini silmenin omega değerine olan etkisi △ (𝐺, 𝑣) = 2(𝑘 − ℓ − 1) kadardır. İspat. 𝐺, 𝑣 ∈ 𝐺 köşesinde döngüler bulunduran bir graf olsun, bkz. Şekil 5.9. e 1 e 𝑣 2 𝑣1 𝑣2 𝑣k−2ℓ 𝑒ℓ G- 𝑣 Şekil 5.9. Aynı köşede ℓ tane döngüye sahip bir 𝐺 grafı 𝑣 köşesinin ve 𝑣1, 𝑣2, … , 𝑣𝑘−2ℓ komşularının omega değerine olan katkısı 𝑑𝑣 − 2 + 𝑑𝑣 − 2 + ⋯ + 𝑑𝑣 − 2 + 𝑑𝑣 − 2 1 2 k−2ℓ olur. Şimdi de 𝐺 grafından 𝑣 köşesi silinsin, bkz. Şekil 5.10. 86 𝑣1 𝑣2 𝑣𝑘−2ℓ Şekil 5.10. 𝑣 köşesi silinmiş 𝐺 grafı 𝐺 − 𝑣 grafında 𝑣 köşesinin her bir komşusunun 𝐺’deki derecesi 1 azalacağından, 𝑣 köşesinin komşularının (𝐺 − 𝑣)’ye olan katkısı 𝑑𝑣 − 3 + 𝑑𝑣 − 3 + ⋯ + 𝑑𝑣 − 3 1 2 k−2ℓ olur. Dolayısıyla (𝐺)’de △ (𝐺, 𝑣) = [𝑑𝑣 + 𝑑1 𝑣 + ⋯ + 𝑑2 𝑣 + 𝑘 − 2(𝑘 − 2ℓ + 1)]k−2ℓ − [𝑑𝑣 + 𝑑𝑣 + ⋯ + 𝑑𝑣 − 3(𝑘 − 2ℓ)] 1 2 k−2ℓ = 2(𝑘 − ℓ − 1) kadar azalma olacaktır. 5.3.3. Örnek. 𝐷 = {1(3), 3(1), 4(2), 5(2), 6(1)} olsun. 𝐺 de bu derece dizisine ait graf olsun. (𝐺) = 12 olur, bkz. Şekil 5.11. 𝑣 𝐺 𝐺′ _ _ Şekhil 5.11. Bir graftan döngüye sahip bir köşe shilmek 87 Döngüye sahip olan 𝑣 köşesi 𝐺 grafından silindiğinde yeni derece dizisi, 𝐷′ = {1(3), 2(1), 3(1), 4(3)} için (𝐺′) = 4 elde edilir. △ (𝐺, 𝑣) = 2(𝑘 − ℓ − 1) = 2(6 − 1 − 1) = 8 olur. 5.3.2. Teorem’in aşağıdaki özel durumu, silinen köşede hiçbir döngü olmaması durumundaki değişimi verir: 5.3.4. Teorem. 𝐺, döngüye sahip olmayan bir graf olsun. Derecesi 𝑑𝑣 olan bir 𝑣 ∈ 𝐺 köşesini silmek, (𝐺)’nin 2𝑑𝑣 − 2 kadar azalmasına yol açar. Yani △ (𝐺, 𝑣) = 2𝑑𝑣 − 2 dir. İspat. 𝑘 = 𝑑𝑣 olmak üzere 𝑣 köşesinin komşu köşeleri 𝑣1, 𝑣2, … , 𝑣𝑘 olsun, bkz. Şekil 5.12. v k v 1 v v 2 v 4 v 3 G Şekil 5.12. 𝑣 köşesi ve komşuları 𝐺 grafında 𝑣1, 𝑣2, … , 𝑣𝑘 köşelerinin dereceleri sırasıyla 𝑑1, 𝑑2, … , 𝑑𝑘 olsun. 𝑣 köşesinin ve komşularının 𝐺 grafında omega değerine katkısı 𝑑1 − 2 + 𝑑2 − 2 + ⋯ + 𝑑𝑘 − 2 + 𝑑𝑣 − 2 = 𝑑1 + 𝑑2 + ⋯ + 𝑑𝑘 + 𝑑𝑣 − 2𝑘 − 2 88 kadar; 𝑣 köşesinin komşularının 𝐺 − 𝑣 grafında omega değerine katkısı ise 𝑑1 − 3 + 𝑑2 − 3 + ⋯ + 𝑑𝑘 − 3 = 𝑑1 + 𝑑2 + ⋯ + 𝑑𝑘 − 3𝑘 kadardır. Böylece omega değerindeki azalma △ (𝐺, 𝑣) = (𝐺) − (𝐺 − 𝑣) = 𝑑𝑣 − 2𝑘 − 2 + 3𝑘 = 𝑑𝑣 − 2𝑑𝑣 − 2 + 3𝑑𝑣 = 2𝑑𝑣 − 2 olarak bulunur. 5.3.5. Örnek. 𝐷 = {1(3), 3(1), 4(3), 5(2)} olsun. 𝐺 de bu derece dizisine ait graf olsun. Bu grafdaki 𝑣 köşesi silindiğinde bu köşeye bağlı tüm kenarların da silindiğini hatırlayınız, bkz. Şekil 5.13. 𝑣 𝐺 𝐺′ _ _ h Şekil.5.13 Bir graftan bir köşe silmek h O halde (𝐺) = 10 ′ olur. 𝑣 köşesini sildikten sonra da  (𝐺 ) = 2 elde edilir. (𝐺) − 𝐺′ ( ) = 8 olduğu görülür. Dolayısıyla, △ (𝐺, 𝑣) = 2𝑑𝑣 − 2 = 2.5 − 2 = 8 dir. 89 (𝐺 − {𝑢1, 𝑢2, … , 𝑢𝑘}) değerini hesaplamak için 5.3.2. Teorem ve 5.3.4. Teorem 𝐺 grafına ardarda uygulanmalıdır. Burada tek dikkat edilmesi gereken nokta, bu 𝑘 tane köşenin aynı anda silinmesi istendiğinde bu köşelerin birbirine komşu olmaması gerektiğidir. Aksi halde ilk adımda bir köşe çıkarıldığında bu köşeye bitişik olan kenarlar da çıkarılacağından ikinci adımda derecelerde değişme olacaktır. Aşağıdaki sonuç genel durumla ilgilidir: 5.3.6. Teorem. Bir 𝐺 grafından 𝑢1, 𝑢2, … , 𝑢𝑘 köşelerinin aynı anda silinmesiyle ’da oluşan azalma miktarı △ (𝐺, 𝑢1, 𝑢2, … , 𝑢𝑘); 𝑖 = 1, 2, … , 𝑘 için 𝐺 grafından bir 𝑢𝑖 köşesi silindiğinde ’da oluşan azalma miktarı da △ (𝐺, 𝑢𝑖) olsun. Ayrıca 𝑢1, 𝑢2, … , 𝑢𝑘 köşelerinin silinmesi sırasında silinen ve bu köşelerden herhangi ikisine aynı anda bitişik olan kenarların sayısı  olsun. Bu durumda k G,u1,u2 ,,uk   (G,i)  2 i1 dır. Yani 𝐺 grafından 𝑢1, 𝑢2, … , 𝑢𝑘 köşelerinin aynı anda silinmesiyle ’da oluşan azalma miktarı bulunmak istendiğinde 𝐺 grafından 𝑖 = 1, 2, … , 𝑘 için 𝑢𝑖 köşesi silindiğinde ’da oluşan azalma miktarlarını ayrı ayrı hesaplayıp toplamak ve elde edilen bu toplamdan silinen iki komşu köşeye bitişik olan tüm kenarların sayısını çıkarmak yeterli olacaktır. İspat. İspat iki köşe için yapılacaktır. İspat, tümevarımla sonlu köşeye genelleştirilebilir. 𝑢 ve 𝑣, komşu iki köşe olsun. 𝑢 köşesi silindiğinde 𝑢𝑣 kenarıyla birlikte 𝑑𝑢 − 1 tane daha 𝑢’ya bitişik kenarın da silindiği hatırlanırsa benzer şekilde 𝑣 köşesi silindiğinde 𝑢𝑣 kenarıyla birlikte 𝑑𝑣 − 1 tane daha 𝑣’ye bitişik kenar silinecektir. Her iki köşe birden silindiğinde ise 𝑢𝑣 kenarıyla birlikte 𝑑𝑢 − 1 + 𝑑𝑣 − 1 = 𝑑𝑢 + 𝑑𝑣 − 2 tane daha kenar silinmelidir. Bu da toplam 𝑑𝑢 + 𝑑𝑣 − 1 tane kenarın silinmesi gerektiğini gösterir. 5.2.2. Teorem gereği bir kenar silmenin, grafın  değerini 2 azalttığı hatırlanırsa sonuç görülür. Tek tek silme ile toplu silme arasındaki farkı iki komşu köşe silerek bir de iki komşu olmayan köşe silerek gösteren bir örnek aşağıda verilmiştir: 5.3.7. Örnek. 𝐷 = {1(3), 2(1), 3(4), 4(2), 5(1), 7(2)} derece dizisi için (𝐷) = 18’dir. Şekil 5.14’deki 𝐺 grafı bu derece dizisine sahip bir graftır: 90 𝑢1 𝑢3 _ 1 𝑢6 𝑢4 𝑢2 _ _ _ 𝑢5 4 2 3 _ 4 Şekil 5.14. 𝐷 = {1(3), 2(1), 3(4), 4(2), 5(1), 7(2)} derece dizisinin bir 𝐺 çizimi Şimdi sırasıyla 𝐺 grafından sadece 𝑢1 köşesini, sadece 𝑢4 köşesini, 𝑢1 ve 𝑢4 komşu köşelerini ve son olarak da 𝑢2 ve 𝑢6 komşu olmayan köşelerini silerek komşu köşeler silmekle komşu olmayan köşeler silmenin farkı örneklenecektir: a) Sadece 𝑢1 köşesi silinirse: 𝑑(𝑢1) = 3 olduğundan, 𝑢1 köşesinin silinmesiyle omega değerinde △ (𝐺, 𝑢1) = 2𝑑𝑢1 − 2 = 2.3 − 2 = 4 kadar azalma olur. Bu durumda yeni derece dizisi 𝐷 = {1(3), 2(2), 3(3), 4(2), 7(2)1 } olduğundan (𝐷1) = 14 olarak hesaplanır. Gerçekten de △ (G, 𝑢1) = (𝐺) − (𝐺 − 𝑢1) = (𝐷) − (𝐷1) = 18 − 14 = 4 olduğu görülür, bkz. Şekil 5.15. 𝑢3 _ 1 𝑢6 𝑢 𝑢4 2 _ _ _ 𝑢5 4 2 3 _ 4 Şekil 5.15. Bir graftan bir köşe silmek 91 b) Sadece 𝑢4 köşesi silinirse: 𝑑(𝑢4) = 4 olduğundan, 𝑢4 köşesinin silinmesiyle omega değerinde △ (𝐺, 𝑢4) = 2𝑑𝑢4 − 2 = 2.4 − 2 = 6 kadar azalma olur. Bu durumda yeni derece dizisi 𝐷 = {1(3), 2(4), 3(1), 4(2), 7(2)4 } olduğundan (𝐷4) = 12 olarak hesaplanır. Gerçekten de △ (G, 𝑢4) = (𝐺) − (𝐺 − 𝑢4) = (𝐷) − (𝐷4) = 18 − 12 = 6 olduğu görülür, bkz. Şekil 5.16. 𝑢1 𝑢3 _ 1 𝑢6 𝑢2 _ _ 𝑢5 1 3 _ 4 Şekil 5.16. Bir graftan bir köşe silmek c) 𝑢1 ve 𝑢4 komşu köşeleri beraber silinirse: △ (𝐺, 𝑢1) = 4 ve △ (𝐺, 𝑢4) = 6 olduğundan, bu köşelerin silinmesiyle omega değerinde △ (𝐺, 𝑢1, 𝑢4) = △ (𝐺, 𝑢1) +△ (𝐺, 𝑢4) − 2η = 4 + 6 − 2.1 = 8 kadar azalma olur. Bu durumda 𝑢1 ve 𝑢4 komşu köşelerinin beraber silinmesi durumunda elde edilecek yeni derece dizisi 𝐷 = {1(4), 2(2), 3(2)1,4 , 4 (1), 7(2)} olduğundan (𝐷1,4) = 10 olarak hesaplanır. Gerçekten de △ (𝐺, 𝑢1, 𝑢4) = (𝐺) − (𝐺, 𝑢1, 𝑢4) = 18 − 10 = 8 olduğu görülür, bkz. Şekil 5.17. 92 𝑢3 _ 1 𝑢6 𝑢2 _ _ 𝑢5 2 3 _ 4 Şekil 5.17. Bir graftan iki komşu köşe silmek d) 𝑢2 ve 𝑢6 komşu olmayan köşeleri beraber silinirse: △ (𝐺, 𝑢2) = 4 ve △ (𝐺, 𝑢6) = 4 olduğundan, bu köşelerin silinmesiyle omega değerinde △ (𝐺, 𝑢2, 𝑢6) = △ (𝐺, 𝑢2) +△ (𝐺, 𝑢6) − 2η = 4 + 4 − 2.0 = 8 kadar azalma olur. Bu durumda 𝑢2 ve 𝑢6 komşu olmayan köşelerin beraber silinmesi durumunda elde edilecek yeni derece dizisi 𝐷2,6 = {1(3), 2(3), 3(2), 4(1), 6(1), 7(1)} olduğundan (𝐷2,6) = 10 olarak hesaplanır. Gerçekten de △ (𝐺, 𝑢2, 𝑢6) = (𝐺) − (𝐺, 𝑢2, 𝑢6) = 18 − 10 = 8 olduğu görülür, bkz. Şekil 5.18. 𝑢1 𝑢3 _ 1 𝑢4 _ 𝑢5 2 _ 4 Şekil 5.18. Bir graftan komşu olmayan iki köşe silmek 93 5.3.8. Sonuç. Eğer 𝑢1, 𝑢2, … , 𝑢𝑘 köşeleri, 𝐺’de birbiri ile komşu olmayan köşeler ise 𝑘 △ (𝐺, 𝑢1, 𝑢2, … , 𝑢𝑘) = ∑△ (𝐺, 𝑢𝑖) 𝑖=1 elde edilir. 94 6. UÇ PROBLEMLER 6.1. Giriş Graf teoride şimdiye kadar en iyi bilinen topolojik değişmez (invaryant) Euler karakteristiğidir. Bu karakteristik sayı, yukarıda da belirtildiği gibi topolojide yüzey hakkında, graf teoride de yüzeye çizilen tüm grafların ortak özellikleri hakkında bilgi vermektedir. Burada tanımlanan omega invaryantı da bir anlamda verilen bir derece dizisine karşılık olarak çizilebilen tüm grafların ortak özelliklerini belirlemede faydalıdır ve bu nedenle bir invaryanttır. 250 yıldır bilinen Euler karakteristiği bir çok alanda önemli uygulamalara sahiptir ama omega invaryantı Euler karakteristiğinin kullanılmasıyla doğrudan elde edilemeyecek olan çizilebilirlik, bağlantılılık, devirlilik, bileşen sayısı, kiriş sayısı, döngü sayısı vb. ile ilgili bilgiler doğrudan elde edilebilir. Euler karakteristiği ile yapılan sınıflandırmalar omega ile de yapılabilir. Bu çalışmada (𝐺) ≤ −4 ise 𝐺 grafının kesinlikle bağlantısız olduğu; (𝐺) = −2 ise ve 𝐺 çiziminin bağlantılı olması isteniyorsa 𝐺 grafının kesinlikle bir ağaç olduğu önceden ispat edilmiştir. Benzer şekilde 𝐺 grafı çizilebilir ve bağlantılı ise (𝐺) ≥ 0 olduğunda 𝐺 grafı kesinlikle en az bir devire sahiptir. Diğer yandan 𝐺 grafının tüm bileşenlerinin devirli olması durumunda (𝐺) ≥ 0 olur. Ayrıca (𝐺) ≤ −4 olan bir 𝐺 grafının bileşenlerinin tümü birden devirli olamaz. Bir derece dizisi verildiğinde bu derece dizisine sahip birçok grafın çizilebildiği buraya kadar olan kısımda bir çok defa belirtildi. Bu çizimlerin bazı ortak özellikleri ve bu özellikleri ifade eden net formüller bulunduğu gibi, bazı özelliklerin de ortak olmadığı ve çizimden çizime değiştiği söylenebilir. Bu tür durumlarda net formüller bulunamayacağından ancak istenen özelliğin aldığı değerlerin bulunduğu aralıkları belirlemek gereklidir. Yani bir özelliğin maksimum ve minimum değerlerinin belirlenmesi hedeflenebilir. Bu tür problemlere uç (extremal) problemler denilmektedir. Bu bölümde verilen bir derece dizisinin olası tüm çizimleri hakkında bazı uç problemler incelenecektir ve mümkün olan (𝐺) ≥ 0, (𝐺) = −2 ve (𝐺) ≤ −4 durumlarında verilen derece dizisine sahip tüm çizimler için, tüm bağlantılı çizimler için ve tüm temel çizimler için maksimum döngü sayısı bulunacaktır. 95 Belirli bir derece dizisinin çizimlerinin ne kadar farklı olabileceğini görmek için, 𝐷 = {1(8), 5(1), 6(1), 7(1), 9(2)} derece dizisi ele alınsın. (𝐷) = 18’dir. Şekil 6.1’deki graflar olası tüm çizimlerin bazılarıdır. Şekil 6.1. {1(8), 5(1), 6(1), 7(1), 9(2)} derece dizisine sahip 5 graf Şimdi (𝐷) ≥ 0 olan ilk durum ile devam edilecektir. 𝑟, 𝑠 ∈ ℕ olsun. Bir kenarın bir ucuna 𝑟 tane döngü ve diğer ucuna 𝑠 tane döngü eklenerek elde edilen graf 𝐵𝑟,𝑠 ile gösterilecektir, bkz. Şekil 6.2. B0,0 B B 0,1 1,1 B B B B 0,2 1,2 2,2 0,3 Şekil 6.2. Bazı 𝐵𝑟,𝑠 grafları 𝑞 ∈ ℕ olsun. Tek bir köşeye 𝑞 tane döngü eklenerek elde edilen graf 𝐿𝑞 ile gösterilsin. İlk bir kaç tane 𝐿𝑞, Şekil 6.3’de görülmektedir: 96 L0 L L 1 2 L L 3 4 Şekil 6.3. Bazı 𝐿𝑞 grafları Bu iki graf sınıfı sayesinde aşağıdaki sonuç verilebilir: 6.1.1. Teorem. Çizilebilir bir derece dizisi 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} olsun. Bu derece dizisine sahip olan herhangi bir 𝐺 grafının maksimum bileşen sayısı 1 𝑐𝑚𝑎𝑥 = ∑ 𝑎𝑖 + ∑ 𝑎𝑖 2 𝑑𝑖 ç𝑖𝑓𝑡 𝑑𝑖 𝑡𝑒𝑘 dir. İspat. Maksimum bileşen sayısını belirlemek için her bir bileşen mümkün olduğunca küçük seçilmelidir. İlk bakışta 𝐺’nin köşelerinin sayısı olan 𝑛’in doğal bir üst sınır olduğu söylenebilir. Şimdi 2𝑞 şeklindeki her bir çift köşe derecesi için, bir köşeye sahip bir 𝐿𝑞 bileşeni seçilsin. Böylelikle çift dereceli köşelereden kaynaklanan ∑𝑎2𝑖 tane bileşen vardır. İkinci olarak, tek dereceli bir köşe tek başına bir bileşen oluşturamaz. Çünkü böyle bir durumda, bu bileşen tek başına bir graf olduğundan el sıkışma lemması gereği köşelerinin derecelerinin çift olması gereken toplamı tek olurdu. Dolayısıyla tek dereceli bir köşeye sahip en küçük bileşen, iki tane tek dereceli köşeye sahip olan 𝐵𝑟,𝑠’dir. Böylece 1 bu bileşenlerin maksimum sayısı da ∑𝑎2𝑖−1 olacaktır. 2 6.1.2. Örnek. 𝐷 = {1(4), 2(2), 4(2), 5(2)} derece dizisi için (𝐷) = 6 olur, bkz. Şekil 6.4. 97 Şekil 6.4. 𝐷’nin temel formdaki bir çizimi 𝐷’ye karşılık gelen bağlantılı ya da bağlantısız başka çizimler de vardır. 𝐷’nin maksimum bileşen sayısı, 𝑎1 + 𝑎3 + 𝑎5 𝑐𝑚𝑎𝑥 = 𝑎2 + 𝑎4 + 2 4 + 0 + 2 = 2 + 2 + 2 = 7 olarak elde edilir. 𝐷’nin maksimum bileşene sahip bir çizimini gösteren graf, Şekil 6.5’de verilmiştir. Şekil 6.5. Verilen derece dizisinin maksimum bileşenli bir çizimi 6.2. Maksimum döngü sayısı Bu bölümde verilen bir derece dizisinin çizimlerindeki döngülerin sayısını hesaplamaya yönelik bir uç problemi ele alınacaktır. 𝐷 negatif olmayan bir tam sayı kümesi olsun. 𝐿𝐹(𝐷), 𝐿𝐶(𝐷) ve 𝐿(𝐷) sayıları şu şekilde tanımlanır: Çizilebilir bir 𝐷 derece dizisi verilsin. 𝐷’ye karşılık gelen grafların bir temel çizimindeki maksimum döngü sayısı 𝐿𝐹(𝐷) ile; 𝐷’ye karşılık gelen bağlantılı graflardaki maksimum döngü sayısı 𝐿𝐶(𝐷) ile; 98 ve son olarak 𝐷’ye karşılık gelen tüm graflardaki maksimum döngü sayısı da 𝐿(𝐷) ile gösterilsin. Aşağıdaki eşitsizlik tanımlardan aşikârdır: 6.2.1. Lemma. Herhangi bir 𝐷 derece dizisi için 𝐿𝐹(𝐷) ≤ 𝐿𝐶(𝐷) ≤ 𝐿(𝐷) olur. Ayrıca bu üç fonksiyon da toplamsaldır. 6.3. (𝑫) ≥ 𝟎 durumu Öncelikle 𝐿 fonksiyonu ele alınsın. Çift sayı olan herbir 𝑑𝑖 derecesi için bir tek köşe 𝑑 noktasında birbirine komşu 𝑖 tane döngüsü olan bir bileşen çizildiğini ve tek sayı olan 2 𝑑 −1 𝑑𝑗−1 herbir 𝑑 𝑖𝑖 ve 𝑑𝑗 derece çifti için 𝑟 = ve 𝑠 = olmak üzere 𝑟 + 𝑠 döngüye sahip 2 2 bir 𝐵𝑟,𝑠 bileşeni olduğu hatırlanırsa 𝐷 derece dizisinin tüm olası çizimlerinde en fazla toplam, 𝑑 𝑑 −1 𝐿(𝐷) = ∑ 𝑖 𝑗𝑑𝑖 ç𝑖𝑓𝑡 + ∑2 𝑑𝑗 𝑡𝑒𝑘 2 1 = [2𝑚 − ∑𝑑 𝑡𝑒𝑘 1] 2 𝑖 1 = 𝑚 − ∑ 2 𝑑 1 𝑖 𝑡𝑒𝑘 döngü bulunduğu ispatlanılmış olur: 6.3.1. Teorem. Herhangi bir 𝐷 derece dizisinin çizimlerinin sahip olabileceği maksimum döngü sayısı, 1 𝐿(𝐷) = 𝑚 − ∑ 1 2 𝑑𝑖 𝑡𝑒𝑘 dir. 1 6.3.2. Örnek. 𝐷 = {1(2), 3(2), 4(1), 5(1), 6(1), 7(1)} olsun. 𝐿(𝐷) = 15 − (6) = 12 olur. 2 Şimdi 𝐿𝐹(𝐷) sayısı bulunacaktır: 99 6.3.3. Teorem. (𝐷) ≥ 0 olsun. 𝐷 derece dizisinin temel çizimlerinin sahip olabileceği maksimum döngü sayısı olan 𝐿𝐹(𝐷) için aşağıdakiler geçerlidir: (𝐷) i. Eğer 𝑎1 > ∑𝑑 >1,𝑡𝑒𝑘 1 ise 𝐿𝐹(𝐷) = olur. 𝑖 2 1 ii. Eğer 𝑎1 ≤ ∑𝑑𝑖>1,𝑡𝑒𝑘 1 ise 𝐿𝐹(𝐷) = ((𝐷) + 𝑎1 − ∑2 𝑑𝑖>1,𝑡𝑒𝑘 1) olur. İspat. i. Köşe derecelerinin 𝑎1 + 2𝑎2 + 3𝑎3 + ⋯ +△ 𝑎△ şeklindeki toplamının 2𝑚 olduğu bilinmektedir. İlk olarak 𝑎1 > ∑𝑑 >1,𝑡𝑒𝑘 1 olsun. Yani sallanan köşelerin sayısı, 𝑖 tüm tek dereceli köşelerin sayısının yarısından büyük olsun. Maksimum sayıda döngü bulmak istendiğinden minimum sayıda kiriş ve katlı kenar olması hedeflenmektedir. Varsayım gereği 𝑎1 > ∑𝑑 >1,𝑡𝑒𝑘 1 olduğundan yeterli sayıda sallanan kenara sahip 𝑖 olunduğu açıktır ve bu yüzden ne kirişlere ne de katlı kenarlara ihtiyaç duyulmaz. Bu nedenle, 𝑎1 tane sallanan kenarın her biri için toplam köşe sayısından 2 eksiltilir. (𝐷) ≥ 0 durumunda bir temel formun (𝑎2 + 𝑎3 + ⋯ + 𝑎) −gen içerdiği hatırlanırsa bu çokgenin kenarlarının her biri için köşe derecelerinin toplamından 2 çıkarılması gerektiği sonucuna ulaşılır. Bu yüzden geriye kalan köşe derecelerinin toplamı, 𝑎1 + 2𝑎2 + 3𝑎3 + ⋯ +△ 𝑎△ − 2𝑎1 − 2(𝑎2 + 𝑎3 + ⋯ + 𝑎△) = 2𝑚 − 2𝑛 = (𝐷) olur ve her bir döngünün iki ucu olduğu için (𝐷) 𝐿𝐹(𝐷) = 2 elde edilir. Alternatif bir ispat daha verilebilir: (𝐷) ≥ 0 ve 𝑎1 > ∑𝑑 >1,𝑡𝑒𝑘 1 olsun. Devir 𝑖 bulunduran bir temel formda 𝐷 derece dizisinin herhangi bir 𝐺 çiziminde kenarlar tarafından çevrelenen tüm bölgeler bir ana devir ve etrafındaki döngülerden oluştuğundan ve (𝐷) 𝑟 = + 1 2 100 olduğundan maksimum sayıda döngü elde etmek için hiçbir kiriş ya da katlı kenar olmaması gerektiğinden hareketle 𝑟 = 𝐿𝐹(𝐷) + 1 elde edilir. ii. İkinci olarak 𝑎1 ≤ ∑𝑑 >1,𝑡𝑒𝑘 1 olsun. Bu durumda, önceki durumda olduğu gibi hareket 𝑖 etmek için yeterli sayıda sallanan köşe bulunmamaktadır. Çift dereceli köşeler düşünülürse aynı köşeye iki sallanan kenar eklemek, maksimum değerini bulmak istenilen döngü sayısını azaltır. Bir köşeye sallanan kenar ve bir kiriş eklemek de aynı etkiye sahiptir. Bu nedenle çift dereceye sahip köşelere sallanan kenar eklenmemelidir. Şimdi de derecesi tek olan köşeler ele alınsın. Birden fazla sallanan kenar eklemek, tekrar döngü sayısını azaltacağından tek dereceli köşelere en fazla birer tane sallanan kenar eklenebilir. Bir derece dizisinde el sıkışma lemması gereği tek dereceli köşelerin sayısının çift olmak zorunda olduğu hatırlanırsa bu sayı, 𝑘 ∈ ℕ olmak üzere 2𝑘 olarak alınır ve bu köşelerden 𝑎1 tanesi sallanan kenarlara sahip olacaktır. Bu 𝑎1 köşenin herbiri maksimum 𝑑𝑖−3 döngüye sahip olacaktır. Ayrıca geriye kalan 2𝑘 − 𝑎1 tek dereceli köşenin herbiri de 2 𝑑 −3 maksimum 𝑖 tane döngüye sahiptir. Sonuç olarak, 2𝑘 tane tek 𝑑𝑖 dereceli köşenin 2 𝑑 −3 herbiri maksimum ∑ 𝑖𝑑 >1,𝑡𝑒𝑘 ( ) tane döngüye sahip olacaktır. Benzer şekilde, çift 𝑑 𝑖 2 𝑖 𝑑 −2 derecesine sahip köşenin maksimum döngü sayısı da ∑ 𝑖𝑑 >1,ç𝑖𝑓𝑡 ( ) olarak hesaplanır. 𝑖 2 Bu nedenle 𝐷 derece dizisinin temel formundaki maksimum döngü sayısı, 𝑑 −3 𝑑 −2 𝐿𝐹(𝐷) = ∑ 𝑖𝑑 >1,𝑡𝑒𝑘 ( )+∑ 𝑖 𝑖 2 𝑑𝑖 ç𝑖𝑓𝑡 ( ) 2 1 = [ ∑ 𝑑𝑖 + ∑ 𝑑𝑖 − ∑ 3 − ∑ 2] 2 𝑑𝑖>1,𝑡𝑒𝑘 𝑑𝑖 ç𝑖𝑓𝑡 𝑑𝑖>1,𝑡𝑒𝑘 𝑑𝑖 ç𝑖𝑓𝑡 1 = [∑1≤𝑑 ≤△ 𝑑𝑖 − 𝑎1 − 2(∑2 𝑖 1≤𝑑𝑖≤△ 1 − 𝑎1) − ∑𝑑 >1,𝑡𝑒𝑘 1] 𝑖 1 = [2𝑚 − 𝑎1 − 2(𝑛 − 𝑎 ) − ∑2 1 𝑑𝑖>1,𝑡𝑒𝑘 1] 1 = [ + 𝑎1 − ∑𝑑 >1,𝑡𝑒𝑘 1] 2 𝑖 101 elde edilir. 6.3.4. Örnek. 𝐷 = {1(4), 3(4), 4(2)} derece dizisi için (𝐷) = 4 olur. Bu durumda 𝑎1 ≤ ∑𝑑 >1,𝑡𝑒𝑘 1 şartı gereği 𝑖 1 𝐿𝐹(𝐷) = (4 + 4 − 4) = 2 2 olur, bkz. Şekil 6.6. Şekil 6.6. 𝐷 = {1(4), 3(4), 4(2)} derece dizisinin maksimum döngülü bir temel çizimi 6.3.5. Örnek. 𝐷 = {1(4), 3(2), 4(4)} derece dizisi için (𝐷) = 6 olur. O halde 𝑎1 > ∑𝑑𝑖>1,𝑡𝑒𝑘 1 olduğundan (𝐷) 6 𝐿𝐹(𝐷) = = =3 2 2 elde edilir, bkz. Şekil 6.7. Şekil 6.7. 𝐷 = {1(4), 3(2), 4(4)} derece dizisinin maksimum döngülü bir temel çizimi 102 Bir derece dizisinin bazıları bağlantılı bazıları da bağlantısız olarak bir çok yolla çizilebildiği bilinmektedir. Şimdi temel çizim formları da dahil olmak üzere tüm olası bağlantılı çizimlerin maksimum döngü sayısı hesaplanacaktır. 6.3.6. Teorem. (𝐷) ≥ 0 olsun. Verilen bir 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} derece dizisinin tüm bağlantılı çizimlerinin sahip olabileceği maksimum döngü sayısı, 1. Eğer tüm dereceler çift ise (𝐷) a) 𝑛 = 1 ise yani ∑△𝑖=1 𝑎𝑖 = 1 ise 𝐿𝐶(𝐷) = + 1 olur. 2 (𝐷) b) 𝑛 > 1 ise yani ∑△𝑖=2 𝑎𝑖 > 1 ise 𝐿𝐶(𝐷) = olur. 2 (𝐷) 2. Eğer tek dereceli en az bir köşe varsa 𝐿𝐶(𝐷) = + 1’dir. 2 İspat. 1a) 𝑛 = 1 olduğundan yani graf tek bir köşeye sahip olduğundan çizilecek her bir kenar yine aynı köşeye bağlanacaktır. Dolayısıyla her bir kenarı bir döngü olacaktır. O halde bu tek köşede kenar sayısı kadar yani 𝑚 tane döngü olacaktır. Yani tüm kapalı (𝐷) bölgeler döngülerden ibaret olacağından 3.2.4.Teorem gereği + 1 tane döngü 2 çizilebilir. 1b) 𝑛 > 1 iken maksimum döngüye sahip çizimi yapmak için en pratik yol, maksimum döngüye sahip bir temel çizim yapmaktır. Bir temel çizim yaparken ilk olarak 𝑘 = (𝑎2 + 𝑎3 + ⋯ + 𝑎△) −gen çizerek başlanır. Daha sonra da bu en uzun devirin üzerine 2𝑘𝑖 2𝑘 −2 derecesine sahip her bir köşe için 𝑖 = 𝑘𝑖 − 1 tane döngü çizilerek şekil tamamlanmış 2 olur. 2. İkinci olarak, tek dereceli en az bir köşe mevcut olsun. El sıkışma lemması gereği tek dereceli köşelerin sayısı çift olacağından en az 2 tane tek dereceli köşe bulunacaktır. 1 Aranan çizimi yapmak için ilk olarak [𝑎1 + 2 + ∑2 𝑑𝑖>1,𝑡𝑒𝑘 1 + ∑𝑑𝑖 ç𝑖𝑓𝑡 2] uzunluklu bir 𝑑 −2 yol çizilir. Herbir çift 𝑑i derecesine sahip köşeye 𝑖 tane döngü eklenir. Burada iki alt 2 durum söz konusudur: 2.a. 𝑎1 = 0 durumu. Yolun iki ucunda da sallanan köşe olamaz. Bu yüzden tek dereceli köşelerden ikisi, diyelim ki 𝑑𝑎, 𝑑𝑏 derecelerine sahip iki köşe, yolun iki ucuna sırasıyla 𝑑𝑎−1 𝑑 −1 ve 𝑏 tane döngü ekleyerek yerleştirilir. Geriye ∑𝑑 >1,𝑡𝑒𝑘 1 − 2 tane tek dereceli 2 2 𝑖 103 köşe kalır. Bu sayının çift olduğuna dikkat ediniz. İkinci adımda bu tek dereceli köşeler 𝑑𝑘 ve 𝑑𝑡 şeklinde ikişer ikişer gruplanarak Şekil 6.2’de verilen 𝐵𝑖 𝑖 𝑟,𝑠 graflarına dönüştürülür. 𝐵𝑟,𝑠’nin iki köşesinden birisi ilk adımda çizilen yol üzerinde kalacaktır. Diğeri ise bu köşenin yol üzerinde olmayan komşu köşesi olur. Yol üzerindeki köşenin 𝑑𝑘 −3 𝑑𝑡 −1 derecesi 𝑑𝑘 ise bu köşeye 𝑖 tane döngü, diğerine de 𝑖 tane döngü eklendiğinde 𝑖 2 2 böylelikle aranan graf elde edilmiş olur. Bu grafın maksimum döngü sayısı ise 1 ∑𝑑𝑖>1,𝑡𝑒𝑘 1 − 2𝐿𝐶(𝐷) = [ ∑ d𝑖 − ∑ 1 − 2 + ∑ (d𝑖 − 2)] 2 2 𝑑𝑖>1,𝑡𝑒𝑘 𝑑𝑖>1,𝑡𝑒𝑘 𝑑𝑖 ç𝑖𝑓𝑡 1 = [ ∑ (d − 2) + 2 + ∑ (d − 2)] 2 𝑖 𝑖 𝑑𝑖>1,𝑡𝑒𝑘 𝑑𝑖 ç𝑖𝑓𝑡 1 = [2𝑚 − 2𝑛 + 2)] 2 (𝐷) = + 1 2 şeklinde bulunur. 2.b. 𝑎1 > 0 durumu. Burada da üç durum mevcuttur: 2.b.i. ∑𝑑 >1,𝑡𝑒𝑘 1 = 𝑎1 olsun. 𝑎𝑖 1 = 1 ise bu tek sallanan köşe ilk durumdaki gibi yolun bir ucuna yerleştirilir. El sıkışma lemması gereği en az bir tane daha derecesi tek olan köşe mevcut olacağından geriye kalan tek dereceli köşelerden birisi, diyelim ki derecesi 𝑑 olanı, yolun diğer ucuna (𝑑 − 1)/2 tane döngü yardımıyla yerleştirilir. Derecesi bir çift 𝑑 −2 𝑑i sayısı olan her bir köşeye 𝑖 tane döngü eklenir, eğer kaldıysa derecesi tek sayı olan 2 köşeler de ikişer ikişer gruplanıp 2.a’daki gibi hareket edilirse hedeflenen çizime ulaşılır. 𝑎1 ≥ 2 ise bu durumda iki uca da birer sallanan köşe konularak ve diğer işlemler 𝑎1 = 1 durumundaki gibi takip edilerek benzer yolla sonuca gidilir. 2.b.ii. ∑𝑑 >1,𝑡𝑒𝑘 1 > 𝑎1 olsun. 2.b.i. şıkkındaki gibi hareket edilerek istenen çizime 𝑖 ulaşılır. 104 2.b.iii. ∑𝑑 >1,𝑡𝑒𝑘 1 < 𝑎1 olsun. Bu durumda 𝑛 + 2 − 𝑎1 uzunluklu bir yol çizilerek 𝑖 1 başlanır. Bu uzunluğu bulmak için önceki adımlarda çizilen [𝑎1 + 2 + ∑2 𝑑𝑖>1,𝑡𝑒𝑘 1 + ∑𝑑 ç𝑖𝑓𝑡 2] uzunluklu bir yol ile başlanırsa olması gerekenden fazla döngü ve yine olması 𝑖 𝑎1−∑𝑑 >1,𝑡𝑒𝑘 1−2 gerekenden az sallanan köşe elde edilir. İstenen sonuca ulaşmak için 𝑖 tane 2 döngünün her biri yerine bir çift sallanan kenar eklenir ve her bir işlemde yoldan bir köşe eksiltilir. Bu da 𝑛 + 2 − 𝑎1 uzunluklu bir yol elde edileceği anlamına gelir. Yukarıdaki adımlarda olduğu gibi çift ve tek dereceleri köşeleri yerleştirerek istenen graf elde edilir. Görüldüğü gibi bu ispatın 2.b kısmında takip edilen ortak yöntem, verilen uzunlukta bir yol çizerek bu yolun iki ucuna döngüler yardımıyla iki adet tek dereceli köşe eklemek ve kalan tek dereceli köşeleri ikişer ikişer gruplayıp 𝐵𝑟,𝑠 grafları olarak, kalan çift dereceli köşeleri de gerekli sayıda döngü ekleyerek yol üzerine yerleştirmek şeklinde özetlenebilir. 6.3.7. Örnek. 𝐷 = {2(2), 4(3), 6(1)} derece dizisi için (𝐷) = 10 olur ve böylece (𝐷) 10 𝐿𝐶(𝐷) = = = 5 elde edilir, bkz. Şekil 6.8. Bu çizimin aynı zamanda bir temel 2 2 çizim olduğuna dikkat ediniz. Şekil 6.8. {2(2), 4(3), 6(1)}’nin maksimum döngülü bağlantılı bir çizimi 6.3.8. Örnek. 𝐷 = {1(4), 3(2), 4(4)} derece dizisi için (𝐷) = 6 olur. O halde 𝐿𝐶(𝐷) = (𝐷) 6 + 1 = + 1 = 4 elde edilir, bkz. Şekil 6.9. 2 2 105 Şekil 6.9. {1(4), 3(2), 4(4)}’nin maksimum döngülü bağlantılı bir çizimi 6.3.9. Örnek. 𝐷 = {1(4), 3(4), 4(2)} derece dizisi için (𝐷) = 4 olur. Bu durumda (𝐷) 4 𝐿𝐶(𝐷) = + 1 = + 1 = 3 olur, bkz. Şekil 6.10. 2 2 Şekil 6.10. {1(4), 3(4), 4(2)}’nin maksimum döngülü bağlantılı bir çizimi 6.4. (𝑫) = −𝟐 durumu (𝐷) = −2 olsun. O halde bu derece dizisi hem bağlantılı hem de bağlantısız çizilebilir. (𝐷) = −2 ve 𝐷 bağlantılı olduğunda 𝐷 derece dizisine ait olan graf devir bulundurmayan (ağaç) bir graftır. Bu da 𝐷’ye ait grafın hiçbir döngüye sahip olmadığını gösterir. Buradan da aşağıdaki sonuca ulaşılır: 6.4.1. Teorem. (𝐷) = −2 olsun. 𝐷 derece dizisinin tüm bağlantılı 𝐺 çizimleri için 𝐿(𝐺) = 𝐿𝐹(𝐺) = 𝐿𝐶(𝐺) = 0 dır. İspat. (𝐷) = −2 olduğunda 𝐺 bağlantılı bir çizim ise 𝐺’nin hiçbir devir bulundurmadığı görülmüştü. Buna göre sonuç aşikârdır. O halde (𝐷) = −2 özelliğindeki bir 𝐷 derece dizisinin 𝐺 çiziminin bağlantısız olduğu varsayılırsa bu durumda şu sonuç elde edilir: 6.4.2. Teorem. (𝐷) = −2 ve 𝐺, bu derece dizisinin bağlantısız bir çizimi olsun. 𝑎1 − 2 − ∑𝑑 >1,𝑡𝑒𝑘 1 𝐿𝐹(𝐺) = 𝑖 2 106 ve 1 𝐿(𝐺) = 𝑚 − ∑ 1 2 𝑑𝑖 𝑡𝑒𝑘 dir. İspat. Yukarıdaki duruma benzer şekilde ispatı yapılabilir. 6.5. (𝑫) ≤ −𝟒 durumu (𝐷) ≤ −4 olan bir derece dizisinin tüm çizimlerinin kesinlikle bağlantısız olduğu gösterilmişti. Ayrıca (𝐷) ≤ −4 iken temel çizimlerin karma olduğunu, yani bir tane ana bileşen ile yanında belli sayıda 𝐾2’den oluşur. Bu 𝐾2’lerde herhangi bir döngü olamayacağından bütün döngüler ana devir üzerindedir. Hatırlanacağı gibi ana bileşen, uzunluğu 𝑎2 + 𝑎3 + ⋯ + 𝑎△ olan bir devir ile bu devirin köşelerine eklenen döngü ve sallanan kenarlardan oluşur. Derecesi çift olan köşelerde döngü kullanılamayacağı için sallanan kenara ihtiyaç olmayacaktır. Benzer şekilde derecesi tek olan köşelerde de mümkün olan en az sayı olan birer tane sallanan kenarı koymak yeterli olacaktır. O halde ana bileşende ∑𝑑 >1,𝑡𝑒𝑘 1 tane 1 (sallanan kenar) kullanılır ve geriye kalan 𝑎1 −𝑖 ∑𝑑 >1,𝑡𝑒𝑘 1 tane 1’i ise ikişer ikişer kullanarak (𝑎1 − ∑𝑑 >1,𝑡𝑒𝑘 1)/2 tane 𝐾2 oluşturulur. 𝑖 𝑖 O halde AB ile gösterilecek olan ana bileşenin derece dizisi (∑𝑑 >1,𝑡𝑒𝑘 1){1 𝑖 , 2(𝑎2), 3(𝑎3), … ,△(𝑎△)} olur. 𝑎1 > ∑𝑑 >1,𝑡𝑒𝑘 1 olduğundan toplamsallık 𝑖 özelliği kullanılırsa 𝐿𝐹(𝐷) = 𝐿𝐹(𝐴𝐵) + ∑𝐿𝐹(𝐾2) = 𝐿𝐹(𝐴𝐵) (𝐴𝐵) = 2 1 = (𝑎3 + 2𝑎2 4 + ⋯ + (△ −2)𝑎△ − ∑𝑑𝑖>1,𝑡𝑒𝑘 1) 1 = ((𝐷) + 𝑎1 − ∑𝑑 >1,𝑡𝑒𝑘 1) 2 𝑖 107 elde edilir. 6.5.1. Teorem. Eğer (𝐷) ≤ −4 ise 1 𝐿𝐹(𝐷) = ((𝐷) + 𝑎1 − ∑ 1) 2 𝑑𝑖>1,𝑡𝑒𝑘 dir. 6.5.2. Örnek. 𝐷 = {1(45), 2(1), 3(2), 5(2), 9(3), 10(1)} derece dizisi için (𝐷) = −8 olur. O halde 1 𝐿𝐹(𝐷) = ((𝐷) + 𝑎1 − ∑𝑑 >1,𝑡𝑒𝑘 1) 2 𝑖 1 = (−8 + 45 − 7) 2 = 15 elde edilir. Karşılık gelen temel çizim Şekil 6.11’deki gibidir. … 19 tane 𝐾2 Şekil 6.11. 𝐷’ye karşılık gelen bir karma temel çizim İkinci olarak, (𝐷) ≤ −4 olduğunda 𝐿𝐶(𝐷)’yi ele almak istenirse hatırlanacağı gibi bu durumda 𝐷’nin bağlantılı bir çizimi elde edilemez. Dolayısıyla 𝐿𝐶(𝐷) sayısı, bu durumda tanımlı değildir. 108 Sonuncu olarak, 𝐷 derece dizisinin tüm çizimlerinin sahip olabileceği maksimum döngü sayısı olan 𝐿(𝐷) için 1 𝐿(𝐷) = 50 − . 52 2 = 24 bulunur, bkz. Şekil 6.12: … 22 tane 𝐾2 Şekil 6.12. {1(45), 2(1), 3(2), 5(2), 9(3), 10(1)}’in maksimum döngülü bir çizimi 109 7. SONUÇ Graflar, son yıllarda kimya, fizik, farmakoloji, elektronik mühendisliği, toplum bilim, biyoloji gibi birçok alanda ortaya çıkan uygulamaları nedeniyle ciddi bir çalışma alanı haline gelmiştir. Matematiğin günümüzde diğer disiplinlere en fazla uygulanabilen alt dali graf teoridir. Bu nedenle bu alanda çok fazla sayıda araştırma mevcuttur ve sadece matematikçiler için değil, grafların uygulanabildiği tüm bilim alanlarındaki araştırmacılar için önemli bir çalışma alanı olmuştur. Bu tezde 250 yıldır bilinen önemli bir graf invaryantı olan Euler karakteristiğine benzer şekilde yeni bir graf invaryantı tanımlanmıştır. Adına omega denilen bu invaryant yardımıyla verilen bir derece dizisine karşılık gelen tüm graf çizimlerinin ortak bir çok özelliğini elde etmek mümkün olabilmektedir. Omega invaryantının topolojik graf teori, cebirsel graf teori, spektral graf teori ve topolojik graf indeksleri gibi alanlarda ve bunların uygulamalarında önemli uygulamaları ortaya çıkmaya başladığından kısa zamanda önemli bir kavram olarak literatürdeki yerini alacağı öngörülmektedir. 110 KAYNAKLAR Aldous, J. M., Wilson, R. J. 2004. Graphs and Applications, An Introductory Approach. Springer, London. Benjamin, A., Chartrand, G., Zhang, P. 2015. The Fascinating World of Graph Theory, Princeton University Press, Princeton. Bondy, J. A., Murty, U. S. R. 1982. Graph Theory with Applications. North Holland, NY. Bondy, J. A. Murty, U. S. R. 2008. Graph Theory. Springer NY. Capobianco, M., Molluzzo, J. C. 1978. Examples and Counterexamples in Graph Theory. North-Holland, NY. Chartrand, G. 1985. Introductory Graph Theory. New York, Dover. Chartrand, G., Zhang, P. 2012. A First Course in Graph Theory. New York, Dover. Clark, J., Holton, D. A. 1995. A First Look at Graph Theory. World Scientific, Singapour. Deo, N. 1974. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, NJ. Diestel, R. 2010. Graph Theory. Springer GTM. Edmonds, J. 1964. Existence of k-edge-connected ordinary graphs with prescribed degrees. J of Research of the Nat. Bureau of Standards-B Mathematics and Mathematical Physics, 68B (2), 73-74. Foulds, L. R. 1992. Graph Theory Applications. Springer, New York. Gross, J. L., Yellen J. 2006. Graph Theory and Its Applications (Second Edition). CRC Press, USA. Hakimi, S. L. 1962. On the realizability of a set of integers as degrees of the vertices of a graph. J. SIAM Appl. Math., 10, 496-506. Hartsfield, N., Ringel, G. 2003. Pearls in Graph Theory, A Comprehensive Introduction. Dover NY. Havel, V., 1955. A remark on the existence of finite graphs (Czech). Casopic Pest. Mat., 80, 477-480. Ivanyi, A., Lucz, L., Gombos, G., Matuszka, T. 2013. Parallel Enumeration of Degree Sequences of Simple Graphs II. Acta Univ. Sapientiae, Informatica 5 (2), 245-270. 111 Kim, H., Toroczkai, Z., Miklos, I., Erdös, P. L., Szekely, L. A. 2009. On Realizing all Simple Graphs with a Given Degree Sequence. J. Phys. A: Math. Theor. 42, 1-6. Miller, J. W. 2013. Reduced Criteria for Degree Sequences, Discrete Mathematics 313, 550-562. Skiena, S., 1990. Line Graphs, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA, Addison-Wesley, 128 and 135-139. Skiena, S. 1990. Implementing Discrete Mathematics, Combinatorics and Graph Theory with Mathematica. Reading, MA, Addison-Wesley, 210. Thulasiraman, K., Swamy, M. N. S. 1992. Graphs: Theory and Algorithms. John Wiley and Sons, NY. Triphati, A., Venugopalan, S., West, D. B. 2010. A short constructive proof of the Erdös-Gallai characterization of graphic lists, Discrete Math. 310, 843-844. Triphati, A., Tyagi, H. 2008. A Simple Criterion on Degree Sequences of Graphs, Discrete Applied Mathematics 156, 3513-3517. Trudeau, R. J. 1993. Introduction to Graph Theory. Dover, NY. Tutte, W. T. 1998. Graph Theory as I have Known It. Oxford Science Publications, Oxford. Tyshkevich, R. I., Mel'nikov, O. I., Kotov, V. M. 1981. On Graphs and Degree Sequences: Canonical Decomposition, Kibernetika 6, 5-8. Tyshkevich, R. I., Chernyak, A. A., Chernyak, Zh. A. 1987. Graphs and Degree Sequences I, Cybernetics 23 (6), 734-745. Vasudev, C. 2006. Graph Theory with Applications. New Age International Publishers, India. Vasudev, C. 2007. Combinatorics and Graph Theory. New Age International Publishers, India. Wallis, W. D. 2007. A Beginner's Guide to Graph Theory. Birkhauser, Boston. West, D. B. 2001. Introduction to Graph Theory. Pearson, India. Wilson, R. J. 1998. Introduction to Graph Theory. Addison Wesley, Malaysia. Wilson, R. J., Watkins, J. J. 1990. Graphs, An Introductory Approach. John Wiley and Sons, NY. Zverovich, I. E., Zverovich, V. E. 1992. Contributions to the Theory of Graphic Sequences, Discrete Mathematics 105, 293-303. 112 ÖZGEÇMİŞ Adı Soyadı : Sadık DELEN Doğum Yeri ve Tarihi : İstanbul, 07/05/1979 Yabancı Dili : İngilizce Eğitim Durumu (Kurum ve Yıl) Lise : Atatürk Lisesi, 1996 Lisans : Bursa Uludağ Üniversitesi, Fen-Edebiyat Fakültesi, Matematik Bölümü, 2011 Bütünleştirilmiş Doktora : Bursa Uludağ Üniversitesi, Fen Bilimleri Enstitüsü, Matematik Anabilim Dalı, 2019 Çalıştığı Kurum ve Yıl : - İletişim (e–posta) : sd.mr.math@gmail.com.tr Yayınları : Delen, S., Cangul, I. N. 2018. A New Graph Invariant. Turkish Journal of Analysis and Number Theory, 6 (1), 30-33. Delen, S., Cangul, I. N. 2018. Extremal Problems on Components and Loops in Graphs. Acta Mathematica Sinica, English Series, 34, 1-11. https://doi.org/10.1007/s10114-018- 8086-6, ISSN: 1439-8516 Delen, S., Togan, M., Yurttas, A., Cangul, I. N., New Results on Edge and Vertex Deletion in Graphs, MICOPAM Proceedings Book, (2018), 175-179, ISBN 978-86-6016- 036-4 113 Yurttas, A., Togan, M., Delen, S., Cangul, I. N., Omega Invariant and Its Applications in Graph Theory, MICOPAM Proceedings Book, (2018), 86-90, ISBN 978-86-6016-036- 4 Mishra, V. N., Delen, S., Cangul, I. N., Algebraic Structure of Graph Operations in Terms of Degree Sequences, International Journal of Analysis and Applications, 16 (6) (2018) 809-821, DOI: 10.28924/2291-8639-16-2018-809, ISSN: 2291-8639 Mishra, V. N., Delen, S., Cangul, I. N., Degree Sequences of Join and Corona Products of Graphs, EJMAA-Electronic Journal of Mathematical Analysis and Applications, 7 (1) (2019) 5-13, ISSN: 2090-729X Delen, S., Cangul, I. N., Applications of a New Invariant for Graphs, (submitted) Delen, S., Yurttas, A., Togan, M., Cangul, I. N., Omega invariant of graphs and cyclicness, (submitted) Delen, S., Togan, M., Yurttas, A., Ana, U., Cangul, I. N., The Effect of Edge and Vertex Deletion on Omega Invariant, (submitted) Yurttas, A., Togan, M., Delen, S., Ana, U., Cangul, I. N., The Effect of a new Graph Theoretical Invariant Omega on Some Topological Graph Indices, (submitted) Delen, S., Cangul, I. N., Degree Sequences of Join and Corona Product of Graphs, Third International Conference on Recent Advances in Pure and Applied Mathematics (ICRAPAM 2016), 19-23.05.2016, Bodrum-Mugla-Turkey Delen, S., Cangul, I. N., Algebraic Properties of Join and Corona Product of Graphs, International Conference on Analysis and its Applications, Ahi Evran University, 12- 15.07.2016, Kirsehir-Turkey Cangul, I. N., Delen, S., Yurttas, A., Ana, U., Degree sequences of several graph classes, The 29th International Conference of the Jangjeon Mathematical Society on Number Theory, Special Functions and Its Applications, 8-10.08.2016, Pondicherry- India Delen, S., Cangul, I. N., Catalogue of Degree Sequences of Molecular Graphs, International Conference on Recent Advances in Pure and Applied Mathematics (ICRAPAM 2017), May 11-15, 2017, Palm Wings Ephesus Resort Hotel, Kusadasi - Aydin, TURKEY www.icrapam.org Cangul, I. N., Delen, S., Yurttas, A., Togan, M., Topological Applications of a new Graph Invariant, International Conference on Current Scenario in Pure and Applied 114 Mathematics (ICCSPAM 2018), 14th–16th February 2018, PG & Research Department of Mathematics, Kongunadu Arts and Science College (Autonomous), G. N. Mills Post, Coimbatore - 641029, Tamil Nadu, India, http://kongunaducollege.ac.in/iccspam2018/index.php Delen, S., Cangul, I. N., Applications of a New Invariant for Graphs, International Conference on Pure and Applied Mathematics (ICPAM 2018), 19th – 21st February 2018, PG & Research Department of Mathematics, Sri Chandrasekharenda Saraswathi Viswa Mahavidyalaya (SCSVMV), Enathur, Kanchipuram, India, http://www.kanchiuniv.ac.in/ICPAM/index.html Cangul, I. N., Delen, S., Yurttas, A., Togan, M., Topological Graph Indices and a new Graph Invariant, Science Forum, 24th February, 2018, Department of Mathematics, RVCE, Bangalore, India http://rvce.edu.in/Comm-Science Cangul, I. N., Delen, S., Yurttas, A., Togan, M., Fundamental Form of a Graph, 3rd International Conference on Computational Mathematics and Engineering Sciences, 04- 06 May, 2018, Girne, Turkish Republic of Northern Cyprus, https://www.cmescongress.org/ Cangul, I. N., Delen, S., Yurttas, A., Togan, M., A New Graph Theoretical Invariant in Terms of Degree Sequence, Тhe 14th Serbian Mathematical Congress (14th SMAK), 16th-19th May, 2018, Kragujevac, Republic of Serbia, https://imi.pmf.kg.ac.rs/kongres/index.php#about Cangul, I. N., Delen, S., Yurttas, A., Togan, M., New Properties of Realizations of Degree Sequences, Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays, 28th May-1st June, 2018, UP FAMNIT Koper, Slovenia, https://conferences.famnit.upr.si/event/4/ Cangul, I. N., Delen, S., Yurttas, A., Togan, M., Omega Invariant of Graphs, International Congree of Mathematicians, Rio de Janerio, Brazil, 1st-9th August, 2018, http://icm2018.org/portal/en/ Cangul, I. N., Delen, S., Togan, M., Yurttas, A., Some applications of a new graph invariant omega, 2nd International Conference on Applied Mathematics and Numerical Methods, Department of Applied Mathematics, University of Craiova, Craiova, Romania, 19th-20th October, 2018, http://cis01.central.ucv.ro/ICAMNM/?Home 115 Cangul, I. N., Yurttas, A., Togan, M., Delen, S., Omega Invariant and Its Applications in Graph Theory, The Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, Dedicated to Professor Gradimir V. Milovanović on the Occasion of his 70th Anniversary, Antalya-Turkey, 26th–29th October, 2018, http://micopam2018.akdeniz.edu.tr/information/ Delen, S., Togan, M., Yurttas, A., Cangul, I. N., Fundamental Forms and Omega Invariant of Graphs, The Mediterranean International Conference of Pure & Applied Mathematics and Related Areas, Dedicated to Professor Gradimir V. Milovanović on the Occasion of his 70th Anniversary, Antalya-Turkey, 26th–29th October, 2018, http://micopam2018.akdeniz.edu.tr/information/ Cangul, I. N., Delen, S., Graph Theory, Discrete Groups and Some Invariants, International Conference on Number Theory and Graph Theory to commemorate the sixty second birthday of Dr. Chandrashekar Adiga, 27-29 June 2019, Department of Studies in Mathematics, University of Mysore, Mysore, India 116 BURSA ULUDAĞ ÜNİVERSİTESİ TEZ ÇOĞALTMA VE ELEKTRONİK YAYIMLAMA İZİN FORMU Yazar Adı Soyadı Sadık DELEN Tez Adı Omega İnvaryantı Enstitü Fen Bilimleri Enstitüsü Anabilim Dalı Matematik Tez Türü Doktora Tez Danışman(lar)ı Prof. Dr. İsmail Naci CANGÜL Çoğaltma (Fotokopi Çekim) Tezimden fotokopi çekilmesine izin veriyorum izni Tezimin sadece içindekiler, özet, kaynakça ve içeriğinin % 10 bölümünün fotokopi çekilmesine izin veriyorum Tezimden fotokopi çekilmesine izin vermiyorum Yayımlama izni T e z i m in elektronik ortamda yayımlanmasına izin veriyorum Hazırlamış olduğum tezimin belirttiğim hususlar dikkate alınarak, fikri mülkiyet haklarım saklı kalmak üzere Bursa Uludağ Üniversitesi Kütüphane ve Dokümantasyon Daire Başkanlığı tarafından hizmete sunulmasına izin verdiğimi beyan ederim. Tarih: 01/02/2019 İmza : 117