強Menger連通性的研究

Abstract

連通性是連接網路上ㄧ個重要的量測因子。此篇論文中我們由介紹Menger定理及強Menger連通性開始。我們在類超立方體及配對合成網路上研究此強Menger連通性。首先，我們證明所有屬於n維度超立方體的圖即使有n-2個壞點，仍保有強Menger連通性。更進ㄧ步我們證明:假若我們限制此圖在壞了某些點之後，每個點仍至少有兩個鄰近的點是好的，則此時n維度超立方體的圖壞點數可達到2n-5仍保有強Menger連通性。最後，我們證明更廣義種類的圖，稱為配對合成網路，滿足某些條件之後仍保有強Menger連通性。

Vertex connectivity is an important parameter in interconnection networks.In this thesis we start this thesis by introducing Menger's Theorem and strongly Menger connected property. Then we extend strongly Menger connected property in n-dimensional hypercube-like networks and matching composition networks. First,we show that all graphs in the class of n-dimensional hypercube-like networks have some strongly Menger-connected property,even if these graphs are with n-2 fault vertexs.Furthermore, if we restrict some conditions for each vertex having at least two fault-free adjacent vertices, the class of hypercube-like networks have the strongly Menger-connected property, even if these graph are with 2n-5 fault vertexs. Last, we show that a more general class of graphs, called Matching Composition Networks, satisfying some conditions can have strongly Menger-connected property.