Çizgelerde tepe birleştirilmişlik sayısı üzerine

Abstract

Çizge Kuramı, temel matematikteki matematiksel ilişkiler konusu incelenirken kullanılabildiği gibi,modern hayatta karşılaşılan karmaşık ve geniş kapsamlı birçokprobleme de çözüm getirebilmektedir. Herhangi bir ağ yapısı çizgelerle ifadeedildiğinde bu çizgenin bazı tepelerinin bozulması durumunda dahi bağlantı noktalarıarasındaki iletişimin sürdürülmesi istenir. Ağlarda iletişimi sağlayan bağlantı noktaları,çizgelerdeki tepelere karşılık gelir. Bu tezde öncelikle tepe birleştirilmişlik kavramı ve bu kavramlaile ilgili tanım ve teoremler verilmiş, daha sonra literatürde yer alan tepe birleştirilmişlik algoritmalarıincelenmiştir. Birleştirilmiş bir çizgenin tepe birleştirilmişlik sayısını veren yenibir algoritma önerilmiştir. Bu algoritmanın literatürdeki diğer algoritmalardan farkı,silinen tepeleri kümesini de verebilmesidir. Bu algoritmaya ek olarak, tepe birleştirilmişlik problemiile ilgili matematiksel modeller önerilmiştir. Bunun yanı sıra, bir çizgedeki yoğun tepe ve tepeyoğunluk sayısı kavramları tanımlanarak temel çizge sınıfları için tepe yoğunluk sayılarıhesaplanmış ve sonuçlarıverilmiştir. Son olarak, genetik algoritma tekniği ile tepe birleştirilmişlik sayısınıelde etmek için bir bilgisayar programı yazılmış ve farklı çizgeler için hesaplamadenemeleri yapılmıştır.Anahtar Sözcükler: Graf Teori, tepe birleştirilmişlik, tepe birleştirilmişlik algoritmaları,matematiksel model, tepe yoğunluk sayısı.

Graph theory can be used when examining the mathematical relations in basicmathematics, can give a solution to many complex and comprehensive problems encounteredin modern life. Any network structure, when it is expressed by graphs,even if corruption of some vertices, the communication between the ports is to bemaintained. The ports in the network communications corresponds vertices in graph theory.In this thesis, firstly the concept of vertex connectivity definitions and theoremsare given, then vertex connectivity algorithms are investigated in the literature. A newalgorithm is proposed for calculating the vertex connectivity number of a connectedgraph. The difference of this algorithm from similar algorithms in literature is tobe given the set of deleted vertices. In addition to this algorithm, new mathematicalmodels have been proposed related with the vertex connectivity problem.Besides of this, an intense vertex and vertex intensity number concepts are defined.The intensity number is calculated for some graph families and the resultswere given. Finally, by using genetic algorithms technique, we have obtained vertex connectivitynumber. A computer program is written and the computational experimentsare carried out for different graphs.Key Words: Graph Theory,vertex connectivity, vertex connectivity algorithms,mathematical models, vertex intensity number.