GRAF ENERJİSİ Feriha ÇELİK T. C. BURSA ULUDAĞ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ GRAF ENERJİSİ Feriha ÇELİK 0000-0002-0791-9293 Prof. Dr. İsmail Naci CANGÜL (Danışman) DOKTORA TEZİ MATEMATİK ANABİLİM DALI BURSA–2021 Her Hakkı Saklıdır ÖZET Doktora Tezi GRAF ENERJİSİ Feriha ÇELİK Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı Danışman: Prof. Dr. İsmail Naci CANGÜL (Bursa Uludağ Üniversitesi) Bu çalışmanın amacı, graf teorinin en önemli uygulama alanlarından birisi olan graf enerjisi konusunda yeni sonuçlar elde etmektir. Graf enerjisi, son 40 yılda ortaya çıkan ve hızla gelişen bir alandır ve lineer cebir metodlarını kullanarak graflar hakkında matematiksel sonuçlar elde etmeye ve bu sonuçlar yardımıyla kimyasal moleküllerin enerjileri hakkında yeni sonuçlar elde etmeye yarar. Bu tez sekiz bölümden oluşmaktadır. Birinci bölüm giriş bölümü olarak düzenlenmiştir. Temel tanım ve sonraki bölümlerde kullanılacak bazı önemli kavram ve sonuçlar bu bölümde hatırlatılmıştır. İkinci bölümde graflarve grafların enerjileri hakkında kuramsal temellerinden bahsedilmiştir. Üçüncü bölümde tez boyunca kullanılacak olan materyal ve yöntemler hakkında bilgi verilmiştir. Dördüncü bölümde bazı özel graf türleri için spektral polinomlar oluşturulmuş, oluşturulan bu polinomlar için indirgeme bağıntıları geliştirilip bu grafların enerjilerini veren formüller elde edilmiştir. Beşinci bölümde ise, dördüncü bölümde oluşturulan enerji formülleri için indirgeme bağıntıları oluşturulmuş bunun yanında hesaplamaları kolaylaştıracak bazı alternatif enerji indirgeme bağıntıları da verilmiştir. Altıncı bölümde graflar üzerinde yeni birleşim operasyonları, yedinci bölümde ise bir graf için alt bölüm operasyonları tanımlanmış olup bu bölümlerde, elde edilen yeni graflar için grafların polinomlarını, polinomlar için indirgeme bağıntılarını ve grafların enerjilerini veren yeni yöntemler geliştirilmiştir. Son bölüm olan sekizinci bölümde ise elde edilen bulgu ve sonuçlara yer verilmiştir. Anahtar Kelimeler: alt bölüm grafı, enerji, graf, köşe birleşim grafı, spektral polinom, spektrum 2021, vi + 79 sayfa. i ABSTRACT PhD Thesis GRAPH ENERGY Feriha ÇELİK Bursa Uludağ University Graduate School of Natural and Applied Sciences Department of Mathematics Supervisor: Prof. Dr. Ismail Naci CANGUL (Bursa Uludag University) The aim of this work is to obtain new and original results on graph energy which is one of the most important application areas of graph theory. Graph energy appeared and fastly developed in the last 40 years. By means of linear algebraic methods, we can obtain mathematical values on the graphs and these values help us to comment on the molecular energies of the molecules under study. This PhD thesis consists of 6 chapters. The first section is organized as the Introduction. Fundamental notions and results which will be needed later on in the thesis are recalled here. In the second chapter, the material and methods used in the thesis are mentioned. In the third chapter, spectral polynomials of some specific graph classes are constructed and recurrence relations for these polynomials are obtained to find some formulae for the energy of these graph classes. In the fourth chapter, recurrence relations for the energy formulae obtained in the third chapter are established and some alternative energy recurrence relations to ease the calculations are given. In the fifth chapter, some new union operations on graphs, in the sixth chapter, subdivision operations for a graph are introduced and in these chapters, new techniques giving the spectral polynomials, their recurrence formulae and graph energy are established. Key Words: energy, graph, spectral polynomial, spectrum, subdivision graph, vertex union graph 2021, vi + 79 pages. ii ÖNSÖZ VE TEŞEKKÜR Tanıdığım günden bu yana değerli bilgileri ile yoluma ışık olan, bu çalışmanın başından itibaren planlanmasında, yürütülmesinde ve oluşumunda ilgi ve desteğini hiçbir zaman esirgemeyen, her konuda çekinmeden fikrine başvurabildiğim, engin bilgi ve tecrübelerinden yararlandığım, meslek hayatımda da en büyük rol model aldığım saygıdeğer hocam Prof. Dr. İsmail Naci CANGÜL'e; hayatımın her evresinde benim yanımda olan, bana olan maddi ve manevi desteklerini hiçbir zaman esirgemeyen, saygı ve sevgi kelimelerinin anlamlarını yaşayarak öğreten hayattaki en büyük şansım olan aileme sonsuz teşekkürler... Feriha ÇELİK 14/10/2021 iii İÇİNDEKİLER Sayfa ÖZET …………………………………………………………………………...........i ABSTRACT ……………………………………………………………………... ....ii ÖNSÖZ VE TEŞEKKÜR ……………………………………………………..........iii İÇİNDEKİLER …………………………………………………………………... ...iv SİMGELER DİZİNİ …………………………………………………………….. ....v ŞEKİLLER DİZİNİ …………………………………………………………….. ...vi 1. GİRİŞ ………………………………………………………………………….. .....1 2. KURAMSAL TEMELLER.……………………………………………………….9 3. MATERYAL VE YÖNTEM ………………………………………………….....10 4. GRAFLARIN SPEKTRAL POLİNOMLARI, İNDİRGEME BAĞINTILARI ve ENERJİLERİ..............................................................................................................11 5. GRAFLARDA ENERJİ İNDİRGEME BAĞINTILARI.......................................29 6. GRAFLARDA BİRLEŞİM ve BİRLEŞİMİN KARAKTERİSTİK POLİNOM ÜZERİNDEKİ ETKİSİ …..........................................................................................40 7. ALT BÖLÜM GRAFLARININ KARAKTERİSTİK POLİNOMLARI, İNDİRGEME BAĞINTILARI VE ENERJİLERİ......................................................63 8. BULGULAR, TARTIŞMA VE SONUÇ...............................................................75 KAYNAKLAR...........................................................................................................77 ÖZGEÇMİŞ................................................................................................................79 iv SİMGELER DİZİNİ Simgeler Açıklama 𝐺 Graf 𝑉(𝐺) 𝐺 grafının köşe kümesi 𝐸(𝐺) 𝐺 grafının kenar kümesi d(u) 𝑢 köşesinin derecesi 𝐾𝑛 𝑛 köşeli tam graf 𝐶𝑛 𝑛 köşeli devir grafı 𝑃𝑛 𝑛 köşeli yol grafı 𝑆𝑛 𝑛 köşeli yıldız grafı 𝐾𝑟,𝑠 İki parçalı tam graf 𝑃𝑜𝑙(𝐺) 𝐺 grafının karakteristik polinomu S(G) 𝐺 grafının spektrumu 𝐸(𝐺) 𝐺 grafının enerjisi 𝐺1 ⋁𝑣𝐺2 𝐺1 ve 𝐺2 graflarının köşe birleşim grafı 𝐺 𝑒1 ⋁𝑣𝐺2 𝐺1 ve 𝐺2 graflarının bir köşede kenar birleşim grafı 𝑆(𝐺) 𝐺 grafının alt bölüm grafı 𝑆𝑟(𝐺) 𝐺 grafının 𝑟-alt bölüm grafı v ŞEKİLLER DİZİNİ Şekil 1.1. Pregel Nehri ...................................................................................................... 1 Şekil 1.2. Königsberg grafı ...………………….......……………………………….........1 Şekil 1.3. 7 köşeli ve 10 kenarlı graf örneği.......................................................................2 Şekil 1.4. Basit bir graf.......................................................................................................3 Şekil 1.5. Basit olmayan bir graf........................................................................................3 Şekil 1.6. Basit olmayan bir graf.......................................................................................3 Şekil 1.7. G ve ?̅? grafları...................................................................................................4 Şekil 1.8. 2 −düzenli graf .........................................................................………............4 Şekil 1.9. Bir 𝐺 grafı ve bu grafa ait 𝐴 komşuluk matrisi………………………….........5 Şekil 1.10. P5 patika grafı..................................................................................................6 Şekil 1.11. 𝐶3, 𝐶4, 𝐶5 devir grafları......…….....................................................................6 Şekil 1.12. 𝑆6 yıldız grafı..........…….................................................................................7 Şekil 1.13. 𝐾3, 𝐾4, 𝐾5 tam grafları…………….................................................................7 Şekil 1.14. 𝐾2,3 ve 𝐾3,3 iki parçalı tam grafı......................................................................8 Şekil 1.15. Bağlantılı graf örnekleri...................................................................................8 Şekil 1.16. Bağlantısız graf örnekleri.................................................................................8 Şekil 6.1. G1, G2 ve G1 ⋁vG2 köşe birleşim grafı ..........................................................41 Şekil 6.2. K5 ve K5 ⋁vK5 köşe birleşim grafı ................................................................42 Şekil 6.3. Sn ve Sn graflarında merkez köşe birleşim grafı ............................................48 Şekil 6.4. Sn ve Sn grafları için merkez dışında köşe birleşim grafı .............................. 49 Şekil 6.5. Pn ve Pn⋁vPn köşe birleşim grafı …….............................................……….53 Şekil 6.6. G1, G2 ve G ⋁ e 1 vG2 grafları ............................................................................54 Şekil 6.7. K5 ve K ⋁ e 5 vK5 grafı .......................................................................................55 Şekil 6.8. Sn ile v merkez köşede kenar birleşim grafı Sn ⋁ e v Sn.....................................59 Şekil 6.9. Sn ve v uç köşede kenar birleşim grafı S e n ⋁v Sn ............................................60 Şekil 6.10. Pn ve P ⋁ e n vPn grafı........................................................................................62 Şekil 7.1. Bir G grafı ve bu grafın S(G) alt bölüm grafı...................................................63 Şekil 7.2. Pn ve S(Pn) grafı...............................................................................................64 Şekil 7.3. Sn ve Sn'in alt bölüm grafı S(Sn).....................................................................65 vi 1. GİRİŞ Graf Teori, 1736 yılında ünlü matematikçi Leonhard Euler’in (1707-1783) yazdığı ''Königsberg Köprü Problemi" adlı makale ile ortaya atıldığı düşünülse de literatürdeki bazı kaynaklar Graf Teorinin ilk bilinen örneklerinin Pisagor okuluna kadar uzandığını göstermektedir (M.Ö. 300). Königsberg kasabasının içinden akan Pregel nehrinin ortasında Şekil 1.1.'deki gibi bir ada ve bir yarımada bulunmaktadır. Bu adayı ve yarımadayı birbirine ve kıyılara bağlayan köprüleri birer kez kullanma koşulu ile, başlanılan yere geri dönebilmeyi amaçlayan bir problem ortaya atılmış ve çözümü yıllarca tartışılmıştır. Leonhard Euler (1707-1783) tarafından yayınlanan bir makalede, yıllarca tartışılan bu Königsberg Köprü Probleminin bir çözümünün olmadığını gösteren bir teori yer almaktadır. Şekil 1.1. Pregel nehri B A D C Şekil 1.2. Königsberg grafı Graflar günlük hayatta karşılaşılan pek çok problemin birer matematiksel modellemesi olup matematiğin çeşitli alanlarında var olan teorileri kullanarak üzerinde çalışılan problemlerin çözümlerinde daha kolay fikir yürütebilmeye olanak tanır. Günümüzde 1 graflara birçok bilim dalında sıklıkla başvurulmakta ve birçok problemin çözümünde graflar kullanılmaktadır. Bunlar arasında graflara başvurulan bazı problemler, kimyasal atom ve moleküller, dört renk problemi, pazarlamacı problemi, tesisat problemi, birçok , optimizasyon problemleri, kişi-toplum arası ilişkileri inceleyen problemlerdir. Aşağıda bu tezde kullanılacak olan bazı temel kavramlar tanımlanacaktır. Bu kavramlarla ilgili daha geniş bilgi için Chen (1976), Biggs ve ark. (1986), Foulds (1992), Harary (1994), West (1996), Bollobas (1998), Berge (2001), Golumbic ve Hartman (2005), Bondy ve Murty (2008), Harris ve ark. (2008), Balakrishnan ve Ranganathan (2012), Çevik ( 2010) kaynaklarına başvurulabilir. 1.1. Tanım. Köşe (vertex) denilen elemanlardan oluşan bir küme ile adına kenar (edge) denilen, her biri iki köşeyi birleştiren, elemanlardan oluşan ikinci bir kümenin elemanlarının oluşturduğu sıralı ikililer kümesine bir graf (graph) denir. Bir 𝑮 grafını çizebilmek için grafın köşelerinden oluşan 𝑽(𝑮) kümesi ile bu köşelerin birleştirilmesiyle oluşan 𝑬(𝑮) kenarların kümesini bilmek gerekir. Bilinen bu kümeler ile 𝑮 grafı G=(V(G),E(G)) şeklinde gösterilir. Biz bu grafı 𝑮(𝑽, 𝑬) ile göstereceğiz. a 𝑒1 b 𝑒 𝑒2 𝑒8 10 g 𝑒4 c 𝑒 𝑒 97 𝑒3 𝑒6 𝑒 f e 5 d Şekil 1.3. 7 köşeli ve 10 kenarlı bir graf örneği 2 Şekil 1.3.’de verilen graf örneğinin köşe kümesi 𝑉(𝐺) = { 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔} ve kenar kümesi 𝐸(𝐺) = { 𝑒1, 𝑒2, 𝑒3, 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8, 𝑒9, 𝑒10}’dir. 1.2. Tanım. 𝑉(𝐺) kümesinin eleman sayısına mertebe (order), 𝐸(𝐺) kümesinin eleman sayısına ise boyut (size) denir. 1.3. Tanım. Bir 𝐺 grafında bir 𝑢 köşesini uç kabul eden tüm kenarların sayısına bu 𝑢 köşesinin derecesi (degree) denir ve 𝒅𝒆𝒈(𝒖) ile gösterilir. Örneğin Şekil 1.3.’de 𝑑𝑒𝑔(𝑎) = 2 ve 𝑑𝑒𝑔(𝑏) = 4’tür. 1.4. Tanım. Başlangıç ve bitiş köşeleri aynı olan bir kenara döngü (loop) adı verilir. 1.5. Tanım. Herhangi iki köşesi arasında birden fazla kenara sahip olmayan ve döngü içermeyen graflara basit (simple) graf denir. Şekil 1.4. Basit bir graf Şekil 1.5. Basit olmayan bir graf A B Şekil 1.6. Basit olmayan bir graf 3 Yukarıda verilen Şekil 1.4.’deki graf basit graf iken, Şekil 1.5.’teki graf, içerdiği döngüden dolayı basit graf değildir. Şekil 1.6.’daki grafta da 𝐴 ile 𝐵 köşeleri arasında iki kenar bulunduğu için basit graf değildir. 1.6. Tanım. Bir 𝐺 grafında ∀ 𝑢, 𝑣 ∈ 𝑉(𝐺) 𝑖ç𝑖𝑛 𝑢𝑣  𝐸(𝐺) olacak şekildeki 𝑢𝑣 kenarlarının oluşturduğu grafa tümleyen (complement) graf denir ve ?̅? ile gösterilir. Şekil 1.7. G ve ?̅? grafları 1.7. Tanım. Bir 𝐺 grafında ∀ 𝑢 ∈ 𝑉(𝐺) için tüm 𝑑𝑒𝑔(𝑣) değerleri eşit ise bu grafa düzenli (regular) graf denir. Eğer 𝑑𝑒𝑔(𝑣) = 𝑛 ise grafa n-düzenli (n-regular) de denilir. Şekil 1.8. 2-düzenli graf 1.8. Tanım. Bir 𝑒 ∈ 𝐸(𝐺) alındığında, bu 𝑒 kenarı, 𝑢 ∈ 𝑉(𝐺) köşesi ile birleşiyorsa 𝑒 kenarı 𝑢 köşesi ile bitişiktir (incident) denir. 1.9. Tanım. Aralarında en az bir kenar bulunan köşelere komşu (adjacent) köşeler, ortak bir ucu bulunan kenarlara ise komşu kenarlar denir. Örneğin 𝑢, 𝑣 ∈ 𝑉(𝐺) için 𝑢𝑣 ∈ 𝐸(𝐺) ise 𝑢 ile 𝑣 köşeleri komşu köşelerdir. Eğer 𝑢𝑣  𝐸(𝐺) ise 𝑢 ile 𝑣'ye komşu olmayan (non-adjacent) köşeler denir. 4 1.10. Tanım. Köşeleri 𝑣1, 𝑣2, 𝑣3, … , 𝑣𝑛 olan 𝑛 köşeli bir 𝐺 grafında 1, 𝑣𝑖 𝑣𝑒 𝑣𝑗 𝑘𝑜𝑚ş𝑢 (𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡) 𝑘öş𝑒𝑙𝑒𝑟 𝑖𝑠𝑒[𝐴]𝑖,𝑗 = { 0, 𝑑𝑖ğ𝑒𝑟 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟𝑑𝑎 olacak şekilde 𝑛 𝑥 𝑛 tipinde yazılan [𝑨]𝒊,𝒋 kare matrisine 𝑮 grafının komşuluk (adjacency) matrisi denir ve 𝑨 ile gösterilir. 𝑣1 0 1 1 1 0 𝑣5 𝑣2 1 0 0 0 1 A= 1 0 0 1 1 1 0 1 0 1 [0 1 1 1 0] 𝑣 𝑣 4 3 Şekil 1.9. Bir 𝐺 grafı ve bu grafa ait 𝐴 komşuluk matrisi 1.11. Tanım. 𝐴 matrisi bir 𝐺 grafına ait komşuluk matrisi olmak üzere |𝐴 − 𝜆𝐼𝑛| = 0 ifadesinin kökleri olan 𝜆1, 𝜆2, ⋯, 𝜆𝑛 sayılarına 𝐴 matrisinin özdeğerleri denilir. Eşitliğin sol tarafı ile elde edilen polinoma 𝑮 grafının karakteristik polinomu denir. 1.12. Tanım. Bir 𝐺 grafına ait komşuluk matrisinin tüm özdeğerlerinin kümesine 𝑮 grafının spektrumu denir. Bir G grafının karakteristik polinomuna spektral polinom da denir. 1.13. Tanım. Bir 𝐺 grafının komşuluk matrisinin özdeğerleri 𝜆1, 𝜆2, … , 𝜆𝑛 olmak üzere bu özdeğerlerin mutlak değerlerinin toplamına 𝑮 grafının enerjisi denir ve 𝑬(𝑮) ile gösterilir. n E G |i | i1 şeklindedir. 5 Şimdi tez boyunca sıkça kullanılacak olan bazı özel graf türlerini hatırlayalım: 1.14. Tanım. Bir 𝐺 grafının bazı köşeleri 𝑣1, 𝑣2,… , 𝑣𝑡 є 𝑉 olsun. 𝑖 = 1,2, … , 𝑡 için 𝑣𝑖𝑣𝑖+1 є 𝐸 dizisine 𝐺 grafının bir yolu (walk) denir. Tüm köşeleri farklı olan yola patika (path) denir. 𝑛 köşeli bir patika Pn ile gösterilir. Şekil 1.10. 𝑷𝟓 patika grafı Tez boyunca patika için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 2 alınacaktır. 1.15. Tanım. Başlangıç ve bitiş noktaları aynı köşeye denk gelen 𝑛 köşeye sahip bir 𝐺 grafı kapalı bir patika ise bu grafa devir (cycle) graf denir ve Cn ile gösterilir. Şekil 1.11. 𝑪𝟑, 𝑪𝟒, 𝑪𝟓 devir grafları Tez boyunca devir graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 3 alınacaktır. Çünkü 𝑛 = 1 ve 𝑛 = 2 için 𝐶𝑛 = 𝑃𝑛’dir. 1.16. Tanım. Tüm köşelerin merkezdeki tek bir köşeye bağlandığı grafa yıldız (star) graf denir ve Sn ile gösterilir. 𝑆𝑛 grafında merkezdeki köşenin derecesi 𝑛 − 1, diğer köşelerin dereceleri ise 1 olur. 6 Şekil 1.12. 𝑺𝟔 yıldız grafı Tez boyunca yıldız graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 4 alınacaktır. Çünkü 𝑛 = 1,2,3 için 𝑆𝑛 = 𝑃𝑛’dir. 1.17. Tanım. Bir 𝐺 grafında her köşe çifti arasında bir kenar bulunuyorsa bu grafa tam (complete) graf denir ve Kn ile gösterilir. Şekil 1.13. 𝑲𝟑, 𝑲𝟒, 𝑲𝟓 tam grafları Tez boyunca tam graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 4 alınacaktır. Çünkü 𝑛 = 1 ve 𝑛 = 2 için 𝐾𝑛 = 𝑃𝑛 ve 𝑛 = 3 için 𝐾𝑛 = 𝐶𝑛’dir. 1.18. Tanım. Bir 𝐺(𝑉, 𝐸) grafında, 𝑉 kümesi 𝐴 ve 𝐵 gibi iki ayrık alt kümeye ayrıldığında 𝐸 kenar kümesinden alınan her bir kenarın bir köşesi 𝐴 kümesinde diğeri de 𝐵 kümesinde oluyorsa bu graflara iki parçalı (bipartite) graf denir. Eğer A kümesindeki her bir köşe 𝐵 kümesindeki her bir köşeyle birleşiyorsa bu grafa iki parçalı tam (complete bipartite) graf denir ve 𝐴 kümesinin eleman sayısı 𝑟 ve 𝐵 kümesinin eleman sayısı 𝑠 olmak üzere tam iki parçalı graf Kr,s ile gösterilir. 7 Şekil 1.14. 𝑲𝟐,𝟑 ve 𝑲𝟑,𝟑 iki parçalı tam grafı 1.19. Tanım. 𝑢 ve 𝑣, 𝐺 grafının iki köşesi olsun. Eğer 𝑢'dan 𝑣'ye giden bir patika bulunabilirse 𝑢 ve 𝑣 köşelerine 𝐺 grafında bağlantılı köşeler denir. Bir 𝐺 grafında her köşe çifti bağlantılı bir köşe çifti ise 𝐺 grafına bağlantılı graf denir. Bağlantılı olmayan grafa ise bağlantısız graf denir. 𝐺1 𝐺2 𝐺3 Şekil 1.15. Bağlantılı graf örnekleri 𝐺1 𝐺2 Şekil 1.16. Bağlantısız graf örnekleri 8 2. KURAMSAL TEMELLER Graflar, matematiğin ve belki de birçok bilim dalının en hızlı büyüyen ve genişleyen dallarından birisidir. Bunun en başlıca nedeni grafları neredeyse tüm bilimlere uygulayabilmemiz ve çok değerli bilgilere kolayca ulaşabilmemizdir. Sosyal bilimlerden pozitif bilimlere, mühendislikten ulaştırmaya, enerjiden kimyaya, fizikten biyolojiye tüm dallarda graflardan faydalanarak sonuçlar elde etmek mümkündür. Basitçe bunu açıklayacak olursak bir graf köşe ve kenarlardan oluşan bir şekildir. Bu köşeleri üzerinde çalıştığımız nesneleri modellemede kullanabiliriz. Örneğin bir moleküldeki atomları birer köşe ile modellemek oldukça yaygın bir uygulamadır. Bir ulaştırma probleminde şehirler köşelerle modellenebilir. Tüm alanlarda benzer modellemeler yapılabilir. Köşeler arasındaki kenarlar ise bu köşelere karşılık gelen nesneler arasındaki ilişkileri yansıtır. Örneğin bir moleküldeki atomlardan birbirine bir kimyasal bağla bağlı olanları, model graftaki köşeler arasına bir kenar çizerek temsil edebiliriz. Ya da ulaştırma probleminde aralarında bir yol mevcut olan şehirlere karşılık gelen köşeler arasına bir kenar çizeriz. Hayattaki birçok kavramda bu tür ilişkiler mevcut olduğundan grafların uygulama alanları da hızla artmaktadır. Modellediğimiz bir graf, matematikçiler için kolayca çalışılabilecek bir nesnedir. Bu grafı birçok matematiksel yöntem yardımıyla çalışabiliriz. Örneğin bir grafı 0 ve 1’lerden oluşan bir matrisle birebir bir şekilde ifade edebiliriz. Bu sayede bilgisayar dillerinden uygun olanları kullanabilir ve bu tür bir program yardımıyla grafın birçok parametresini hesaplayabiliriz. Küçük boyutlu graflarda el ile yapılabilecek bu işlemler, büyük boyutlu graflarda, örneğin networklerde ve sosyal medya ağlarında, bu tür programların ve yüksek hızlı işlemcilerin kullanımını gerektirmektedir. Bir grafın matrislerle çalışılması fikri yaklaşık 40 yıl önce graf enerjisini tanımlayan Ivan Gutman tarafından Gutman (1978) makalesinde tanımlanmıştır. Gutman, binlerce atıf alan bu makalesinde bir grafın komşuluk matrisini tanımlamış ve bu matrisin özdeğerlerini lineer cebir yöntemleriyle hesaplayarak bu özdeğerlerin mutlak değerlerinin toplamı ile molekülün kimyasal enerjisi arasında bir ilişki bulunduğunu göstermiştir. Bu klasikleşmiş tanım, zaman içinde farklı graf matrislerinin kullanılmasıyla yüzün üzerinde farklı graf enerjisi kavramının tanımlanmasına ve çalışılmasına neden olmuştur. Bu tezde Gutman’ın tanımladığı klasik enerji tanımı çalışılmış ve birçok yeni özellikleri elde edilmiştir. Çeşitli sık kullanılan graf sınıfları için graf enerjisinin hesaplanması, bu enerji değerleri arasında ilişkilerin kurulması esas hedef olarak belirlenmiştir. Büyük boyutlu bazı özel graf çeşitlerinin enerjilerini daha küçük boyutlu benzer grafların enerjileri yardımıyla hesaplamayı mümkün kılan indirgeme bağıntıları bu tezin en önemli sonuçları arasındadır. Ayrıca graflarda birleşim işleminin graf enerjisine etkisi, karakteristik polinom yardımıyla elde edilmiştir. Kimyada önemli uygulamaları olan alt bölüm graflarının karakteristik polinomları oluşturulmuş ve bunlar genel formüllerle ifade edilmiştir. Bu polinomlar yardımıyla alt bölüm graflarının enerjileri, grafın enerjisiyle ilişkilendirilmiştir. 9 3. MATERYAL ve YÖNTEM Matematiğin en önemli alt dallarından biri olan lineer cebir oldukça geniş bir çalışma alanına sahiptir. Matematiğin uygulama alanı bulduğu birçok bilim dalında da lineer cebir yöntemlerine sıklıkla başvurulmaktadır. Belirli kurallar çerçevesinde oluşturulan bir matrisin, determinantı yardımıyla elde edilen özdeğerleri, üzerinde çalışılan bir sistemin özel değerlerde nasıl davrandıklarını belirlemede önemli bir yer tutmaktadır. Örneğin bu değerler sisteme ait özel bir frekans değeri, dalgaların girişimi veya kuvvet dengesinin sağlandığı bir durum olabileceği gibi sisteme ait özel bir enerji türü de olabilir. Eğer verilen matris bir graf matrisi ise bu matrisin özdeğerlerinin mutlak değerleri toplamı, graf enerjisi adı verilen ve birçok uygulama alanı olan bir kavramı ortaya çıkarmaktadır. Bununla birlikte farklı graf matrislerine bağlı olarak farklı graf enerjileri de tanımlanmaktadır. Bu tezde literatürde bilinen bazı özel graf türleri için ve tezde yeni tanımlanan graflar üzerindeki bazı operasyonlar için öncelikle grafların komşuluk matrisleri oluşturulmuştur. Ardından ise lineer cebirde yer alan determinantın özellikleri, satır-sütun operasyonları gibi işlemlerle oluşturulan yeni graf türlerinin karakteristik polinomları, bu polinomların kökleri yani özdeğerleri hesaplanmış, özel indirgeme bağıntıları oluşturulmuş böylece enerjisi hesaplanmak istenen graf sistemleri için birçok kolaylaştırıcı sonuç elde edilmiştir. 10 4. GRAFLARIN SPEKTRAL POLİNOMLARI, İNDİRGEME BAĞINTILARI ve ENERJİLERİ Grafların uygulamada kullanılan önemli özelliklerinden biri, üzerinde çalışılan sistemin enerjisi hakkında bilgi veriyor oluşudur. Graf enerjisi olarak adlandırılan bu terim, ilk olarak 1930'larda, bir organik molekül sınıfı için, içinde sistemin enerjisini de bulunduran Schrödinger denkleminin yaklaşık çözümlerini bulma arayışı içinde olan Alman Matematikçi Erich Hückel tarafından ortaya atılmıştır. 1978'li yıllarda ise Ivan Gutman sadece moleküler graflar için tanımlı olan enerji kavramını tüm graflara genelleştirmiştir. Bu bölümde tez boyunca sıklıkla kullanılacak olan G = 𝑃𝑛, 𝑆𝑛, 𝐾𝑛, 𝐶𝑛 ve 𝐾𝑚,𝑛 graf türleri için bu grafların spektral polinomları verilmiş, bu polinomlar kullanılarak spektrumlarına geçilmiş ve spektrumları kullanarak da grafların enerji bağıntıları oluşturulmuştur. Bununla birlikte bu polinomların sağladıkları indirgeme bağıntılarına da yer verilmiştir. 4.1. Grafların Karakteristik Polinomları 𝐺(𝑉, 𝐸) grafı, döngü ve çoklu kenar içermeyen 𝑛 boyutlu basit ve bağlantılı bir graf olsun. 𝑣1, 𝑣2, 𝑣3, … , 𝑣𝑛 ∈ 𝑉(𝐺) için 𝐺 grafının 𝑛 × 𝑛 tipindeki komşuluk matrisi 1, 𝑣 𝑣𝑒 𝑣 [𝐴] = { 𝑖 𝑗 𝑘𝑜𝑚ş𝑢 (𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡) 𝑘öş𝑒𝑙𝑒𝑟 𝑖𝑠𝑒 𝑖,𝑗 0, 𝑑𝑖ğ𝑒𝑟 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟𝑑𝑎 olacak şekilde oluşturulur. Bu oluşturulan 𝐴 matrisi için |𝐴 − 𝜆𝐼𝑛| = 0 denkleminin kökleri 𝐺 grafının özdeğerlerini verirken eşitliğin solundaki determinantın açık hali ise 𝜆’ya bağlı, derecesi n olan bir polinom vermektedir. Bu polinoma spektral polinom, polinomun köklerinin oluşturduğu kümeye ise grafın spektrumu denir. Spektral polinom Pol(G) ile spektrum ise 𝑆(𝐺) ile gösterilir. Literatürde birçok özelliği iyi bilinen G = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarının karakteristik polinomlarını veren teorem aşağıda verilmiştir (Brouwer ve Haemers 2012). 11 Lemma 4.1.1. [Çelik 2016] G = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarının karakteristik polinomları (−1)𝑛(𝜆 + 1)𝑛−1(𝜆 − 𝑛 + 1), 𝐺 = 𝐾 𝑛 , 𝑃𝑜𝑙(𝐺) = (−𝜆)𝑛−2(𝜆2 − 𝑛 + 1), 𝐺 = 𝑆𝑛, {(−1)𝑚+𝑛𝜆𝑚+𝑛−2(𝜆2 −𝑚𝑛), 𝐺 = 𝐾𝑚,𝑛 şeklindedir. İspat. 𝐴 komşuluk matrisi oluşturulan G = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 grafları için |𝐴 − 𝜆𝐼𝑛| determinantına lineer cebirin uygun satır-sütun işlemleri uygulanılarak istenilen sonuca kolayca ulaşılmaktadır. Sonuç 4.1.2. 𝐺 = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarının spektrumları {(−1)𝑛−1, 𝑛 − 1}, 𝐺 = 𝐾 , 𝑛 𝑆(𝐺) = {0𝑛−2, ∓√𝑛 − 1}, 𝐺 = 𝑆𝑛, {{0𝑚+𝑛−2 ∓ √𝑚𝑛}, 𝐺 = 𝐾𝑚,𝑛 şeklindedir. İspat. Bir 𝐺 grafının karakteristik polinomunun köklerinin oluşturduğu kümeye o grafın spektrumu denildiği daha önce belirtilmiştir. Dolayısıyla Lemma 4.1.1.'de verilen polinomların köklerinin oluşturduğu kümenin, istenilen sonucu verdiği açıktır. Spektrumlarının elemanları, yalnızca trigonometrik ifadeler cinsinden yazılabilen 𝑃𝑛 ve 𝐶𝑛 grafları için bu grafların karakteristik polinomları aşağıda verilmiştir. Lemma 4.1.3. [Çelik 2016, Çelik ve Cangül 2017] 𝑃𝑛 yol grafının karakteristik polinomu 12 𝑛 2 𝑛 − 𝑘 ∑(−1)𝑘 ( ) 𝜆𝑛−2𝑘 , 𝑛 ç𝑖𝑓𝑡 𝑠𝑎𝑦𝚤,𝑘 𝑃𝑜𝑙(𝑃 ) = 𝑘=0𝑛 𝑛−1 2 𝑛 − 𝑘 ∑(−1)𝑘+1 ( ) 𝜆𝑛−2𝑘, 𝑛 𝑡𝑒𝑘 𝑠𝑎𝑦𝚤 { 𝑘𝑘=0 şeklindedir. İspat. 𝑃𝑛 n köşeli bir yol grafı olmak üzere bu graf için 𝐴 komşuluk matrisi oluşturulup |𝐴 − 𝜆𝐼𝑛| determinantı için gerekli satır-sütun işlemleri yapıldığında istenilen sonuca ulaşılmaktadır. Lemma 4.1.3.'de bulunan 𝑃𝑜𝑙(𝑃𝑛) polinomunun köklerinin 𝜋𝑖 𝜆𝑖 = 2𝑐𝑜𝑠 ( ) 𝑖 = 1, 2, 3, … , 𝑛 𝑛+1 şeklinde olduğu iyi bilinen bir sonuçtur (Brouwer ve Haemers 2012, Li ve ark. 2012). Dolayısıyla 𝑃𝑛 polinomunun spektrumu 𝜋𝑖 𝑆(𝑃𝑛) = {𝜆𝑖 ∶ 𝜆𝑖 = 2𝑐𝑜𝑠 ( ) , 𝑖 = 1, 2, 3, … , 𝑛 } 𝑛+1 şeklindedir. Lemma 4.1.4. [Çelik 2016] 𝑛 ≥ 3 için 𝐶𝑛 devir grafın karakteristik polinomu 𝑛−1 2 𝑛 ∑ (−1)𝑘𝑇(𝑛, 𝑘)𝜆𝑛−2𝑘 − 2 + 2(−1)2 , 𝑛 ç𝑖𝑓𝑡 𝑠𝑎𝑦𝚤, 𝑘=0 𝑃𝑜𝑙(𝐶 ( )𝑛) = 𝑛−1 2 ∑(−1)𝑘+1𝑇(𝑛, 𝑘)𝜆𝑛−2𝑘 + 2, 𝑛 𝑡𝑒𝑘 𝑠𝑎𝑦𝚤 { 𝑘=0( ) şeklindedir. Burada 𝑇(𝑛, 𝑘) sayısı, Lucas (Cardan) polinomunun katsayıları (𝑂𝐸İ𝑆 𝐴034807) olmak üzere 13 𝑇(𝑛, 0) = 1 ve 𝑛 − 𝑘 𝑛 − 𝑘 − 1 𝑛(𝑛 − 𝑘 − 1)! 𝑛 𝑇(𝑛, 𝑘) = ( ) + ( ) = , 𝑘 ≤ 𝑘 𝑘 − 1 (𝑛 − 2𝑘)! 𝑘! 2 olarak tanımlanmaktadır. İspat. 𝐶𝑛 grafının karakteristik polinomunu bulmak için tümevarım uygulanarak istenilen sonuca ulaşılmaktadır. Bulunan polinom incelendiğinde katsayıları 𝑂𝐸İ𝑆 𝐴034807'de verilen Lucas (Cardan) polinomunun katsayıları ile aynı olduğu görülmektedir. Gerekli düzenlemeler ile istenilen sonuca kolayca ulaşılmaktadır. Lemma 4.1.4.'de bulunan 𝑃𝑜𝑙(𝐶𝑛) polinomunun köklerinin 2𝜋𝑖 𝜆𝑖 = 2𝑐𝑜𝑠 ( ) 𝑖 = 0, 1, 2, 3, … , 𝑛 − 1 𝑛 şeklinde olduğu iyi bilinen bir sonuçtur (Brouwer ve Haemers 2012, Li ve ark. 2013). Dolayısıyla 𝐶𝑛 polinomunun spektrumu 2𝜋𝑖 𝑆(𝐶𝑛) = {𝜆𝑖 ∶ 𝜆𝑖 = 2𝑐𝑜𝑠 ( ), 𝑖 = 1, 2, 3, … , 𝑛 − 1 } 𝑛 şeklindedir. Örnek 4.1.5. 𝐾5 tam grafı için bu grafın polinomunu ve spektrumunu belirleyelim. 𝑛 = 5 için 𝐾𝑛 tam grafının karakteristik polinomu ve spektrumu Lemma 4.1.1. ve Sonuç 4.1.2. gereği 𝑃𝑜𝑙(𝐾 45) = −(𝜆 + 1) (𝜆 − 4) ve 𝑆(𝐾5) = { −1 4, 4} şeklindedir. 14 Örnek 4.1.6. 𝑆7 yıldız grafı için bu grafın polinomunu ve spektrumunu belirleyelim. 𝑛 = 7 için 𝑆𝑛 yıldız grafının karakteristik polinomu ve spektrumu Lemma 4.1.1. ve Sonuç 4.1.2. gereği 𝑃𝑜𝑙 (𝑆 5 27) = (−𝜆) (𝜆 − 6) ve 𝑆(𝑆 5 7) = { 0 , ∓√6} olarak bulunur. Örnek 4.1.7. 𝐾3,2 tam iki parçalı graf için bu grafın polinomunu ve spektrumunu bulalım. 𝑚 = 3, 𝑛 = 2 için 𝐾𝑚,𝑛 tam iki parçalı grafın karakteristik polinomu ve spektrumu Lemma 4.1.1. ve Sonuç 4.1.2. gereği 𝑃𝑜𝑙 (𝐾3,2) = (−1) 5 𝜆3  (𝜆2 − 6) ve 𝑆(𝐾 33,2) = { 0 , ∓√6} olarak belirlenir. Örnek 4.1.8. 𝑃6 yol grafı için bu grafın polinomunu bulalım. 𝑛 = 6 için 𝑃𝑛 yol grafının karakteristik polinomu Lemma 4.1.3. gereği 3 6 − 𝑘 𝑃𝑜𝑙 (𝑃6) = ∑(−1) 𝑘 ( ) 𝜆6−2𝑘 𝑘 𝑘=0 = 𝜆6 − 5𝜆4 + 6𝜆2 − 1 olarak bulunur. Örnek 4.1.9. 𝐶5 devir grafı için bu grafın polinomunu belirleyelim. 𝑛 = 5 için 𝐶𝑛 devir grafının karakteristik polinomu Lemma 4.1.4. gereği 15 2 𝑃𝑜𝑙 (𝐶5) = (∑(−1) 𝑘+1𝑇(5, 𝑘)𝜆5−2𝑘) + 2 𝑘=0 = −𝜆5 + 5𝜆3 − 5𝜆 + 2 olarak belirlenir. 4.2. Karakteristik Polinomların İndirgeme Bağıntıları Bir grafın enerjisini hesaplayabilmek için o grafın komşuluk matrisinden gelen özdeğerlerinin mutlak değerleri alınarak bu verilerin toplanması gerektiği Tanım 1.13.'de verilmiştir. Özdeğerlerinin hesaplanmasında oldukça kullanışlı bir yöntem olarak geliştirilen, kökleri bu özdeğerleri veren karakteristik polinomlar graf teoride önemli bir yer tutar. Bu bölümde karakteristik polinomları bilinen graflar ile köşe sayısı daha fazla olan aynı tür graflar arasında ilişkiler verilecektir (Çelik 2016). İlk olarak 𝐾𝑛 tam grafı için Pol(𝐾𝑛) polinomunun sağladığı indirgeme bağıntısı verilecektir. Teorem 4.2.1. 𝐾𝑛 tam grafı için Pol(𝐾𝑛) polinomunun sağladığı indirgeme bağıntısı, 𝑃𝑜𝑙(𝐾𝑛)=−𝜆 𝑃𝑜𝑙(𝐾𝑛−1) − (𝑛 − 1)(−λ − 1) 𝑛−2, 𝑛 ≥ 3 şeklindedir. Bu polinoma gerekli düzenlemeler yapıldığında 𝑃𝑜𝑙(𝐾𝑛) = −(𝜆 + 𝑛 − 1)𝑃𝑜𝑙 (𝐾𝑛−1)– (𝑛 − 1)(𝜆 + 1)𝑃𝑜𝑙 (𝐾𝑛−2) eşitliği elde edilir. İspat. 𝑛 köşeli bir 𝐾𝑛 tam grafının komşuluk matrisi, 16 0 1 1 1   1 0 1 1   𝐴 = 1 1 0 1     1 1 1 0 𝑛×𝑛 olup köşegeninin elemanları 0, diğer tüm elemanlarının 1 olduğu 𝑛 × 𝑛 tipinde bir kare matristir. Dolayısıyla  1 1 1 1  1 1 𝑃𝑜𝑙(𝐾𝑛) = |𝐴 − 𝜆𝐼𝑛| = 1 1  1 1 1 1  𝑛×𝑛 şeklindedir. Bu determinant birinci sütuna göre açılırsa  1 1 1 1 1 1 1 1  1 1 1  1 1 = −𝜆 − (𝑛 − 1) 1 1  1 1 1  1 1 1 1  1 1 1  (𝑛−1)×(𝑛−1) (𝑛−1)×( 𝑛−1) 1 1 1 1 1  1 1 = −𝜆𝑃𝑜𝑙(𝐾𝑛−1) − (𝑛 − 1) (𝟒. 𝟏) 1 1  1 1 1 1  (𝑛−1)×( 𝑛−1) elde edilir. Son determinanttaki birinci satır −1 ile çarpılıp diğer satırlara eklenirse 17 (1) 0 0 0 0 (1) 0 0 0 0 (1) 0 0 0 0 (1) (𝑛−2)×( 𝑛−2) determinantı elde edilir ve bu determinantın değeri olan (−1 − 𝜆)𝑛−2 değeri (4.1)’de yerine yazıldığında 𝑃𝑜𝑙(𝐾𝑛) = −𝜆 𝑃𝑜𝑙(𝐾 𝑛−2 𝑛−1) − (𝑛 − 1)(−λ − 1) ifadesinin elde edildiği kolayca görülür. Benzer şekilde yukarıdaki indirgeme bağıntısına gerekli düzenlemeler yapıldığında aşağıdaki bağıntı da elde edilebilir: Sonuç 4.2.2. 𝐾𝑛 grafının özdeğerlerini kök kabul eden 𝑃𝑜𝑙(𝐾𝑛) polinomunun indirgeme bağıntısı 𝑃𝑜𝑙(𝐾𝑛) = −(𝜆 + 𝑛 − 1)𝑃𝑜𝑙 (𝐾𝑛−1)– (𝑛 − 1)(𝜆 + 1)𝑃𝑜𝑙 (𝐾𝑛−2) şeklindedir. Bir sonraki teoremde ise 𝑆𝑛 yıldız grafı için indirgeme bağıntısı oluşturulacaktır. Teorem 4.2.3. 𝑆𝑛 yıldız grafı için 𝑃𝑜𝑙(𝑆𝑛) polinomunun sağladığı indirgeme bağıntısı 𝑃𝑜𝑙(𝑆𝑛) = −𝜆 𝑃𝑜𝑙(𝑆 ) − (−𝜆) 𝑛−2 𝑛−1 , 𝑛 ≥ 4 şeklindedir. İspat. 𝑛 köşeli bir 𝑆𝑛 tam grafının komşuluk matrisi 18 0 0 0 1   0 0 0 1   𝐴 = 0 0 0 1     1 1 1 0 𝑛×𝑛 olup, 𝑛 × 𝑛 tipinde bir matristir. Bu matriste 𝑎𝑛𝑛 = 0 olup 𝑛. satır ve 𝑛. sütundaki diğer tüm elemanlar 1 sayısına eşit iken diğer tüm elemanlar da 0’a eşittir. Dolayısıyla  0 0 1 0  0 1 𝑃𝑜𝑙(𝑆𝑛) = |𝐴 − 𝜆𝐼𝑛| = 0 0  1 1 1 1  𝑛×𝑛 şeklindedir. Bu determinant birinci sütuna göre açılırsa  0 0 1 0 0 0 1 0  0 1  0 0 1 = −𝜆 + (−1)𝑛+1 0 0  1 0  0 1 1 1 1  0 0 0 1 (𝑛−1)×(𝑛−1) (𝑛−1)×( 𝑛−1) İkinci kısımda elde edilen determinant her seferinde 1. sütuna göre açılıp bu işlem 3 × 3 tipindeki determinant elde edilene kadar tekrarlanırsa = −𝜆 𝑃𝑜𝑙(𝑆 ) + (−1)𝑛+1[(−𝜆)𝑛−4𝑛−1 (−𝜆) 𝑛−4(−𝜆)2] bağıntısı elde edilir. Uygun düzenlemeler yapılarak 𝑃𝑜𝑙(𝑆𝑛) = −𝜆𝑃𝑜𝑙(𝑆𝑛−1) − 1(−𝜆) 𝑛−2, 𝑛 ≥ 4 olduğu kolayca görülür. 19 Üçüncü olarak 𝐾𝑚,𝑛 tam iki parçalı graf için 𝑃𝑜𝑙(𝐾𝑚,𝑛) polinomunun sağladığı indirgeme bağıntısı aşağıdaki teoremde verilecektir. Teorem 4.2.4. 𝐾𝑚,𝑛 tam iki parçalı graf için 𝑃𝑜𝑙(𝐾𝑚,𝑛) polinomunun sağladığı indirgeme bağıntısı 𝑃𝑜𝑙(𝐾𝑚,𝑛) = −𝜆𝑃𝑜𝑙(𝐾𝑚−1,𝑛) − 𝑛(−𝜆) 𝑚+𝑛−2 𝑚 > 1 ve 𝑃𝑜𝑙( 𝐾1,𝑛) = −𝜆𝑃𝑜𝑙( 𝐾1,𝑛−1) − (−𝜆) 𝑛−1 𝑚 = 1 olacak şekilde yazılabilir. İspat. 𝑚 = 1 için 𝐾1,𝑛 grafı 𝑆𝑛+1 yıldız grafı ile 𝐾1,𝑛−1 grafı da 𝑆𝑛 yıldız grafı aynı yapıya sahiplerdir. Dolayısıyla Teorem 4.2.3.'de gerekli düzenlemeler yapılarak istenilen sonuca ulaşılır. 𝑚 > 1 için Lemma 4.1.1.'de verilen 𝐾𝑚,𝑛 grafının polinomunda uygun düzenlemeler yapılarak 𝑃𝑜𝑙(𝐾 ) = (−1)𝑚+𝑛𝜆𝑚+𝑛−2(𝜆2𝑚,𝑛 −𝑚𝑛) = (−𝜆)𝑚+𝑛−2(𝜆2 −𝑚𝑛) = (−𝜆)(−𝜆)𝑚+𝑛−3(𝜆2 −𝑚𝑛 + 𝑛 − 𝑛) = −𝜆[(−𝜆)𝑚+𝑛−3(𝜆2 −𝑚𝑛 + 𝑛)] − 𝑛(−𝜆)𝑚+𝑛−2 = −𝜆𝑃𝑜𝑙(𝐾𝑚−1,𝑛) − 𝑛(−𝜆) 𝑚+𝑛−2 Teorem 4.2.4.'ün ispatı tamamlanır. Bundan sonraki iki teoremde ise 𝑃𝑛 yol graflarının ve 𝐶𝑛 devir graflarının karakteristik polinomlarının sağladıkları indirgeme bağıntıları oluşturulacaktır. 20 Teorem 4.2.5. 𝑃𝑛 yol grafı için 𝑃𝑜𝑙(𝑃𝑛) polinomunun sağladığı indirgeme bağıntısı 𝑃𝑜𝑙(𝑃𝑛) = −𝜆𝑃𝑜𝑙(𝑃𝑛−1) − 𝑃𝑜𝑙(𝑃𝑛−2), 𝑛 ≥ 3 şeklindedir. İspat. 𝑛 köşeli bir 𝑃𝑛 yol grafının komşuluk matrisi 0 1 0 0   1 0 1 0   𝐴 = 0 1 0 0     0 0 0 0 𝑛×𝑛 olup karakteristik polinom tanımından  1 0 0 1  1 0 𝑃𝑜𝑙(𝑃𝑛) = |𝐴 − 𝜆𝐼| = 0 1  0 0 0 0  𝑛×𝑛 elde edilir. Bu determinant birinci satıra göre açılırsa  1 0 0 1 1 0 0 1  1 0 0  1 0 = −𝜆 − 0 1  0 0 1  0 0 0 0  0 0 0  (𝑛−1)×(𝑛−1) (𝑛−1)×( 𝑛−1) ifadesine ulaşılır. Burada soldaki determinantın değeri 𝑃𝑜𝑙(𝑃𝑛−1)’e eşit olurken sağdaki determinant birinci sütuna göre tekrar açılırsa 21  1 0 0 1  1 0 = −𝜆𝑃𝑜𝑙(𝑃𝑛−1) − 0 1  0 0 0 0  (𝑛−2)×(𝑛−2) ifadesi elde edilir. Son elde edilen determinantın 𝑃𝑜𝑙(𝑃𝑛−2)’yi veren determinant olduğu açıktır. Buradan hareketle 𝑃𝑜𝑙(𝑃𝑛) = −𝜆𝑃𝑜𝑙(𝑃𝑛−1) − 𝑃𝑜𝑙(𝑃𝑛−2) olduğu kolayca görülür. Teorem 4.2.6. 𝐶𝑛 devir grafı için 𝑃𝑜𝑙(𝐶𝑛) polinomunun sağladığı indirgeme bağıntısı 𝑃𝑜𝑙(𝐶𝑛) = −𝜆𝑃𝑜𝑙(𝐶𝑛−1) − 𝑃𝑜𝑙(𝐶𝑛−2) + (−1) n𝑃𝑜𝑙(𝐶1), 𝑛 ≥ 3 şeklindedir. İspat. 𝑃𝑜𝑙(𝑃𝑛) ifadesinin indirgeme bağıntısı için uygulanan işlem basamaklarının benzerleri 𝑃𝑜𝑙(𝐶𝑛) için de uygulanarak istenilen indirgeme bağıntısı kolayca elde edilir. 4.3. Grafların Enerji Bağıntıları İlk olarak Erick Hückel tarafından ortaya atılan grafların enerjisi kavramı, moleküler grafların bazı özelliklerini çalışmada oldukça fayda sağladığından, Kimyasal Graf Teori'de önemli bir yere sahiptir. Özellikle literatürde sık kullanılan ve birçok özelliği iyi bilinen bazı özel graf türleri için bu grafların enerjileri bu bölümde hatırlatılacaktır. Tanım 1.13.'de de belirtildiği gibi bir grafın enerjisi, o grafa ait spektrumun tüm elemanlarının mutlak değerce toplamına eşittir. Bu tanım gereği n köşeli bir 𝐺 grafının spektrumu {𝜆𝑖, 𝑖 = 1,2,⋯ , 𝑛} olmak üzere grafın enerjisi 22 𝑛 𝐸(𝐺) =∑|𝜆𝑖| 𝑖=1 bağıntısı ile hesaplanır. Buradan hareketle bu bölümde G = 𝐾𝑛, 𝑆𝑛, 𝐾𝑚,𝑛, 𝑃𝑛 ve 𝐶𝑛 grafları için enerji bağıntıları verilecektir. Enerji kavramı ile ilgili ek bilgi olarak Gutman (1978), Walikar ve ark. (1999), Adiga ve ark. (2007), Nikiforov (2007) çalışmalarına bakılabilir. Lemma 4.3.1. [Çelik 2016] 𝐺 = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarının enerji bağıntıları 2(𝑛 − 1), 𝐺 = 𝐾𝑛, 𝐸(𝐺) = 2|√𝑛 − 1|, 𝐺 = 𝑆𝑛, {2|√𝑚𝑛|, 𝐺 = 𝐾𝑚,𝑛 şeklindedir. İspat. 𝐺 = 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarının her biri için Sonuç 4.1.2.'de verilen spektrumların elemanlarının mutlak değerleri alınarak toplandığında istenilen sonuca kolayca ulaşıldığı görülmektedir. Burada 𝑃𝑛 ve 𝐶𝑛 graflarının özdeğerleri trigonometrik değerler içerdiğinden enerji bağıntıları da diğer graflara göre farklılık göstermektedir. Bu graflar için enerji bağıntılarına ulaşırken faydalandığımız Çelik ve Cangul (2016)'da verilen aşağıdaki sonuçları hatırlayalım. Lemma 4.3.2. 𝑃𝑛’in spektrumunda her 𝑘 = 1, 2, … , 𝑛 için 𝜆𝑘 = −𝜆𝑛+1−𝑘 olur. 23 𝜋𝑖 İspat. 𝑆(𝑃𝑛) = {𝜆𝑖 ∶ 𝜆𝑖 = 2𝑐𝑜𝑠 ( ) , 𝑖 = 1, 2, 3, … , 𝑛} olmak üzere 𝑛+1 𝜋(𝑛+1−𝑘) 𝜆𝑛+1−𝑘 = 2𝑐𝑜𝑠 ( ) 𝑛+1 𝜋(𝑛+1) 𝜋𝑘 = 2 𝑐𝑜𝑠 ( − ) 𝑛+1 𝑛+1 𝜋𝑘 = 2 𝑐𝑜𝑠 (𝜋 − ) 𝑛+1 𝜋𝑘 =−2𝑐𝑜𝑠 ( ) 𝑛+1 = −𝜆𝑘. Lemma 4.3.3. 𝐶𝑛’in spektrumunda her 𝑘 = 0,1, 2, … , 𝑛 − 1 için 𝜆𝑘 = 𝜆𝑛−𝑘 olur. 2𝜋(𝑛−𝑘) 2𝜋𝑛 2𝜋𝑘 İspat. 𝜆𝑛−𝑘 = 2 𝑐𝑜𝑠 ( ) = 2 𝑐𝑜𝑠 ( − ) 𝑛 𝑛 𝑛 2𝜋𝑘 = 2 𝑐𝑜𝑠 (𝑛 − ) 𝑛 2𝜋𝑘 = 2 𝑐𝑜𝑠 (− ) 𝑛 2𝜋𝑘 = 2 𝑐𝑜𝑠 ( ) 𝑛 = 𝜆𝑘. Teorem 4.3.4. 𝑃𝑛 bir yol grafı olmak üzere yol grafının enerjisi 𝑛−1 2 𝑛 2∑|𝜆𝑖| 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛, 𝜋𝑖 𝐸(𝑃𝑛) =∑2 |cos ( )| = 𝑖=1 𝑛 + 1 𝑛 𝑖=1 2 2∑|𝜆𝑖| 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 { 𝑖=1 şeklindedir. 24 İspat. {𝜆𝑖 | 𝑖 = 1, 2, 3, … , 𝑛} kümesi 𝑃𝑛’in spektrumu olmak üzere enerji tanımından 𝑛 𝜋𝑖 𝐸(𝑃𝑛) =∑2 |cos ( )| 𝑛 + 1 𝑖=1 elde edilir. Bununla birlikte ilk olarak Lemma 4.3.2. gereği 𝑛 tek sayı iken 𝜆1 = −𝜆𝑛, 𝜆2 = 𝜆𝑛−1, …, 𝜆𝑛−1 = 𝜆𝑛+3 ve 𝜆𝑛+1 = 0 2 2 2 olur. Dolayısıyla 𝑛−1 2 𝐸(𝑃𝑛) = 2∑|𝜆𝑖| 𝑖=1 olduğu kolayca görülür. İkinci olarak n çift sayı iken Lemma 4.3.2. gereği 𝜆1 = −𝜆𝑛, 𝜆2 = 𝜆𝑛−1, …, 𝜆𝑛 = 𝜆𝑛+2 2 2 olur. Buradan da enerjinin tanımı kullanılarak 𝑃𝑛 grafının enerjisinin 𝑛 2 𝐸(𝑃𝑛) = 2∑|𝜆𝑖| 𝑖=1 olduğu kolaylıkla yazılabilir. 25 Teorem 4.3.5. 𝑛 ≥ 3 için 𝐶𝑛 bir devir grafı olmak üzere bu grafın enerjisi 𝑛−1 2 𝑛−1 2 + 2∑|𝜆𝑖| 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛, 2𝜋𝑖 𝐸(𝐶𝑛) = ∑2 |cos ( )| = 𝑖=1 𝑛 𝑛−2 𝑖=0 2 4 + 2∑|𝜆𝑖| 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 { 𝑖=1 şeklindedir. İspat.{𝜆𝑖 | 𝑖 = 0,1, … , 𝑛 − 1} kümesi 𝐶𝑛’in spektrumu olmak üzere enerji tanımından 𝑛−1 2𝜋𝑖 𝐸(𝐶𝑛) = ∑2 |cos ( )| 𝑛 𝑖=0 elde edilir. Burada ilk olarak 𝑛 tek olduğu durumda Lemma 4.3.3. gereği 𝜆0 = 2, 𝜆1 = 𝜆𝑛−1, 𝜆2 = 𝜆𝑛−2, …, 𝜆𝑛−1 = 𝜆𝑛+1 2 2 elde edilir. Enerji tanımından 𝑛−1 𝑛−1 2 𝐸(𝐶𝑛) = ∑|𝜆𝑖| = 2 + 2∑|𝜆𝑖| 𝑖=0 𝑖=1 olduğu kolayca görülür. İkinci olarak 𝑛 çift olduğu durumda Lemma 4.3.3. gereği 𝜆0 = 2, 𝜆1 = 𝜆𝑛−1, 𝜆2 = 𝜆𝑛−2, … , 𝜆𝑛−2 = 𝜆𝑛+2 2 2 elde edilir. Enerji tanımı kullanılarak 26 𝑛−2 𝑛−1 2 𝐸(𝐶𝑛) = ∑|𝜆𝑖| = 4 + 2∑|𝜆𝑖| 𝑖=0 𝑖=1 olduğu kolaylıkla görülür. Yukarıda verilen 𝐸(𝐶𝑛) bağıntısına alternatif olarak Li ve ark. ( 2012)’da 𝜋 4 cot 𝑛 ≡ 0(𝑚𝑜𝑑4) 𝑛𝜋 𝐸(𝐶𝑛) = 4 csc 𝑛 ≡ 2(𝑚𝑜𝑑4) 𝑛 𝜋 {2 csc 𝑛 ≡ 1(𝑚𝑜𝑑2)2𝑛 bağıntısı da verilmiştir. Örnek 4.3.6. Köşe sayısı 8 olan tam grafın enerjisi Lemma 4.3.1. gereği 𝐸(𝐾8) = 2. (8 − 1) = 14 şeklindedir. Örnek 4.3.7. Köşe sayısı 5 olan yıldız grafın enerjisi Lemma 4.3.1. gereği 𝐸(𝑆5) = 2|√5 − 1| = 4 şeklindedir. Örnek 4.3.8. Köşe sayısı 13 olan iki parçalı tam grafın enerjisi Lemma 4.3.1. gereği 𝐸(𝐾4,9) = 2|√4.9| = 12 şeklindedir. 27 Örnek 4.3.9. Köşe sayısı 16 olan yol grafın enerjisi Teorem 4.3.4. gereği 16 8 𝜋𝑖 𝐸(𝑃16) =∑|𝜆𝑖| = 2∑|2cos | 17 𝑖=1 𝑖=1 şeklindedir. Örnek 4.3.10. Köşe sayısı 7 olan yol grafın enerjisi Teorem 4.3.4. gereği 7 3 𝜋𝑖 𝐸(𝑃7) =∑|𝜆𝑖| = 2∑|2cos | 8 𝑖=1 𝑖=1 şeklindedir. Örnek 4.3.11. Köşe sayısı 7 olan devir grafın enerjisi Teorem 4.3.5. gereği 6 3 2𝜋𝑖 𝐸(𝐶7) =∑|𝜆𝑖| = 2 + 2∑|2cos | 7 𝑖=0 𝑖=1 şeklindedir. Örnek 4.3.12. Köşe sayısı 16 olan devir grafın enerjisi Teorem 4.3.5. gereği 15 7 2𝜋𝑖 𝐸(𝐶16) =∑|𝜆𝑖| = 4 + 2∑|2cos | 16 𝑖=0 𝑖=1 şeklindedir. 28 5.GRAFLARDA ENERJİ İNDİRGEME BAĞINTILARI Grafların uygulama alanlarından enerji kavramı, graf teoride oldukça önemli bir yer tutmaktadır. Bu doğrultuda birçok graf türünün enerjisini hesaplamada kolaylık sağlayan bağıntılar geliştirilmiştir. Bu bölümde literatürden de iyi bilinen bazı graf türleri için, aynı türe ait graflarda, köşe sayısı daha küçük olan graflar ile köşe sayısı daha büyük olan graflar arasındaki enerji ilişkileri incelenecek, incelemelerin sonunda yeni enerji indirgeme bağıntıları oluşturulacaktır. Bununla birlikte özellikle köşe sayısı 2'nin kuvvetleri şeklinde olan devir grafları için enerji hesaplamada yeni yöntemler geliştirilecektir. 5.1. 𝑪𝒏 Devir Grafında Enerji İndirgeme Bağıntısı 𝐶𝑛 bir devir graf olmak üzere, literatürden de bilindiği gibi bu graf türünün spektrumunun 2𝜋𝑖 elemanları 𝜆𝑖 = 2 cos ( ), 𝑖 = 0,1,2, … , 𝑛 − 1 şeklindedir. Burada daha önce 𝐶𝑛 için 𝑛 bulunan spektrumlar arası geçiş bağıntıları kullanılarak 2𝑛 köşeye sahip devir grafının enerjisini hesaplamaya yarayan yeni ve kullanışlı bir bağıntı geliştirilecektir (Çelik 2016). 𝐶𝑛 grafının enerji indirgeme bağıntısına geçmeden önce, enerji için gerekli olan spektrumun elemanlarında gerekli düzenlemeler yapılmalıdır. Bu grafın spektrumunun elemanlarını ayrı ayrı hesaplamak yerine Lemma 4.3.3. kullanılarak 𝜆0, 𝜆1, 𝜆2, ..., 𝜆 𝑛 ⟦ ⟧ 2 değerlerini hesaplamak daha kullanışlı olacaktır. Bununla birlikte 𝑛 ≥ 3 için 𝐶𝑛 grafının spektrumu 𝑆(𝐶𝑛) = {𝜆0, 𝜆1, 𝜆2, ..., 𝜆𝑛−2, 𝜆𝑛−1} şeklinde ve 𝐶2𝑛 grafının spektrumu 𝑆(𝐶2𝑛) = {µ0, µ1,..., µ2𝑛−2, µ2𝑛−1} şeklinde gösterildiğinde her 𝑗 = 1, 2, 3… , 2𝑛 − 1 için 𝜆𝑖 ve µ𝑗 arasında 2𝜋2𝑗 2𝜋𝑗 µ2𝑗 = 2 cos ( ) = 2 cos ( ) = 𝜆2𝑛 𝑛 𝑗 bağıntısı vardır. Trigonometrik yarım açı formülleri kullanılarak her 𝑘 = 1, 2, … , 𝑛 − 1 için 29 µ𝑘 = µ2𝑛−𝑘 = ∓√𝜆𝑘 + 2 bağıntısı elde edilir (Çelik 2016). İlk olarak 𝐶2𝑛 grafının enerjisini hesaplamak için geliştirilen bağıntı verilecektir. Teorem 5.1.1. 𝑛 ≥ 3 için 𝐸(𝐶2𝑛) ifadesi 2 𝑛 köşeye sahip devir grafının enerjisi olmak üzere 𝐸(𝐶2𝑛) = 4 1 + √2 + 2√√2 + 2 + 2 2√√√2 + 2 + 2 +⋯ ( + 2𝑛−3√√…√√√2 + 2 + 2 +⋯+ 2 ) şeklindedir. Burada son terimde 𝑛 − 2 tane karekök iç içedir. İspat. Eşitliğin doğruluğu tümevarım yöntemi kullanılarak gösterilecektir. Tümevarımın ilk adımı olarak 𝑛 = 3 değeri için teoremin doğruluğu incelensin. 𝑆(𝐶4) = 𝑆(𝐶22) = {𝜆0, 𝜆1, 𝜆2, 𝜆3} ve 𝑆(𝐶8) = 𝑆(𝐶23) = {𝜇0, 𝜇1, … , µ7} şeklinde olsun. Burada 𝑆(𝐶4 ) = {𝜆0 = 2, 𝜆1 = 0, 𝜆2 = −2, 𝜆3 = 0} olup yukarıda verilen bağıntılar kullanılarak 30 𝜇0 = 𝜆0 = 2, 𝜇2 = 𝜆1 = 0, 𝜇4 = 𝜆2 = −2, 𝜇6 = 𝜆3 = 0 ve µ1 = µ7 = √𝜆1 + 2, µ3 = µ5 = √𝜆3 + 2 elde edilir. Bu değerler teoremde yerine yazılırsa 7 𝐸(𝐶23) =∑|𝜇𝑖| = |𝜇0| + |𝜇1| + |𝜇2| + |𝜇3| + |𝜇4| + |𝜇5| + |𝜇6| + |𝜇7| 𝑖=0 =|𝜆0| + |𝜆1|+|𝜆2| + |𝜆3| + 2(|𝜇1| + |𝜇3|) = 𝐸(𝐶4) + 2(√𝜆1 + 2 + √𝜆3 + 2) = 4(1 + √2) olur. Böylece 𝑛 = 3 için teoremin doğruluğu açıktır. Şimdi 𝐶2𝑛−1 'nin spektrumunun {𝛽0, 𝛽1, 𝛽2, ..., 𝛽2𝑛−1−1} olduğu ve teoremin 𝐶2𝑛−1 için de doğru olduğu kabul edilsin. Spektrumun (2𝑘 + 1). terimi 𝛽 √√ √√2𝑘+1 = … √2 + 2 + 2 +⋯+ 2 şeklinde 𝑛 − 3 kez karekök ifadesinin kullanılmasıyla hesaplanır. Tüm bunlar göz önünde bulundurularak 𝐶2𝑛−1 'in enerjisi 31 𝐸(𝐶2𝑛−1) = 4 1 + √2 + 2√√2 + 2 + 2 2√√√2 + 2 + 2 +⋯ ( + 2𝑛−4√√…√√√2 + 2 + 2 +⋯+ 2 ) şeklinde ifade edilebilir. Tümevarımın son adımında ise köşe sayısı 2𝑛 olan her devirli graf için enerji 2𝑛−1 𝐸(𝐶2𝑛) = ∑ |𝛼𝑘| 𝑘=0 2𝑛−1−1 2𝑛−1−1 = ∑ |𝛼2𝑘| + ∑ |𝛼2𝑘+1| 𝑘=0 𝑘=0 2𝑛−1−1 2𝑛−1−1 = ∑ |𝛽𝑘| + ∑ |√𝛽2𝑘+1 + 2| 𝑘=0 𝑘=0 = 4 (1 + √2 + 2√√2 + 2 +⋯ +2𝑛−3√√…√√√2 + 2 + 2 +⋯+ 2 ) olup verilen teoremin her 𝑛 ≥ 3, 𝑛 ∈ 𝑁 için doğruluğu kanıtlanmış olur. Teorem 5.1.2. 𝑛 ≥ 3 olmak üzere 𝐶2𝑛 devirli grafının enerjisi için indirgeme bağıntısı 32 𝐸(𝐶 𝑛) = 𝐸(𝐶 ) + 2𝑛−1√√𝑛−1 …√√2 2 √2 + 2 + 2 +⋯+ 2 şeklindedir. Burada eşitliğin sağında 𝑛 − 3 kez karekök iç içedir. Örnek 5.1.3. 𝐸(𝐶32) değerini hesaplayalım. 𝐸(𝐶32) = 𝐸(𝐶25) olduğundan Teorem 5.1.1. kullanılarak 𝐸(𝐶25) = 4(1 + √2 + 2√√2 + 2 + 2 2√√√2 + 2 + 2) ≈ 55,808 olduğu hesaplanır. Örnek 5.1.4. 𝐸(𝐶64) değerini hesaplayalım. 𝐸(𝐶64) = 𝐸(𝐶26) olduğundan Teorem 5.1.1. kullanıldığında 𝐸(𝐶 6) = 4(1 + √2 + 2√√2 + 2 + 22√√2 √2 + 2 + 2 +23√√√√2 + 2 + 2 + 2) ≈ 119,496 değerine ulaşılır. 33 Örnek 5.1.5. 𝐸(𝐶32) ≈ 55,808 olarak veriliyor. Buna göre 𝐸(𝐶64) ≈ 119,496 olduğunu Teorem 5.1.2.'yi kullanarak gösterelim. 𝐸(𝐶26) = 𝐸(𝐶 ) + 2 5√ 5 √√2 √2 + 2 + 2 + 2 ≈ 55,808 + 32.1,990 ≈ 119,496. Devir grafında spektrumun elemanlarının trigonometrik ifadeler olması, diğer bazı özel graf türlerine göre, literatürdeki bilgilere alternatif olacak farklı sonuçlar ortaya çıkarmaktadır. Bir sonraki teoremde 𝑛 ≥ 3 için spektrumu ve enerjisi bilinen 𝐶𝑛 grafınının verilerini kullanarak 2𝑛 köşeye sahip 𝐶2𝑛 grafının enerjisini hesaplamada kolaylık sağlayan indirgeme bağıntısı verilecektir. Teorem 5.1.6. 𝑛 ≥ 3 için, 𝑆(𝐶𝑛) = {𝜆0, 𝜆1, 𝜆2, ..., 𝜆𝑛−2, 𝜆𝑛−1} olsun. 𝐸(𝐶𝑛) ile 𝐸(𝐶2𝑛) arasındaki ilişki 𝑛 2 ∑√𝜆2𝑗−1 + 2, 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 𝐸(𝐶2𝑛) − 𝐸(𝐶𝑛) 𝑗=1 = 𝑛−1 2 2 ∑√𝜆2𝑗−1 + 2, 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛 { 𝑗=1 şeklindedir. İspat. Enerjinin tanımından 𝑛−1 𝐸(𝐶𝑛) = ∑|𝜆𝑗| 𝑗=0 34 olduğu bilinmektedir. Bununla birlikte Çelik ve Cangül (2017)'de verilen 𝑆(𝐶𝑛) ve 𝑆(𝐶2𝑛) arasındaki bağıntıdan 𝑛 ⟦ ⟧ 𝐸(𝐶2𝑛) = 𝐸(𝐶𝑛) + ∑ 2 𝑗=1√𝜆2𝑗−1 + 2 elde edilir. Buradan da 𝑛 2 ∑√𝜆 2𝑗−1 + 2, 𝑚 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 𝐸(𝐶2𝑛) − 𝐸(𝐶𝑛) 𝑗=1 = 2 𝑛−1 2 ∑√𝜆2𝑗−1 + 2, 𝑚 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛 { 𝑗=1 sonucuna ulaşılır. 5.2. 𝑷𝒏 Yol Grafında Enerji İndirgeme Bağıntısı 𝑃𝑛 bir yol grafı olmak üzere bu graf türünün spektrumunun elemanlarının trigonometrik bağıntılarla hesaplanması spektrumlar arası geçişlerde farklılıklar gösterdiği gibi enerjiler arası geçişlerde de farklılıklar göstermektedir. Bir sonraki teoremde 𝐸(𝑃𝑛) ile 𝐸(𝑃2𝑛) arasındaki ilişki verilecektir. Teorem 5.2.1. 𝑛 ≥ 1 için, 𝑆(𝑃𝑛) = {𝜆1, 𝜆2, ..., 𝜆𝑛−1, 𝜆𝑛} olsun. 𝐸(𝑃𝑛) ile 𝐸(𝑃2𝑛) arasında 𝑛 2 ∑√𝜆2𝑗−1 + 2, 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 𝐸(𝑃2𝑛) − 𝐸(𝑃𝑛) 𝑗=1 = 2 𝑛−1 2 ∑√𝜆2𝑗−1 + 2, 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛 { 𝑗=1 bağıntısı vardır. 35 İspat. Enerjinin tanımından 𝑛 𝐸(𝑃𝑛) =∑|𝜆𝑗| 𝑗=1 olduğu bilinmektedir. Bununla birlikte Celik ve Cangül(2017)'de verilen 𝑆(𝑃𝑛) ve 𝑆(𝑃2𝑛) arasındaki bağıntıdan 𝑛 ⟦ ⟧ 𝐸(𝑃 22𝑛) = 𝐸(𝑃𝑛) + ∑ √𝜆2𝑗−1 + 2 𝑗=1 elde edilir ve buradan da 𝑛 2 ∑√𝜆2𝑗−1 + 2, 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛 𝐸(𝑃2𝑛) − 𝐸(𝑃𝑛) 𝑗=1 = 2 𝑛−1 2 ∑√𝜆2𝑗−1 + 2, 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛 { 𝑗=1 sonucu elde edilir. 5.3. 𝑲𝒏 Tam Grafında Enerji İndirgeme Bağıntısı 𝐾𝑛 tam grafının spektrumun elemanlarının −1 (𝑛−1) ve 𝑛 − 1 olduğu Sonuç 4.1.2.'de verilmiştir. Enerji tanımı gereği bu değerlerin mutlak değerlerinin toplamı olan 2(𝑛 − 1) değeri 𝐸(𝐾𝑛) değerine eşittir. 𝐸(𝐾𝑛) ile 𝐸(𝐾2𝑛−1) arasındaki indirgeme bağıntısı aşağıdaki teoremde verilecektir. Teorem 5.3.1. 𝑛 ≥ 3 için 𝐸(𝐾2𝑛−1) tam grafının enerji indirgeme bağıntısı 𝐸(𝐾2𝑛−1) = 2𝐸(𝐾𝑛) 36 şeklindedir. İspat. Özel bazı graf türlerinin enerjileri için Çelik (2016), Çelik ve Cangül (2017), Brouwer ve Haemers (2012), Li ve ark. (2012) çalışmalarına bakıldığında 𝐾𝑛 tam grafının spektrumun elemanlarının −1(𝑛−1) ve 𝑛 − 1 olduğu ve enerji tanımından da enerjisinin 2(𝑛 − 1) değerine eşit olduğu bilinen bir sonuçtur. Buradan hareketle Lemma 4.3.1. kullanılarak 𝐸(𝐾2𝑛−1) = 2(2𝑛 − 1 − 1) = 2(2𝑛 − 2) = 2.2(𝑛 − 1) = 2𝐸(𝐾𝑛) elde edilir. 5.4. 𝑲𝒎,𝒏 İki Parçalı Tam Grafta Enerji İndirgeme Bağıntısı 𝐾𝑚,𝑛 iki parçalı tam grafının spektrumunun elemanlarının 0 (𝑚𝑛−2) ve ∓√𝑚𝑛 şeklinde, enerjisinin ise 2√𝑚𝑛 şeklinde olduğu Sonuç 4.1.2.'de ve Lemma 4.3.1.'de verilmiştir. Bir sonraki teoremde ise 𝐸(𝐾𝑚,𝑛) ile 𝐸(𝐾2𝑚,𝑛) arasındaki indirgeme bağıntısı verilecektir. Teorem 5.4.1. 2𝑚 + 𝑛 köşeli iki parçalı tam bir grafın enerjisini veren 𝐸(𝐾2𝑚,𝑛) ile veya 𝑚 + 2𝑛 köşeli iki parçalı tam bir grafın enerjisini veren 𝐸(𝐾𝑚,2𝑛) ile 𝑚+ 𝑛 köşeli iki parçalı tam grafın enerjisini veren 𝐸(𝐾𝑚,𝑛) arasında 𝐸(𝐾2𝑚,𝑛) = 𝐸(𝐾𝑚,2𝑛) = √2𝐸(𝐾𝑚,𝑛) olacak şeklinde bir indirgeme bağıntısı vardır. İspat. Lemma 4.3.1.'den 37 𝐸(𝐾2𝑚,𝑛) = 𝐸(𝐾𝑚,2𝑛) = 2√2𝑚𝑛 = 2√2√𝑚𝑛 = √2𝐸(𝐾𝑚,𝑛) sonucuna ulaşılır. Bununla birlikte köşe sayısı 𝑟𝑚 + 𝑠𝑛 olan iki parçalı tam grafı için enerji indirgeme bağıntısı aşağıda sonuçta verilmiştir. Sonuç 5.4.2. 𝐾𝑟𝑚,𝑠𝑛 grafı için enerji indirgeme bağıntısı 𝐸(𝐾𝑟𝑚,𝑠𝑛) = √𝑟𝑠 ∙ 𝐸(𝐾𝑚,𝑛) şeklindedir. İspat. Lemma 4.3.1.'den 𝐸(𝐾𝑟𝑚,𝑠𝑛) = 2√𝑟𝑚 ∙ 𝑠𝑛 = 2√𝑟𝑠 ∙ √𝑚𝑛 = √𝑟𝑠 ∙ 𝐸(𝐾𝑚,𝑛) olup istenilen bağıntı elde edilir. 5.5. 𝑺𝒏 Yıldız Grafında Enerji İndirgeme Bağıntısı 𝑆 yıldız grafının özdeğerlerinin 0(𝑛−2)𝑛 ve ∓√𝑛 − 1, enerjisinin ise 2√𝑛 − 1 olduğu Sonuç 4.1.2.'de ve Lemma 4.3.1.'de verilmiştir. Burada ise bu veriler kullanılarak 𝐸(𝑆𝑛) ile 𝐸(𝑆2𝑛−1) arasında enerji indirgeme bağıntısı verilecektir. Teorem 5.5.1. n köşeli yıldız grafın enerjisi ile 2𝑛 − 1 köşeli yıldız grafın enerjisi arasında 38 𝐸(𝑆2𝑛−1) = √2𝐸(𝑆𝑛) şeklinde bir indirgeme bağıntısı vardır. İspat. Lemma4.3.1. kullanıldığında 𝐸(𝑆2𝑛−1) = 2√2𝑛 − 1 − 1 = 2√2𝑛 − 2 = 2√2√𝑛 − 1 = √2𝐸(𝑆𝑛) olacak şekilde indirgeme bağıntısı elde edilir. 39 6. GRAFLARDA BİRLEŞİM ve BİRLEŞİMİN KARAKTERİSTİK POLİNOM ÜZERİNDEKİ ETKİSİ Günlük hayatta sık sık karşılaştığımız ve kullanım alanı oldukça yaygın olan grafların incelenmesi ve bu graflar üzerinde yapılan çalışmalar akıllara farklı sorular getirmekte, bunun da bir sonucu olarak graflar üzerinde pek çok operasyonlar tanımlanmaktadır. İki grafın kartezyen çarpımı, belirlenen bir köşeden iki grafın birleşimi, bir kenar ile köprü kurularak birleşim, bir graftan kenar ekleme ya da kenar silme, köşe ekleme ya da graftan köşe silme gibi pek çok operasyon tanımlanabilmektedir. Örneğin 𝐺1 = (𝑉1, 𝐸1) ve 𝐺2 = (𝑉2, 𝐸2) olarak verilen iki grafın birleşimi denildiğinde klasik birleşim işlemi düşünülerek 𝐺1 ∪ 𝐺2 = (𝑉1 ∪ 𝑉2, 𝐸1 ∪ 𝐸2) grafı oluşturulur. Bu bölümde klasik birleşim yönteminden farklı olarak 𝐾𝑛, 𝑆𝑛 ve 𝑃𝑛 grafları için iki yeni birleşim metodu tanımlanacak, birleşim sonucunda oluşan yeni grafların karakteristik polinomları belirlenecek ve bu polinomlar ile bileşenlerin karakteristik polinomları arasındaki ilişki araştırılacaktır. 6.1. İki Grafın Bir Köşede Birleşimi Bu bölümde üzerinde çalışılacak olan yeni bir birleşim metodu tanımlanacaktır: Tanım 6.1. 𝐺1 ve 𝐺2 iki graf olsun. 𝑉(𝐺1) ve 𝑉(𝐺2) kümelerinden belirlenen birer köşe 𝑣 olarak isimlendirilsin. Bu 𝑣 köşelerini özdeşleyecek şekilde iki graf 𝑣 köşesinde birleştirilsin. Elde edilen grafa, verilen grafların 𝒗 köşesinde birleşimi denir ve 𝑮𝟏 ⋁𝒗𝑮𝟐 ile gösterilir. Burada 𝐺1⋁𝑣𝐺2 grafının köşe kümesi 𝑉(𝐺1⋁𝑣𝐺2) = 𝑉(𝐺1) ∪ 𝑉(𝐺2) ve kenar kümesi 𝐸(𝐺1⋁𝑣𝐺2) = 𝐸(𝐺1) ∪ 𝐸(𝐺2) dir. Ayrıca |𝑉(𝐺1)| = 𝑛1 ve |𝑉(𝐺2)| = 𝑛2 olmak üzere |𝑉(𝐺1⋁𝑣𝐺2)| = 𝑛1 + 𝑛2 − 1; |𝐸(𝐺1)| = 𝑚1 ve |𝐸(𝐺2)| = 𝑚2 olmak üzere |𝐸(𝐺1 ⋁𝑣𝐺2)| = 𝑚1 +𝑚2 dir. 40 v v v 𝐺1 𝐺2 𝐺1 ⋁𝑣𝐺2 Şekil 6.1. 𝐺1, 𝐺2 ve 𝐺1⋁𝑣𝐺2 köşe birleşim grafı Birçok kullanım alanı olan graflar, özellikle kimyasal moleküller için oldukça önemli bir yere sahiptir. Hakkında literatürde pek çok veri bulunan molekül yapıları, çeşitli kurallar çerçevesinde, bir araya gelerek daha büyük moleküllere dönüşebilmektedir. Yapısal değişiklik gösteren yeni molekül yapılarının incelenmesi sırasında kullanılan graf teorinin uygulama basamakları için hem zamandan hem de işlem kalabalığından tasarruf sağlayacak bazı bağıntılar bu bölümde verilecektir. Simetri ve düzenlilik, grafları konu alan birçok alanda en çok aranan özellikler arasındadır. Moleküler grafların geneli belirli bir noktaya göre simetrik olan iki alt grafın birleşimi şeklindedir. Bu yüzden de bu bölümde iki aynı grafın belirlenen bir köşede simetrik olacak şekilde birleştirilmesi ile oluşan birleşim grafları ve bu grafların karakteristik polinomları oluşturulacaktır. Böylece oluşturulan polinomlar sayesinde, büyük bir grafın karakteristik polinomunu baştan yazmak yerine bileşenler cinsinden polinomu oluşturma kolaylığı elde edilmiş olacaktır. Literatürden de iyi bilinen 𝑃𝑛, 𝐾𝑛 ve 𝑆𝑛 graflarının karakteristik polinomlarını kullanarak 𝑃𝑛 ⋁𝑣𝑃𝑛, 𝐾𝑛 ⋁𝑣𝐾𝑛 ve 𝑆𝑛 ⋁𝑣 𝑆𝑛 graflarının karakteristik polinomları formülize edilecektir. İlk olarak 𝐾𝑛 tam grafı için 𝐾𝑛 ⋁𝑣𝐾𝑛 köşe birleşim grafı ve bu grafın karakteristik polinomu verilecektir. Teorem 6.1.1. 𝐾𝑛 tam grafı için bir 𝑣 köşesinde köşe birleşim grafı olan 𝐾𝑛 ⋁𝑣𝐾𝑛 için karakteristik polinom 41 𝑃𝑜𝑙(𝐾 ⋁ 𝐾 ) = (1 + 𝜆)𝑛−2[(−1)𝑛+1𝑛 𝑣 𝑛 ((𝑛 − 2)𝑃𝑜𝑙(𝐾𝑛−1) +(𝜆 − 𝑛 + 2)𝑃𝑜𝑙(𝐾𝑛)) − 𝑃𝑜𝑙(𝐾𝑛−1)] şeklindedir. İspat. 𝐾𝑛 tam grafı için bir 𝑣 köşesinde köşe birleşim grafı olan 𝐾𝑛 ⋁𝑣𝐾𝑛 grafınının karakteristik polinomunun hesaplanmasına geçilmeden önce 𝐾5 ⋁𝑣𝐾5 grafı açıklık sağlamak amacıyla aşağıdaki Şekil 6.2.'de verilmiştir. 𝑣 𝑣 𝐾5 𝐾5⋁𝑣𝐾5 Şekil 6.2. 𝐾5 ve 𝐾5 ⋁𝑣𝐾5 köşe birleşim grafı 2𝑛 − 1 köşeye sahip 𝐾𝑛 ⋁𝑣𝐾𝑛 grafının komşuluk matrisi, 0 1 1 ⋯ 1 1 1 1 ⋯ 1 1 0 1 ⋯ 1 1 0 0 ⋯ 0 1 1 0 ⋯ 1 1 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 1 1 1 ⋯ 0 1 0 0 ⋯ 0 𝐴 = 1 1 1 ⋯ 1 0 0 0 ⋯ 0 1 0 0 ⋯ 0 0 0 1 ⋯ 1 1 0 0 ⋯ 0 0 1 0 ⋯ 1 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 1 0 0 ⋯ 0 0 1 1 ⋯ 1 [1 0 0 ⋯ 0 0 1 1 ⋯ 0](2𝑛−1)×(2𝑛−1) şeklinde oluşturulur. Bu komşuluk matrisinin bazı satır ve sütunları incelendiğinde sol üst kısmının 𝐾𝑛 tam grafının komşuluk matrisine, sağ alt kısmının ise 𝐾𝑛−1 tam grafınınn komşuluk matrisine ait olduğu kolayca görülmektedir. Literatürden 𝐾𝑛 ⋁𝑣𝐾𝑛 grafının karakteristik polinomu 𝑃𝑜𝑙(𝐾𝑛 ⋁𝑣𝐾𝑛) = |𝐴 − 𝜆𝐼2𝑛−1| olup 42  1 1 1 1 1 1 | 1  1 1 1 0 0 | 1 1  1 1 0 0 | | 𝑃𝑜𝑙(𝐾𝑛 ⋁𝑣𝐾𝑛) = 1 1 1  1 0 0 | 1 1 1 1  0 0 | 1 0 0 0 0  1 | | 1 0 0 0 0 1  (2𝑛−1)×(2𝑛−1) şeklindedir. Bu determinanta önce elementer işlemlerden −𝐶2𝑛−1 + 𝐶𝑛+1 → 𝐶𝑛+1, −𝐶2𝑛−1 + 𝐶𝑛+2 → 𝐶𝑛+2, −𝐶2𝑛−1 + 𝐶𝑛+3 → 𝐶𝑛+3, ⋯ , −𝐶2𝑛−1 + 𝐶2𝑛−2 → 𝐶2𝑛−2 olacak 1 1 şekilde önce sütun işlemleri uygulanıp ardından da 𝑅2𝑛−1 + 𝑅𝑛+1 → 𝑅𝜆 𝑛+1, 𝑅𝜆 2𝑛−1 + 1 1 𝑅𝑛+2 → 𝑅𝑛+2, 𝑅2𝑛−1 + 𝑅𝑛+3 → 𝑅𝑛+3, ⋯ , 𝑅2𝑛−1 + 𝑅2𝑛−2 → 𝑅2𝑛−2 satır işlemleri 𝜆 𝜆 (1+𝜆) uygulandıktan sonra (𝑛 + 1). satırdan (2𝑛 − 2). satıra kadar her bir satır 𝜆 parantezine alınırsa yukarıdaki determinantın eşiti  1 1 1 0 0 0 1 | 1  1 1 0 0 0 0 | 1 1  1 0 0 0 0 | 𝑛−2 1 1 1  0 0 0 0 | 1 + 𝜆 = ( ) 1 0 0 0 1 1 1 0 𝜆 | 1 0 0 0 1 1 1 0 | 1 0 0 0 1 1 1 0 | 1 0 0 0 1 1 1 0 | 1 0 0 0 1  1  1   (2𝑛−1)×(2𝑛−1) şekline dönüşür. Bu adımda (𝑛 + 1). satır (−1) ile çarpılıp altında kalan tüm satırlara eklenir ve ardından son 𝑛 − 2 satırın her biri 𝜆 parantezine alınırsa 43  1 1 1 1 1 1 1 | 1  1 0 0 0 0 0 | 1 1 1 0 0 0 0 0 | | 1 1  0 0 0 0 0 = (1 + 𝜆)𝑛−2 1 0 0 1  0 0 0 0 | 0 0 0 1 1 0 0 0 | 0 0 0 1 0 1 0 0 | 0 0 0 1 0 0 1 0 | 0 0 0 1 0 0 0 1 (2𝑛−1)×(2𝑛−1) determinantı elde edilir. Burada ise (𝑛 + 2). satırdan (2𝑛 − 2). satıra kadar olan tüm satırlar (𝑛 + 1). satıra eklenip elde edilen determinant son satıra göre açılırsa  1 1 1 1 1 1 1 1  1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1  0 0 0 0 0 = (1 + 𝜆)𝑛−2 1 0 0 (n  2  ) 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 ( 0 0 0 1 0 0 0 1 (2𝑛−2)×(2𝑛−2)  1 1 1 1 1 1 1 1  1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1  0 0 0 0 0 +(−1)3𝑛 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 (2𝑛−2)×(2𝑛−2)) 44 ifadesi elde edilir. Birinci determinantta elementer sütun işlemlerinden 𝐶2𝑛−2 + 𝐶2𝑛−3 + 𝐶2𝑛−4 + ⋯+ 𝐶𝑛+1 → 𝐶𝑛+1 işlemi uygulanıp ikinci determinantta son satırına göre açılırsa  1 1 (n  2) 1 1 1 1 1  1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1  0 0 0 0 0 = (1 + 𝜆)𝑛−2 1 0 0 (n  2  ) 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 ( (2𝑛−2)×(2𝑛−2)  1 1 1 1 1 1 1 1  1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1  0 0 0 0 0 +(−1)3𝑛 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 (2𝑛−3)×(2𝑛−3)) şeklinde yeni determinantlar elde edilir. Elde edilen bu deterninantlardan başta elde edilen (2𝑛 − 2) × (2𝑛 − 2) tipindeki determinantı önce son satırına göre açıp ardından ise her iki determinantı da (𝑛 + 2). satıra gelinceye kadar son satırlarına göre açma işlemi devam ettirildiğinde 45  1 1 1 1 n  2 1  1 1 1 0 1 1  1 1 0 = (1 + 𝜆)𝑛−2 (−1)𝑛−4 1 1 1  1 0 1 1 1 1  0 ( 1 0 0 0 0 (n  2  ) (𝑛+1)×(𝑛+1)  1 1 1 1 1 1  1 1 1 0 1 1  1 1 0 +(−1)3𝑛 1 1 1  1 0 1 1 1 1  0 1 0 0 0 0 0 (𝑛+1)×(𝑛+1)) toplamı elde edilir. Bu iki determinant önce son satırlarına göre açılıp ardından da yeni determinantlar son sütunlarına göre açılırsa  1 1 1 1  1 1 𝑛−2 = (1 + 𝜆) (−1)𝑛+1 (𝑛 − 2) 1 1  1 1 1 1  ( (𝑛−1)×(𝑛−1)  1 1 1 1  1 1 1 1  1 1 1 1  1 1 +(−1)𝑛(𝑛 − 2 − 𝜆) 1 1  1 1 − 1 1  1 1 1 1  1 1 1 1 1 1 1 1 1  1 1 1  𝑛×𝑛 (𝑛−1)×(𝑛−1)) ifadesi elde edilir. En son elde edilen determinantlar 𝐾𝑛 ve 𝐾𝑛−1 tam graflarının karakteristik polinomlarını veren determinantlar olup yerine yazıldığında istenen sonuca ulaşılmış olur. 46 Teorem 6.1.1.'in bir sonucu olarak 𝑃𝑜𝑙(𝐾𝑛 ⋁𝑣𝐾𝑛)'in formülü 𝜆 cinsinden aşağıdaki şekilde de formülize edilebilir. Sonuç 6.1.2. 𝜆, 𝐾𝑛 ⋁𝑣𝐾𝑛 grafının karakteristik polinomunun kökleri olmak üzere 𝑃𝑜𝑙(𝐾𝑛 ⋁𝑣𝐾𝑛) = −(𝜆 − 𝑛 + 2)(𝜆 2 − (𝑛 − 2)𝜆 − 2𝑛 + 2)(𝜆 + 1)2𝑛−4 şeklinde yazılabilir. İspat. Lemma 4.1.1. gereği 𝑃𝑜𝑙(𝐾𝑛) ve 𝑃𝑜𝑙(𝐾𝑛−1) formülleri Teorem 6.1.1.'de yerine yazılırsa istenen sonuç kolaylıkla elde edilir. Örnek 6.1.3. 𝐾6⋁𝑣𝐾6 grafı için bu grafın karakteristik polinomunu ve spektrumunu hesaplayalım. 𝑛 = 6 için 𝑃𝑜𝑙(𝐾6⋁𝑣𝐾6) = −(𝜆 − 6 + 2)(𝜆 2 − (6 − 2)𝜆 − 2 ∙ 6 + 2)(𝜆 + 1)2∙6−4 = −(𝜆 − 4)(𝜆2 − 4𝜆 − 10)(𝜆 + 1)8 şeklindedir ve bu polinomun kökleri spektrumu verir. Bu durumda 𝑆(𝐾6⋁𝑣𝐾6) spektrum olmak üzere 𝑆(𝐾6⋁𝑣𝐾6) = {−1 (8), 4, 2 ± √14} şeklindedir. Yukarıdaki örnekte görüldüğü gibi 𝐾𝑛 ⋁𝑣𝐾𝑛 grafı için bulunan sonuçlar, bu grafın karakteristik polinomunu ve spektrumunu bulmada oldukça kolaylık sağlamaktadır. 47 İkinci olarak 𝑆𝑛 yıldız grafı için 𝑆𝑛 ⋁𝑣 𝑆𝑛 köşe birleşim grafı ve bu grafın karakteristik polinomu incelenecektir. Teorem 6.1.4. 𝑆𝑛 yıldız grafı için bir 𝑣 köşesinde köşe birleşim grafı olan 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafının karakteristik polinomu 𝑃𝑜𝑙(𝑆2𝑛−1), 𝑣 𝑘öş𝑒𝑠𝑖 𝑚𝑒𝑟𝑘𝑒𝑧 𝑘öş𝑒 𝑖𝑠𝑒 𝑃𝑜𝑙(𝑆𝑛 ⋁𝑣 𝑆𝑛) = { (−𝜆)𝑛−3(𝜆2 − 𝑛 + 2)(𝑃𝑜𝑙(𝑆𝑛) − (−𝜆) 𝑛−2), 𝑑𝑖ğ𝑒𝑟 𝑡ü𝑚 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟 şeklindedir. İspat. İlk olarak alınan iki tane 𝑛 köşeli 𝑆𝑛 yıldız grafın merkez köşeleri 𝑣 olarak isimlendirilsin. Bu 𝑣 köşeleri özdeşlenecek şekilde iki graf birleştirildiğinde oluşan 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafı, merkezi 𝑣 olan 2𝑛 − 1 köşeli 𝑆2𝑛−1 yıldız grafıdır. 𝑣 𝑣 𝑆𝑛 𝑆𝑛 ⋁𝑣 𝑆𝑛 Şekil 6.3. 𝑆𝑛 ve 𝑆𝑛 graflarında merkez köşe birleşim grafı Lemma 4.1.1.'e göre 𝑃𝑜𝑙(𝑆𝑛 ⋁𝑣 𝑆𝑛) = 𝑃𝑜𝑙(𝑆2𝑛−1) = (−𝜆) 𝑛−2(𝜆2 − 𝑛 + 1) şeklindedir. 48 İkinci adımda 𝑣 köşesi, alınan 𝑆𝑛 grafları için merkez dışında herhangi bir köşe olacak şekilde etiketlensin ve bu 𝑣 köşelerini özdeşleyecek şekilde graflara köşe birleşim işlemi uygulansın. Elde edilen 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafının daha anlaşılır olması için Şekil 6.4. verilmiştir. 𝑣 𝑣 𝑆𝑛 𝑆𝑛 ⋁ 𝑣 𝑆𝑛 Şekil 6.4. 𝑆𝑛 ve 𝑆𝑛 grafları için merkez dışında köşe birleşim grafı 2𝑛 − 1 köşeye sahip 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafının komşuluk matrisi 0 1 0 ⋯ 0 1 0 0 ⋯ 0 1 0 1 ⋯ 1 0 0 0 ⋯ 0 0 1 0 ⋯ 0 0 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 0 1 0 ⋯ 0 0 0 0 ⋯ 0 𝐴 = 1 0 0 ⋯ 0 0 1 1 ⋯ 1 0 0 0 ⋯ 0 1 0 0 ⋯ 0 0 0 0 ⋯ 0 1 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ 0 1 0 0 ⋯ 0 [0 0 0 ⋯ 0 1 0 0 ⋯ 0](2𝑛−1)×(2𝑛−1) şeklindedir. Literatürden 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafının karakteristik polinomu 𝑃𝑜𝑙(𝑆𝑛 ⋁𝑣 𝑆𝑛) = |𝐴 − 𝜆𝐼2𝑛−1| 49  1 0 0 1 0 0 0 1  1 1 0 0 0 0 0 1  0 0 0 0 0 0 1 0  0 0 0 0 = 1 0 0 0  1 1 1 0 0 0 0 1  0 0 0 0 0 0 1 0  0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0  (2𝑛−1)×(2𝑛−1) ile bulunur. Yukarıdaki determinant incelendiğinde sol üstteki 𝑛 × 𝑛'lik kısım 𝑆𝑛 yıldız grafının karakteristik polinomunu hesaplamaya yarayan determinanta, sağ altta kalan (𝑛 − 1) × (𝑛 − 1)'lik kısım ise 𝑆𝑛−1 yıldız grafına ait karakteristik polinomu hesaplamaya yarayan determinanta ait olduğu kolayca görülür. Bu determinanta önce 1 1 elementer sütun işlemlerinden 𝐶 𝜆 2𝑛−1 + 𝐶𝑛+1 → 𝐶𝑛+1, 𝐶𝜆 2𝑛−1 + 𝐶𝑛+2 → 𝐶𝑛+2, 1 1 𝐶2𝑛−1 + 𝐶𝑛+3 → 𝐶𝑛+3, ⋯ , 𝐶2𝑛−1 + 𝐶2𝑛−2 → 𝐶2𝑛−2 işlemleri uygulanıp ardından da 𝜆 𝜆 1 1 1 1 𝐶𝑛+2 + 𝐶𝑛+1 → 𝐶𝑛+1, 𝐶 + 𝐶 → 𝐶 , 𝐶 + 𝐶𝜆 𝜆 𝑛+3 𝑛+1 𝑛+1 𝜆 𝑛+4 𝑛+1 → 𝐶𝑛+1, ⋯ , 𝐶𝜆 2𝑛−2 + 𝐶𝑛+1 → 𝐶𝑛+1 işlemleri uygulandığında  1 0 0 1 0 0 0 1  1 1 0 0 0 0 0 1  0 0 0 0 0 0 1 0  0 0 0 0 n  2   2= 1 0 0 0 1 1 1  0 0 0 0 0  0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  (2𝑛−1)×(2𝑛−1) 50 determinantı elde edilir. Bu determinantta her 𝑖 = 𝑛 + 2,⋯ , 2𝑛 − 1 ve her 𝑗 = 1,⋯ , 𝑛 + 1 için 𝑎𝑖𝑗 = 0 olduğu görülmektedir. Sıfıra eşit olan terimler, determinantın hesaplanmasında kolaylık sağlayan bir metodu kullanma olanağı sağlar. Bu metodun bir sonucu olarak yukarıdaki determinant, determinantın sol üst kısmındaki (𝑛 + 1) × (𝑛 + 1)'lik terimlerin determinantı ile sağ alt kısımdaki (𝑛 − 2) × (𝑛 − 2)'lik terimlerin determinantı çarpımına eşittir. Bu çarpım  1 0 0 1 1  1 1 0  0 0 0 0 1  0 0 0  0 0 = . 0 0  0 0 1 0  2   (n  3)  1 0 0 0  1 0 0 0 (𝑛−2)×(𝑛−2)  (𝑛+1)×(𝑛+1) şeklinde gösterilir. Elde edilen ikinci determinant (𝑛 − 2) × (𝑛 − 2) tipindeki diyagonal matrisin determinantı olup değeri diyagonal elemanların çarpımına eşittir. Baştaki (𝑛 + 1) × (𝑛 + 1) tipindeki kare matrisin determinantı ise son satıra göre açılırsa yukarıdaki determinantlar çarpımı 1 0 0 0 1  1 1 1 0 −𝜆2 + (𝑛 − 3)𝜆 + 1 1  0 0 0 = (−𝜆)𝑛−2 𝑃𝑜𝑙(𝑆𝑛) + (−1) 𝑛+2 𝜆 1 0  0 0 ( 1 0 0  0 𝑛×𝑛) şekline dönüşür. Son determinanta, uygun elementer satır ve sütun işlemleri uygulanmaya devam edildiğinde −𝜆2 + (𝑛 − 3)𝜆 + 1 = (−𝜆)𝑛−2 ( ∙ 𝑃𝑜𝑙(𝑆 ) 𝜆 𝑛 51 0 0 0 0 1 1 0 0 0 0 2 −𝜆 + 𝑛 − 2 1  0 0 0 +(−1)𝑛+2 ( ) 𝜆 1 0  0 0 1 0 0  0 𝑛×𝑛) toplamı elde edilir. Bu toplam yer alan 𝑛 × 𝑛 tipindeki determinanta her 𝑖 = 3,⋯ , 𝑛 için −𝑅2 + 𝑅𝑖 → 𝑅𝑖 şeklinde elementer satır işlemi uygulanıp ardından da son satıra göre açılırsa istenilen sonuca ulaşılır. Teorem 6.1.4'ün bir sonucu olarak 𝑃𝑜𝑙(𝑆𝑛 ⋁𝑣 𝑆𝑛)'in formülü 𝜆 cinsinden aşağıdaki şekilde de formülize edilebilir. Sonuç 6.1.5. 𝜆, 𝑆𝑛 ⋁𝑣 𝑆𝑛 grafının karakteristik polinomunun kökleri olmak üzere 𝑃𝑜𝑙(𝑆 2𝑛−5 2 2𝑛 ⋁𝑣 𝑆𝑛) = −𝜆 (𝜆 − 𝑛 + 2)(𝜆 − 𝑛) şeklinde yazılabilir. İspat. Lemma 4.1.1. kullanılarak 𝑃𝑜𝑙(𝑆𝑛) bağıntısı Teorem 6.1.4.'te yerine yazılırsa istenen sonuç kolaylıkla elde edilir. Örnek 6.1.6. 𝑣 köşesi merkez köşe olmasın. Bu durumda 𝑆7 ⋁𝑣 𝑆7 grafının karakteristik polinomunu ve spektrumunu hesaplayalım. 𝑛 = 7 için 𝑃𝑜𝑙(𝑆 ⋁ 2∙7−5 2 27 𝑣 𝑆7) = −𝜆 (𝜆 − 7 + 2)(𝜆 − 7) = −𝜆9(𝜆2 − 5)(𝜆2 − 7) şeklindedir ve bu polinomun kökleri spektrumu verir. Bu durumda 𝑆(𝑆7⋁𝑣 𝑆7) spektrum olmak üzere 52 𝑆(𝑆7⋁𝑣 𝑆 ) = {0 (9) 7 , ∓√5,∓√7} şeklindedir. Bu bölümde son olarak 𝑃𝑛 yol grafı için köşe birleşim grafı incelenecektir. Teorem 6.1.7. 𝑃𝑛 yol grafında, uç köşe olan bir 𝑣 köşesi için köşe birleşim grafı 𝑃𝑛 ⋁𝑣𝑃𝑛 'in karakteristik polinomu 𝑃𝑜𝑙(𝑃𝑛 ⋁𝑣𝑃𝑛) = 𝑃𝑜𝑙(𝑃𝑛−1)[𝑃𝑜𝑙(𝑃𝑛) − 𝑃𝑜𝑙(𝑃𝑛−2)] şeklindedir. Ayrıca bu eşitlik 𝑃𝑜𝑙(𝑃𝑛 ⋁𝑣𝑃𝑛) = −𝑃𝑜𝑙(𝑃𝑛−1)[𝜆𝑃𝑜𝑙(𝑃𝑛−1) + 2𝑃𝑜𝑙(𝑃𝑛−2)] olarak da ifade edilebilir. İspat. İki tane 𝑃𝑛 grafı alınarak her ikisinin de uç noktalarından biri 𝑣 olarak isimlendirilsin. Ardından ise bu iki aynı isme sahip köşeler özdeşleşecek şekilde birleştirilip elde edilen graf 𝑃𝑛 ⋁𝑣𝑃𝑛olsun. 𝑣 𝑣 𝑃𝑛 𝑃𝑛 ⋁𝑣𝑃𝑛 Şekil 6.5. 𝑃𝑛 ve 𝑃𝑛 ⋁𝑣𝑃𝑛 köşe birleşim grafı Yukarıdaki Şekil 6.5.'te de görüldüğü gibi elde edilen 𝑃𝑛 ⋁𝑣𝑃𝑛 grafı 2𝑛 − 1 köşeye sahip 𝑃2𝑛−1 yol grafıdır. Lemma 4.1.3. ve Teorem 4.2.5. gereği sonuç aşikardır. Sonuç 6.1.8. 𝜆, 𝑃𝑛 ⋁𝑣𝑃𝑛 grafının karakteristik polinomunun kökleri olmak üzere bu polinom 53 𝑛−1 2𝑛 − 𝑘 − 1 ∑(−1)𝑘+1 ( ) 𝜆2𝑛−𝑘−1 𝑘 𝑘=0 olarak da ifade edilebilir. İspat. Lemma 4.1.3.'te verilen eşitlikte 𝑃𝑛, 𝑃𝑛−1 ve 𝑃𝑛−2 graflarına ait polinomlar Teorem 6.1.7'de yerine yazıldığında istenilen sonuç elde edilir. 6.2. İki Grafın Birer Köşelerinden Yeni Bir Kenar İle Birleşimi Bu bölümde ise köprü görevi gören ilave bir kenar ile oluşturulacak farklı bir birleşim metodu tanımlanacaktır: Tanım 6.2. 𝐺1 ve 𝐺2 iki graf olsun. 𝑉(𝐺1) ve 𝑉(𝐺2) kümelerinden belirlenecek birer köşe 𝑣 olarak isimlendirilsin. İsimlendirilen 𝑣 köşelerinin arasına bir 𝑒 kenarı çizilerek 𝐺1 ve 𝐺2 graflarını birleştirilsin. Elde edilen bu grafa, verilen grafların 𝒗 köşesinde yeni bir kenar ile birleşimi veya kısaca 𝒗 köşesinde kenar birleşimi denir ve 𝑮𝟏 ⋁ 𝒆 𝒗𝑮𝟐 ile gösterilir. Burada 𝐺 𝑒1⋁𝑣𝐺2 grafının köşe kümesi 𝑉(𝐺 ⋁ 𝑒 1 𝑣𝐺2 ) = 𝑉(𝐺1) ∪ 𝑉(𝐺2) ve kenar kümesi 𝐸(𝐺 ⋁𝑒1 𝑣𝐺2 ) = 𝐸(𝐺1) ∪ 𝐸(𝐺2) ∪ {𝑒}'dir. Ayrıca |𝑉(𝐺1)| = 𝑛1 ve |𝑉(𝐺2)| = 𝑛2 olmak üzere |𝑉(𝐺 𝑒1⋁𝑣𝐺2)| = 𝑛1 + 𝑛2 ve ayrıca |𝐸(𝐺1)| = 𝑚1 ve |𝐸(𝐺2)| = 𝑚2 olmak üzere |𝐸(𝐺 ⋁𝑒1 𝑣𝐺2)| = 𝑚1 +𝑚2 + 1'dir. v e v v v 𝑒 𝐺1 𝐺2 𝐺1 ⋁𝑣𝐺2 Şekil 6.6. 𝐺1, 𝐺2 ve 𝐺 𝑒 1⋁𝑣𝐺2 grafları 54 Bu bölümde iki aynı grafın belirlenen bir köşede simetrik olacak şekilde köprü görevi gören bir kenar eklenerek birleştirilmesi ile oluşan graflar ve bu grafların karakteristik polinomları hesaplanacaktır. Bu hesaplamalar büyük bir grafın karakteristik polinomunu baştan hesaplamak yerine bileşenler cinsinden polinomu oluşturma kolaylığı sağlayacak ve bu polinomun kökleri sayesinde de grafların enerjileri kolayca ifade edilebilecektir. Literatürden de iyi bilinen 𝑃𝑛, 𝐾𝑛 ve 𝑆𝑛 graflarının karakteristik polinomları kullanılarak 𝐾 𝑒 𝑒 𝑒𝑛 ⋁𝑣𝐾𝑛, 𝑆𝑛 ⋁𝑣 𝑆𝑛 ve 𝑃𝑛 ⋁𝑣𝑃𝑛 graflarının karakteristik polinomları formülize edilecektir. İlk olarak 𝐾𝑛 tam grafları için bir 𝑣 köşesinde kenar birleşim grafı oluşturulup bu grafın polinomunu veren bağıntı yazılacaktır. Teorem 6.2.1. 𝐾 𝑒𝑛 bir tam graf olmak üzere, 𝐾𝑛 ⋁𝑣𝐾𝑛 grafının karakteristik polinomu (𝜆2−(𝑛−3)𝜆−(2𝑛−3))(𝜆2−(𝑛−1)𝜆−1)(𝜆+1)𝑛−3 𝑃𝑜𝑙(𝐾 ⋁𝑒𝑛 𝑣𝐾𝑛) = ∙ 𝑃𝑜𝑙(𝐾 ) 𝜆−𝑛+1 𝑛 dir. İspat. 𝐾 𝑒𝑛 ⋁𝑣𝐾𝑛 grafı 𝑛 = 5 değeri için Şekil 6.7.'de çzilmiştir. 𝑣 𝑣 𝑒 𝑣 e 𝑒 𝐾5 𝐾5⋁𝑣𝐾5 Şekil 6.7. 𝐾5 ve 𝐾5⋁ 𝑒 𝑣𝐾5 grafı Benzer şekilde 𝐾𝑛 tam grafı için 𝑣 köşesinde kenar birleşim grafı olan 2𝑛 köşeli 𝐾𝑛 ⋁ 𝑒 𝑣𝐾𝑛 grafı oluşturulduğunda 55 0 1 ⋯ 1 1 1 0 ⋯ ⋯ 0 1 0 ⋯ 1 1 0 0 ⋯ ⋯ 0 0 ⋯ 1 1 ⋯ 1 1 0 ⋯ 0⋮ ⋱ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ 1 1 ⋯ 0 1 0 0 ⋯ ⋯ 0 𝐴 = 1 1 ⋯ 1 0 0 0 ⋯ ⋯ 0 1 0 ⋯ 0 0 0 1 ⋯ ⋯ 1 0 0 ⋯ 0 0 1 0 ⋯ ⋯ 1 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ 0 0 1 1 ⋯ ⋯ 1 [0 0 ⋯ 0 0 1 1 ⋯ ⋯ 0]2𝑛×2𝑛 komşuluk matrisi elde edilir. Yukarıdaki matris incelendiğinde sol üstte ve sağ altta kalan 𝑛 × 𝑛'lik kısımların 𝐾𝑛 tam grafına ait komşuluk matrisi olduğu kolayca görülür. 𝐴 matrisi kullanılarak elde edilen 𝐾 𝑒𝑛 ⋁𝑣𝐾𝑛 grafına ait karakteristik polinom 𝑃𝑜𝑙(𝐾𝑛 ⋁ 𝑒 𝑣𝐾𝑛) = |𝐴 − 𝜆𝐼2𝑛|  1 1 1 1 0 0 0 1  1 1 0 0 0 0 1 1  1 0 0 0 0 1 1 1  0 0 0 0 = 1 0 0 0  1 1 1 0 0 0 0 1  1 1 0 0 0 0 1 1  1 0 0 0 0 1 1 1  2𝑛×2𝑛 şeklinde oluşturulur. Bu determinantta ilk olarak elementer satır işlemlerinden her 𝑖 = 𝑛 + 3, 𝑛 + 4,⋯ , 2𝑛 için −𝑅𝑛+2 + 𝑅𝑖 → 𝑅𝑖 operasyonu ardından ise elementer sütun işlemlerinden 𝐶𝑛+2 + 𝐶𝑛+3 + 𝐶𝑛+4 +⋯+ 𝐶2𝑛 → 𝐶𝑛+2 operasyonu uygulanırsa 56  1 1 1 0 0 0 0 1  1 0 0 0 0 0 1 1  0 0 0 0 0 1 0 0  n 1 1 1 1 = 0 0 0 1 (n  2  ) 1 1 1 0 0 0 0 0  1   0 0 0 0 0 0 0 0  1   0 0 0 0 0 0 0 0  1   2𝑛×2𝑛 elde edilir. Burada her 𝑖 = 𝑛 + 3, 𝑛 + 4,⋯ , 2𝑛 ve 𝑗 = 1, 2,⋯ , 𝑛 + 2 için 𝑎𝑖𝑗 = 0 olup determinantın değeri determinantın sol üstünde yer alan (𝑛 + 2) × (𝑛 + 2)'lik kısmın determinantı ile sağ altta yer alan (𝑛 − 3) × (𝑛 − 3)'lük kısmın determinantları çarpımına eşittir. Bu eşitlik  1 1 1 0 1  1 0 0  1    0 0 1 1  0 0 0  1    0 = ∙ 1 0 0  (n  1) 0 0  1    (𝑛−3)×(𝑛−3) 0 0 0 1 (n  2  ) (𝑛+2)×(𝑛+2) şeklindedir. Elde edilen ikinci determinant (𝑛 − 3) × (𝑛 − 3) tipindeki diyagonal matrisin determinantı olup değeri diyagonal elemanların çarpımına eşittir. Baştaki (𝑛 + 2) × (𝑛 + 2) tipindeki kare matrisin determinantı ise son satıra göre açılırsa yukarıdaki determinantlar çarpımı  1 1 1 0 1  1 1 0 1 1  1 0 = (−1 − 𝜆)𝑛−3 ∙ ((−1)2𝑛+1 1 1 1  0 1 0 0 0  (𝑛+1)×(𝑛+1) 57  1 1 1 1 1  1 1 0 1 1  1 0 +(𝑛 − 2 − 𝜆) 1 1 1  0 1 0 0 0  (𝑛+1)×(𝑛+1)) elde edilir. Her iki determinant son sütunlarına göre açılıp gerekli düzenlemeler yapıldığında 𝐾𝑛 ve 𝐾𝑛−1 tam graflarının karakteristik polinomlarını veren yeni determinantlar elde edilir. Bu polinomlar yerine yazıldığında istenen sonuca ulaşılır. Sonuç 6.2.2. 𝜆, 𝐾 𝑒𝑛 ⋁𝑣𝐾𝑛 grafının karakteristik polinomunun kökleri olmak üzere 𝑃𝑜𝑙(𝐾 ⋁𝑒 2𝑛−4𝑛 𝑣𝐾𝑛) = (𝜆 + 1) (𝜆 2 − (𝑛 − 1)𝜆 − 1)(𝜆2 − (𝑛 − 3)𝜆 − (2𝑛 − 3)) dir. İspat. Lemma 4.1.1. kullanılarak 𝑃𝑜𝑙(𝐾𝑛)'in formülü Teorem 6.2.1 de yerine yazılırsa istenen sonuç kolaylıkla elde edilir. Örnek 6.2.3. 𝐾 ⋁𝑒7 𝑣𝐾7 grafının karakteristik polinomunu ve spektrumunu hesaplayalım. 𝑛 = 7 için 𝑃𝑜𝑙(𝐾 𝑒7⋁𝑣𝐾7 ) = (𝜆 + 1) 2∙7−4(𝜆2 − (7 − 1)𝜆 − 1)(𝜆2 − (7 − 3)𝜆 − (2 ∙ 7 − 3)) = (𝜆 + 1)10(𝜆2 − 6𝜆 − 1)(𝜆2 − 4𝜆 − 11) şeklindedir ve bu polinomun kökleri spektrumu verir. Bu durumda 𝑆(𝐾 ⋁𝑒7 𝑣𝐾7 ) spektrum olmak üzere 𝑆(𝐾 ⋁𝑒𝐾 ) = {−1(10)7 𝑣 7 , 2 ± √15, 3 ± √10} 58 olur. 𝐾𝑛 ⋁ 𝑒 𝑣𝐾𝑛 grafının karakteristik polinomunu ve spektrumunu bulmada oldukça kolaylık sağlayan yukarıdaki sonuçların benzerleri ikinci olarak da 𝑆𝑛 yıldız grafı olmak üzere 𝑆 ⋁𝑒𝑛 𝑣 𝑆𝑛 için oluşturulacaktır. Teorem 6.2.4. 𝑆𝑛 yıldız grafı için 𝑣 köşesinde kenar birleşim grafı olan 𝑆𝑛 ⋁ 𝑒 𝑣 𝑆𝑛'in karakteristik polinomu −𝜆2𝑛−2 + (−𝜆)𝑛−2(𝜆2 − 𝑛 + 1)𝑃𝑜𝑙(𝑆𝑛), 𝑣 𝑘öş𝑒𝑠𝑖 𝑚𝑒𝑟𝑘𝑒𝑧 𝑘öş𝑒 𝑖𝑠𝑒 𝑒 𝑃𝑜𝑙(𝑆𝑛 ⋁𝑣 𝑆𝑛) = 2 𝜆 −𝑛+2(−𝜆)𝑛−2 ((𝜆2 − 𝑛 + 1)𝑃𝑜𝑙(𝑆𝑛) + ( )𝑃𝑜𝑙(𝑆𝑛−1)) 𝑑𝑖ğ𝑒𝑟 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟 { 𝜆 şeklindedir. İspat. 𝑆𝑛 yıldız grafında, 𝑣 köşesi merkez köşe olmak üzere 𝑣 köşesinde kenar birleşim grafı olan 𝑆 ⋁𝑒𝑛 𝑣 𝑆𝑛 Şekil 6.8.'de, 𝑣 köşesi uç köşe olmak üzere 𝑣 köşesinde kenar birleşim grafı olan 𝑆 𝑒𝑛 ⋁𝑣 𝑆𝑛 Şekil 6.9.'da verilmiştir. 𝑣 𝑣 𝑒 𝑣 𝑆𝑛 𝑆 ⋁𝑒𝑛 𝑣 𝑆𝑛 Şekil 6.8. 𝑆𝑛 ile 𝑣 merkez köşede kenar birleşim grafı 𝑆 ⋁ 𝑒 𝑛 𝑣 𝑆𝑛 59 𝑣 𝑒 𝑣 𝑣 𝑆 𝑛 𝑆 𝑒 𝑛 ⋁𝑣 𝑆𝑛 Şekil 6.9. 𝑆𝑛 ve 𝑣 uç köşede kenar birleşim grafı 𝑆 𝑒 𝑛 ⋁𝑣 𝑆𝑛 𝑆𝑛 ⋁ 𝑒 𝑣 𝑆𝑛 grafının karakteristik polinomunu bulmak için öncelikle oluşturulan grafların 𝐴 komşuluk matrisleri oluşturulur. Ardından ise |𝐴 − 𝜆𝐼2𝑛| determinantı yazılıp 𝑃𝑜𝑙(𝐾 ⋁𝑒𝑛 𝑣𝐾𝑛) için yapılan elementer işlemlere benzer işlemler uygulandığında istenilen sonuçlara kolayca ulaşılır. Sonuç 6.2.5. 𝜆, 𝑆𝑛 ⋁ 𝑒 𝑣 𝑆𝑛 grafının karakteristik polinomunun kökleri olmak üzere 𝜆2𝑛−4((𝜆2 − 𝑛 + 1)2 − 𝜆2), 𝑣 𝑘öş𝑒𝑠𝑖 𝑚𝑒𝑟𝑘𝑒𝑧 𝑘öş𝑒 𝑖𝑠𝑒 𝑃𝑜𝑙(𝑆 𝑒𝑛 ⋁𝑣 𝑆𝑛) = { 𝜆2𝑛−6((𝜆3 − (𝑛 − 1)𝜆)2 − (𝜆2 − 𝑛 + 2)2) 𝑑𝑖ğ𝑒𝑟 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟 ile ifade edilebilir. İspat. Lemma 4.1.1.'de verilen 𝑃𝑜𝑙(𝑆𝑛) bağıntısı, Teorem 6.2.4.'de yerine yazılırsa istenilen sonuca kolayca ulaşılır. Örnek 6.2.6. 𝑣 köşesi 𝑆6 grafının merkez köşesi olmak üzere 𝑆6⋁ 𝑒 𝑣 𝑆6 grafının karakteristik polinomunu ve spektrumunu hesaplayalım. 𝑛 = 6 için 𝑃𝑜𝑙(𝑆 ⋁𝑒 𝑆 ) = 𝜆2∙6−46 𝑣 6 ((𝜆 2 − 6 + 1)2 − 𝜆2) =𝜆8((𝜆2 − 5)2 − 𝜆2) = 𝜆8(𝜆2 + 𝜆 − 5)(𝜆2 − 𝜆 − 5) 60 şeklindedir ve bu polinomun kökleri spektrumu verir. Bu durumda 𝑆(𝑆 ⋁𝑒6 𝑣 𝑆6 ) spektrum olmak üzere 1±√21 −1±√21 𝑆(𝑆 𝑒6⋁𝑣 𝑆6) = {0 (8), , } 2 2 olur. Örnek 6.2.7. 𝑣 köşesi 𝑆5 grafının bir uç köşesi olmak üzere 𝑆 𝑒 5 ⋁𝑣 𝑆5 grafının karakteristik polinomunu hesaplayalım. 𝑛 = 5 için 𝑃𝑜𝑙(𝑆 𝑒 2∙5−6 35⋁𝑣 𝑆5) = 𝜆 ((𝜆 − (5 − 1)𝜆) 2 − (𝜆2 − 5 + 2)2) =𝜆4((𝜆3 − 4𝜆)2 − (𝜆2 − 3)2) = 𝜆4(𝜆3 − 4𝜆 + 𝜆2 − 3)(𝜆3 − 4𝜆 − 𝜆2 + 3) şeklindedir. Bu bölümde son olarak 𝑃𝑛 yol grafı olmak üzere 𝑃𝑛 ⋁ 𝑒 𝑣𝑃𝑛 köşe birleşim grafının polinomu incelenecektir. Teorem 6.2.8. 𝑃𝑛 yol grafının 𝑣 uç köşesinde kenar birleşim grafı olan 𝑃 𝑒 𝑛 ⋁𝑣𝑃𝑛'in karakteristik polinomu 𝑃𝑜𝑙(𝑃𝑛 ⋁ 𝑒 𝑣𝑃𝑛) = −𝜆𝑃𝑜𝑙(𝑃 )𝑃𝑜𝑙(𝑃 ) − 𝑃𝑜𝑙 2 𝑛 𝑛−1 (𝑃𝑛−1) − 𝑃𝑜𝑙(𝑃𝑛)𝑃𝑜𝑙(𝑃𝑛−2) şeklindedir. İspat. 𝑃𝑛 yol grafında 𝑣 uç köşesinde kenar birleşim grafı olan 𝑃𝑛 ⋁ 𝑒 𝑣𝑃𝑛 Şekil 6.10.'da verilmiş olup bu grafın 𝑃2𝑛 grafına ait olduğu aşikardır. 61 𝑣 𝑣 𝑣 𝑒 𝑃𝑛 𝑃𝑛 ⋁ 𝑒 𝑣𝑃𝑛 Şekil 6.10. 𝑃𝑛 ve 𝑃𝑛 ⋁ 𝑒 𝑣𝑃𝑛 grafı 𝑃𝑜𝑙(𝐾 𝑒𝑛 ⋁𝑣𝐾𝑛) ve 𝑃𝑜𝑙(𝑆 𝑒 𝑛 ⋁𝑣 𝑆𝑛) için yapılan hesaplamaların benzer adımları uygulandığında istenilen sonuca ulaşılır. 62 7. ALT BÖLÜM GRAFLARININ KARAKTERİSTİK POLİNOMLARI, İNDİRGEME BAĞINTILARI VE ENERJİLERİ Yaygın bir kullanım alanına sahip olan grafları her an farklı bir şekilde görmek mümkündür. Bu bölümde alt bölüm graflarının tanımını verilip literatürde sıkça karşılaşılan özel graf türleri için önce alt bölüm grafları oluşturulacak ardından ise bu alt bölüm grafların karakteristik polinomları belirlenecektir. Bununla birlikte belirlenen bu polinomların literatürde bilinen polinomlar cinsinden indirgeme bağıntıları ve son olarak da enerji bağıntıları verilecektir. Tanım 7.1. 𝐺(𝑉, 𝐸) bağlantılı, döngü içermeyen ve yönlendirilmemiş bir graf olsun. 𝐺 grafının her bir kenarına derecesi 2 olacak şekilde yeni köşeler eklenmesi ile oluşturulan yeni grafa alt bölüm grafı denir ve 𝐒(𝑮) ile gösterilir. 𝐺 𝑆(𝐺) Şekil 7.1. Bir 𝐺 grafı ve bu grafın 𝑆(𝐺) alt bölüm grafı 7.1. Alt Bölüm Grafların Karakteristik Polinomları Bu bölümde literatürden iyi bilinen 𝑃𝑛, 𝐶𝑛, 𝑆𝑛, 𝐾𝑛 ve 𝐾𝑚,𝑛 graflarına ait alt bölüm grafları oluşturulup ardından elde edilen bu grafların karakteristik polinomları belirlenecektir. İlk olarak 𝑃𝑛 grafına Tanım 7.1'de verilen bilgi doğrultusunda alt bölüm işlemi uygulanacak ve elde edilen bölüm grafı incelenecektir. Teorem 7.1.1. 𝑃𝑛 'in alt bölüm grafı olan 𝐒(𝑃𝑛) grafının karakteristik polinomu 63 𝑛−1 2𝑛 − 𝑘 − 1 𝑃𝑜𝑙(𝐒(𝑃𝑛)) = ∑(−1) 𝑘+1 ( ) 𝜆2𝑛−2𝑘−1 𝑘 𝑘=0 şeklindedir. İspat. 𝑃𝑛 yol grafında her kenara derecesi 2 olacak şekilde yeni köşeler eklenmesi ile oluşan 𝐒(𝑃𝑛) grafı Şekil 7.2.'de verilmiş olup bu grafın 𝑃2𝑛−1 grafına ait kolayca görülebilmektedir. 𝑃𝑛 S(𝑃𝑛) Şekil 7.2. 𝑷𝒏 ve 𝐒(𝑃𝑛) grafı Bu durumda Sonuç 6.1.8 'den dolayı 𝑛−1 2𝑛 − 𝑘 − 1 Pol(𝐒(𝑃𝑛)) = ∑(−1) 𝑘+1 ( ) 𝜆2𝑛−2𝑘−1 𝑘 𝑘=0 şeklindedir. İkinci olarak 𝐶𝑛 grafı için alt bölüm işleminde elde edilen 𝐒(𝐶𝑛) grafı incelenecektir. Teorem 7.1.2. 𝐶𝑛'in alt bölüm grafı olan 𝐒(𝐶𝑛) grafının karakteristik polinomu 𝑛−1 𝑃𝑜𝑙(𝐒(𝐶𝑛)) = [∑(−1) 𝑘 𝑇(2𝑛, 𝑘)𝜆2𝑛−2𝑘 − 2] + 2(−1)𝑛 𝑘=0 şeklindedir. Burada 𝑇(2𝑛, 𝑘) = (2𝑛−𝑘) + (2𝑛−𝑘−1) olup 𝑘 ≤ 𝑛 ve 𝑇(2𝑛, 0) = 1 dir. 𝑘 𝑘−1 İspat. 𝐶𝑛 devir grafında her kenara derecesi 2 olacak şekilde yeni köşeler eklenmesi ile oluşan 𝐒(𝐶𝑛) grafının 𝐶2𝑛 grafı ile aynı graflar olduğu oldukça açıktır. O halde 64 𝑃𝑜𝑙(𝐒(𝐶𝑛) ) = 𝑃𝑜𝑙(𝐶2𝑛) şeklindedir. Bu durumda Lemma 4.1.4. kullanılarak gerekli düzenlemeler yapıldığında 𝑛−1 Pol(𝐒(𝐶 𝑘 2𝑛−2𝑘 𝑛𝑛)) = 𝑃𝑜𝑙(𝐶2𝑛) = [∑(−1) 𝑇(2𝑛, 𝑘)𝜆 − 2] + 2(−1) 𝑘=0 olacak şekilde istenilen sonuca ulaşılır. Bir sonraki adımda 𝑆𝑛 grafı için alt bölüm işlemiyle elde edilen 𝐒(𝑆𝑛) grafı incelenecektir. Teorem 7.1.3. 𝑆𝑛'in alt bölüm grafı olan 𝐒(𝑆𝑛) grafının karakteristik polinomu 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = −𝜆(𝜆 2 − 1)𝑛−2(𝜆2 − 𝑛) şeklindedir. İspat. 𝑆𝑛 devir grafında her kenara derecesi 2 olacak şekilde yeni köşeler eklenmesi ile oluşan 𝐒(𝑆𝑛) grafı, daha anlaşılır olması açısından Şekil 7.3.'de verilmiştir. 𝑆𝑛 𝐒(𝑆𝑛) Şekil 7.3. 𝑆𝑛 ve 𝑆𝑛'in alt bölüm grafı 𝐒(𝑆𝑛) Yukarıda verilen şekil dikkate alınarak oluşturulan 𝐒(𝑆𝑛) grafının 𝐴 komşuluk matrisi 65 0 0 ⋯ 0 1 0 0 ⋯ 0 0 0 0 ⋯ 0 0 1 0 ⋯ 0 0 0 0 ⋯ 0 0 0 1 ⋯ 0 0 ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ ⋯ 0 0 0 ⋯ 1 0 𝐴 = 1 0 ⋯ ⋯ 0 0 0 ⋯ 0 1 0 1 ⋯ ⋯ 0 0 0 ⋯ 0 1 0 0 1 ⋯ 0 0 0 ⋯ 0 1 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 1 0 0 ⋯ 0 1 [0 0 0 ⋯ 0 1 1 ⋯ 1 0](2𝑛−1)×(2𝑛−1) şeklindedir. Bu matris dikkatli bir şekilde incelendiğinde satır ve sütunlarının bazı özel durumlar oluşturduğu görülmektedir. Matrisin içi bu özel durumlar göz önünde bulundurularak parçalandığında 0(𝑛−1)×(𝑛−1), 01×(𝑛−1), 0(𝑛−1)×1, 01×1, 1(𝑛−1)×1, 11×(𝑛−1) ve 𝐼𝑛−1 matrisleri elde edilir. Bu tezde 𝐼𝑛−1 ifadesi 𝑛 − 1 boyutlu birim matris için, 0(𝑛−1)×(𝑛−1) ifadesi 𝑛 − 1 boyutlu sıfır matrisi için, 01×(𝑛−1) ifadesi tüm elemanları 0 dan oluşan 1 × (𝑛 − 1) boyutlu matris için, 0(𝑛−1)×1 ifadesi tüm elemanları 0 dan oluşan (𝑛 − 1) × 1 boyutlu matris için, 01×1 ifadesi elemanı yalnızca 0 olan 1 × 1 boyutlu kare matris için kullanılırken elemanları 1'den oluşan matrisler için de benzer gösterimlerden faydalanılacaktır. Bu gösterimleri kullanarak yukarıdaki komşuluk matrisi tekrar düzenlendiğinde 0(𝑛−1)×(𝑛−1) 𝐼𝑛−1 0(𝑛−1)×1 𝐴 = [ 𝐼𝑛−1 0(𝑛−1)×(𝑛−1) 1(𝑛−1)×1] 0(𝑛−1)×1 11×(𝑛−1) 01×1 (2𝑛−1)×(2𝑛−1) elde edilir. 𝐒(𝑆𝑛) grafının karakteristik polinomu 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = |𝜆𝐼2𝑛−1 − 𝐴| olup 𝜆𝐼𝑛−1 −𝐼𝑛−1 0(𝑛−1)×1 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = | −𝐼𝑛−1 𝜆𝐼𝑛−1 −1(𝑛−1)×1| 01×(𝑛−1) −11×(𝑛−1) 𝜆 (2𝑛−1)×(2𝑛−1) şeklindedir. Bu son determinantta ilk 𝑛 − 1 sütun (−1) ile çarpılıp son sütuna eklenirse 66 𝜆𝐼𝑛−1 −𝐼𝑛−1 −𝜆(𝑛−1)×1 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = | −𝐼𝑛−1 𝜆𝐼𝑛−1 0(𝑛−1)×1 | 01×(𝑛−1) −11×(𝑛−1) 𝜆 (2𝑛−1)×(2𝑛−1) elde edilir. Ardından son satır, ilk 𝑛 − 1 satıra eklenirse 𝜆𝐼𝑛−1 −𝐼𝑛−1 + (−1)(𝑛−1)×(𝑛−1) 0(𝑛−1)×1 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = | −𝐼𝑛−1 𝜆𝐼𝑛−1 0(𝑛−1)×1| 01×(𝑛−1) −11×(𝑛−1) 𝜆 (2𝑛−1)×(2𝑛−1) şeklindeki determinant elde edilir. Bundan sonraki adımda uygun elementer satır-sütun işlemleri uygulanır ve gerekli düzenlemelerin ardından birinci sütuna göre determinant açılırsa 𝜆𝐼 −𝐼 𝑃𝑜𝑙(𝐒(𝑆 )) = −𝜆 | 𝑛−1 𝑛−1 + (−1)(𝑛−1)×(𝑛−1) 𝑛 | −𝐼𝑛−1 𝜆𝐼𝑛−1 (2𝑛−2)×(2𝑛−2) 1 1 elde edilir. Elementer satır işlemlerinden 𝑅1 + 𝑅𝑛 → 𝑅𝑛, 𝑅 + 𝑅𝜆 𝜆 2 𝑛+1 → 𝑅𝑛+1, ⋯ , 1 𝑅 𝜆 𝑛−1 + 𝑅2𝑛−2 → 𝑅2𝑛−2 işlemleri uygulanırsa 𝜆𝐼𝑛−1 −𝐼𝑛−1 + (−1)(𝑛−1)×(𝑛−1) 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = −𝜆 | 𝜆 2 − 1 1 | 0(𝑛−1)×(𝑛−1) ( ) 𝐼𝜆 𝑛−1 + (− ) 𝜆 (𝑛−1)×(𝑛−1) (2𝑛−2)×(2𝑛−2) 𝜆2 − 1 1 = −𝜆|𝜆𝐼𝑛−1| ∙ |( ) 𝐼𝑛−1 + (− ) | 𝜆 𝜆 (𝑛−1)×(𝑛−1) (𝑛−1)×(𝑛−1) 𝜆2 − 1 1 = −𝜆𝑛 |( ) 𝐼 𝜆 𝑛−1 + (− ) | 𝜆 (𝑛−1)×(𝑛−1) (𝑛−1)×(𝑛−1) elde edilir. son determinantta elementer sütun işlemlerinden 𝐶2 + 𝐶3 + 𝐶4 +⋯+ 𝐶𝑛−1 → 𝐶1 uygulanırsa 67 n 1 1 1 1            n 2 1 1 1             𝑃𝑜𝑙(𝐒(𝑆 𝑛𝑛)) = −𝜆 ∙ n 1 2 1 1             n 1 1 2 1             n 1 1 1 2             (𝑛−1)×(𝑛−1) 1 1 1 1 1         2 1 1 1 1          𝑛 = −𝜆𝑛 (𝜆 − ) ∙ 1 2 1 1 1      𝜆     1 1 2 1 1          1 1 1 2 1          (𝑛−1)×(𝑛−1) elde edilir. Burada ise ilk satır −1 ile çarpılıp ikinci satırdan (𝑛 − 1). satıra kadar eklenirse 1 1 1 1 1         1 0   0 0 0  1 𝑛 0 0   0 0 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = −𝜆 𝑛 (𝜆 − ) ∙  𝜆 1 0 0 0   0  1 0 0 0 0    (𝑛−1)×(𝑛−1) determinantına ulaşılır. Bu determinantı birinci sütuna göre açılırsa 68 1   0 0  𝑛 1 𝑃𝑜𝑙(𝐒(𝑆𝑛)) = −𝜆 𝑛 (𝜆 − ) 0   0 𝜆  1 0 0    (𝑛−2)×(𝑛−2) elde edilir. Elde edilen (𝑛 − 2) × (𝑛 − 2) tipindeki determinant ise üst üçgen matrisin determinantı olup değeri köşegen üzerinde bulunan elemanların çarpımına eşittir. Böylece istenilen 𝑃𝑜𝑙(𝐒(𝑆 )) = −𝜆(𝜆2 − 1)𝑛−2𝑛 (𝜆 2 − 𝑛) eşitliği elde edilir. Teorem 7.1.3.'ün bir sonucu olarak 𝐒(𝑆𝑛) grafının spektrumu S(𝐒(𝑆𝑛)) = {0,∓√𝑛,∓1 (𝑛−2)} şeklindedir. Benzer hesaplamalar 𝐾𝑛 ve 𝐾𝑚,𝑛 graflarının alt bölüm grafları için de yapılırsa aşağıdaki sonuçlara ulaşılır: Teorem 7.1.4. 𝐾𝑛'in alt bölüm grafı olan 𝐒(𝐾𝑛) grafının karakteristik polinomu 𝑛 ≥ 1 için 𝑛(𝑛−3) 𝑃𝑜𝑙(𝐒(𝐾𝑛)) = (−1) 𝑛𝜆 2 (𝜆2 − (𝑛 − 2))𝑛−1(𝜆2 − 2(𝑛 − 1)) şeklindedir. 69 Teorem 7.1.4.'ün bir sonucu olarak 𝑃𝑜𝑙(𝐒(𝐾𝑛))'in kökleri spektrumu vereceğinden 𝐒(𝐾𝑛) grafına ait spektrumunun 𝑛(𝑛−3) ( ) (𝑛−1) S(𝐒(𝐾𝑛)) = {0 2 , ∓√𝑛 − 2 , ∓√2(𝑛 − 1)} olduğu kolayca görülmektedir. Teorem 7.1.5. 𝐾𝑚,𝑛'nin alt bölüm grafı olan 𝐒(𝐾𝑚,𝑛) grafının karakteristik polinomu 𝑃𝑜𝑙(𝐒(𝐾 )) = (−1)𝑛𝜆𝑚+(𝑚−1)(𝑛−2)(𝜆2 − (𝑚 + 𝑛))(𝜆2 −𝑚)𝑛−1(𝜆2 𝑚−1𝑚,𝑛 − 𝑛) şeklindedir. Teorem 7.1.5.'in bir sonucu olarak 𝐒(𝐾𝑛) grafının spektrumu ( ) ( ) S (𝐒(𝐾 )) = {0(𝑚+(𝑚−1)(𝑛−2)) 𝑛−1 𝑚−1 𝑚,𝑛 , ∓√𝑚 ,∓√𝑛 ,∓√𝑚 + 𝑛} şeklindedir. 7.2. Alt Bölüm Grafları için İndirgeme Bağıntıları Bir önceki bölümde 𝑃𝑛, 𝐶𝑛, 𝑆𝑛, 𝐾𝑛 ve 𝐾𝑚,𝑛 grafları için alt bölüm graflarını oluşturup karakteristik polinomlarını belirlemiştik. Bu bölümde köşe sayısı artan bölüm grafların polinomlarını hesaplamada kolaylık sağlayacak bağıntılar geliştirilecektir. Teorem 7.2.1. 𝑺(𝑆𝑛), 𝑛 köşeli bir yıldız grafın alt bölüm grafı olmak üzere 𝑃𝑜𝑙(𝑺(𝑆𝑛)) ile 𝑃𝑜𝑙(𝑺(𝑆𝑛+1)) arasında (𝜆2 − 𝑛)𝑃𝑜𝑙(𝑺(𝑆𝑛+1)) = (𝜆 2 − 1)(𝜆2 − 𝑛 − 1)𝑃𝑜𝑙(𝑺(𝑆𝑛)) 𝑛 ≥ 4 şeklinde bir indirgeme bağıntısı vardır. 70 İspat. Teorem 7.1.3.'den 𝑃𝑜𝑙(𝐒(𝑆𝑛+1)) = −𝜆(𝜆 2 − 1)𝑛−1(𝜆2 − 𝑛 − 1) şeklinde olduğu bilinmektedir. Buradan hareketle 𝑃𝑜𝑙(𝐒(𝑆𝑛+1)) = −𝜆(𝜆 2 − 1)𝑛−1(𝜆2 − 𝑛 − 1) = −𝜆(𝜆2 − 1)𝑛−2(𝜆2 − 1)(𝜆2 − 𝑛 − 1) (𝜆2−𝑛) = −𝜆(𝜆2 − 1)𝑛−2(𝜆2 − 1)(𝜆2 − 𝑛 − 1) (𝜆2−𝑛) (𝜆2 − 𝑛 − 1) = (𝜆2 − 1) ∙ 𝑃𝑜𝑙(𝑺(𝑆𝑛)) (𝜆2 − 𝑛) elde edilir. Gerekli düzenleme yapılarak (𝜆2 − 𝑛)𝑃𝑜𝑙(𝑺(𝑆 )) = (𝜆2 − 1)(𝜆2𝑛+1 − 𝑛 − 1)𝑃𝑜𝑙(𝑺(𝑆𝑛)) 𝑛 ≥ 4 sonucuna ulaşılır. Teorem 7.2.2. 𝑺(𝐾𝑛), 𝑛 köşeli bir tam grafın alt bölüm grafı olmak üzere 𝑃𝑜𝑙(𝑺(𝐾𝑛)) ile 𝑃𝑜𝑙(𝑺(𝐾𝑛+1)) arasında 2 2 𝑛 𝑛−1 (𝜆 −2𝑛)(𝜆 −𝑛+1)𝑃𝑜𝑙(𝑺(𝐾𝑛+1)) = −𝜆 𝑃𝑜𝑙(𝑺(𝐾 )) 𝑛 ≥ 1 (𝜆2−𝑛+2)𝑛−1(𝜆2−2𝑛+2) 𝑛 şeklinde bir indirgeme bağıntısı vardır. İspat. Teorem 7.1.5.ten 𝑃𝑜𝑙(𝐒(𝐾𝑛)) ve 𝑃𝑜𝑙(𝐒(𝐾𝑛+1)) polinomlarının (𝑛+1)(𝑛−2) 𝑃𝑜𝑙(𝐒(𝐾 )) = (−1)𝑛+1𝑛+1 𝜆 2 (𝜆 2 − 𝑛 + 1)𝑛(𝜆2 − 2𝑛) ve 𝑛(𝑛−3) 𝑃𝑜𝑙(𝐒(𝐾𝑛)) = (−1) 𝑛𝜆 2 (𝜆2 − 𝑛 + 2)𝑛−1(𝜆2 − 2𝑛 + 2) 71 şeklinde oldukları bilinmektedir. Teorem 7.2.1.'in ispatı için uygulanan işlem basamaklarının benzerleri burada da uygulanarak istenilen sonuca kolaylıkla ulaşılmaktadır. Alt bölüm graflarında polinom indirgeme bağıntısı, son olarak iki parçalı tam grafın alt bölüm grafı olan 𝐒(𝐾𝑚,𝑛) için oluşturulacaktır. Teorem 7.2.3. 𝑺(𝐾𝑚,𝑛), 𝑚 + 𝑛 köşeli iki parçalı tam bir grafın alt bölüm grafı olmak üzere 𝑃𝑜𝑙 (𝑺(𝐾𝑚,𝑛)) ile 𝑃𝑜𝑙 (𝑺(𝐾𝑚+1,𝑛)) arasında 𝜆𝑛−1 2 𝑛−1 (𝜆 −𝑚−𝑛−1)(𝜆2−𝑚−1) (𝜆2−𝑛) 𝑃𝑜𝑙 (𝑺(𝐾𝑚+1,𝑛)) = 2 2 𝑃𝑜𝑙 (𝑺(𝐾𝑚,𝑛)) (𝜆 −𝑚−𝑛)(𝜆 −𝑚) şeklinde bir indirgeme bağıntısı vardır. Buraya kadar alt bölüm operasyonu ile elde edilen yeni grafların polinomları ve bu polinomlar için indirgeme bağıntıları verilmiştir. Burada ise yeni bir alt bölüm operasyonu olan r-altbölüm işlemi tanımlanacaktır. Tanım 7.2. 𝐺(𝑉, 𝐸) bir graf olsun. 𝐸 kümesinden bir köşesi 𝑢 diğer köşesi 𝑣 olan bir 𝑢𝑣 kenarı alınsın. Alınan bu 𝑢𝑣 kenarı üzerine, her birinin derecesi 2 olacak şekilde, 𝑟- tane yeni köşe eklenerek 𝑢𝑣 kenarı 𝑃𝑟+2 şekline dönüştürülsün. Bu işlem 𝐸 kümesinin tüm elemanlarına uygulanarak oluşturulan yeni grafa 𝒓-alt bölüm graf denir ve 𝑺𝒓(𝐺) ile gösterilir. Teorem 7.2.4. 𝑺𝒓(𝑃𝑛), 𝑛 köşeli yol grafın 𝑟-alt bölüm grafı olsun. Bu grafın karakteristik polinomu 𝑃𝑜𝑙(𝑺𝒓(𝑃𝑛)) = 𝑃𝑜𝑙(𝑃 𝒓 𝑛(𝑟+1)−𝑟) ve |𝑉(𝑺 (𝐶𝑛))| = 𝑛(𝑟 + 1) − 𝑟 şeklindedir. 72 Teorem 7.2.5. 𝑺𝒓(𝐶𝑛), n köşeli devir grafın 𝑟-alt bölüm grafı olsun. Bu grafın karakteristik polinomu 𝑃𝑜𝑙(𝑺𝒓(𝐶𝑛)) = 𝑃𝑜𝑙(𝐶𝑛(𝑟+1)) ve |𝑉(𝑺 𝒓(𝐶𝑛))| = 𝑛(𝑟 + 1) şeklindedir. 7.3. Alt Bölüm Grafları için Enerji Bağıntıları E. Hückel tarafından, bir 𝐺 grafının özdeğerlerinin mutlak değerlerce toplamı olarak tanımlanan graf enerjisi kavramı, graf teorinin alt alanlarından biri olan spektral graf teori için de oldukça önemlidir (Hückel 1933). Ayrıca moleküler hesaplamalarda da oldukça sık başvurulan grafların enerjisi kavramı, bu bölümde yapısal olarak 𝐾𝑛, 𝑆𝑛 ve 𝐾𝑚,𝑛 graflarına ait alt bölüm graflar için incelenecektir (Cvetkovic ve ark. 1995, Adiga ve ark. 2007). İlk olarak 𝐒(𝐾𝑛) grafının enerji bağıntısı hesaplanacaktır. Teorem 7.3.1. 𝐸(𝑺(𝐾𝑛)), 𝐒(𝐾𝑛) grafının enerjisi olmak üzere bu grafın enerjisi 𝐸(𝑺(𝐾𝑛)) = 2 ((𝑛 − 1)√𝑛 − 2 + √2(𝑛 − 1)) bağıntısı ile hesaplanır. İspat. Teorem 7.1.4.'in bir sonucu olarak 𝐒(𝐾𝑛) grafının spektrumu 𝑛(𝑛−3) ( ) (𝑛−1) S(𝐒(𝐾𝑛)) = {0 2 , ∓√𝑛 − 2 , ∓√2(𝑛 − 1)} şeklinde verilmiştir. Spektrumun elemanlarının mutlak değerlerinin toplamı alındığında istenilen sonuca kolaylıkla ulaşılır. 73 İkinci olarak 𝐒(𝑆𝑛) grafının enerji bağıntısı hesaplanacaktır. Teorem 7.3.2. 𝐸(𝑺(𝑆𝑛)), 𝐒(𝑆𝑛) grafının enerjisi olmak üzere bu grafın enerjisi 𝐸(𝑺(𝑆𝑛)) = 2(𝑛 − 2 + √𝑛) bağıntısı ile hesaplanır. İspat. Teorem 7.1.3.'ün bir sonucu olarak 𝐒(𝑆𝑛) grafının spektrumu S(𝐒(𝑆𝑛)) = {0,∓1 𝑛−2, ∓√𝑛} şeklinde verilmiştir. Spektrumun elemanlarının mutlak değerlerinin toplamı alındığında istenilen sonuca kolaylıkla ulaşılır. Bu bölümde son olarak ise 𝐒(𝐾𝑚,𝑛) grafı için enerji bağıntısı verilecektir. Teorem 7.3.3. 𝐸 (𝑺(𝐾𝑚,𝑛)), 𝐒(𝐾𝑚,𝑛) grafının enerjisi olmak üzere bu grafın enerjisi 𝐸 (𝑺(𝐾𝑚,𝑛)) = 2(√𝑚 + 𝑛 + (𝑛 − 1)√𝑚 + (𝑚 − 1)√𝑛) bağıntısı ile hesaplanır. İspat. Teorem 7.1.5.'in bir sonucu olarak 𝐒(𝐾𝑚,𝑛) grafının spektrumu (𝑛−1) (𝑚−1) S (𝐒(𝐾 (𝑚+(𝑚−1)(𝑛−2))𝑚,𝑛)) = {0 ,∓√𝑚 ,∓√𝑛 ,∓√𝑚 + 𝑛} şeklinde verilmiştir. Spektrumun elemanlarının mutlak değerlerinin toplamı alındığında istenilen sonuca kolaylıkla ulaşılır. 74 8. BULGULAR, TARTIŞMA VE SONUÇ 8.1. Bulgular Bu tezde klasik graf enerjisi ile ilgili dört ana konu incelenmiştir. Bu dört konudan birisinde var olan sonuçlara yenileri eklenmiş, üçünde ise tamamen ilk defa çalışılan yeni sonuçlar elde edilmiştir. Ele alınan ilk problem grafların spektral (karakteristik) polinomları ile ilgilidir. Bu problem daha önce çeşitli bilim insanları tarafından çalışılmış olup burada varolan sonuçlara yenileri eklenmiştir. Devir, patika, yıldız, tam graflar gibi belli başlı graf sınıflarının karakteristik polinomları hesaplanmış ve bunlar arasında indirgeme bağıntıları elde edilmiştir. İkinci problemde patika ve devir graflarının graf enerjileri arasında indirgeme bağıntıları elde edilmiştir. Bu tür bir indirgeme bağıntısı yardımıyla örneğin 5 köşeli bir grafın enerjisini bildiğimizde 10 köşeli, 20 köşeli, 40 köşeli, vs. benzer grafların enerjilerini kolayca hesaplamak mümkün olmaktadır. Üçüncü problemde graf birleşiminin karakteristik polinoma ve grafın enerjisine etkisi hesaplanmıştır. Dördüncü problemde ise kimyasal uygulamaları olan alt bölme graflarının enerjileri, grafın kendi enerjisi cinsinden hesaplanmıştır. 8.2. Tartışma ve Sonuç Bu tezde graf enerjisi ile ilgili büyük çoğunluğu yeni ve tümü orijinal sonuçlar elde edilmiştir. Enerji kavramının kimyasal uygulamaları nedeniyle bu tezde bulunan sonuçların hem bu konuda çalışacak matematikçilere, hem de konunun moleküler boyuttaki uygulamalarını yapan kimyacılara faydalı olacağı ve yol göstereceği düşünülmektedir. Bu tezde elde edilen sonuçlardan hareketle daha ileri çalışmalar da yapılabilir. Örneğin, alt bölme grafları dışındaki diğer türetilmiş grafların enerjileri, ana grafın enerjisi cinsinden hesaplanabilir. Benzer şekilde iki graftan bir işlemle elde edilen yeni bir grafın 75 enerjisi, bileşen grafların enerjilerine bağlı olarak elde edilebilir. Graf enerjisi kavramı diğer graf enerjileriyle karşılaştırılabilir ve yapılacak mukayese sonucunda hangi uygulamalarda hangi enerji türünün kullanımının avantajlı olduğu belirlenebilir. Diğer graf türleri için enerji hesabı yapılabilir. Ayrıca graf enerjisi kavramı, diğer graf kavramlarıyla ilişkilendirilebilir. 76 KAYNAKLAR Adiga, C., Khoshbakht, Z., Gutman, I., 2007. More graphs whose energy exceeds the number of vertices, Iranian Journal of Mathematical Sciences and Informatics, 2(2), 57- 62. Balakrishnan, R., Ranganathan, K. 2012. A Textbook of Graph Theory, Springer, New York., 425 pp. Berge, C. 2001. The Theory of Graphs, Fletcher & Son Ltd., UK. Biggs, N. L., Lloyd, E. K., Wilson, R. J. 1986. Graph Theory 1736-1936, Oxford University Press, London. Bollobas, B. 1998. Modern Graph Theory, Springer, New York. Bondy, J. A., Murty, U. S. R. 2008. Graph Theory, Springer, New York. Brouwer, A. E., Haemers, W. H., 2012. Spectra of Graphs, Springer, New York. Chen, W. 1976. Applied Graph Theory, North-Holland Publishing Company, New York. Cvetkovic, D., Doob, M., Sachs, H., 1995. Spectra of Graphs - Theory and Aplications, Academic Press, Heidelberg. Çelik, F. 2016. Graflar ve Enerji. Yüksek Lisans Tezi, Uludağ Üniversitesi, Fen Bilimleri Enstitüsü, Matematik Anabilim Dalı, Bursa. Çelik, F., Cangül, İ. N., 2017. Formulae and Recurrence Relations on Spectral Polynomials of Some Graphs. Advanced Studies Contemporary Mathematics, 27 (3): 325-332. Çelik, F., Cangül, İ. N., 2018. Some Recurrence Relations for The Energy of Cycle and Path Graphs. Proceeding of the Jangjeon Mathematical Society, 21 (3): 347-355. Çelik, F., Cangül, İ. N., 2019. On the Spectra of Cycles and Paths, Turkic World of Mathematical Society Journal of Applied and Engineering Mathematics, 9 (3): 571-580. Çelik, F., Şanlı, U., Cangül, İ. N., 2021. The Spectral Polynomials of Two Joining Graphs: Splices and Links, Boletim da Sociedade Paranaense de Matemática, 39: 1-12. Çevik, A. S., Gutman, I., Güngör, A. D., Bozkurt, S. B., 2010. Randic Matrix and Randic Energ, Communications in Mathematical and in Computer, 64 (1): 239-250. Foulds, L. R. 1992. Graph Theory Applications, Springer, New York. Golumbic, M. C., Hartman, I. B. 2005. Graph Theory, Combinatorics and Algorithms, 77 Springer, New York. Gutman, I., 1978. The Energy of a Graph. Ber. Math. Statist. Sekt. Forshungsz. Graz 103, 1−22. Hückel, E., 1933. Die freien Radikale der organischen Chemie, Zeitschrift für Physik 83, 632-668. Harary, F. 1994. Graph Theory, Addison-Wesley, USA. Harris, J. M., Hirst, J. L., Mossinghoff, M. J. 2008. Combinatorics and Graph Theory, Springer, New York. Li, X., Shi, Y., Gutman, I., 2012. Graph Energy. Springer, New York. Nikiforov, V., 2007. The energy of graphs and matrices. J. Math. Anal. Appl. 326, 1472- 1475. Şanlı, U., Çelik, F., Delen, S., Cangül, İ. N., 2020. Connectedness Criteria for Graphs by Means of Omega Invariant, FILOMAT 34 (2): 1-6 Togan, M., Yurttaş, A., Şanlı, U., Çelik, F., Cangül, İ. N., 2020. Inverse problem for Bell Index, FILOMAT 34 (2): 1-7. Walikar, H. B., Ramane, H. S., Hampiholi, P. R., 1999. On the energy of a graph, in: R. Balakrishnan, H. M. Mulder, A. Vijayakumar (Eds.), Graph Connections, Allied Publishers, New Delhi, pp. 120-123. West, D. B. 1996. Introduction to Graph Theory. Upper Saddle River, Prentice Hall. Yurttaş Güneş, A., Togan, M., Çelik, F., Cangül, İ. N., 2019. Cut Vertex and Cut Edge Problem for the Topological Indices of Graphs, Journal of Taibah University for Science, 13 (1): 1175-1183. 78