Bir grafın zedelenebilirliği ve k-iletişim sayısı üzerine
Başlık çevirisi mevcut değil.
- Tez No: 28457
- Danışmanlar: PROF. DR. HÜSAMETTİN BAKOĞLU
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Grafikler, Zedelenme, İletişim ağları, Graphics, Bruise, Communication networks
- Yıl: 1993
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET Bir iletişim ağının zedelenebilirlik (vulnerability) değeri, bazı merkezlerin veya bağlantı hatlarının bozulmasından sonra iletişimin kesilmesine kadar ağın dayanma gücünü gösterir. n-merkezli bu iletişim ağını temsil eden bir G grafının bazı tepelerinin atılmasıyla zedelenebilirlik değerinin hesaplanması problemi bugüne kadar Chvatal [9], Barefoot-Entringer-Swart [1,2], Woodal [17] v.b araştırma cılar tarafından çeşitli açılardan ele alınarak incelenmiştir.Ancak, G grafından atılan tepelerin kümesi S olmak üzere, G-S grafının bileşenleri ile grafın zedelenebilirlik değeri arasındaki ilişki hakkında kesin ve doyurucu bir bilgi bugüne kadar verilmemiştir. Bu çalışmada, bizim amacımız, G-S grafının bileşenlerinin tepe sayısını önceden belirleyerek, bir G grafının zedelenebil iri iğinin ölçülmesi problemini yeni bir yaklaşımla incelemektir. Bir G grafının zedelenebilirlik değerini, G-S grafının yapısına ait bilgiler belirler. Ancak, daha önce verilen tanımlar, G-S grafının yapısı hakkında fazla bir bilgi vermemektedir. Halbuki, zedelenebilirlik problemini bizim yaklaşımımız ile ele aldığımızda, G-S grafının yapısı için daha çok bilgi elde edilmektedir. Birinci bölümde, önce bu çalışmada kullanılacak graflara ait tanım ve bazı teoremler ifade edilmiştir.Sonra bir G grafının zedelenebilirlik kavramı incelenmiştir. Buradan, zedelenebilirlik değerinin ölçümü için bir G grafının 50k-iletişim sayası olarak adlandırdığımız yeni bir tanım, verilmiş ve bu sayı com^CG) ile gösterilmiştir. îkinci bölümde, bir G grafının k-iletişim sayısı hakkında bilgi verildikten sonra herhangi bir G grafı için licom^CGJın-k olduğu gösterilmiştir. Yapısı bilinen grafların k-iletişim sayıları hesaplanmış ve grafların invaryantl arından yararlanarak bir G grafının k-iletişim sayısı için bazı sonuçlar elde edilmiştir. G=UGi grafı için comj<(G)=com]<(Gı) +...+com}ç(Gm) olup olmadığı araştırıldıktan sonra, son olarak, kuvvet işleminin ard arda uygulanması ile elde edilen grafların k-iletişim sayıları arasındaki ilişki gösterilmiştir. üçüncü bölümde, genel olarak k-iletişim sayısını elde edemediğimiz bazı grafların 1-iletişim veya 2-iletişim sayıları hesaplanmıştır.Bir G grafı için comx (G)=cc(G) olduğu gösterildikten sonra, Hamiltonian bir G grafının comı(G) değeri için bir alt sınır verilmiştir.Bir T agaeı için comı(T)<n- A<T) olduğu gösterildikten sonra, comı(G) değeri grafın bir spanning ağacına göre elde edilmiştir.Daha sonra, splite bir G grafının 2-iletişim sayısı için bir alt sınır bulunmuştur. Splite bir G grafının çapının en çok 3 olduğunu gösterdikten 2 sonra splite bir G grafı için com2(G ) değeri hesaplanmıştır 51
Özet (Çeviri)
SUMMARY In communication network the value of vulnerability shows the resistance of the network to disruption of communication after the breakdown of some stations or communication links. Up to now, the computation of the vulnerability value of a graph G, which represents the communication network with n-stations and from which certain vertices are removed, has been investigated.Chvatal [9], Barefoot-Entringer-Swart [1,2], Woodal [17] etc. recently working in this field. Howewer, any satisfactory result between the components of the graph G-S and the vulnerability value of the graph G has not been obtained yet, where S denotes the set of the remove 1 vertices of G.In this study, our mean aim is to investigate the problem of the vulnerability measure of G with a new approach by predetermining the number of vertices of the components of the graph G-S. The knowledge about the structure of G-S graph describes the value of vulnerability of a graph G.But, the definitions given before, does not give enough information about the structure of G-S graph. Now, considering vulnerability problem by our approaching we get more about the structure of G-S graph. In the first chapter, some definitions and theorems are given for reference mean. More over, the notion of vulnerability for a graph G is explained. Hence, a new definition for the measure of vulnerability, such as k-communication number of a graph G, is given and it is 52denoted by coi%(G). In the second chapter, after giving some information about k-communication number of a graph G, we showed that licomj^GJin-k for an arbitrary graph G.The k-communication numbers for the graphs whose structures are well-known were calculated and using the invariants of graphs, some results have been obtained for the k-communication number. After investigating comıc(G)=com^(Gı) +...+comk(Gm) m whether holds for the graph G=UGi, we also showed that there 1=1 is a relation between the k-communication numbers of the graphs obtained by successive application of the power operation. In the third chapter, 1-communication or 2-communication numbers of some graphs for which a general k-communication number was not obtainable are calculated for some special cases. After showing comi(G) is equal to cc(G) for a given graph, a lower bound is given for a comi(G) value of a Hamiltonian graph G. After showing comi(T)<n- A(T) for an arbitrary tree T, the comi(G) value is obtained according to a spanning tree of the graph G.Then, we find a lower bound for a 2-communication number of a splite graph G. Also after showing the diameter for a splite graph G can 2 be at most tree, the com2(G ) value for a splite graph G is calculated. 53
Benzer Tezler
- Bir grafın zedelenebilirliği ve l-ayrıt iletişim sayısı üzerine
Başlık çevirisi yok
JALE (İPEK) BİNTAŞ
