Bir grafın toplam etki sayısı

Graf etiketleme, graf teoride son zamanlarda hızla gelişmekte olan bir problemdir. Bu problem, tepelere ya da ayrıtlara ya da ikisine de bazı şartlara bağlı olarak tam sayı ya da rasyonel sayı atama işlemidir. Literatürde kod teori, astronomi, devre tasarımı, veri tabanı yönetimi gibi birçok uygulaması vardır. Ayrıca bilgisayar bilimlerinde de kriptografi, veri madenciliği, iletişim ağları gibi bir çok alanda önemli bir yeri vardır. Etiketlerin toplamını göz önünde bulunduran ve bir tepe etiketleme problemi olan toplam etki sayısı, graf etiketlemede yeni bir yaklaşımdır. Bir çok tepe etiketleme problemi tüm etiketlerin toplamını minimize etmeye çalışırken, toplam etki sayısı bu toplamı maksimize etmeyi amaçlar. Bu tezde, bir grafın toplam etki sayısı çalışılmıştır. Özel grafların tümleyenlerinin ve tümleyen prizmalarının toplam etki sayıları ile ilgili bazı teoremler verilmiştir. Ayrıca Dijkstra algoritmasını kullanarak bir grafın toplam etki sayısını hesaplayan bir algoritma tasarlanmıştır.

The graph labeling problem that appears in graph theory has a fast development recently. This problem is an assignment of integers or rationals to the vertices or edges or both subject to certain conditions. There are many applications in the literature such as coding theory, astronomy, circuit design, data base management. Graph labeling is also very important major areas of computer science like data mining, cryptography, communication network etc. The total influence number that can be viewed as vertex labeling problems concerned with the sum of the labels is a new approach to the concept of graph labeling. Although many vertex labeling problems concerning with the sum of all of the labels study to minimize the sum, the total influence number has the aim of maximizing the sum. In this thesis, the total influence number of a graph is studied. We give some theorems about the total influence numbers of complement graphs and complementary prisms for specific graphs. Additionally, an algorithm based on Dijkstra algorithm for computing the total influence number of a graph is given.