Bir Hiperküp Varyantında Yapısal Bağlantılılık

Abstract

Bir iletişim ağındaki temel problemlerden biri, veri akışının devamlılığının sağlanmasıdır. Günümüzde çeşitli uygulamalarda kullanılan iletişim ağlarının modellenmesinde sıklıkla karşılaşılan yöntemlerden biri de çizge teorisidir. Ağlar üzerinde herhangi bir merkezde ya da merkezler arasındaki bağlantılarda hasar meydana geldiğinde, geriye kalan ağdaki iletişimin ne durumda olacağını belirlemek oldukça önemli bir problemdir. Etkin ağ topolojisi seçimi yapabilmek için bu ölçümlerin önceden yapılması gerekir. Bu amaçla, çizgeler üzerinde çeşitli zedelenebilirlik parametreleri tanımlanmıştır. Bu parametrelerden en eski olanı, bağlantılılık sayısıdır; hasar gördüğünde çizgeyi bağlantısız hale getiren minimum tepe sayısını verir. Ancak, bağlantılılık sayısı tanımında, herhangi bir tepenin bütün komşularının aynı anda hasar görebileceği kabul edilmektedir ve bu analiz özellikle büyük boyutlu ağlarda elverişli sonuçlar sunamamaktadır. Literatürde, bu eksikliğin giderilmesi amacıyla tanımlanmış farklı zedelenebilirlik parametreleri mevcuttur. Diğer yandan ağ dayanıklılığı konusunda şimdiye kadar yapılmış olan çalışmaların birçoğu, tepelerin çevreden bağımsız bir şekilde hasar gördükleri kabul edilerek yapılmaktadır. Halbuki, birçok gerçek dünya probleminde, hasarlı bir tepenin komşularının daha zedelenebilir olması ya da hasar görme olasılığının daha yüksek olması beklenmektedir. 2016 yılında Lin ve ark. tarafından tanımlanmış yapısal bağlantılılık yaklaşımında, hasarın her bileşeninin belirli bir yapıya sahip olduğu veya belirli bir yapının altyapısı olduğu durumlar ele alınmaktadır. Bu tez çalışmasında, regüler ve sonsuz bir çizge sınıfı olan katlı divide-andswap küpler ele alınmıştır ve bu sınıf yapısal bağlantılılık ve altyapısal bağlantılılık açısından incelenmiştir.

One of the main problems in a communication network is the continuity of data flow. Modeling with graph theory is a common method for addressing problems in communication networks used in various applications. It is an important problem to determine the state of communication in the remaining network when damage occurs in any center on the network or in the connections between the centers. These measurements must be conducted in advance to determine an effective network topology. For this purpose, several vulnerability parameters have been defined on graphs. Connectivity is one of the oldest vulnerability parameters; it determines the minimum number of vertices whose deletion results in a disconnected graph. However, in the definition of connectivity, it is assumed that all the neighbors of any vertex can be damaged at the same time, and this analysis cannot yield favorable results. In the literature, there are several vulnerability parameters defined to compensate for this deficiency. On the other hand, most studies on network vulnerability so far have assumed that vertices are damaged independently of their neighborhoods. However, in many real-world problems, the neighbors of a damaged vertex will be more vulnerable, or, more likely to be damaged. In 2016, Lin et al. proposed the structure connectivity, to consider the cases where each component of the damage has a specific structure or is a substructure of a specific structure. In this thesis, we addressed a regular infinite graph class, namely folded divideand- swap cubes and investigated this class in terms of structure and substructure connectivity.