Yönlü graflar

Abstract

Bu çalışmada, graf teorinin en ilginç ve geniş uygulama alanına sahip olan türü olan yönlü graflar ele alınmıştır. Başta elektrik devreleri olmak üzere bir çok grafta köşelerin modellediği nesneler arasında tek taraflı bağıntı veya ilişkiler olabilir ve bu durumda klasik graflar yerine yönlü graflar kullanılmaktadır. Bu tez 8 bölümden oluşmaktadır. Birinci bölüm giriş bölümü olup bu bölümde graflarla ilgili temel kavramlar hatırlatılmış ve tezin ilerleyen bölümlerinde kullanılacak olan bazı sonuçlar verilmiştir. Ayrıca sık kullanılan graf türleri ve temel özellikleri hatırlatılmıştır. İkinci bölümde genel anlamda yönlendirilmiş graflar ele alınmıştır. Ayrıca yönlü, etiketlenmiş ve etiketlenmemiş graf tanımları ve temel özellikleri de verilmiştir. Üçüncü bölümde yönlü grafların karakteristik polinomları elde edilmiştir. Klasik grafların karakteristik polinomları 0 ve 1’lerden oluşurken, yönlendirilmiş grafların karakteristik polinomları 0, 1 ve -1’lerden oluşmaktadır. Dördüncü bölümde yönlü ve yönlendirilmiş grafların karakteristik polinomları; beşinci bölümde ise yönlü grafların karakteristik polinomları incelenmiştir. Altıncı bölümde kenar ekleme ve benzeri büyütme işlemlerinin karakteristik polinoma etkisi ele alınmıştır. Yedinci bölümde yönlü grafları birleştirme ve ayrıştırmanın karakteristik polinoma etkisi ele alınmıştır. Sekizinci ve son bölüm, Sonuç bölümüdür ve kısa bir değerlendirme verilmiştir.

In this thesis, directed graphs which form the most interesting type of graphs with a large application area are studied. In many graphs like electrical circuits, there may be one way relations between the vertices modelling things in the problem and in such cases, directed graphs are used instead of graphs. This thesis consists of 8 chapters. The first chapter is the introductory chapter and the fundamental notions are recalled here together with the results which will be needed in later chapters. Also some frequently used graph classes and their fundamental properties are given. In the second chapter, the notion of directed graphs are considered. Further, the oriented, labeled and unlabeled graphs are recalled. In the third chapter, the characteristic polynomials of directed graphs are studied. While characteristic polynomials of classical graphs consists of 0 and 1s, the characteristic polynomials of directed graphs consists of 0, 1 and -1s. In the fourth and fifth chapters, characteristic polynomials of directed and oriented graphs are studied. In the sixth and seveth chapters, the effects of edge addition and similar operations on characteristic polynomials and the effects of joining or seperating graphs are studied. In the eighth and last chapter, some conclusions are summarized.