La conectividad condicional, definida por Harary en 1983, mide el mínimo número de vértices (o ramas) que hay que eliminar de un grafo o digrafo de forma que todas las componentes conexas resultantes tengan una propiedad prefijada de antemano. La importancia de los diferentes tipos de conectividad condicional está unida al concepto de supervivencia de las componentes que se determinan cuando la red se interrumpe, lo que se expresa especificando las propiedades de estas componentes. Engloban tanto la conectividad estándar como la superconectividad ya que pueden ser interpretadas como conectividades condicionales con respecto a la propiedad que consiste en tener más de cero vértices o un vértice respectivamente.En esta tesis presentamos condiciones suficientes de dos tipos que garantizan altas conectividades condicionales: cotas superiores sobre diámetro y cotas inferiores sobre el orden, ambas formuladas en términos del girth en el caso de grafos, o bien en función del semigirth l en el caso de digrafos.El primer tipo de conectividad condicional abordada es la t-distancia conectividad que juega un papel importante a la hora de medir la fiabilidad de la red como una función de la distancia entre los nodos que queremos comunicar. En este caso se requiere que los conjuntos desconectadotes separen vértices que estaban suficientemente alejados en el (di)grafo original. Se define el t-grado y se muestra que los parámetros que miden la t-distancia conectividad la arco t-distancia conectividad y el t-grado están relacionados por desigualdades que generalizan las desigualdades conocidas para las conectividades estándar. Además, se prueba que otra de las propiedades que estos nuevos parámetros mantienen es la independencia.El trabajo realizado previamente permite profundizar en el estudio de la superconectividad de (di)grafos y de digrafos bipartitos. Se aborda el problema de desconectar de manera no trivial un digrafo superconectado, centrándonos en calcular la máxima distancia a la que se encuentra alejado un vértice de un conjunto desconectador no trivial de cardinal relativamente pequeño. Se introducen los parámetros que miden la superconectividad de un digrafo superconectado, y se estudian condiciones suficientes sobre el diámetro y el orden para obtener cotas inferiores sobre estas medidas de superconectividad. Por último se desarrolla un estudio en el caso de grafos, paralelo al realizado en el caso dirigido. Se expone una tabla en cuyas entradas figuran los órdenes de los grafos con el mayor número de vértices que se conocen hasta el momento junto con sus conectividades respectivas.La última parte de la tesis está dedicado al estudio de grafos que modelan redes conectadas de forma óptima con respecto a la siguiente propiedad de tolerancia a fallos: Cuando algunos nodos o uniones fallan, se exige que en las componentes que se determinan en la red haya un número mínimo de nodos conectados entre sí. Esta conectividad condicional se denomina extraconectividad, que corresponde con la propiedad consistente en tener al menos un cierto número de vértices. Desde este punto de vista, tanto la conectividad estándar como la superconectividad, constituyen medidas de conectividad condicional. El trabajo llevado a cabo mejora sustancialmente las primeras condiciones suficientes sobre el diámetro dadas por Fiol y Fàbrega quienes ya habían conjeturado que la cota superior sobre el diámetro que se había encontrado era posible mejorarla. / The conditional connectivity defined by Harary in 1983, gives the minimum number of vertices or edges which have to be eliminated from a graph or a digraph in such a way all the resulting connected components satisfy a determined property The importance of the different types of conditional connectivity is linked to the concept of survival of the components that determine when the network is interrupted, which is expressed by specifying the properties of these components. They include both connectivity standard as superconectividad as they can be interpreted as a conditional connectivities with respect to the property that is to have more than zero points or a vertex respectively.In this thesis we present sufficient conditions of two types that guarantee high conditional connectivities: upper bounds on diameter and lower bounds on the order, both in terms of girth made in the case graph, or in terms of semigirth l in the directed case.The first type of conditional connectivity addressed is the t-distance connectivity that plays an important role in measuring the reliability of the network as a function of the distance between the nodes that we want to communicate. In this case disconnecting sets are required to separate vertices that were sufficiently distant in the original (di)graph. The t-degree is defined and it is shown that the parameters that measure the t-distance connectivity the arc t-distance connectivity and t-degree inequalities are related by the same inequalities known for standard connectivities. In addition, it is proved that another of the properties that these new parameters keep is the independence.The work done previously allows to study in depth the superconectivity of digraphs and bipartite digraphs. It addresses the problem of disconnecting in a non-trivial way a superconnected digraph, focusing on calculating the maximum distance that is a remote vertex from a non-trivial disconnecting set of cardinality relatively small. The superconnectivity parameters are introduced and sufficient conditions on the diameter and on the order to obtain good measures of superconnectivity are given. Finally, there has been a case study in graphs, conducted in parallel to the directed case addressed. A table whose entries include orders of the graph with the largest number of vertices that are known so far along with their respective connectivities is exposed.The last part of the thesis is devoted to the study of connected graphs modeling networks in an optimal way with respect to the following property of fault tolerance: When some nodes or links fail, it is required that all the components that are determined by the network have a minimum number of nodes connected to each other.This kind of conditional connectivity is called extraconectivity, and corresponds to the property of having at least a certain number of vertices. From this point of view, both as the standard connectivity and superconectivity constitute measures of conditional connectivity. The work carried out substantially improves the early sufficient conditions on the diameter given by Fiol and Fàbrega who had already conjetured that the upper bound on the diameter, which they had been found could be improved.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/6726 |
| Date | 24 November 1995 |
| Creators | Balbuena Martínez, Camino |
| Contributors | Fàbrega, Josep (Fàbrega Canudas), Fiol Mora, Miquel Àngel, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada i Telemàtica |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Spanish |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0021 seconds