BAZI TÜRETİLMİŞ GRAFLARIN KOMŞULUK MATRİSLERİ VE STATÜ İNDEKSLERİ Berke ÖZMEN T.C. BURSA ULUDAĞ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ BAZI TÜRETİLMİŞ GRAFLARIN KOMŞULUK MATRİSLERİ VE STATÜ İNDEKSLERİ Berke ÖZMEN Aysun YURTTAŞ GÜNEŞ (I.Danışman) İsmail Naci CANGÜL (II. Danışman) YÜKSEK LİSANS TEZİ MATEMATİK ANABİLİM DALI BURSA – 2025 Her Hakkı Saklıdır TEZ ONAYI Berke ÖZMEN tarafından hazırlanan “Bazı türetilmiş grafların komşuluk matrisleri ve statü indeksleri” adlı tez çalışması aşağıdaki jüri tarafından oy birliği ile Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalında YÜKSEK LİSANS TEZİ olarak kabul edilmiştir. Danışman: Doç. Dr. Aysun YURTTAŞ GÜNEŞ İkinci Danışman: Prof. Dr. İsmail Naci CANGÜL (Bursa Uludağ Üniversitesi) Başkan: Prof. Dr. Musa DEMİRCİ 0000-0002-6439-8439 Bursa Uludağ Üniversitesi, Fen-Edebiyat Fakültesi, Matematik Anabilim Dalı İmza Üye : Doç. Dr. Aysun YURTTAŞ GÜNEŞ 0000-0001-8873-1999 Bursa Uludağ Üniversitesi, Fen-Edebiyat Fakültesi, Matematik Anabilim Dalı İmza Üye : Dr. Öğrt. Üye. Mert Sinan ÖZ 0000-0002-6206-0362 Bursa Teknik Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Matematik Anabilim Dalı İmza Yukarıdaki sonucu onaylarım Prof. Dr. Ali KARA Enstitü Müdürü ../../2025 B.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ı, - ve 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. 28/02/2025, İmza Berke ÖZMEN TEZ YAYINLANMA FİKRİ MÜLKİYET HAKLARI BEYANI Enstitü tarafından onaylanan lisansüstü tezin/raporun tamamını veya herhangi bir kısmını, basılı (kâğıt) ve elektronik formatta arşivleme ve aşağıda verilen koşullarla kullanıma açma izni Bursa Uludağ Üniversitesi’ne aittir. Bu izinle Üniversiteye verilen kullanım hakları dışındaki tüm fikri mülkiyet hakları ile tezin tamamının ya da bir bölümünün gelecekteki çalışmalarda (makale, kitap, lisans ve patent vb.) kullanım hakları tarafımıza ait olacaktır. Tezde yer alan telif hakkı bulunan ve sahiplerinden yazılı izin alınarak kullanılması zorunlu metinlerin yazılı izin alınarak kullandığını ve istenildiğinde suretlerini Üniversiteye teslim etmeyi taahhüt ederiz. Yükseköğretim Kurulu tarafından yayınlanan “Lisansüstü Tezlerin Elektronik Ortamda Toplanması, Düzenlenmesi ve Erişime Açılmasına İlişkin Yönerge” kapsamında, yönerge tarafından belirtilen kısıtlamalar olmadığı takdirde tezin YÖK Ulusal Tez Merkezi / B.U.Ü. Kütüphanesi Açık Erişim Sistemi ve üye olunan diğer veri tabanlarının (Proquest veri tabanı gibi) erişimine açılması uygundur. Danışman Adı-Soyadı Tarih Öğrencinin Adı-Soyadı Tarih İmza Bu bölüme kişinin kendi el yazısı ile okudum anladım yazmalı ve imzalanmalıdır. İmza Bu bölüme kişinin kendi el yazısı ile okudum anladım yazmalı ve imzalanmalıdır. BURSA ULUDAĞ ÜNİVERSİTESİ LİSANSÜSTÜ TEZ TANITIMI ÖĞRENCİ VE DANIŞMAN FORMU FR 3.4.6_27 DANIŞMAN Adı SOYADI : Aysun Yurttaş GÜNEŞ ÜNVANI : Doçent Doktor FEN BİLİMLERİ ENSTİTÜSÜ MATEMATİK ABD E-POSTA : ayurttas@uludag.edu.tr YÖKSİS ARAŞTIRMACI ID : ORCID : 0000-0001-8873-1999 TÜBİTAK ID : 156622 WOS RESEARCHER ID : MDT-6149-2025 SCOPUS AUTHOR ID : 37090056000 Google Scholar ID : 6SO9120AAAAJ ÖĞRENCİ Adı SOYADI : Berke ÖZMEN ÜNVANI : Yüksek Lisans Öğrencisi FEN BİLİMLERİ ENSTİTÜSÜ MATEMATİK ABD E-POSTA : berkeozmen1864@gmail.com PROGRAMI: YÜKSEK LİSANS ORCID : 0000-0003-1067-5151 TÜBİTAK ID : TBTK-0140-6508 WOS RESEARCHER ID : MDT-6149-2025 SCOPUS AUTHOR ID : Google Scholar ID : 96R4LFcAAAAJ BURSA ULUDAĞ ÜNİVERSİTESİ YÜKSEK LİSANS/DOKTORA EĞİTİMİ BOYUNCA BİLİMSEL ÇALIŞMALARI VE FAALİYETLERİ* 1. Balseven, Y., Kose, D., Ozmen, B., Yurttas Gunes, A., Ozden Ayna, H., Cangul, Ismail Naci, Some New Properties of Line Graphs and Their Omega Invariants, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) 2. Ozmen, B., Balseven, Y., Kose, D., Ozden Ayna, H., Yurttas Gunes, A., Cangul, Ismail Naci, Power Graphs of Some Graph Classes, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) 3. Kose, D., Ozmen, B., Balseven, Y., Ozden Ayna, H., Yurttas Gunes, A., Cangul, Ismail Naci, Omega Invariant of Second and Third Power Graphs of Tadpole Graphs, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler 4.182.125- Graflar Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler Anahtar Kelimeler i ÖZET Yüksek Lisans Tezi BAZI TÜRETİLMİŞ GRAFLARIN KOMŞULUK MATRİSLERİ VE STATÜ İNDEKSLERİ Berke ÖZMEN Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı Danışman: Doç. Dr. Aysun YURTTAŞ GÜNEŞ İkinci Danışman: Prof. Dr. İsmail Naci CANGÜL (Bursa Uludağ Üniversitesi) Bu tezde bazı türetilmiş grafların komşuluk, bitişiklik ve mesafe matrisleri elde edilmiş ve bu matrisler yardımıyla grafların statü indeks hesaplamaları ele alınmıştır. Bu tez üç bölümden oluşmaktadır. Birinci bölümde, graflarla ilgili temel tanımlara, grafların kullanım alanlarına, graf türlerine ve grafların matrislerine yer verilmiştir. İkinci bölümde, grafların komşuluk, bitişiklik ve mesafe matrisleri arasındaki dönüşümler yardımıyla S1 ve S2 statü indeks hesapları verilmiştir. Üçüncü bölümde ise graf türlerinin çekirdek, gölge ve görüntü graflarının ve graf işlemlerinin komşuluk matrisleri bulunmuştur. Anahtar Kelimeler: çekirdek graf, gölge graf, görüntü graf, statü indeks 2025, IIIV+50 sayfa ii ABSTRACT Master Thesis ADJACENCY MATRICES AND STATUS INDICES OF SOME DERIVED GRAPHS Berke ÖZMEN Bursa Uludağ University Graduate School of Natural and Applied Sciences Department of Mathematics Supervisor: Assoc. Prof. Dr. Üyesi Aysun YURTTAŞ GÜNEŞ Second Supervisor: Prof. Dr. İsmail Naci CANGÜL (Bursa Uludağ University) In this thesis, neighborhood, adjacency and distance matrices of some derived graphs are obtained and status index calculations of graphs are discussed with the help of these matrices. This thesis consists of three parts. In the first part, basic definitions about graphs, usage areas of graphs, graph types and graph matrices are given. In the second part, S1 and S2 status index calculations are given with the help of transformations between neighborhood, adjacency and distance matrices of graphs. In the third part, neighborhood matrices of core, shadow and image graphs of graph types and graph operations are found. Keywords: kernel graph, shadow graph, image graph, status index 2025, IIIV+ 50 pages iii ÖNSÖZ ve TEŞEKKÜR Bu tezin hazırlanma sürecinde bana her zaman destek olan, sabırlarını ve anlayışlarını esirgemeyen aileme en derin şükranlarımı sunarım. Özellikle zorlu zamanlarda yanımda olarak bana güç verdiler ve bu başarıya ulaşmamda büyük bir rol oynadılar. Onların sevgisi ve desteği olmasaydı, bu yolculuğu tamamlamak çok daha zor olurdu. Ayrıca, tez sürecim boyunca bilgi ve deneyimlerini benimle paylaşan, yol gösteren ve her aşamada bana rehberlik eden danışmanım Doç. Dr. Aysun YURTTAŞ GÜNEŞ’e, akademik çevremdeki hocalarım Prof. Dr. İsmail Naci CANGÜL’e ve Doç. Dr. Hacer ÖZDEN AYNA’ya içten teşekkürlerimi sunarım. Onların değerli katkıları ve yapıcı eleştirileri, bu çalışmanın daha nitelikli bir hale gelmesine büyük ölçüde katkı sağlamıştır. Bunun yanı sıra, arkadaşlarım Duygu Köse’ye ve Yasin Balseven’e ve çalışma arkadaşlarıma da teşekkür etmek isterim. Motivasyonumu yüksek tutmamda, bana ilham vermede ve her zaman yanımda olarak bu süreci daha keyifli hale getirmede büyük payları var. Onların dostlukları ve desteği, bu zorlu süreçte beni ayakta tutan önemli bir güç kaynağı oldu. Son olarak, bu tezin tamamlanmasında doğrudan veya dolaylı olarak katkısı bulunan herkese minnettarlığımı ifade etmek isterim. Her birinizin desteği ve katkısı, bu başarıya ulaşmamda büyük bir anlam taşıyor. Hepinize sonsuz teşekkürler. Berke Özmen …/…/2025 iv SİMGELER ve KISALTMALAR Simgeler Açıklama 𝑛 Köşe sayısı 𝑚 Kenar sayısı 𝑉(𝐺) 𝐺 grafının köşe kümesi 𝐸(𝐺) 𝐺 grafının kenar kümesi 𝐺 = (𝑉, 𝐸) 𝐺 𝐺raf |𝑉(𝐺)| 𝐺 grafının mertebesi |𝐸(𝐺)| 𝐺 grafının boyutu (𝑢, 𝑣) 𝐺 grafının komşu noktaları d(𝑢, 𝑣) 𝐺 grafının noktalarının en kısa uzaklığı 𝑑eg(𝑣𝑛) 𝐺 grafının derecesi 𝑁𝑛 𝑛 köşeli boş graf 𝑃𝑛 𝑛 köşeli yol graf 𝐶𝑛 𝑛 köşeli çevre graf 𝐾𝑛 𝑛 köşeli tam graf 𝐾𝑛,𝑚 İki parçalı tam graf 𝑆𝑛 𝑛 köşeli yıldız graf 𝑊𝑛 𝑛 köşeli tekerlek graf 𝑇r,s Larva grafı 𝐿𝑛 Merdiven grafı 𝑊𝑛,𝑚 Yel değirmeni grafı 𝐷𝑟,𝑠 Dostluk grafı 𝑃 Petersen grafı 𝑇𝑛 Taç grafı Im×n m×n birim matris Jm×n m×n tüm girdileri 1 olan matris 0m×n m×n tüm girdileri 0 olan matris Kısaltmalar Açıklama A Bitişiklik matrisi B Bitişiklik matris D Mesafe matrisi M1 Birinci Zagreb İndeksi M2 İkinci Zagreb İndeksi W Wiener İndeksi S1 Statü birinci indeksi S2 Statü ikinci indeksi S Statü matrisi S Statü dizisi deg Derece dizisi d Grafın çapı v İÇİNDEKİLER Sayfa ÖZET..................................................................................................................................i ABSTRACT......................................................................................................................ii ÖNSÖZ ve TEŞEKKÜR .................................................................................................iii SİMGE ve KISALTMALAR DİZİNİ..............................................................................iv ŞEKİLLER DİZİNİ.........................................................................................................vii ÇİZELGELER DİZİNİ………………...........................................................................viii 1. GRAFLARA GİRİŞ ...................................................................................................... 1 1.1. GRAF İLE İLGİLİ TEMEL KAVRAMLAR ............................................................. 2 1.1.1. KÖŞE VE KENAR ................................................................................................. 2 1.1.2. DERECE VE OMEGA İNVARYANT .................................................................... 2 1.1.3. BASİT BAĞLANTILI VE BAĞLANTISIZ GRAF ............................................... 3 1.1.4. YÖNLENDİRİLMİŞ VE YÖNLENDİRİLMEMİŞ GRAFLAR ............................ 4 1.1.5. PATİKA, AĞAÇ VE DEVİR GRAFLARI ............................................................. 4 1.1.6. UZAKLIK ............................................................................................................... 5 1.1.7. ÇAP, YARIÇAP VE MERKEZ ............................................................................... 5 1.1.8. KOMŞULUK MATRİSİ ......................................................................................... 6 1.1.9. DERECE MATRİSİ ................................................................................................ 6 1.1.10. BİTİŞİKLİK MATRİSİ ......................................................................................... 7 1.1.11. LAPLACE MATRİSİ ............................................................................................ 8 1.1.12. MESAFE MATRİSİ .............................................................................................. 8 1.1.13. STATÜ ................................................................................................................... 9 2. GRAF HESAPLAMALARI İÇİN YARDIMCI ÖZELLİKLER ................................ 10 2.1. BAZI TEMEL KAVRAMLAR ................................................................................ 10 2.1.1. HADAMARD ÇARPIMI ..................................................................................... 10 2.1.2. STATÜ DİZİSİ ...................................................................................................... 10 2.1.3. SİGNUM MATRİSİ .............................................................................................. 11 2.1.4. BİTİŞİKLİK MATRİSİ YARDIMIYLA KOMŞULUK MATRİSİ HESABI ....... 12 2.1.5. KOMŞULUK MATRİSİ YARDIMIYLA MESAFE MATRİSİ HESABI ............ 13 2.1.6. MESAFE MATRİSİ YARDIMIYLA KOMŞULUK MATRİSİNİN HESABI ..... 14 2.1.7. BİRİNCİ VE İKİNCİ STATÜ İNDEKSLERİNİN HESAPLANMASI ............... 15 2.1.8. WİENER İNDEKSİ .............................................................................................. 17 2.1.9. BİRİNCİ VE İKİNCİ ZAGREB İNDEKSLERİ ................................................... 17 3. ÖZEL GRAFLAR VE STATÜ İNDEKSLERİ ........................................................... 19 3.1. SIFIR GRAFI ........................................................................................................... 19 3.2. PATİKA GRAFI ....................................................................................................... 19 3.3. DEVİR GRAFI ........................................................................................................ 21 3.4. YILDIZ GRAFI........................................................................................................ 22 3.5. TAM GRAFI ............................................................................................................ 23 3.6. LARVA GRAFI ........................................................................................................ 25 3.7. MERDİVEN GRAFI ................................................................................................ 26 3.8. TEKERLEK GRAFI ................................................................................................ 27 3.9. ÇARK GRAFI .......................................................................................................... 28 3.10. PETERSEN GRAFI ............................................................................................... 29 3.11. DOSTLUK GRAFI ................................................................................................ 30 3.12. YEL DEĞİRMENİ GRAFI .................................................................................... 31 vi 3.13. İKİ PARÇALI TAM GRAFI .................................................................................. 33 4. TÜRETİLMİŞ GRAFLAR ......................................................................................... 34 4.1.1. DOĞRU GRAFI ................................................................................................... 34 4.1.2. ÇEKİRDEK GRAFI ............................................................................................. 35 4.1.3. GÖRÜNTÜ GRAFI .............................................................................................. 36 4.2. GÖLGE GRAFI ....................................................................................................... 37 4.3. GRAFLARDA İŞLEMLER ..................................................................................... 38 4.3.1. KÖŞE BİRLEŞİMİ ............................................................................................... 38 4.3.2. KÖPRÜ EKLEME ................................................................................................ 40 4.3.3. TOPLAMA............................................................................................................ 41 4.3.4. KARTEZYEN ÇARPIM ....................................................................................... 43 4.3.5. SİMETRİK FARK ................................................................................................ 45 4.3.6. TAÇ ÇARPIMI ..................................................................................................... 46 5. SONUÇ ....................................................................................................................... 48 KAYNAKLAR ................................................................................................................ 49 ÖZGEÇMİŞ .................................................................................................................... 50 vii ŞEKİLLER DİZİNİ Sayfa Şekil 1.1. Königsberg efsanevi yedi köprüsü 1 Şekil 1.2. Königsberg’in yedi köprüsü grafı 2 Şekil 1.3 Bir grafın temsili 2 Şekil 1.4 Şekil 1.3’deki grafın derece temsili 3 Şekil 1.5 Şekil 1.3’deki grafın bağlantılı ve bağlantısız temsili 4 Şekil 1.6 Şekil 1.3’deki grafın yönlendirilmiş temsili 4 Şekil 1.7 Şekil 1.3’deki grafın üzerindeki patika, devir ve bir ağaç grafı 5 Şekil 1.8 Şekil 1.3’teki grafın merkez, çap ve yarıçapı 6 Şekil 2.1 Yönlendirilmiş ve ağırlıklı graf ve onun signum grafı 11 Şekil 2.2 Bir grafın çapı 13 Şekil 3.1 Sıfır grafı 19 Şekil 3.2 Patika grafı 20 Şekil 3.3 Devir grafı 21 Şekil 3.4 Yıldız grafı 22 Şekil 3.5 Tam graf 24 Şekil 3.6 Larva grafı 25 Şekil 3.7 Merdiven grafı 26 Şekil 3.8 Tekerlek grafı 27 Şekil 3.9 Çark grafı 28 Şekil 3.10 Petersen graf 29 Şekil 3.11 Dostluk grafı 30 Şekil 3.12 Yel değirmeni grafı 31 Şekil 3.13 İki parçalı tam graf 33 Şekil 4.1 Şekil 1.3’deki grafın doğru grafı 34 Şekil 4.2 Bir grafın çekirdeği 35 Şekil 4.3 Görüntü grafı 36 Şekil 4.4 Gölge grafı 37 Şekil 4.5 Bir köşede birleştirilmiş graf 38 Şekil 4.6 İki grafın köprü ile birleştirilmesi 40 Şekil 4.7 İki grafın toplamı 42 Şekil 4.8 İki grafın kartezyen çarpımı 44 Şekil 4.9 Grafların simetrik farkı 45 Şekil 4.10 Taç çarpımı 46 viii ÇİZELGELER DİZİ Nİ Sayfa Çizelge 1.1. Şekil 1.3’deki grafın komşuluk matrisi 6 Çizelge 1.2 Şekil 1.3’deki grafın derece dizisinin derece matrisi 7 Çizelge 1.3 Şekil 1.3’deki grafın bitişiklik matrisi 7 Çizelge 1.4 Şekil 1.3’deki grafın Laplace matrisi 8 Çizelge 1.5 Şekil 1.3’deki grafın mesafe matrisi 8 Çizelge 2.1 Şekil 1.3’deki grafın mesafe matrisi ve statü dizisi 10 Çizelge 2.2 Şekil 2.1’deki grafın ağırlık matrisinin signum matrisi 11 Çizelge 2.3 Şekil 1.3’deki grafın bitişiklik matrisi ile komşuluk matrisi hesabı 12 Çizelge 2.5 Şekil 1.3’deki grafın mesafe matrisi hesabı 14 Çizelge 2.6 Şekil 1.3’teki grafın mesafe ve komşuluk matrisi 15 Çizelge 2.7 Şekil 1.3’deki grafın S matrisi ile statü dizisi hesabı 15 Çizelge 2.8 Şekil 1.3’deki grafın S1 statü indeksi hesabı 16 Çizelge 2.8 Şekil 1.3’deki grafın S2 statü indeksi hesabı 16 Çizelge 2.10 Şekil 1.3’deki grafın birinci Zagreb indeksi 17 Çizelge 2.11 Şekil 1.3’deki grafın ikinci Zagreb indeks 18 Çizelge 3.1 Şekil 3.1’deki grafın A, B ve D matrisleri 19 Çizelge 3.2 Şekil 3.12’deki patika grafının A, B ve D matrisleri 20 Çizelge 3.3 Şekil 3.3’deki devir grafının A, B ve D matrisleri 22 Çizelge 3.4 Şekil 3.4’daki devir grafının A, B ve D matrisleri 23 Çizelge 3.5 Şekil 3.5’deki tam grafın A, B ve D matrisleri 24 Çizelge 3.6 Şekil 3.6’deki larva grafının A, B ve D matrisleri 25 Çizelge 3.7 Şekil 3.7’daki merdiven grafının A, B ve D matrisleri 26 Çizelge 3.8 Şekil 3.8’deki tekerlek grafının A, B ve D matrisleri 27 Çizelge 3.9 Şekil 3.9’daki çark grafının A, B ve D matrisleri 28 Çizelge 3.10 Şekil 3.10’deki Petersen grafının A, B ve D matrisleri 29 Çizelge 3.11 Şekil 3.11’deki dostluk grafının A, B ve D matrisleri 30 Çizelge 3.12 Şekil 3.12’deki yel değirmeni grafının A, B ve D matrisleri 32 Çizelge 3.13 Şekil 3.13’deki iki parçalı tam grafının A, B ve D matrisleri 33 Çizelge 4.1 Doğrusal grafın komşuluk matrisi hesabı 34 Çizelge 4.2 Çekirdek grafın komşuluk matrisi hesabı 35 Çizelge 4.3 Görüntü grafın komşuluk matrisi 36 Çizelge 4.4 Gölge grafın komşuluk matris 37 Çizelge 4.5 Bir köşede birleştirilmiş grafın komşuluk matrisi 38 Çizelge 4.6 Bir köşede birleştirilmiş grafın mesafe matrisi 39 Çizelge 4.7 Bir köprü ile birleştirilmiş grafın komşuluk matrisi 40 Çizelge 4.8 Bir köprü ile birleştirilmiş grafın mesafe matrisi 41 Çizelge 4.9 İki grafın toplamının komşuluk matrisi 42 Çizelge 4.10 İki grafın kartezyen çarpımın komşuluk matrisi 44 Çizelge 4.11 Grafların simetrik farkının komşuluk matrisi 45 Çizelge 4.12 Taç çarpımı komşuluk matrisi 47 1 1. GRAFLARA GİRİŞ Graflarla ilgili serüven, 1736 yılında matematiğin büyük ustalarından Leonhard Euler'in, Königsberg kasabasının sakin sularında yedi köprüyle örülü bir adacık olan Kneigh'in etrafında dönüp dolaşıp başlangıç noktasına geri dönebilir mi sorusuyla başladı. Şekil 1.1 Königsberg efsanevi yedi köprüsü Şekil 1.1'de görülen Königsberg ve onun efsanevi yedi köprüsü, sadece bir coğrafyanın değil, aynı zamanda matematik dünyasının da sınırlarını zorluyordu. Euler, bu sorunu bir matematik şölenine dönüştürerek graf teorini temelini atmıştı. Pregel Nehri'nin bu köprülerle bölünen dört bölgeyi aşıp, yedi köprüyü birer kez geçerek başlangıç noktasına dönebilme sorusu sadece Königsberg sakinlerini değil, tüm matematik dünyasını büyülemiştir. Euler'in simgelerle dokuduğu bu matematiksel hikâye, Graf Teori'nin kapılarını aralayarak, matematiksel düşüncenin sınırlarını genişletti. Biggs, Lloyd ve Wilson (1986), bu büyülü anıyı hatırlatarak Euler'in bu serüvenle başlattığı matematiksel devrimi vurguladı. Bilgisayar bilimleri, ağ tasarımı, ulaşım planlaması gibi birçok alanda Graf Teori'nin izleri görülebilir. Euler'in bu efsanevi hikayesi, matematiğin sadece bir problem çözme aracı olmanın ötesinde bir keşif ve sanat alanı olduğunu vurgulayarak, matematik dünyasına kattığı derinlikle hatırlanmaktadır. 2 Şekil 1.2. Königsberg’in yedi köprüsü grafı 1.1. Graf ile İlgili Temel Kavramlar 1.1.1. Köşe ve kenar G = (V, E) ikilisine graf denir. Bir grafta köşe kümesi 𝑉(𝐺) = {𝑣1, 𝑣2, … , 𝑣𝑛} olmak üzere |𝑉(𝐺)| = n sayısına grafın mertebesi, kenar kümesi E(𝐺) = {𝑒1, 𝑒2, … , 𝑒𝑚} olmak üzere |𝐸(𝐺)| = 𝑚 sayısına grafın boyutu denilir. Şekil 1.3 Bir grafın temsili 1.1.2. Derece ve omega invaryant Bir 𝐺 grafında bir köşeye komşu olan köşelerin sayısına o köşenin derecesi denilir ve 𝑑eg(𝑣𝑖) ile ifade edilir. Bir 𝐺 grafının köşe derecelerinin toplamı kenarının sayısının iki katına eşittir (Euler, 1736). Yani 3 2𝑚 = ∑ 𝑑𝑒𝑔(𝑣𝑖) 𝑣𝑖∈𝑉 (1.1) olur. 𝐷 = {1(𝑎1), 2(𝑎2), 3(𝑎3), … , ∆(𝑎∆)}, ifadesi derece dizisi olarak tanımlanır. Sırasıyla her dereceden kaç tane eleman olduğunu belirtir. Grafın en büyük köşe derecesine grafın maksimum derecesi denir ve ∆ ile gösterilir. Omega invaryantı ve devir (yüz) sayısı (Delen, 2019) 𝛺(𝐺) = 𝑎3 + 2𝑎4 + 3𝑎5 + ⋯+ (∆ − 2)𝑎∆ − 𝑎1 = 2(𝑚 − 𝑛) (1.2) 𝑟 = Ω(𝐺) 2 + 𝑐 (1.3) şeklinde verilir. Burada c sayısı grafın bileşen sayısıdır. Şekil 1.4 Şekil 1.3’deki grafın derece temsili 1.1.3. Basit bağlantılı ve bağlantısız graf Bir grafta bir köşeden diğer köşeye mutlaka bir patika çizilebilirse bağlantılıdır aksi halde iki veya daha fazla ayrık graftan oluşur. 4 Şekil 1.5 Şekil 1.3’deki grafın bağlantılı ve bağlantısız temsili 1.1.4. Yönlendirilmiş ve yönlendirilmemiş graflar V’deki farklı köşelerin sıralı ikililerinden elde edilen kenarlara yönlü kenar denilir. Kenarları yönlü olan grafa yönlü graf adı verilir. Bir yönlü grafta farklı u ve v her bir köşe ikilisi (u.v) ve (v,u) kenarlarından sadece birisi yönlü bir kenar ise bu grafa aynı zamanda yönlendirilmiş graf denir. Şekil 1.6 Şekil 1.3’deki grafın yönlendirilmiş temsili 1.1.5. Patika, ağaç ve devir grafları Patika grafı bir köşeden diğer köşeye uzanan bir yoldur. Bu yolda tekrar aynı köşeden geçilmez. Devir grafı verilen başlangıç ve bitiş köşelerinin aynı olduğu patika grafıdır. Devir grafı içermeyen graflara ağaç denir. 5 Şekil 1.7 Şekil 1.3’deki grafın üzerindeki patika, devir ve bir ağaç grafı 1.1.6. Uzaklık Bir G grafında u ve v köşesi arasında farklı patikalar bulunabilir. Bu patikalardan en kısa olanın uzunluğuna u,v köşeleri arasındaki uzaklık denir ve 𝑑(𝑢, 𝑣) ile gösterilir. 1.1.7. Çap, yarıçap ve merkez Bir G grafının merkezi, diğer noktalara olan en kısa toplam yol uzunluğunun en küçük olduğu noktalardır. Bir grafın yarıçapı, grafın genel yapısı ve noktalar arasındaki bağlantıların uzunluklarına bağlı olarak değişir. Bir grafın köşeleri arasındaki uzaklıkların en büyüğüne G’nin çapı denir ve çap(G) veya d(G) ile gösterilir. Graf teorisinde "yarıçap", bir grafın merkezinden en uzak noktaya olan en kısa yolun uzunluğunu ifade eder. Yani, bir grafın yarıçapı, graf içindeki herhangi bir nokta ile merkezi nokta arasındaki en kısa yolun uzunluğudur. Özetle, bir grafın yarıçapı, grafın merkezi köşesinden en uzak köşeye olan en kısa yolun uzunluğunu ifade eder ve grafın topolojik özelliklerini anlamak için kullanılır. Çap ve yarıçap, bir grafın "genişliği" veya "uzaklığı" hakkında fikir veren ölçütlerdir. 6 Şekil 1.8 Şekil 1.3’teki grafın merkez, çap ve yarıçapı 1.1.8. Komşuluk matrisi A(G), komşuluk matrisi graf içindeki köşeler arasındaki bağlantıların ilişkilerini gösterir. Bir 𝐴𝑛𝑥𝑛 kare matrisinin (𝑖, 𝑗) bileşeni, i. köşe ile j. köşe arasında bir kenar varsa, matrisin (𝑖, 𝑗) ve (𝑗, 𝑖) bileşenleri 1 olur; aksi halde, her ikisi de 0 olur: 𝑎𝑖𝑗 = { 1 ; 𝑖. 𝑘öş𝑒, 𝑗. 𝑘öş𝑒 𝑖𝑙𝑒 𝑏𝑎ğ𝑙𝚤𝑦𝑠𝑎 0 ; 𝑖. 𝑘öş𝑒, 𝑗. 𝑘öş𝑒 𝑖𝑙𝑒 𝑏𝑎ğ𝑙𝚤 𝑑𝑒ğ𝑖𝑙𝑠𝑒 A 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 Çizelge 1.1. Şekil 1.3’deki grafın komşuluk matrisi 1.1.9. Derece matrisi Derece matrisi köşegeni grafın dereceleri olan bir matristir ve deg(G) ile gösterilir. Bir komşuluk matrisinin her bir sütunun elemanları toplamı ile G grafının derece dizisinin di elemanları elde edilir ve d derece dizisi oluşturulur. Yani, 7 𝑑 = {𝑑1𝑑2, 𝑑3, … , 𝑑𝑖} , 𝑎𝑖,𝑗 ∈ 𝐴(𝐺) 𝑖𝑠𝑒 𝑑𝑖 = ∑𝑎𝑖,𝑗 𝑛 𝑗=1 (1.4) olur. Örneğin d=(2,3,4,2,2,1) derece dizisi olan grafın derece matrisi aşağıdaki gibidir: Deg(G) 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 1 Çizelge 1.2 Şekil 1.3’deki grafın derece dizisinin derece matrisi 1.1.10. Bitişiklik matrisi B(G) bitişiklik matrisi, G grafının kenarları ve köşeleri arasındaki bağlantılarını gösteren matristir. Bir 𝐵m x n matrisinin (𝑖, 𝑗) bileşeni, i. kenar ile j. köşe arasında bir bağlantı varsa, matrisin (𝑖, 𝑗) ve (𝑗, 𝑖) bileşenleri 1 olur; aksi halde, her ikisi de 0 olur: 𝑏𝑖𝑗 = { 1 ; 𝑖. 𝑘𝑒𝑛𝑎𝑟 𝑗. 𝑘öş𝑒𝑦𝑒 𝑏𝑎ğ𝑙𝚤𝑦𝑠𝑎 0 ; 𝑖. 𝑘𝑒𝑛𝑎𝑟 𝑗. 𝑘öş𝑒𝑦𝑒 𝑏𝑎ğ𝑙𝚤 𝑑𝑒ğ𝑖𝑙𝑠𝑒 B 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 Çizelge 1.3 Şekil 1.3’deki grafın bitişiklik matrisi 8 1.1.11. Laplace matrisi L(G), Laplace matrisi derece matrisinin komşuluk matrisiyle arasındaki farka eşittir. Aynı zamanda bitişiklik matrisinin transpozu ile kendisinin çarpımı olarak da ifade edilir: (Chung, 1992) 𝐿 = 𝐷 − 𝐴 (1.5) 𝐿 = 𝐵𝑇𝐵 (1.6) Çizelge 1.4 Şekil 1.3’deki grafın Laplace matrisi 1.1.12. Mesafe matrisi D(G) mesafe matrisi, G grafının her bir köşesinin diğer köşelere uzaklıklarını gösteren matristir. 𝐷𝑖𝑗 = 𝑑(𝑣𝑖, 𝑣𝑗) ile gösterilir. D 0 1 1 2 2 2 1 0 1 2 2 1 1 1 0 1 1 2 2 2 1 0 1 3 2 2 1 1 0 3 2 1 2 3 3 0 Çizelge 1.5 Şekil 1.3’deki grafın mesafe matrisi L 2 -1 -1 0 0 0 -1 3 -1 0 0 -1 -1 -1 4 -1 -1 0 0 0 -1 2 -1 0 0 0 -1 -1 2 0 0 -1 0 0 0 1 9 1.1.13. Statü Bir v köşesinin statüsü σ(v), v köşesinin tüm köşelere uzaklıkları toplamıdır. Statü ayrıca, her bileşeni mesafe matrisinde karşılık gelen kolonun bileşenleri toplamı olarak da tanımlanır (F. Harary, 1959): 𝜎(𝑣) = ∑ 𝑑(𝑣, 𝑢) 𝑢∈𝑉(𝐺) (1.7) S1 statü indeksi, kenarlar üzerinden her bir kenarı oluşturan köşelerin statülerinin toplamının toplamıdır: 𝑆1 = ∑ 𝜎(𝑢) + 𝜎(𝑣) 𝑢𝑣∈𝐸(𝐺) (1.8) S2 statü indeksi, kenarlar üzerinden her bir kenarı oluşturan köşelerin statülerinin çarpımının toplamıdır: 𝑆2 = ∑ 𝜎(𝑢). 𝜎(𝑣) 𝑢𝑣∈𝐸(𝐺) (1.9) Bu tezin amacı grafların birinci ve ikinci statü indekslerinin hesaplanmasıdır. Ayrıca çekirdek, gölge ve görüntü graflarının mesafe matrisleri verilecektir. Bu matrisler verildiğinde grafın nasıl elde edileceği üzerinde durulacaktır. 10 2. GRAF HESAPLAMALARI İÇİN YARDIMCI ÖZELLİKLER 2.1. Bazı Temel Kavramlar Bu kısımda ileride kullanılacak olan bazı temel kavramlar verilecektir. 2.1.1. Hadamard çarpımı Hadamard çarpımı ∘ ile gösterilir. 𝐴 = [𝑎𝑖𝑗] 𝑣𝑒 𝐵 = [𝑏𝑖𝑗], m×n boyutlu matris olmak üzere A ∘ B = [𝑎𝑖𝑗𝑏𝑖𝑗]𝑚×𝑛 olarak tanımlanan ikili işlemdir. Birimi J olarak gösterilir tüm bileşenleri 1 olan m×n boyutlu matristir ve bir matrisin her bir bileşeni 0’dan farklı ise Hadamard tersi vardır ve bu matris, her bir bileşeni kendisinin çarpma işlemine göre tersini barındıran matristir. Ayrıca birleşme ve değişme özelliğine sahiptir. Sıfır matrisi tüm elemanları 0 olan matristir (Horn, 2011). Cebirsel özellikleri aşağıdaki gibidir: 𝐴 ∘ 𝐵 = 𝐵 ∘ 𝐴 𝐴 ∘ (𝐵 ∘ 𝐶) = (𝐴 ∘ 𝐵) ∘ 𝐶 𝐴 ∘ (𝐵 + 𝐶) = (𝐴 + 𝐵) ∘ 𝐶 𝐴 ∘ 𝐽 = 𝐴 𝐴 ∘ 0 = 0 𝐴 ∘ Â = 𝐽 2.1.2. Statü dizisi 𝜎 statü dizisi, elemanları tüm köşelerin statüleri olan dizidir. Köşelerin statüleri 𝜎 = {𝜎(𝑣1), 𝜎(𝑣2), 𝜎(𝑣3), … , 𝜎(𝑣𝑛)} şeklinde ifade edilir. D 0 1 1 2 2 2 1 0 1 2 2 1 1 1 0 1 1 2 2 2 1 0 1 3 2 2 1 1 0 3 2 1 2 3 3 0 Çizelge 2.1 Şekil 1.3’deki grafın mesafe matrisi ve statü dizisi σ= {8 7 6 9 9 11} 11 Mesafe matrisinin her bir kolonunun toplamı her bir köşenin statüsünü verecektir. 2.1.3. Signum matrisi δ(A) veya sgn A ile gösterilen signum matrisi, bir A matrisinin a𝑖𝑗 elemanının değerine basit sgn fonksiyonu uygulayarak elde edilen matristir. Bu sayede ağırlıklı ve yönlü olan bir graf matrisi, ağırlıksız ve yönsüz graf matrisine dönüşecektir. Sonuç olarak 𝛿(𝐴) = [𝑠𝑔𝑛( a𝑖𝑗)] olacaktır (Thomas, 2020): δ(A) = { 1 ; a𝑖𝑗 > 0 0 ; a𝑖𝑗 = 0 −1 ; a𝑖𝑗 < 0 (2.1) Bu tezde yönlü olmayan, ağırlıksız, basit, bağlantılı graflarla çalışılacaktır. Dolayısıyla böyle grafların komşuluk, bitişiklik ve mesafe matrislerinin bileşenleri 0 ya da pozitif sayılar olacaktır. Örneğin: Şekil 2.1 Yönlendirilmiş ve ağırlıklı graf ve onun signum grafı 0 3 4 0 0 0 0 1 1 0 0 0 2 0 1 0 0 3 1 0 1 0 0 1 A = 1 1 0 1 1 0 δ(A) = 1 1 0 1 1 0 0 0 1 0 2 0 0 0 1 0 1 0 0 0 1 3 0 0 0 0 1 1 0 0 0 2 0 0 0 0 0 1 0 0 0 0 Çizelge 2.2 Şekil 2.1’deki grafın ağırlık matrisinin signum matrisi 12 2.1.4. Bitişiklik matrisi yardımıyla komşuluk matrisi hesabı Bir G grafının bitişiklik matrisi biliniyorsa bu matristen faydalanarak Laplace matrisi bulunur ve bu sayede komşuluk matrisi aşağıdaki şekilde hesaplanır. Burada yapılan işlem ilk olarak bitişiklik matrisi ve transpozunu çarparak Laplace matrisini bulmak, sonra da Laplace matrisinden derece matrisini çıkarmaktır: 𝐵𝐵𝑇 = 𝐿 (2.2) 𝐿 − 𝑑𝑒𝑔(𝐺) = 𝐴 (2.3) B BT L 1 0 0 0 0 1 0 1 1 0 0 0 0 2 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 3 1 0 0 1 0 1 1 0 1 1 0 x 0 0 1 1 0 0 = 1 1 4 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 2 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 2 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 L deg(G) A 2 1 1 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 1 3 1 0 0 1 0 3 0 0 0 0 1 0 1 0 0 1 1 1 4 1 1 0 - 0 0 4 0 0 0 = 1 1 0 1 1 0 0 0 1 2 1 0 0 0 0 2 0 0 0 0 1 0 1 0 0 0 1 1 2 0 0 0 0 0 2 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 Çizelge 2.3 Şekil 1.3’deki grafın bitişiklik matrisi ile komşuluk matrisi hesabı 13 2.1.5. Komşuluk matrisi yardımıyla mesafe matrisi hesabı Komşuluk matrisinden mesafe matrisine ulaşmak için ilk bilinmesi gereken grafın çapı olacaktır. Bir grafın çapı bulunurken herhangi iki köşesi arasındaki uzaklık bulunacağından bu sayede mesafe matrisi de elde edilir. Bir matrisin kuvvetlerini An ile gösterirsek bu matrisin signum matrisi δ(An) olacaktır. Burada en büyük kuvveti d=n olarak kabul edilirse bu sayede mesafe matrisi şu şekilde hesaplanır (Thomas, 2020): 𝐷𝑛 = δ(A𝑛) − δ[δ(A𝑛) ∘ δ(A𝑛−1) + δ(A𝑛) ∘ δ(A𝑛−2) + ⋯+ δ(A𝑛) ∘ δ(A1) + δ(A𝑛) ∘ δ(A0)] (2.4) Dn matrisi, A matrisinin en büyük kuvvetinin signum matrisinin kendinden önceki kuvvetlerinin signum matrisleriyle Hadamard çarpımlarının toplamını alarak ve son olarak da yine en büyük kuvvetli A signum matrisinden çıkarılmasıyla elde edilir (Thomas, 2020): 𝐷 = 𝑑.𝐷𝑑 + (𝑑 − 1). 𝐷𝑑−1 + (𝑑 − 2)𝐷𝑑−2+⋯+ 2.𝐷2 + 1.𝐷1 𝐷 = ∑ 𝑛.𝐷𝑛 𝑑 𝑛=1 (2.5) Dn matrisleri kendi indisi kadar çarpılır ve daha sonra tümü toplanırsa D mesafe matrisi elde edilir. Şekil 2.2 Bir grafın çapı 14 Yukarıdaki şekilde verilen G grafı ele alınırsa bu grafın çapı 𝑑 = 3 𝑜𝑙𝑎𝑐𝑎𝑘𝑡𝚤𝑟. An δ(An) Dn 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 n=1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 3 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 n=2 1 1 4 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 2 1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 2 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 D 2 4 5 2 2 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 2 2 2 4 2 6 2 2 3 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 2 2 1 d=n=3 5 6 4 5 5 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 2 2 2 5 2 3 1 1 1 1 1 1 1 0 0 0 0 0 1 2 2 1 0 1 3 2 2 5 3 2 1 1 1 1 1 1 1 0 0 0 0 0 1 2 2 1 1 0 3 1 3 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 2 1 2 3 3 0 𝐷 = 1.𝐷1 + 2.𝐷2 + 3.𝐷3 Çizelge 2.4 Şekil 1.3’deki grafın mesafe matrisi hesabı 2.1.6. Mesafe matrisi yardımıyla komşuluk matrisinin hesabı “Yukarıdaki işlemler ile elde edilen bir mesafe matrisinden komşuluk matrisine nasıl dönülebilir?’’ sorusu akıllara gelebilir. Tek yapılması gereken D mesafe matrisinin bileşenleri 1 olan değerlerinin komşuluk matrisinin elemanları olduğunun görülmesidir. O halde D matrisinin 1 dışındaki tüm elemanları sıfır yapılmalıdır. 15 D A 0 1 1 2 2 2 0 1 1 0 0 0 1 0 1 2 2 1 1 0 1 0 0 1 1 1 0 1 1 2 1 1 0 1 1 0 2 2 1 0 1 3 0 0 1 0 1 0 2 2 1 1 0 3 0 0 1 1 0 0 2 1 2 3 3 0 0 1 0 0 0 0 Çizelge 2.5 Şekil 1.3’teki grafın mesafe ve komşuluk matrisi 2.1.7. Birinci ve ikinci statü indekslerinin hesaplanması Bu indeksleri hesaplamak için ilk olarak simetriden faydalanarak mesafe matrisinin satırları toplamıyla statü dizisi σ elde edilir. İkinci aşama olarak σ ile B bitişiklik matrisinin her 𝐵𝑗, j=1, 2, …, n kolonuyla Hadamard çarpımı yapılıp yeni bir S matrisi elde edilir: 𝜎 ∘ 𝐵𝑗 = 𝑠𝑗 (2.6) Bu 𝑆 = (𝑠1, 𝑠2, 𝑠3, … , 𝑠𝑛) matrisi yardımıyla S1 ve S2 aşağıdaki gibi bulunur. D σ 0 1 1 2 2 2 8 1 0 1 2 2 1 7 1 1 0 1 1 2 6 2 2 1 0 1 3 9 2 2 1 1 0 3 9 2 1 2 3 3 0 11 B σ S 1 1 0 0 0 0 0 8 8 8 0 0 0 0 0 1 0 1 0 0 0 1 7 7 0 7 0 0 0 7 0 1 1 1 1 0 0 6 0 6 6 6 6 0 0 0 0 0 1 0 1 0 9 0 0 0 9 0 9 0 0 0 0 0 1 1 0 9 0 0 0 0 9 9 0 0 0 0 0 0 0 1 11 0 0 0 0 0 0 11 Çizelge 2.6 Şekil 1.3’deki grafın S matrisi ile statü dizisi hesabı 16 S1 birinci statü indeksi, tüm komşu olan köşelerin statülerinin toplamını oluşturan bir s1 dizisi tanımlanırsa, bu dizinin elemanlarının toplamıdır. Bunun için S matrisinin sütunlarının toplamıyla s1 dizisi elde edilir. Bu s1 dizisinin elemanları toplanarak S1 birinci statü indeksi elde edilir. S 8 8 0 0 0 0 0 7 0 7 0 0 0 7 0 6 6 6 6 0 0 0 0 0 9 0 9 0 0 0 0 0 9 9 0 0 0 0 0 0 0 11 s1= {15 14 13 15 15 18 18} S1=108 Çizelge 2.7 Şekil 1.3’deki grafın S1 statü indeksi hesabı S2 ikinci statü indeksi, tüm komşu olan köşelerin statülerinin çarpımını oluşturan bir s2 dizisi tanımlanırsa, bu dizinin elemanlarının toplamıdır. Bunun için S matrisi yardımıyla 𝑆′ = 𝑆 + (𝐽 − 𝐵) matrisi elde edilir. Bu sayede matristeki 0 değerleri 1 olarak alınır. Sonra sütun çarpımıyla s2 dizisi elde edilir. Ardından s2 dizisinin elemanları toplanarak S2 elde edilir. Şekil 1.3’deki graf ele alınırsa, B J 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 S 𝑆′= S+ (J-B) 8 8 0 0 0 0 0 8 8 1 1 1 1 1 7 0 7 0 0 0 7 7 1 7 1 1 1 7 0 6 6 6 6 0 0 1 6 6 6 6 1 1 0 0 0 9 0 9 0 1 1 1 9 1 9 1 0 0 0 0 9 9 0 1 1 1 1 9 9 1 0 0 0 0 0 0 11 1 1 1 1 1 1 11 s2 ={56 48 42 54 54 81 77} S2=412 Çizelge 2.8 Şekil 1.3’deki grafın S2 statü indeksi hesabı 17 2.1.8. Wiener indeksi Bir G grafının Wiener indeksi W(G), graf üzerindeki herhangi iki u, v köşesinin arasındaki uzaklıkların toplamıdır. Aynı zamanda köşelerin statülerinin toplamının yarısı olarak da ifade edilebilir (H. Wiener): W(G) = ∑ 𝑑(𝑢, 𝑣) = 1 2 𝑢,𝑣∈𝑉(𝐺) ∑ 𝜎 𝑢∈𝑉(𝐺) (𝑢) (2.7) 2.1.9. Birinci ve ikinci Zagreb indeksleri Bir G grafının birinci Zagreb indeksi M1, graftaki köşelerin derecelerinin karelerinin toplamı veya her bir kenarı oluşturan köşelerin derecelerinin toplamının toplamıdır. (I. Gutman, N. Trinajstic, 1972) 𝑀1(𝐺) = ∑ 𝑑(𝑢)2 = ∑ 𝑑(𝑢) + 𝑑(𝑣) 𝑢𝑣∈𝐸(𝐺)𝑢∈𝑉(𝐺) (2.8) Ayrıca bitişiklik matrisinin sütunları 𝐵𝑗 ile derece dizisi Hadamard çarpımı yapılırsa oluşan sütunlar ile yeni bir M matrisi oluşturulursa M matrisinin sütun toplamı yapılarak m1 dizisi ve bu dizinin elemanlarının toplamıyla da M1 birinci Zagreb indeksi bulunabilir. Örneğin: Çizelge 2.9 Şekil 1.3’deki grafın birinci Zagreb indeksi B d D 1 1 0 0 0 0 0 2 2 2 0 0 0 0 0 1 0 1 0 0 0 1 3 3 0 3 0 0 0 3 0 1 1 1 1 0 0 ∘ 4 → 0 4 4 4 4 0 0 0 0 0 1 0 1 0 2 0 0 0 2 0 2 0 0 0 0 0 1 1 0 2 0 0 0 0 2 2 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 m1 ={5 6 7 6 6 4 4} M1=38 18 Bir grafın ikinci Zagreb indeksi M2, graftaki kenarları oluşturan köşelerin derecelerinin çarpımlarının toplamıdır: (I. Gutman, N. Trinajsti´c, 1972) 𝑀2(𝐺) = ∑ 𝑑(𝑢)𝑑(𝑣) 𝑢𝑣∈𝐸(𝐺) (2.9) Ayrıca bitişiklik matrisinin sütunları 𝐵𝑗 ile derece dizisi Hadamard çarpımı yapılırsa ve oluşan sütunlar ile yeni bir M matrisi oluşturulursa 𝑀′= M-(J-B) matrisinin sütunları toplamıyla m2 dizisi ve bu dizinin elemanları toplamıyla da M2 ikinci Zagreb indeksi bulunabilir. B d M 𝑀′ 1 1 0 0 0 0 0 2 2 2 0 0 0 0 0 2 2 1 1 1 1 1 1 0 1 0 0 0 1 3 3 0 3 0 0 0 3 3 1 3 1 1 1 3 0 1 1 1 1 0 0 ∘ 4 → 0 4 4 4 4 0 0 → 1 4 4 4 4 1 1 0 0 0 1 0 1 0 2 0 0 0 2 0 2 0 1 1 1 2 1 2 1 0 0 0 0 1 1 0 2 0 0 0 0 2 2 0 1 1 1 1 2 2 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 m2 ={9 10 11 10 10 8 8} M2=49 Çizelge 2.10 Şekil 1.3’deki grafın ikinci Zagreb indeks 19 3. ÖZEL GRAFLAR VE STATÜ İNDEKSLERİ 3.1. Sıfır grafı 𝑁𝑛 sıfır grafı, kenar kümesi boş küme olan graftır. (∞, iki köşe arasında bağlantı olmadığını belirtir.) Şekil 3.1 Sıfır grafı Çizelge 3.1 Şekil 3.1’deki grafın komşuluk, bitişiklik ve mesafe matrisleri 3.2. Patika grafı 𝑃𝑛 patika grafı, 𝑖 = 1, 2, … ,𝑛 için birbirinden farklı 𝑣𝑖 köşelerinin 𝑣𝑖𝑣𝑖+1 şeklinde birleşmesiyle oluşan graftır. Bu graf 𝑛 köşeye ve 𝑛 − 1 kenara sahiptir. 𝑣1 ve 𝑣𝑛 köşelerine patika grafının uç köşeleri, kenar sayısına da uzunluğu denir. Bu tez çalışmasında patika grafı için köşe sayısı en az iki alınacaktır. A(N) B(N) D(N) 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 0 0 0 0 0 ∞, ∞, ∞, ∞, 0 ∞ 0 0 0 0 0 0 ∞, ∞, ∞, ∞, ∞, 0 20 Şekil 3.2 Patika grafı A B D 0 1 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 1 0 1 0 0 0 1 1 0 0 0 1 0 1 2 3 4 0 1 0 1 0 0 0 1 1 0 0 2 1 0 1 2 3 0 0 1 0 1 0 0 0 1 1 0 3 2 1 0 1 2 0 0 0 1 0 1 0 0 0 1 1 4 3 2 1 0 1 0 0 0 0 1 0 0 0 0 0 1 5 4 3 2 1 0 σ= {15 11 9 9 11 15} Çizelge 3.2 Şekil 3.12’deki patika grafının komşuluk, bitişiklik ve mesafe matrisleri Bir Pn patika grafının birinci ve ikinci statü indeksleri (Yalnaik1, 2016): 𝜎𝑆(𝑃𝑛)(𝑣𝑖) = 𝑖(𝑖 − 1) 2 + (𝑛 − 1 − 𝑖)(𝑛 − 𝑖) 2 𝑆1(𝑃𝑛) = ∑[𝜎(𝑣𝑖) + 𝜎(𝑣𝑖+1)] 𝑖=1 = 1 3 [𝑛(𝑛 − 1)(2𝑛 − 1)] 𝑆2(𝑃𝑛) = ∑ 𝜎 𝑛−1 𝑖=1 (𝑣𝑖)𝜎(𝑣𝑖+1) = (𝑛 − 1)(𝑛4 − 𝑛2) 4 − 𝑛(𝑛 − 1)(𝑛3 − 𝑛) 2 + 𝑛(𝑛 − 1)(2𝑛 − 1)(2𝑛2 − 1) 6 − 𝑛3(𝑛 − 1)2 2 + 1 30 [6(𝑛 − 1)5 + 15(𝑛 − 1)4 + 10(𝑛 − 1)3 − (𝑛 − 1)] ( 2.10) 21 3.3. Devir grafı 𝐶n devir grafı, patika grafındaki uç köşelerin bir kenarla birleştirilmesi sonucu oluşan grafa denilir. Bu grafın kenar ve köşe sayısı birbirine eşittir. Her bir köşenin derecesi 2’dir. Köşe sayısının 1 ve 2 olduğu durumlarda devir grafı, patika grafı ile aynıdır. Bu tez çalışmasında devir grafı için köşe sayısı en az üç alınacaktır. Bir Cn devir grafının birinci ve ikinci statü indeksleri, 𝜎(𝐶𝑛) = 𝑛2 + (−1) 𝑛 − 1 2 4 n tek ise; 𝑆1(𝐶𝑛) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝑆(𝐶𝑛)) = 𝑛3 − 𝑛 2 𝑆2(𝐶𝑛) = ∑ 𝜎𝑢. 𝜎𝑣 = 𝑢,𝑣𝜖𝐸(𝐶𝑛) ( 𝑛2 − 1 4 ) 2 . 𝑛 n çift ise; 𝑆1(𝐶𝑛) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝑆(𝐶𝑛)) = 𝑛3 2 𝑆2(𝐶𝑛) = ∑ 𝜎𝑢. 𝜎𝑣 = 𝑢,𝑣𝜖𝐸(𝐶𝑛) 𝑛5 16 (2.11) ile hesaplanır. Şekil 3.3 Devir grafı 22 A B D 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 2 3 4 3 2 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 2 3 4 3 2 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 2 1 0 1 2 3 4 3 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 3 2 1 0 1 2 3 4 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 4 3 2 1 0 1 2 3 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 3 4 3 2 1 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 2 3 4 3 2 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 2 3 4 3 2 1 0 Çizelge 3.3 Şekil 3.3’deki devir grafının komşuluk, bitişiklik ve mesafe matrisleri 3.4. Yıldız grafı 𝑆𝑛 yıldız grafı, merkezdeki bir köşenin 𝑛 − 1 tane köşe ile birleştirilmesiyle oluşan grafa denilir. Bu grafta kenar sayısı, köşe sayısının bir eksiğidir. Bu tez çalışmasında yıldız grafı için köşe sayısı en az iki alınacaktır. Şekil 3.4 Yıldız grafı Yıldız gafının komşuluk, bitişiklik ve mesafe matrisleri aşağıda verilmiştir: σ ={ 16 16 16 16 16 16 16 16} 23 A B D 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 2 2 0 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 2 2 2 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 2 2 2 2 0 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 2 2 2 2 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 2 2 2 2 0 σ= {7 13 13 13 13 13 13 13} Çizelge 3.4 Şekil 3.4’daki devir grafının komşuluk, bitişiklik ve mesafe matrisleri Bir Sn yıldız grafının birinci ve ikinci statü indeksleri, 𝜎𝑆(𝑆𝑛)(𝑣0) = 𝑛 − 1 𝜎𝑆(𝑆𝑛)(𝑣1)= 2n-1 𝑆1(𝑆𝑛) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝑆𝑛) = 3𝑛2 − 5𝑛 + 2 𝑆2(𝑆𝑛) = ∑ 𝜎𝑢. 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝑆𝑛) = 2𝑛3 − 5𝑛2 + 4𝑛 (2.12) ile hesaplanır. 3.5. Tam grafı Kn tam graf, her bir köşesinin diğer tüm köşelerle komşu olduğu graftır. Her köşe n-1 tane kenara komşudur. 24 Şekil 3.5 Tam graf A B D 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 Çizelge 3.5 Şekil 3.5’deki tam grafın komşuluk, bitişiklik ve mesafe matrisleri Bir Kn tam grafının birinci ve ikinci Statü indeksleri: 𝜎𝐾𝑛 (𝑣) = 𝑛 − 1 𝑆1(𝐾𝑛) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝐾𝑛) = (𝑛 + 𝑛(𝑛 − 3) 2 ) (2𝑛 − 2) 𝑆2(𝐾𝑛) = ∑ 𝜎𝑢. 𝜎𝑣 𝑢,𝑣𝜖𝐸(𝐾𝑛) = 2𝑛3 (2.13) σ = {6 6 6 6 6 6 6} 25 3.6. Larva grafı 𝑇r,s larva grafı, devir grafı ile patika grafının ortak bir köşede birleştirilmesi ile oluşan grafa denir. Devir grafının uzunluğu r, patika grafının uzunluğu da s olmak üzere larva grafı r + s tane köşe ve kenara sahiptir. Şekil 3.6 Larva grafı A B D 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 2 2 1 1 2 3 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 2 2 2 3 4 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 2 1 0 1 2 3 4 5 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 2 2 1 0 1 3 4 5 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 2 2 1 0 2 3 4 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 2 3 3 2 0 1 2 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 2 3 4 4 3 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 3 4 5 5 4 2 1 0 σ= { 12 15 18 18 15 14 18 24} Çizelge 3.6 Şekil 3.6’deki larva grafının komşuluk, bitişiklik ve mesafe matrisleri Bir 𝑇r,s larva grafının birinci ve ikinci statü indeksleri 𝜎(𝑣0) = 𝑟2 4 + 𝑠(𝑠 + 1) 2 𝜎(𝑣𝑟𝑖 ) = 𝑟2 4 + 𝑖. 𝑠 + (𝑠)(𝑠+1) 2 ; 𝑖 = 1,2,3… 𝑟 2⁄ 26 𝜎 (𝑣𝑠𝑗 ) = 𝑟2 4 + 𝑗 ⋅ 𝑟 + (𝑠 − 𝑗)(𝑠 − 𝑗 + 1) 2 + 𝑗(𝑗 − 1) 2 ; 𝑗 = 1,2,3… 𝑠 (2.14) ile hesaplanır. 3.7. Merdiven grafı 𝐿𝑛 merdiven grafı, bir devir grafının aynı devir grafı ile aynı köşelerin birer kenar oluşturmasıyla ortaya çıkan graftır. Başka bir deyişle, iki n-genin karşılıklı birer köşelerinden birleştirilmesiyle elde edilir. Bu grafın köşe sayısı 2𝑛, kenar sayısı ise 3𝑛 ile hesaplanır. Şekil 3.7 Merdiven grafı A B D 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 2 2 1 1 2 3 3 2 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 2 2 2 1 2 3 3 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 2 1 0 1 2 3 2 1 2 3 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 2 2 1 0 1 3 3 2 1 2 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 2 2 1 0 2 3 3 2 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 2 3 3 2 0 1 2 2 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 2 1 2 3 3 1 0 1 2 2 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 3 2 1 2 3 2 1 0 1 2 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 3 3 2 1 2 2 2 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 2 3 3 2 1 1 2 2 1 0 Çizelge 3.7 Şekil 3.7’daki merdiven grafının komşuluk, bitişiklik ve mesafe matrisleri σ= { 17 17 17 17 17 17 17 17 17 17 } 27 3.8. Tekerlek grafı 𝑊𝑛 tekerlek grafı, 𝑛 ≥ 3 olmak üzere devir grafının bütün köşeleriyle bağlantısı olacak şekilde yeni bir köşe eklenmesi ile tekerlek grafı oluşur. 𝑛 köşe ve 2𝑛 − 2 tane kenara sahiptir. Komşuluk matrisi için merkez nokta çıkarıldığında devir grafı elde edildiği görülür. Şekil 3.8 Tekerlek grafı A B D 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 2 2 2 2 2 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 2 2 2 2 2 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 1 0 1 2 2 2 2 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 2 2 1 0 1 2 2 2 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 2 2 2 1 0 1 2 2 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 2 2 2 2 1 0 1 2 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 2 2 2 2 2 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 2 2 2 2 2 1 0 Çizelge 3.8 Şekil 3.8’deki tekerlek grafının komşuluk, bitişiklik ve mesafe matrisleri Bir 𝑊𝑛 tekerlek grafının birinci ve ikinci statü indeksleri 𝜎𝑊𝑛 (𝑣1) = 𝑛 − 1 𝜎𝑊𝑛 (𝑣2) = 2𝑛 − 5 σ { 8 13 13 13 13 13 13 13 13 } 28 𝑆1(𝑊𝑛) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢𝑣𝜖𝐸(𝑊𝑛) = 9𝑛2 − 25𝑛 + 16 𝑆2(𝑊𝑛) = ∑ 𝜎𝑢. 𝜎𝑣 = 26𝑛 − 33𝑛2 + 57𝑛 − 30 𝑢𝑣𝜖𝐸(𝑊𝑛) (2.15) ile hesaplanır. 3.9. Çark grafı Gn çark grafı, tekerlek grafının devir üzerindeki kenarların üzerine birer köşe eklenmesiyle elde edilir. Çark grafının komşuluk matrisi incelenirse ilk satır sütunda ardışık 0,1 elemanları görülür. Geri kalan girdiler devir grafının komşuluk matrisidir. Şekil 3.9 Çark grafı A B D 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 2 1 2 1 2 1 2 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 2 0 1 2 3 4 3 2 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 2 3 2 3 2 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 2 2 1 0 1 2 3 4 3 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 3 2 1 0 1 2 3 2 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 2 4 3 2 1 0 1 2 3 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 3 2 3 2 1 0 1 2 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 2 2 3 4 3 2 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 2 3 2 3 2 1 0 Çizelge 3.9 Şekil 3.9’daki çark grafının komşuluk, bitişiklik ve mesafe matrisleri σ= { 12 18 15 18 15 18 15 18 15 } 29 3.10. Petersen grafı P(G) Petersen grafı özel bir graftır. Petersen grafının komşuluk matrisi, bir devir grafının komşuluk matrisi ile bu devir grafının birim matrisle toplamının bir J matrisinden çıkarılması yardımıyla hesaplanabilir. J-I yerine K tam grafının komşuluk matrisi alınabilir: 𝐴(𝑃(𝐺)) = [ A( 𝐶𝑛) 𝐼𝑛 𝐼𝑛 𝐽𝑛 − 𝐼𝑛 − 𝐴(𝐶𝑛) ] (2.16) Şekil 3.10 Petersen graf A B D 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 2 2 1 1 2 2 2 2 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 2 2 2 1 2 2 2 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 2 1 0 1 2 2 2 1 2 2 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 2 2 1 0 1 2 2 2 1 2 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 2 2 1 0 2 2 2 2 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 2 2 2 2 0 2 1 1 2 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 2 1 2 2 2 2 0 2 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 2 2 1 2 2 1 2 0 2 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 2 2 2 1 2 1 1 2 0 2 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 2 2 2 1 2 1 1 2 0 Çizelge 3.10 Şekil 3.10’deki Petersen grafının komşuluk, bitişiklik ve mesafe matrisleri σ= { 15 15 15 15 15 15 15 15 15 15 } 30 3.11. Dostluk grafı Dr,s dostluk grafı, r tane Cs devir grafının tek bir ortak noktada birleşmesiyle oluşur. Şekil 3.11 Dostluk grafı A B D 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 2 2 1 2 2 1 1 2 2 1 1 1 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 2 1 2 2 3 3 2 2 3 3 2 2 2 3 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 2 1 2 3 3 2 2 3 3 2 2 2 3 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 2 1 2 0 1 3 4 4 3 3 4 4 3 3 3 4 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 2 2 1 1 0 3 4 4 3 3 4 4 3 3 3 4 4 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 3 3 0 1 2 2 2 3 3 2 2 2 3 3 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 3 4 4 1 0 1 2 3 4 4 3 3 3 4 4 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 3 4 4 2 1 0 1 3 4 4 3 3 3 4 4 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 3 3 2 2 1 0 2 3 3 2 2 2 3 3 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 2 2 3 3 2 3 3 2 0 1 2 2 2 2 3 3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 2 3 3 4 4 3 4 4 3 1 0 1 2 3 3 4 4 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 3 4 4 3 4 4 3 2 1 0 1 3 3 4 4 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 2 2 3 3 2 3 3 2 2 2 1 0 2 2 3 3 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 2 2 3 3 2 3 3 2 2 3 3 2 0 2 2 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 2 2 3 3 2 3 3 2 2 3 3 2 2 0 1 2 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 2 3 3 4 4 3 4 4 3 3 4 4 3 2 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 2 3 3 4 4 3 4 4 3 3 4 4 3 1 2 1 0 Çizelge 3.11 Şekil 3.11’deki dostluk grafının komşuluk, bitişiklik ve mesafe matrisleri Birinci statü indeksi, σ= {24 36 36 48 48 36 48 48 36 36 48 48 36 36 36 48 48} 31 𝜎(𝑣𝑖) = 𝑚. (𝑛2 − 1) 4 + 4(𝑛 − 1)(𝑚 − 1) ⋅ 𝑖 𝑆1(𝐷𝑟,𝑠) = ∑ 𝜎𝑢 + 𝜎𝑣 𝑢𝑣𝜖𝐸(𝐷𝑟,𝑠) = 𝜎𝑣∈𝐶𝑠 (𝑣). (2𝑟𝑠 − 𝑠 − 𝑟 + 1) (2.17) ile hesaplanır. 3.12. Yel değirmeni grafı 𝑊𝑛 𝑚 yel değirmeni grafı, m tane Kn tam grafın bir noktada birleşmesiyle oluşur. n-1 ve mn dereceli iki tip noktaya sahiptir. Kn komşuluk matrisiyle ilişkisi ve köşelerinin statü hesabı aşağıda verildiği gibidir: Şekil 3.12 Yel değirmeni grafı 𝜎𝑊𝑛 𝑚(𝑣1) = 𝑚(𝑛 − 1) 𝜎𝑊𝑛 𝑚(𝑣2) = 2𝑛𝑚 − 2𝑚 − 𝑛 + 1 𝑊𝑛 𝑚 = G1x𝐺2 = [ 0 1 1 ⋯ 1 1 𝐴 0 ⋯ 0 1 0 𝐴 ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ 0 1 0 ⋯ 0 𝐴] (2.18) 32 ile Çizelge 3.12 Şekil 3.12’deki yel değirmeni grafının komşuluk, bitişiklik ve mesafe matrisleri A D 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 2 2 2 2 0 1 1 1 2 2 2 2 2 2 2 2 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 2 2 2 2 1 0 1 1 2 2 2 2 2 2 2 2 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 2 2 2 2 1 1 0 1 2 2 2 2 2 2 2 2 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 2 2 2 2 1 1 1 0 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 2 2 2 2 2 2 2 2 0 1 1 1 2 2 2 2 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 2 2 2 2 2 2 2 2 1 0 1 1 2 2 2 2 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 2 2 2 2 2 2 2 2 1 1 0 1 2 2 2 2 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 2 2 2 2 2 2 2 2 1 1 1 0 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 B 1 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 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 1 1 0 0 0 0 0 0 0 0 0 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 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 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 1 1 0 0 0 0 0 0 0 0 0 0 0 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 1 1 0 0 0 0 0 0 0 0 0 0 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 0 1 1 0 0 0 0 0 0 0 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 1 0 0 1 1 0 0 0 0 0 0 0 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 1 1 1 0 0 0 0 0 0 0 0 0 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 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 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 1 1 0 0 0 0 0 0 0 0 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 1 0 1 0 0 0 0 0 1 0 0 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 1 1 0 0 0 0 0 0 1 0 0 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 0 1 0 0 1 0 0 0 0 0 0 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 1 1 0 0 0 0 0 0 0 0 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 1 0 1 0 0 0 0 0 1 0 0 0 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 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 σ= {16 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28} 33 3.13. İki parçalı tam grafı 𝐾𝑛,𝑚 iki parçalı tam graf, V1, V2 iki köşe kümesi olmak üzere V1’deki her bir köşenin V2’deki her bir köşeyle birleştirilmesiyle elde edilir. İki parçalı tam grafın komşuluk matrisi 𝐴(𝐾𝑛,𝑚(𝐺)) = [ 0𝑛×𝑚 𝐽𝑛×𝑚 𝐽𝑛×𝑚 0𝑛×𝑚 ] (2.19) ile verilebilir. , Şekil 3.13 İki parçalı tam graf A B D 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 2 0 2 2 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 2 2 0 2 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 2 2 2 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 2 2 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 2 0 2 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 2 2 0 Çizelge 3.13 Şekil 3.13’deki iki parçalı tam grafının komşuluk, bitişiklik ve mesafe matrisleri σ= {9 9 9 9 8 8 8} 34 4. TÜRETİLMİŞ GRAFLAR Bu bölümde, türetilmiş grafların bilinen graf matrislerini kullanarak komşuluk matrislerinin nasıl elde edilebileceği verilecektir. 4.1.1. Doğru grafı L(G) doğru grafı, bir grafın kenarlarını köşe kabul ederek G grafında birbirine komşu olan kenarların L(G) de komşu köşeler kabul edildiği graftır (Skiena, 1990). Şekil 4.1 Şekil 1.3’deki grafın doğru grafı Şekil 1.3’deki grafın doğru grafının komşuluk matrisi 𝐿(𝐺) = 𝐵𝑇𝐵 − 2𝐼 (3.1) ile bulunur. BT B 2I L(G) 1 1 0 0 0 0 1 1 0 0 0 0 0 2 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 2 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 x 0 1 1 1 1 0 0 - 0 0 2 0 0 0 = 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 2 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 2 0 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 Çizelge 4.1 Doğrusal grafın komşuluk matrisi hesabı 35 4.1.2. Çekirdek grafı K(G) çekirdek grafı, bir grafın köşelerinin derecelerinin minimum 2 dereceli olacak şekilde indirgenmesi ile elde edilir. Yani, bir dereceli köşelerin graftan çıkarılmasıyla elde edilen graftır. Eğer hala sallanan kenar kalırsa bunlar da silinir. Bu işleme sallanan kenar kalmayana kadar devam edilir. Şekil 4.2 Bir grafın çekirdeği A → A' → K(G)=A'' 0 1 1 0 0 0 0 1 0 0 1 4 0 1 1 0 0 0 2 0 1 1 0 0 2 1 0 1 0 0 1 0 0 0 0 0 3 1 0 1 0 0 1 3 1 0 1 0 0 2 1 1 0 1 1 0 0 0 0 0 0 4 1 1 0 1 1 0 4 1 1 0 1 1 4 0 0 1 0 1 0 0 0 1 0 0 3 0 0 1 0 1 0 2 0 0 1 0 1 2 0 0 1 1 0 0 0 0 0 0 0 2 0 0 1 1 0 0 2 0 0 1 1 0 2 0 1 0 0 0 0 1 0 0 1 0 3 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 2 2 4 2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 3 4 2 2 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 4 3 4 3 2 3 1 1 1 1 1 Çizelge 4.2 Çekirdek grafın komşuluk matrisi hesabı Çekirdek grafının hesabı komşuluk matrisi hesabı yapılırken grafın komşuluk matrisin alt ve yan toplamalarında (derece dizisi) 1 olan satır ve sütun silinir. Bu işlem tekrarlanırsa sonuçta dereceleri 1’den büyük olan çekirdek grafının komşuluk matrisine ulaşılabilir. 36 Ayrıca matrisin sütun sırası derece değerlerini büyükten küçüğe sıralanırsa işlem basitçe son satır ve sütunları silmek olarak belirtilebilir. 4.1.3. Görüntü grafı Im(G) görüntü grafı, bir grafın kendisi ve kopyası alınarak köşelerin kendi kopyalarıyla birleştirilmesiyle elde edilir. Şekil 4.3 Görüntü grafı Şekil 3.3’deki görüntü grafının komşuluk matrisi: A 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 Çizelge 4.3 Görüntü grafın komşuluk matrisi 𝐴(𝐼𝑚(𝐺)) = [ 𝐴(𝐺) 𝐼𝑛×𝑛 𝐼𝑛×𝑛 𝐴(𝐺) ] (3.2) ile hesaplanır. 37 4.2. Gölge grafı Sh(G) gölge grafı, bir grafın kendisi ile kenarları silinmiş olan kopyası alınıp grafın köşelerinin kenarsız kopyasında kendi komşularına denk gelen köşeler ile birleştirilmesiyle elde edilir. Şekil 4.4 Gölge grafı Şekil 3.4’deki gölge grafın komşuluk matrisi, 𝐴(𝑆ℎ(𝐺)) = [ 𝐴(𝐺) 𝐴(𝐺) 𝐴(𝐺) 0𝑛×𝑛 ] (3.3) A 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 Çizelge 4.4 Gölge grafın komşuluk matris 38 4.3. Graflarda işlemler 4.3.1. Köşe birleşimi G1 ve G2 graflarının bir köşesini ortak kullanarak elde edilir. Bu işlem G1⩀G2 ile gösterilsin. Herhangi bir karışıklığa yol açmamak için birleştirilecek noktaların ardışık indisli olmasına dikkat edilmelidir. Bu işlem ile edilen grafın komşuluk matrisini bulurken iki grafın da komşuluk matrisleri hesaplanıp G1 matrisinin son satır ve sütün bileşeni ile G2 matrisinin ilk satır ve sütün bileşeni denk gelecek şekilde birleştirilip kalan bileşenleri 0 ile doldurulur. Şekil 4.5 Bir köşede birleştirilmiş graf A(G1) A(G2) A(𝑮𝟏⩀𝑮𝟐) 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 Çizelge 4.5 Bir köşede birleştirilmiş grafın komşuluk matrisi 39 Şimdi bu iki matris yardımıyla G1⩀G2 grafının mesafe matrisi hesaplanabilir. Burada iki grafın mesafe matrislerine ihtiyaç duyulacaktır. Bunlar elde edildikten sonra komşuluk matrisini elde etmede kullanılan aşamalar aynen uygulanacaktır. G1 matrisin son sütunu ile G2 matrisinin ilk satırını toplam tablosu oluşturacak şekilde kullanılsın. Son olarak bulunan toplam tablosunun sonucu bir T matrisi ile gösterilip T matrisi, transpozu ve 0 matrisleri yerine yerleştirilir. D(G1) D(G2) D(𝑮𝟏⩀𝑮𝟐) 0 1 2 2 2 0 1 1 2 0 1 2 2 2 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 2 1 0 1 1 1 1 0 2 2 1 0 1 1 0 0 0 2 1 1 0 2 2 1 2 0 2 1 1 0 2 0 0 0 2 1 1 2 0 2 1 1 2 0 1 1 2 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 2 0 0 0 0 2 1 2 0 Toplam T D Tablosu 3 3 4 0 1 2 2 2 3 3 4 2 3 3 4 2 2 3 1 0 1 1 1 2 2 3 1 2 2 3 2 2 3 2 1 0 1 1 2 2 3 1 2 2 3 3 3 4 2 1 1 0 2 3 3 4 2 3 3 4 2 1 1 2 0 1 1 2 0 1 1 2 TT 3 2 2 3 1 0 1 1 3 2 2 3 3 2 2 3 1 1 0 2 3 2 2 3 4 3 3 4 2 1 2 0 4 3 3 4 Çizelge 4.6 Bir köşede birleştirilmiş grafın mesafe matrisi 40 4.3.2. Köprü ekleme G1 ve G2 graflarının arasında bir köprü oluşturacak şekilde yeni bir kenar eklenerek elde edilir. A(G1⋯G2) ile gösterilsin. Bu iki grafın bir kenar ile birleştirilecek köşeleri ardışık şekilde indislenmelidir. İki grafın komşuluk matrisleri bulunup bunları aşağıda verilecek şekilde bir bağlantısız grafın komşuluk matrisi oluşturulur. Ardından birleştirilen ardışık köşelerin komşu olduğunu göstermek için 1 elemanları eklenir. Şekil 4.6 İki grafın köprü ile birleştirilmesi A(G1) A(G2) A(G1UG2) A(G1⋯ G2) 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 → 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 Çizelge 4.7 Bir köprü ile birleştirilmiş grafın komşuluk matrisi 41 Şimdi elde edilen grafın mesafe matrisi kolayca hesap edilebilir. Bunun için iki grafın mesafe matrisini elde ettikten sonra bu grafları bağlantısız iki graf mesafe matrisi şeklinde bir mesafe matrisi oluşturulacaktır. G1 grafının mesafe matrisinin son sütünü ile G2 grafının mesafe matrisinin ilk satırının her elemanın bir fazlasını alarak toplam tablosu oluşturulacaktır. Son olarak bulunan toplam tablosunun sonucu bir T matrisi ile gösterilip T matrisi, transpozu ve 0 matrisleri yerine yerleştirilecektir: D(G1) D(G2) D(G1UG2) D(G1⋯G2) 0 1 2 2 2 0 1 1 2 0 1 2 2 2 0 0 0 0 0 1 2 2 2 3 4 4 5 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 2 3 3 4 2 1 0 1 1 1 1 0 2 2 1 0 1 1 0 0 0 0 2 1 0 1 1 2 3 3 4 2 1 1 0 2 2 1 2 0 2 1 1 0 2 0 0 0 0 2 1 1 0 2 3 4 4 5 2 1 1 2 0 2 1 1 2 0 0 0 0 0 2 1 1 2 0 1 2 2 3 0 0 0 0 0 0 1 1 2 3 2 2 3 1 0 1 1 2 0 1 1 2 0 0 0 0 0 1 0 1 1 4 3 3 4 2 1 0 1 1 + 1 1 1 1 0 0 0 0 0 1 1 0 2 4 3 3 4 2 1 1 0 2 1 2 2 3 0 0 0 0 0 2 1 2 0 5 4 4 5 3 2 1 2 0 T 2 3 4 4 5 3 4 4 5 TT 1 2 3 3 4 2 3 3 4 3 2 2 3 1 1 2 3 3 4 2 3 3 4 4 3 3 4 2 2 3 4 4 5 3 4 4 5 4 3 3 4 2 0 1 2 2 3 1 2 2 3 5 4 4 5 3 + 1 2 2 3 Çizelge 4.8 Bir köprü ile birleştirilmiş grafın mesafe matrisi 4.3.3. Toplama 42 G1 ve G2 graflarının toplamı, köşe kümesi V1∪V2 ve kenar kümesi hem G1 ve G2 graflarının kenarlarını hem de G1 grafındaki her bir köşe ile G2 grafındaki köşelerin birleştirilmesiyle oluşan kenarların oluşturduğu graftır. 𝐺1+𝐺2 ile gösterilir. Köşe dereceleri hesaplanırsa, her nokta komşularına 1 uzaklıkta iken diğer noktalara karşısındaki grafa gidip geldiğinden uzaklığı 2 olacağı görülür. Basitçe bu grafı oluşturmak için bir komşuluk matrisi oluşturulsun. Şekil 4.7 İki grafın toplamı A(G1) A(G2) A(𝐺1+𝐺2) 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 1 0 Çizelge 4.9 İki grafın toplamının komşuluk matrisi 𝐾öş𝑒 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑛1 + 𝑛2 𝐾𝑒𝑛𝑎𝑟 𝑠𝑎𝑦𝚤𝑠𝚤:𝑚1 + 𝑚2 + 𝑛1. 𝑛2 43 A(𝐺1 + 𝐺2) = [ 𝐺1𝑛1×𝑚1 𝐽𝑛1×𝑚2 𝐽𝑛2×𝑚1 𝐺2𝑛2×𝑚2 ] (3.4) ile hesaplanır. 4.3.4. Kartezyen çarpım G1⊠G2 kartezyen çarpım grafı V(G1⊠G2)=V(G1).V(G2) köşe kümesi üzerinde 𝒖=(𝒖1,𝒖2) ve v=(𝒗1,𝒗2) köşelerinin ya birinci bileşenler eşitken ikinci bileşenlerin komşu olması ya da ikinci bileşenler eşitken birinci bileşenlerin komşu olması durumunda iki köşenin bir kenar oluşturmasıyla elde edilen graftır. Kartezyen çarpım ne kadar karmaşık olsa da aşağıdaki adımları uygulayarak komşuluk matrisi kolayca elde edilebilir. İlk olarak iki grafın komşuluk matrisleri elde edilir. İkinci grafımızda her bir bileşeni incelenir. Eğer, bileşenler köşegen üzerindeyse o bileşen yerine ilk grafın matrisi yazılır. Değilse iki durum vardır: komşuluk değeri 1 ise birim matris o bileşen yerine yazılır, komşuluk değeri 0 ise sıfır matrisi yazılır. Bu matrisler ilk matrisin boyutundadır. Kartezyen çarpımının komşuluk matrisi bu şekilde elde edilir. 𝐾öş𝑒 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑛1. 𝑛2 𝐾𝑒𝑛𝑎𝑟 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑛1. 𝑚2 + 𝑚1. 𝑛2 a𝑖𝑗 ∈ 𝐺2 𝑖ç𝑖𝑛 h𝑖𝑗 = { a𝑖𝑗 = 0 ; h𝑖𝑗 = 0𝑛×𝑚 a𝑖𝑗 = 1 ; h𝑖𝑗 = 𝐼𝑛×𝑚 𝑗 = 𝑖 ; h𝑖𝑗 = 𝐴(𝐺1) 𝐴(𝐺1 ⊠ 𝐺2) = [ h𝑖𝑗 ⋯ h𝑖𝑗 ⋮ ⋱ ⋮ h𝑖𝑗 ⋯ h𝑖𝑗 ] (3.5) Aşağıdaki gösterimden yararlanılabilir: 44 Şekil 4.8 İki grafın kartezyen çarpımı A1 A2 A1 ⊠ A2 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 Çizelge 4.10 İki grafın kartezyen çarpımın komşuluk matrisi A2 grafı bir harita gibi düşünülebilir. Bu harita sayesinde kartezyen çarpım grafı kolaylıkla elde edebilir. 45 4.3.5. Simetrik fark Simetrik fark işlemi “G1 ve G2 graflarının köşelerinin oluşturduğu sıralı ikililerin arasında iki bileşeni de kendi grafında komşuysa komşu değildir” olarak tanımlanır. Bu işlem, basit olarak iki grafın sıralı bir şekilde olmasına dikkat ederek komşuluk matrislerinin farkını bularak elde edilir. Tabii ki köşe sayıları farklı olabileceğinden küçük boyutlu matrise 0 satır ve sütunları ile aynı kare matrise ulaştırıp çıkarma işlemi yapılır. Bağlantısız noktalardan kurtulmak için 0 satır ve sütunlarını silinir. İndisleme farklı olursa tamamen farklı bir graf elde edilir. Şekil 4.9 Grafların simetrik farkı A A’ 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 A-A’ 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 ─ 1 1 0 0 0 0 = 0 0 0 1 1 0 → 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 Çizelge 4.11 Grafların simetrik farkının komşuluk matrisi 𝐾öş𝑒 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑛1. 𝑛2 𝐾𝑒𝑛𝑎𝑟 𝑠𝑎𝑦𝚤𝑠𝚤: 2. 𝑛1. 𝑚2 + 2. 𝑛2𝑚1 − 4.𝑚1. 𝑚2 (3.6) 46 4.3.6. Taç çarpımı Taç çarpımının hesaplanması için iki grafın komşuluk matrisi kullanılacaktır. Hangi grafın merkezde olduğu önemlidir. Bu grafa birinci graf denilsin. Bu graftaki tüm köşelerin karşısında ikinci graf çizilsin ve tüm köşelerle birleştirilsin. Bu sayede taç grafı çizilmiş olacaktır. Şimdi ikinci grafın komşuluk matrisinin üst ve sol tarafına bir satır ve sütün eklensin ilk bileşen ilk grafın komşuluk matrisi diğer bileşenler birim matris olacak şekilde alınır. Geri kalan matris elemanlarının bileşenleri 1 ise birim matris, 0 ise sıfır matris yazılarak grafın komşuluk matrisi oluşturulur. Şekil 4.10 Taç çarpımı 𝐾öş𝑒 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑛1 + 𝑛1. 𝑛2 𝐾𝑒𝑛𝑎𝑟 𝑠𝑎𝑦𝚤𝑠𝚤: 𝑚1 + 𝑛1. (𝑚2 + 𝑛2) a𝑖𝑗 ∈ 𝐺2 𝑖ç𝑖𝑛 h𝑖𝑗 = { a𝑖𝑗 = 0 ; h𝑖𝑗 = 0𝑛×𝑚 a𝑖𝑗 = 1 ; h𝑖𝑗 = 𝐼𝑛×𝑚 A(𝐺1x𝐺2) = [ 𝐴(𝐺1) 𝐼 ⋯ I 𝐼 h𝑖𝑗 ⋮ ⋱ ⋮ I ⋯ h𝑖𝑗] (3.7) 47 A(G1) A(G2) A(G1 x G2) 0 0 0 0 1 A I I I I 0 0 1 1 0 0 0 1 0 I 0 0 I 0 0 1 0 1 0 0 0 1 0 I 0 0 I 0 0 1 1 0 1 1 1 0 1 I I I 0 I 1 0 0 1 0 0 0 1 0 I 0 0 I 0 A(G1 x G2) 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 Çizelge 4.12 Taç çarpımı komşuluk matrisi 48 5. SONUÇ Yapılan işlemler excel üzerinden detaylı örneklerle kontrol edilmiştir. Graphonline.ru internet sitesinin sunmuş olduğu algoritmalarla hesaplamalar yapılmış ve excelde kendi kurduğumuz hesaplamalar ile birleştirerek bileşen sayısının artışından doğan karmaşadan sıyrılarak genellemelere ulaşılmıştır. Bu sayede bir grafın komşuluk, bitişiklik, mesafe matrisleri ve derece dizilerinin birbiriyle ilişkileri incelenmiş, statü ve statü indeksleri hesabında kullanımı gösterilmiştir. Çekirdek, gölge, görüntü graf türlerinin genellemelerine bu sayede ulaşılmıştır. 49 KAYNAKLAR Chung, F. (1992). Spektral Graf Teorisi, Amerikan Matematik Derneği. ISBN 978- 0821803158. Delen, S. (2019). Omega İnvaryantı, Doktora Tezi, Bursa Uludağ Üniversitesi Fen. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis (http://math.dartmouth.edu/~euler/. Harary, F. (1959). Status and contrastatus, Sociometry, 22, 23–43. Wiener, H. (1947). Structural determination of paraffin boiling points, J. Am. Horn, A. R., Johnson, R. C., (1990). Matrix Analysis. Gutman, I., Trinajstic, N. (1972). Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17. Skiena, S. (1990). Line Graph. in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 128 and 135-139. Thomas, P. A., Asharafi, A. R. and Bindhu K. (2020). Distance matrix from adjacency matrix. Yalnaik, H. S. (2016). Status connectivity indices of graphs and its applications. 50 ÖZGEÇMİŞ Adı Soyadı : Berke ÖZMEN Doğum Yeri ve Tarihi : Bursa, 23.07.1999 Eğitim Durumu Lise : EGAL( Ertuğrulgazi Anadolu Lisesi) HAAL( Hasan Aslanoba Anadolu Lisesi) Lisans : Uludağ Üniversitesi Matematik Bölümü Yüksek Lisans : Uludağ Üniversitesi Matematik Bölümü Çalıştığı Kurum(lar) : Sınav Koleji(2), Sınav Kurs(2), Kaplan Kurs(1), Bilge Kurs(2), Karacan Kurs(1), Uludağ Koleji (Matemtik Öğretmeni) İletişim (e-posta) : berkeozmen1864@gmail.com Akademik çalışmalar* 1. Balseven, Y., Kose, D., Ozmen, B., Yurttas Gunes, A., Ozden Ayna, H., Cangul, Ismail Naci, Some New Properties of Line Graphs and Their Omega Invariants, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) 2. Ozmen, B., Balseven, Y., Kose, D., Ozden Ayna, H., Yurttas Gunes, A., Cangul, Ismail Naci, Power Graphs of Some Graph Classes, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) 3. Kose, D., Ozmen, B., Balseven, Y., Ozden Ayna, H., Yurttas Gunes, A., Cangul, Ismail Naci, Omega Invariant of Second and Third Power Graphs of Tadpole Graphs, 2nd International E-Conference on Mathematical and Statistical Science: A Selcuk Meeting, 05-07 June, 2023, Selcuk University, Konya, Turkey (Online) mailto:berkeozmen1864@gmail.com