Çizgelerin zedelenebilirlik değerlerinin bulunması üzerine

Abstract

Çizge teorisi matematik ve bilgisayar bilimlerinin önemli dallarından biridir. Günümüzdeki bir çok karmaşık problem çizgeler ile modellenip, çözümleri daha kolay bir biçimde yapılabilir. İletişim ağlarının zedelenebilirliğinin hesaplanması bu problemlerden biridir. Zedelenebilirlik, ağın bazı merkezleri ya da bağlantı hatları hasar gördüğünde, ağın bozulmaya karşı direncini gösterir. Bir iletişim ağının zedelenebilirliğinin hesaplanması için çizge teoride tanımlanmış pek çok çizge parametresi vardır. Bu parametrelerden bazıları bağlantılılık sayısı, bütünlük sayısı, dayanıklılık sayısı, saçılım sayısı, baskınlık sayısı, 2-baskınlık sayısı, bağımlılık sayısı ve 2-bağımlılık sayısıdır. Bu tezde ilk olarak genel çizge tanım ve teoremleri verilmiştir. Ardından bilinen bazı genel çizge yapılarının (yol, çevre, yıldız, tekerlek, tam çizge) orta çizgeleri için 2-baskınlık ve 2-bağımlılık değerleri hesaplanmıştır. Daha sonra, tekerlek çizge, tekerlek çizge ile ilgili çizge yapıları (arkadaşlık, dişli, dümen, ayçiçeği çizge) ve bunların ayrıt çizgeleri için 2-baskınlık ve 2-bağımlılık değerleri hesaplanmıştır. Son olarak, bir çizgenin 2-baskınlık sayısını bulan algoritma verilmiştir.

Graph theory is an important branches of the mathematics and computer science. Nowadays, many problems which have a complex structure can be modeled by graphs, thus solution of these problems can be done easily. One of these problems is computing the vulnerability of communication networks. Vulnerability indicates the resistance of a network to disruptions in communication after a breakdown of some processors or communication links. There are a lot of graph parameters for computing vulnerability of a communication network. Some of them are connectivity, integrity, toughness, scattering number, domination number, 2-domination number, bondage number and 2-bondage number.In this thesis, firstly general graph definitions and theorems are given. Then, 2-domination numbers and 2-bondage numbers are calculated for middle graphs of general graph structure (path, cycle, star, wheel, complete graphs). After, same calculations are made for wheel graphs, wheel related graphs (friendship, gear, helm, sunflower graph) and theirs line graphs. Finally, algorithm is obtained values of 2-domination number of any graph is given.