Renaud Barate
email: renaud.barate@ensta.fr

Antoine Manzanera
email: antoine.manzanera@ensta.fr

Learning Vision Algorithms for Real Mobile Robots with Genetic Programming

We present a genetic programming system to evolve vision based obstacle avoidance algorithms. In order to develop autonomous behavior in a mobile robot, our purpose is to design automatically an obstacle avoidance controller adapted to the current context. We first record short sequences where we manually guide the robot to move away from the walls. This set of recorded video images and commands is our learning base. Genetic programming is used as a supervised learning system to generate algorithms that exhibit this corridor centering behavior. We show that the generated algorithms are efficient in the corridor that was used to build the learning base, and that they generalize to some extent when the robot is placed in a visually different corridor. More, the evolution process has produced algorithms that go past a limitation of our system, that is the lack of adequate edge extraction primitives. This is a good indication of the ability of this method to find efficient solutions for different kinds of environments.

Introduction

The goal of our research is to automatically design vision based controllers for robots. In this work we focus on obstacle avoidance, which is the first necessary function for a robot to be able to explore autonomously its environment. One of the most popular method to perform obstacle avoidance with a single camera is based on optical flow. It has been used recently with an autonomous helicopter for instance [START_REF] Muratet | A contribution to vision-based autonomous helicopter flight in urban environments[END_REF]. However, systems using optical flow don't cope well with thin or lowly textured obstacles. On the other hand, more simple primitives can be used to extract useful informations in the image, generally based on texture, color and luminosity. For instance, Michels and Saxena implemented a system to estimate depth from texture information in monocular images and they used it to drive a robot in an outdoor environment [START_REF] Michels | High speed obstacle avoidance using monocular vision and reinforcement learning[END_REF][START_REF] Saxena | 3-D Depth Reconstruction from a Single Still Image[END_REF]. This system can be quite accurate but it needs a ground truth (depth images) for the learning phase and the number of computed features in each image is quite important. Other obstacle avoidance systems use this kind of information to discriminate the floor from the rest of the scene and calculate obstacle distances in several directions [START_REF] Ulrich | Appearance-based obstacle detection with monocular color vision[END_REF]. Nevertheless those methods suppose that the floor may be clearly discriminated and they neglect potentially useful information from the rest of the scene.

All those methods are either too complex to be used on an onboard PC or not robust enough to deal with all kind of environments. So we want to design a system able to automatically select the kind of visual features that allow obstacle detection in a given environment and to parameterize the whole obstacle avoidance controller to use those features efficiently. For that, we propose to use genetic programming as it allows us to evolve algorithms with little a priori on their structure and parameters. In the experiments presented in this paper, the evolution is an offline supervised learning process. We first record short video sequences in which the robot is manually guided. The algorithms are evaluated on their ability to imitate the commands issued by the human during those sequences.

Evolutionary techniques have already been widely used for robotic navigation and the design of obstacle avoidance controllers [START_REF] Walker | Evolving controllers for real robots: A survey of the literature[END_REF] but in general vision is either overly simplified or not used at all. For instance, Marocco used only a 5 × 5 pixels retina as visual input [START_REF] Marocco | Active vision and feature selection in evolutionary behavioral systems[END_REF]. On the other hand, genetic programming has been proved to achieve humancompetitive results in image processing systems, e.g. for the detection of interest points [START_REF] Trujillo | Synthesis of interest point detectors through genetic programming[END_REF]. Parisian evolution has also been shown to produce very good results for obstacle detection and 3D reconstruction but those systems need two calibrated cameras [START_REF] Pauplin | Evolutionary Optimisation for Obstacle Detection and Avoidance in Mobile Robotics[END_REF].

To our knowledge, only Martin tried evolutionary techniques with monocular images for obstacle avoidance [START_REF] Martin | Evolving visual sonar: Depth from monocular images[END_REF]. The structure of his algorithm is based on the floor segmentation technique and the evaluation is done with a database of hand labeled real world images. In our work, we don't have any a priori on the method to use for obstacle detection and our sequence recording phase is less tedious than the hand labeling of images.

We already showed in a simulation environment that our method can produce algorithms adapted to the visual context and that the use of imitation in the evolution process can greatly improve the results [START_REF] Barate | Evolving Vision Controllers with a Two-Phase Genetic Programming System Using Imitation[END_REF]. In this paper, we also use imitation during the evolution as the algorithms are evaluated on their ability to imitate recorded commands. The main difference is that the robot moves in a real indoor environment and not in simulation. We show that with this evolution by imitation method, the robot can learn to wander autonomously in its environment.

Material and Methods

Structure of the Vision Algorithms

Generally speaking, a vision algorithm can be divided in three main parts: First, the algorithm will process the input image with a number of filters to highlight some features. Then these features are extracted, i.e. represented by a small set of scalar values. Finally these values are used for a domain dependent task, here to generate motor commands to avoid obstacles. We designed the structure of our algorithms according to this general scheme. First, the filter chain consists of spatial and temporal filters, optical flow calculation and projection that will produce an image highlighting the desired features. Then we compute the mean of the pixel values on several windows of this transformed image (feature extraction step). Finally those means are used to compute a single scalar value by a linear combination. We will use this scalar value to determine the presence of an obstacle and to generate a motor command to avoid it.

An algorithm is represented as a tree, the leaves being input data or constant values, the root being output command, and the internal nodes being primitives (transformation steps). The program can use different types of data internally, i.e. scalar values, images, optical flow vector fields or motor commands. For each primitive, the input and output data types are fixed. Some primitives can internally store information from previous states, thus allowing temporal computations like the calculation of the optical flow. Here is the list of all the primitives that can be used in the programs and the data types they manipulate:

• Spatial filters (input: image, output: image): Gaussian, Laplacian, threshold, Gabor, difference of Gaussians, Sobel and subsampling filter. • Temporal filters (input: image, output: image): pixelto-pixel min, max, sum and difference of the last two frames, and recursive mean operator. • Optical flow (input: image, output: vector field): Horn and Schunck global regularization method, Lucas and Kanade local least squares calculation and simple block matching method [START_REF] Barron | Performance of optical flow techniques[END_REF]. The rotation movement is first eliminated by a transformation of the two images in order to facilitate further use of the optical flow. • Projection (input: vector field, output: image): Projection on the horizontal or vertical axis, Euclidean or Manhattan norm computation, and time to contact calculation using the flow divergence. • Windows integral computation (input: image, output: scalar): For this transformation, we define a global coefficient α 0 and several windows on the left half of the image with different positions and sizes. With each window is paired a second window defined by symmetry along the vertical axis. A coefficient α i and an operator (+ or -) are defined for each pair. The resulting scalar value R is a simple linear combination calculated with the following formula:

R = α 0 + n i=1 α i µ i µ i = µ Li + µ Ri or µ i = µ Li -µ Ri
where n is the number of windows and µ Li and µ Ri are the means of the pixel values over respectively the left and right window of pair i.

• Scalar operators (input: scalar(s), output: scalar): Addition, subtraction, multiplication and division operators, a temporal mean calculation and an if-then-else test. • Command generation (input: two scalars, output: command): The motor command is represented by two scalar values: the requested linear and angular speeds. Most of those primitives use parameters along with the input data to do their calculations (for example, the standard deviation value for the Gaussian filter or the position of windows for the windows integral computation). Those parameters are specific to each algorithm; they are randomly generated when the corresponding primitive is created by the genetic programming system described in Sect. 2.3.

Fig. 1 shows an example controller built with this structure. Rectangles represent primitives and ellipses represent data. The algorithm is a single tree, and all the primitives between the input data and the resulting motor command are created and parameterized by the evolution.

Environment and Evaluation Function

The environment used for the experiments presented in this paper is a corridor in our lab, i.e. the long central corridor represented on Fig. 2. It's a relatively simple environment for vision because the floor is dark and the walls are light colored, but the changes in lighting and the openings in the walls create non-trivial challenges for a vision system. The robot that will move in this environment is a Pioneer 3 DX equipped with an onboard PC and a Canon VC-C50i camera. We use 8-bits gray-value images of size 320 × 240 representing a field of view of approximately 42 • × 32 • , the video rate is 10 images / second. We want the robot to learn to avoid the walls, in order to be able to wander autonomously in this corridor. For this, we first record several short sequences where we manually guide the robot to move away from the walls and to center itself in the corridor. We record the camera images and the commands given to the robot at each time step. The goal is to find the algorithm that best matches the recorded commands given the recorded images. This set of sequences will be our learning base, and we use genetic programming as an offline supervised learning system. Fig. 2 shows some of the trajectories and images we used in this learning base. Note that as we don't have an absolute positioning system, all the trajectories in this paper are drawn by hand from the video sequences and are thus quite imprecise. In the images, the arrow represents the yaw speed command (maximum left corresponds to 30 • /s, maximum right to -30 • /s). For the evaluation of the algorithms, we replay the recorded sequence offline and compare at each time step the command issued by the evaluated algorithm with the command recorded during the manual control of the robot. The goal is to minimize the difference between these two commands along the recorded sequence. Formally, we try to minimize two variables F and Y defined by the formulas:

F = n i=1 (f Ri -f Ai ) 2 and Y = n i=1 (y Ri -y Ai ) 2
where f Ri and y Ri are the recorded forward and yaw speed commands for frame i, f Ai and y Ai are the forward and yaw speed commands from the tested algorithm for frame i and n is the number of frames in the video sequence. The evaluations consist in fact in twenty short sequences. Final scores are the means of the scores obtained for the different sequences. Note that as we generally drive the robot at the maximum speed (which is 30 cm/s in these experiments), the forward command is trivial to learn. We'll focus more on the yaw command for the discussion of the results.

The Genetic Programming System

We use genetic programming to evolve vision algorithms with little a priori on their structure. As usual with evolutionary algorithms, the population is initially filled with randomly generated individuals. We use the grammar based genetic programming system introduced by Whigham [START_REF] Whigham | Grammatically-based genetic programming[END_REF] to overcome the data typing problem. It also allows us to bias the search toward more promising primitives and to control the growth of the algorithmic tree.

In the same way that a grammar can be used to generate syntactically correct random sentences, a genetic programming grammar is used to generate valid algorithms. The grammar defines the primitives and data (the bricks of the algorithm) and the rules that describe how to combine them. The generation process consists in successively transforming each non-terminal node of the tree with one of the rules. This grammar is used for the initial generation of the algorithms and for the transformation operators. The crossover consists in swapping two subtrees issuing from identical non-terminal nodes in two different individuals. The mutation consists in replacing a subtree by a newly generated one. Table 1 presents the exhaustive grammar that we used in these experiments for the creation and transformation of the algorithms.

The numbers in brackets are the probability of selection for each rule. A major advantage of this system is that we can bias the search toward the usage of more promising primitives by setting a high probability for the rules that generate them. We can also control the size of the tree by setting small probabilities for the rules that are Table 1. The genetic programming grammar. likely to cause an exponential growth (rules like REAL → ifThenElse(REAL, REAL, REAL, REAL) for instance). The parameters of the primitives are generated randomly when the corresponding rule is selected. We define the bounds for each parameter along with the distribution to use for its generation (uniform or normal). For normal distribution we also define the mean value of the parameter and its standard deviation.

As described previously, we wish to minimize two criteria (F and Y ). For that, our system uses the widely used multi-objective evolutionary algorithm called NSGA-II introduced by K. Deb [5]. Nevertheless, the forward speed command is trivial to learn in this experiment so a classical mono-objective evolutionary algorithm would probably have given similar results.

In order to prevent premature convergence, we separate the population of algorithms in 4 islands, each containing 100 individuals. Those islands are connected with a ring topology; every 10 generations, 5 individuals selected with binary tournament will migrate to the neighbor island while 5 other individuals are received from the other neighbor island. The evolution lasts for 100 generations. For the parameters of the evolution, we use a crossover rate of 0.8 and a probability of mutation of 0.01 for each non-terminal node. We use a classical binary tournament selection in all our experiments. Those parameters were determined empirically with a few tests using different values. Due to the length of the experiments, we didn't proceed to a thorough statistical analysis of the influence of those parameters.

Experiments and Results

Analysis of the Evolved Controllers

In total, the learning phase lasts for 100 generations, that is 40,000 evaluations. Fig. 3 presents the Pareto fronts obtained by taking the best algorithms in all the four islands at different times of the evolution and keeping only nondominated ones. As said before, the target forward command is almost constant in all the learning set so it is very easy to learn. For the yaw command, we clearly see a progressive improvement from the first generation to the last. We present on Fig. 4 an example of an evolved algorithm. Only a part of it can be presented here because the filter chain contains 29 filters. This high number of filters is partly due to bloating, which means that the evolved programs contain some irrelevant parts that have no significant effect on the final result. The only action we took against bloating is to limit the computation time of the algorithm, but it does not prevent the accumulation of quickly computed filters like in this case. Several solutions have been proposed to limit bloating in genetic programming. Among them, the inclusion of program size as an independent criterion in a multi-objective evolutionary algorithm has been shown to produce efficient and small-sized programs (see [START_REF] Bleuler | Multiobjec-Genetic Programming: Reducing Bloat Using SPEA2[END_REF] for instance). As we already use multi-objective optimization in our system, we plan to adapt and test this technique in the near future.

The second and more interesting reason for this high number is that the evolution found a way to go past a limitation of our system. Indeed, the only available operator to transform an image into a scalar is the windows integral computation described before. This operator is welladapted for the computation of large features in the image, but not for point or edge features. The evolved algorithm uses a sobel filter that produces an edge corresponding to the separation between the wall and the floor. Most of the subsequent filters just enlarge this edge to allow the windows integral computation to produce a value depending on this edge. Of course, this could have been done more easily with a simple dilatation filter and we plan to add morphological filters in our system, but the fact that the evolution found a way to go past this limitation is a good indication of the adaptability of this system. Fig. 5 illustrates the method used by this evolved algorithm to compute the motor command. The red arrow is the command issued by the algorithm, the yellow one is the recorded command. The filter chain highlights and enlarges the boundary between the floor and the wall, as well as the more contrasted zone at the end of the corridor. In the resulting image, the wall appears completely white and the boundary is darker. This difference is used by the windows integral computation operator to produce a command that drives the robot away from the wall (the resulting command depends on the difference between the mean pixel value of each red window).

Generalization Performance

In order to test the robustness and generalization performance of these evolved controllers, we place the robot at different positions in the corridor and let it move driven by the evolved algorithm. The robot should move to the end of the corridor without hitting the walls. We place the robot so that the direction it faces and the corridor make an angle of approximately 30 • . This way, the problem is possible to solve without being trivial. We made about ten tests with different starting positions. Each time, the robot managed to reach the end of the corridor except once where it turned into one of the openings in the wall. In one test, it even turned at the end of the corridor to go into the smaller corridor on the right of the map. Fig. 6 shows an example trajectory followed by the robot driven by the evolved algorithm presented before. Note that the two last images correspond to situations that were not included in the learning set. We also tested this evolved algorithm in another corridor visually different from the previous one. In one direction the robot reaches the end of the corridor without problem. On the return trip it failed against two obstacles as shown on Fig. 7. The middle and right images correspond to the two obstacles that the robot failed to avoid. Nevertheless this result is encouraging since this corridor is very different from the one in which the learning base was recorded. These experiments prove that our system can produce vision algorithms adapted to a given context to drive a mobile robot in an indoor environment. We now plan to validate it on a wider range of environments. It will also be necessary to give a functional goal to the controllers, like going to a given point or simply exploring the environment as quickly as possible. We have already shown in simulation how to deal with two possibly conflicting goals [2] but we still have to validate these techniques in a real environment.

In real applications, it's inconceivable to evolve controllers for each kind of environment and task the robot may have to face. Our goal is to build a small database of quite generic controllers, to automatically select one depending on the visual context and to adapt it online to improve its performance. We can not use the complete evolution process online but we could slightly change only the values of the numerical parameters of the algorithm and reward the customized version that drive the robot for the longest time without hitting obstacles for instance. Of course, this would also require a collision detector and a way to move the robot away from the obstacle automatically after the collision. But we hope that starting with an evolved algorithm, this adaptation phase could quickly produce efficient algorithms and thus make the controllers more adaptable to different environments.

Conclusion

We presented in this paper a method to automatically generate algorithms adapted to a given environment. We applied it to the obstacle avoidance problem in a real indoor environment. We showed that our system created efficient algorithms, able to drive the robot in a corridor without hitting the wall and using only monocular vision. We now plan to design an online system to adapt the vision algorithm depending on the context in real-time, in order to have a fully autonomous and adaptive robot.

Figure 1 .

 1 Figure 1. Example of a controller for obstacle avoidance based on optical flow.

Figure 2 .

 2 Figure 2. Top: Examples of trajectories used for the learning base. Bottom: Examples of recorded images and commands.

Figure 3 .

 3 Figure 3. Pareto fronts of the solutions obtained along the generations.

Figure 4 .

 4 Figure 4. Example of an evolved algorithm.

Figure 5 .

 5 Figure 5. Left: Resulting command from the evolved algorithm on an image from the learning base. Right: The same image transformed by the filter chain.

Figure 6 .

 6 Figure 6. Top: Trajectory followed by the robot when driven by an evolved algorithm. Bottom: Images and commands issued by the algorithm in the generalization tests.

Figure 7 .

 7 Figure 7. Top: Trajectory followed by the robot driven by the evolved algorithm in another corridor. Bottom: Images and commands issued by the evolved algorithm in this other corridor.


Christian Tanguy
email: christian.tanguy@orange-ft.com

Exact solutions for the two-and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan

Keywords: network reliability, transfer matrix, zeros of the reliability polynomial, algebraic structures

The two-and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan have been calculated exactly for arbitrary size as well as arbitrary individual edge and node reliabilities, using transfer matrices of dimension four at most. While the all-terminal reliabilities of these graphs are identical, the special case of identical edge (p) and node (ρ) reliabilities shows that their two-terminal reliabilities are quite distinct, as demonstrated by their generating functions and the locations of the zeros of the reliability polynomials, which undergo structural transitions at ρ = 1 2 .

Introduction

Network reliability has long been a practical issue since the pioneering work of Moore and Shannon [START_REF] Moore | Reliable circuits using less reliable relays[END_REF], and will remain addressed by reliability engineers, statistical physicists and applied mathematicians for years, since networks are pervading our everyday life. Not surprisingly, the study of network reliability has led to a huge body of literature, which includes excellent textbooks and surveys [START_REF] Ball | Handbooks in operations research and management science[END_REF][START_REF] Barlow | Mathematical theory of reliability[END_REF][START_REF] Colbourn | The combinatorics of network reliability[END_REF][START_REF] Shier | Network reliability and algebraic structures[END_REF][START_REF] Shooman | Probabilistic reliability: an engineering approach[END_REF]. In the following, we consider a probabilistic approach of reliability, in which the network is represented by an undirected graph G = (V, E), where V is a set of nodes (also called vertices), and E is a set of undirected edges (or links). Each element of V and E has a probability p n or p e to operate correctly; failures of constituents are assumed to occur at random, and to be statistically independent events (this restriction may be relaxed, eventually). Among the different measures of reliability, one often considers the k-terminal reliability, i.e., the probability that a given subset K of k nodes (K ⊂ E) are connected. The most common instances are the allterminal reliability Rel A (K ≡ E) and the two-terminal reliability Rel 2 (s → t), which deals with a particular connection between a source s and a terminal destination t. Both of them are affine functions of each p n and p e .

The sheer number of possible system states, namely 2 |E|+|V | , clearly precludes the use of an "enumeration of states" strategy for realistic networks, and shows that the final expression may be extremely cumbersome. Consequently, most studies have assumed graphs with perfect nodes (p n ≡ 1) and edges of identical reliability p; all reliabilities are then expressed as a polynomial in p, called the reliability polynomial. Radio broadcast networks [START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF] have also been described by networks with perfectly reliable edges but imperfect nodes; in this context, one speaks of residual connectedness [START_REF] Boesch | On residual connectedness network reliability[END_REF]. It was shown early on [START_REF] Colbourn | The combinatorics of network reliability[END_REF] that the calculation of k-terminal reliability is #P-hard, even after the simplifying and restricting assumptions that (i) the graph is planar (ii) all nodes are perfectly reliable (iii) all edges have the same reliability p.

The difficulty of the problem has stimulated many approaches : partitioning techniques [START_REF] Dotson | A new analysis technique for probabilistic graphs[END_REF][START_REF] Yoo | A comparison of algorithms for terminal-pair reliability[END_REF], sum of disjoint products [START_REF] Abraham | An improved algorithm for network reliability[END_REF][START_REF] Balan | Preprocessing minpaths for sum of disjoint products[END_REF][START_REF] Heidtmann | Smaller sums of disjoint products by subproduct inversion[END_REF][START_REF] Rai | A survey of efficient reliability computation using disjoint products approach[END_REF][START_REF] Soh | Experimental results on preprocessing of path/cut terms in sum of disjoint products technique[END_REF], graph simplifications (series-parallel reductions [START_REF] Moore | Reliable circuits using less reliable relays[END_REF], triangle-star (also called delta-wye) transformations [START_REF] Chari | The delta-wye approximation procedure for two-terminal reliability[END_REF][START_REF] Egeland | On dependence and reliability computations[END_REF][START_REF] Gadani | System effectiveness evaluation using star and delta transformations[END_REF][START_REF] Rosenthal | Transformations for simplifying network reliability calculations[END_REF][START_REF] Wang | Transformations of star-delta and delta-star reliability networks[END_REF], factoring [START_REF] Wood | A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability[END_REF]), determination of various lower and upper bounds to reliability polynomials [START_REF] Ball | Handbooks in operations research and management science[END_REF][START_REF] Brecht | Lower bounds for two-terminal network reliability[END_REF][START_REF] Brecht | Improving reliability bounds in computer networks[END_REF][START_REF] Brown | Non-Stanley bounds for network reliability[END_REF][START_REF] Chen | Bounds on the reliability of distributed systems with unreliable nodes & links[END_REF][START_REF] Colbourn | The combinatorics of network reliability[END_REF][START_REF] Colbourn | Bounding Network parameters by approximating graphs[END_REF][START_REF] Prékopa | The use of binomial moments for bounding network reliability[END_REF][START_REF] Scott Provan | Bounds on the reliability of networks[END_REF], Monte-Carlo simulations [START_REF] Fishman | A comparison of four Monte Carlo methods for estimating the probability of st connectedness[END_REF][START_REF] Karger | A randomized fully polynomial time approximation scheme for the all terminal reliability problem[END_REF][START_REF] Nel | Combining Monte Carlo estimates and bounds for network reliability[END_REF], genetic [START_REF] Coit | Reliability optimization of series-parallel systems using a genetic algorithm[END_REF] and ordered binary decision diagram (OBDD) algorithms [START_REF] Kuo | Determining terminal pair reliability based on edge expansion diagrams using OBDD[END_REF][START_REF] Rauzy | A new methodology to handle Boolean models with loops[END_REF][START_REF] Yeh | OBDD-based evaluation of k-terminal network reliability[END_REF][START_REF] Fu-Min | Analyzing network reliability with imperfect nodes using OBDD[END_REF]. The reliability polynomial has also been studied [START_REF] Oxley | Chromatic, flow and reliability polynomials: the complexity of their coefficients[END_REF] with the aim of deriving some useful and hopefully general information from the structure of its coefficients [START_REF] Chari | Reliability polynomials : a survey[END_REF][START_REF] Colbourn | Some open problems on reliability polynomials[END_REF], or the location of its zeros in the complex plane [START_REF] Brown | Roots of the reliability polynomial[END_REF].

The Tutte polynomial T (G, x, y) of a graph G has also been shown to be equivalent to the Potts model partition function of the q-state Potts model [START_REF] Shrock | Exact Potts model partition functions on ladder graphs[END_REF][START_REF] Welsh | The Potts model and the Tutte polynomial[END_REF]. Calculations for various recursive families of graphs G quickly followed [START_REF] Chang | Reliability polynomials and their asymptotic limits for families of graphs[END_REF]. The all-terminal reliability polynomial Rel A (G, p) of graphs is deduced from T (G, 1, 1 1-p ). Royle and Sokal [START_REF] Royle | The Brown-Colbourn conjecture on zeros of reliability polynomials is false[END_REF] proved that the Brown-Colbourn conjecture [START_REF] Brown | Roots of the reliability polynomial[END_REF] on the location of the zeros of Rel A (G, p), while valid for series-parallel reducible graphs, does not hold for a few families of graphs. While these results are extremely valuable to better understand a few properties of graphs and all-terminal reliability polynomials, they still assume that nodes are perfect and that edges have the same reliability.

In recent years, the growth of Internet traffic has called for a better evaluation of the reliability of connections in -among others, optical -networks. This, of course, strongly depends on the connection under consideration. Actual failure rates and maintenance data show that a proper evaluation of twoterminal reliabilities must put node and edge equipments on an equal footing, i.e., both edge (fiber links, optical amplifiers) and node (optical cross-connects, routers) failures must be taken into account. The possibility of node failure has been considered in early papers [START_REF] Aboelfotoh | Computing 2-terminal reliability for radio-broadcast networks[END_REF][START_REF] Evans | Optimally reliable graphs for both edge and vertex failures[END_REF][START_REF] Hänsler | Exact calculation of Computer Network Reliability[END_REF], to quote but a few. Adaptation of algorithms to include imperfect nodes has been addressed, sometimes controversially [START_REF] Netes | Consideration of node failures in network-reliability calculation[END_REF][START_REF] Ke | Reliability evaluation for distributed computing networks with imperfect nodes[END_REF][START_REF] Theologou | Factoring & reductions for networks with imperfect vertices[END_REF][START_REF] Torrieri | Calculation of node-pair reliability in large networks with unreliable nodes[END_REF][START_REF] Fu-Min | Analyzing network reliability with imperfect nodes using OBDD[END_REF]; the two-variable approach for bounds to the reliability polynomial, by Bulka and Dugan [START_REF] Bulka | Network s-t reliability bounds using a 2-dimensional reliability polynomial[END_REF] and Chen and He [START_REF] Chen | Bounds on the reliability of distributed systems with unreliable nodes & links[END_REF], is also worth mentioning. In order to be realistic, different edge reliabilities should be used: for instance, the failure rate of optical fiber links is likely to increase with their length. In this work, we give the exact two-terminal reliability of two well-known graphs, namely the Brecht-Colbourn ladder [START_REF] Brecht | Lower bounds for two-terminal network reliability[END_REF][START_REF] Brecht | Improving reliability bounds in computer networks[END_REF][START_REF] Prékopa | The use of binomial moments for bounding network reliability[END_REF] and the generalized fan [START_REF] Aggarwal | A simple method for reliability evaluation of a communication system[END_REF][START_REF] Neufeld | The most reliable series-parallel networks[END_REF], which have the same all-terminal reliability. Both networks have been studied in the literature, especially the first one, as a case study for different lower bounds of the two-terminal reliability [START_REF] Brecht | Improving reliability bounds in computer networks[END_REF], but with a limited number of nodes. Here, the number of nodes will be arbitrary. Our solution fully exploits the recursive nature of the graphs and the triangle-star transformation with unreliable nodes [START_REF] Gadani | System effectiveness evaluation using star and delta transformations[END_REF]. The final expressions are products of (at most) 4 × 4 transfer matrices, in which the arbitrary reliability of each node and edge appears explicitly. In the case of identical edge (p) and node (ρ) reliabilities, we provide the generating functions of the two-terminal reliabilities, leading to a very simple expression for the generalized fan. Another byproduct is the asymptotic locations of the zeros of the two-terminal reliability polynomials for the Brecht-Colbourn ladder and the generalized fan, which exhibit very different structures and undergo a structural transition at ρ = 1 2 .

Our aim is (i) to give a detailed derivation of the final results, so that people involved in reliability studies can readily use an easy-to-implement formula (ii) compare the exact solution with previous results (iii) exhibit the structural changes undergone by the location of the zeros of reliability polynomials as a function of node reliability (iv) emphasize anew the importance of algebraic structures of the underlying graphs in the determination of their associated polynomials [START_REF] Biggs | Algebraic graph theory[END_REF][START_REF] Shier | Network reliability and algebraic structures[END_REF].

Our paper is organized as follows : In Section 2, we briefly recall the formulae for the triangle-star transformation for unreliable nodes. In Section 3, we define the notations for the different edge and node reliabilities and detail the derivation of the main results (eqs. ( 12) and ( 14) for the Brecht-Colbourn ladder, eqs. ( 23) and [START_REF] Coit | System optimization with component reliability estimation uncertainty : a multi-criteria approach[END_REF] for the generalized fan). Section 4 is devoted to the case where all edges and nodes have identical reliabilities p and ρ, respectively, the size of the network appearing simply as an integer n. We give the analytical solution of the two-terminal reliability Rel 2 (p, ρ; n) for the Brecht-Colbourn ladder and the generalized fan, and the associated generating functions, which encode all the necessary information in a beautifully simple, compact form. The asymptotic power-law or constant behaviors are given when n → ∞.

Prompted by the nearly universal character of the Brown-Colbourn conjecture [START_REF] Brown | Roots of the reliability polynomial[END_REF], we address in Section 5 the location of zeros of the two-terminal reliability polynomials, and show that their structures are very different even though their internal structure is similar. For the sake of completeness, we derive in Section 6 the common all-terminal reliability for both networks, for arbitrary values of edge reliabilities. Finally, we conclude by indicating several directions in which the present results may be further extended, so that, for instance, a catalog of exactly solvable networks -in terms of reliabilitymay be given rapidly [START_REF] Tanguy | [END_REF]. Such a catalog of elementary bricks could be useful for a new and improved set of bounds or benchmarks for alternative methods in the general case.

Triangle-star transformation for unreliable nodes

The triangle-star -also called delta-wye or ∆-Y -transformation has been used many times to simplify calculations of network reliability [START_REF] Chari | The delta-wye approximation procedure for two-terminal reliability[END_REF][START_REF] Colbourn | The combinatorics of network reliability[END_REF][START_REF] Egeland | On dependence and reliability computations[END_REF][START_REF] Gadani | System effectiveness evaluation using star and delta transformations[END_REF][START_REF] Wood | A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability[END_REF][START_REF] Rosenthal | Transformations for simplifying network reliability calculations[END_REF][START_REF] Wang | Transformations of star-delta and delta-star reliability networks[END_REF]. It has mostly been applied in a perfect nodes context, to provide upper and lower bounds to the exact reliability. Here, we exploit this transformation to the full in the case of imperfect nodes in order to obtain exact results. Since it plays a crucial part of the derivation, we give the formulae derived by Gadani [START_REF] Gadani | System effectiveness evaluation using star and delta transformations[END_REF].

p A O p C = b + a c B -a b c B, (1)
p A O p B = c + a b C -a b c C, (2) p B O p C = a + b c A -a b c A, (3) p A O p B p C = a b + b c + a c -2 a b c. (4)
Note that the first three equalities correspond to the probability that the two nodes under consideration are connected, while the last one gives the probability that the three nodes are connected. A word of caution -already given by Gadani -is worth mentioning in the case of successive triangle-star transformation: the triangles should have no common edge or node.

3 Derivation of the main results

Brecht-Colbourn ladder

Let us first name the different edge and node reliabilities of the Brecht-Colbourn ladder, and detail how we can use the triangle-star transformation of the preceding section. Assuming that S 0 is always the source node, and using node reliabilities S i , we note a n the reliability of the edge (S n-2 , S n ), and b n that of (S n-1 , S n ), as shown at the top of Fig. 4.

The application of the triangle-star transformation to Fig. 4 leads to

p 1 p 0 p 2 = b n + a n b n-1 S n-2 -a n b n-1 b n S n-2 , (5)
p 1 p 0 p 3 = a n + b n-1 b n S n-1 -a n b n-1 b n S n-1 , (6)
p 1 p 0 p 2 p 3 = a n b n + a n b n-1 + b n-1 b n -2 a n b n-1 b n . (7)
Writing the two-terminal reliability Rel (S 0 → S n ) = S n S n , we immediately see that

S n = p 1 p 0 S n-1 (a n-1 → a n-1 S n-1 p 2 , b n-1 → p 3 ), (8)
because the transformed graph remains essentially a Brecht-Colbourn ladder, provided that some edges are renormalized (b n-1 must be replaced by p 3 , S n-1 by p 0 , and a n-1 by a n-1 S n-1 p 2 ).

In the case of imperfect nodes, the assumption

S n = α n a n + α n a n S n-1 + β n b n S n-1 + γ n a n b n S n-1 (9)
gives four parameters, for which we want to find a recursion relation. When we use eqs. ( 5)- [START_REF] Barlow | Mathematical theory of reliability[END_REF] in eq. ( 9), there is one slightly tricky point: we are actually dealing with Boolean functions, so that S 2 n-2 ≡ S n-2 (see for instance [START_REF] Aggarwal | A simple method for reliability evaluation of a communication system[END_REF]) and

p 1 p 0 α n-1 S n-2 (a n-1 S n-1 p 2 ) = α n-1 S n-1 S n-2 a n-1 (b n + a n b n-1 S n-2 -a n b n-1 b n S n-2 )
Fig. 4. Decomposition of the ladder using the triangle-star transformation.

≡ α n-1 S n-1 S n-2 a n-1 (b n + a n b n-1 -a n b n-1 b n ). ( 10
)
We deduce

          α n α n β n γ n           = M n-1 •           α n-1 α n-1 β n-1 γ n-1           , (11)
where the 4 × 4 transfer matrix M n-1 is given by

M n-1 =           0 0 S n-2 0 a n-1 b n-1 S n-2 a n-1 b n-1 S n-2 0 a n-1 b n-1 S n-2 a n-1 a n-1 S n-2 b n-1 S n-2 a n-1 b n-1 S n-2 -a n-1 b n-1 S n-2 -a n-1 b n-1 S n-2 -b n-1 S n-2 a n-1 (1 -2 b n-1 ) S n-2           .( 12
)
For n = 2, the two-terminal reliability is easily solved because we have seriesparallel graph:

Rel (BC) 2 (S 0 → S 2 ) = S 2 (a 2 + b 1 S 1 b 2 -a 2 b 1 S 1 b 2 ) S 0 , (13)
which leads to α 2 = S 0 , α 2 = 0, β 2 = b 1 S 0 , and γ 2 = -b 1 S 0 , or equivalently to α 1 = α 1 = γ 1 = 0 et β 1 = 1 (see eq. ( 12)). The final result is

Rel (BC) 2 (S 0 → S n ) = S n (0 0 1 0) • M n • M n-1 • • • M 1 •           0 0 1 0           . (14)
Note that in M 1 , a 1 is quite arbitrary, so that it can be set equal to zero without loss of generality. Equation ( 14) also holds for n equal to 1 or even 0 (following a frequent convention that a product of zero matrices is the identity matrix); it has also been independently checked for the first values of n, using a sum of disjoint products procedure.

In the case of perfect nodes, the ansatz should be S n = α n a n +β n b n +γ n a n b n . The relevant 3 × 3 transfer matrix M ′ n is now

M ′ n =        a n b n 1 a n b n a n b n a n b n -a n b n -b n a n (1 -2 b n )        , (15)
from which we deduce Rel (BC) 2 Let us now turn to the second architecture. The triangle-star transformation, applied to the generalized fan, is displayed on Fig. 5, and we expect the common node T to play a special role in the recursion relation. We can write Rel (fan) 2

(S 0 → S n ; perfect nodes) = (0 1 0) • M ′ n • M ′ n-1 • • • M ′ 1 •        0 1 0        . (16)
(S 0 → S n ) = S n S n , and see immediately that

S n = p 1 p 0 S n-1 (a n-1 → a n-1 S n-1 p 2 , b n-1 → p 3 ), (17)
with

p 1 p 0 p 2 = a n + b n-1 b n T -a n b n-1 b n T, (18)
p 1 p 0 p 3 = b n + a n b n-1 S n-1 -a n b n-1 b n S n-1 , (19)
p 1 p 0 p 2 p 3 = a n b n + a n b n-1 + b n-1 b n -2 a n b n-1 b n . ( 20
)
Our ansatz is now

S n = S n α n a n + α n a n T + β n b n T + γ n a n b n T. (21)
Here again, we must be careful with the Boolean variable T . When using eq. ( 18) in eq. ( 21), all occurrences of T 2 must be replaced by T . The recursion relations take the now familiar form

          α n α n β n γ n           = M n-1 •           α n-1 α n-1 β n-1 γ n-1           , (22)
where the transfer matrix M n is

M n =           a n S n 0 0 0 0 a n S n b n S n a n b n S n a n b n S n a n b n S n 1 a n b n S n -a n b n S n -a n b n S n -b n S n a n (1 -2 b n ) S n           . ( 23
)
When n = 1, we have a series-parallel graph:

Rel (fan) 2 (S 0 → S 1 ) = S 1 (a 1 + b 0 b 1 T -a 1 b 0 b 1 T ) S 0 , (24)
from which we deduce the final expression

Rel (fan) 2 (S 0 → S n ) = (1 T 0 0) • M n • M n-1 • • • M 1 • M 0 •           1 0 0 0           , (25)
with the additional convention a 0 ≡ 1 for M 0 . We have also checked the correctness of eq. ( 25) by a sum of disjoint products procedure for the first values of n. It also agrees with the expression of Aggarwal et al. [START_REF] Aggarwal | A simple method for reliability evaluation of a communication system[END_REF] for n = 3.

In the case of perfect nodes, which is often considered in the literature, the ansatz

S n = α n a n + β n b n + γ n a n b n leads to Rel (fan) 2 (S 0 → S n ; perfect nodes) = (1 0 0) • M ′ n • M ′ n-1 • • • M ′ 1 • M ′ 0 •               , (26)
with

M ′ n =        a n b n a n b n a n b n 1 a n b n -a n b n -b n a n (1 -2 b n )        , (27)
and again a 0 ≡ 1 for M 0 .

It is worth noting that while the sizes of M n and M n for the Brecht-Colbourn and fan cases are identical, their matrix elements are clearly distinct. This actually leads to strong differences, as will be shown in the following section.

4 Identical reliabilities p and ρ

Introduction

While eqs. ( 12) and ( 14) give the two-terminal reliability for the general Brecht-Colbourn ladder, and eqs. ( 23) and ( 25) for the fan, we consider here the special case where all edges and nodes have reliabilities p and ρ, respectively. Because identical edge reliabilities are usually taken for granted, our exact results may help to demonstrate once again the underlying connection between combinatorics and reliability theory, most particularly in the enumeration of self-avoiding walks [START_REF] Colbourn | The combinatorics of network reliability[END_REF][START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF][START_REF] Prékopa | The use of binomial moments for bounding network reliability[END_REF]. This assumption greatly simplifies the problem, since all transfer matrices, with the exception of M 0 in the case of the generalized fan, are identical to a matrix M(p, ρ) (or M (p, ρ)): the two-terminal reliability is essentially the n th power of one matrix. While the determination of its eigenvalues and eigenvectors is one way to solve the problem, we adopt in the following the generating function formalism, which is a fundamental tool in combinatorics [START_REF] Stanley | Enumerative combinatorics[END_REF], and makes for a very compact synthesis of the results. The generating function G(z) is defined by

G(z) = ∞ n=0 Rel (n) 2 (p, ρ) z n . ( 28
)
From the finite-order recursion relations obeyed by Rel

(n)
2 , the generating function is obviously a rational function of z, namely G(z) = N(z)/D(z). In the present study, its denominator is at most of degree 4 in z, because in the absence of further simplification, D(z) = z 4 P carac (1/z), where P carac is the characteristic polynomial of the transfer matrix. The determination of N(z) is then very straightforward: we only need to multiply the first terms of the expansion of G(z) by D(z) to see the numerator N(z) emerge. The partial fraction decomposition of G(z) finally leads to a compact, sometimes very simple, analytical expression of Rel

Brecht-Colbourn ladder

Imperfect nodes and edges

When edge and node reliabilities are p et ρ, the transfer matrix of eq. ( 12) is equal to

M(p, ρ) =           0 0 ρ 0 p 2 ρ p 2 ρ 0 p 2 ρ p p ρ p ρ p 2 ρ -p 2 ρ -p 2 ρ -p ρ p (1 -2 p) ρ           , (29)
and

Rel 2 (S 0 → S n ) = ρ (0 0 1 0) • M(p, ρ) n •           0 0 1 0           . ( 30
)
The characteristic polynomial of this matrix is

P (BC) carac (p, ρ; x) = x 4 -p (2 -p) ρ x 3 -p ρ (1 -ρ (p + p 2 -p 3 )) x 2 +(1 -p) (1 -p ρ) p 2 ρ 2 x -(1 -p) (1 -ρ) p 4 ρ 3 . ( 31
)
The eigenvalues of M(p, ρ) are given by the roots of this polynomial of degree 4.

From the first few values of Rel 2 (S 0 → S n ) (taking n = 2, ..., 10, for instance), we can easily deduce the generating function

G (0) BC (z). G (0) BC (z) = p ρ 2 z 2 N (0) BC (z) D BC (z) , (32)
with

N (0) BC (z) = 1 + p (1 -p) ρ + p 2 ρ(1 -p ρ (2 -p)) z -p 2 ρ 2 (1 -p) 2 z 2 +p 4 (1 -p) ρ 3 (1 -ρ) z 3 (33) D BC (z) = 1 -p (2 -p) ρ z -p ρ (1 -ρ (p + p 2 -p 3 )) z 2 +(1 -p) (1 -p ρ) p 2 ρ 2 z 3 -(1 -p) (1 -ρ) p 4 ρ 3 z 4 (34)
Adding ρ + p ρ 2 z (basically, the two-terminal reliability of a single node, or that of two connected nodes) to G (0) BC (z), the numerator further simplifies, so that we may use another generating function, which of course provides the same coefficient of z n for n ≥ 2, namely

G BC (z) = ρ 1 -p (1 -p) ρ z + p 3 (1 -p) ρ 2 z 2 D BC (z) ; (35)
N BC (z) will be the numerator of G BC (z) in eq. [START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF].

What is the nature of the roots ? Numerically, two situations occur when 0 ≤ p ≤ 1 and 0 ≤ ρ ≤ 1: there are either (i) four real roots or (ii) two real roots and two complex roots. For instance, when ρ = 0.9, there are four real roots if p < 0.5533938..., but only two otherwise. The separation of the two domains occurs when one root is degenerate. When this happens, the equalities P (BC) carac (p, ρ; x) = 0 and ∂P (BC) carac (p, ρ; x) ∂x = 0 lead to a polynomial constraint satisfied by p and ρ, given in the appendix (eq. (A.5)). For a given ρ, there exists a unique solution in the range 0 < p < 1, p crit (ρ), which is displayed in Fig. 6.

Fig. 6. Separation of the domains (ρ, p) for which four real roots exist (under the curve) or two real and two complex roots coexist (above it).

From the inspection of eq. ( 35), we may wonder when numerator and denominator of the generating function may share a common root. A Gröbner basis calculation shows that this happens only when p = 2, outside our range of interest. Therefore, there are four distinct roots most of the times, and when there is a double (real) root of P(p crit (ρ), ρ; x), it is indeed degenerate (there is no simplification of G BC (z)). The exact expression for Rel 2 (S 0 → S n ) can then be deduced using a partial fraction decomposition of G BC (z). When all the eigenvalues λ i are distinct,

G BC (z) = λ i -λ i N BC ( 1 λ i ) D ′ BC ( 1 λ i ) α i 1 1 -λ i z ; (36)
consequently, the two-terminal reliability reads

Rel 2 (S 0 → S n ) = λ i α i λ n i . (37)
In the Brecht-Colbourn case, the root λ max of greatest modulus is always real. Unless p and ρ are equal to 1, λ max < 1, so that Rel

(BC) 2 (S 0 → S n ) decreases
as n → ∞, essentially as a power-law behavior

Rel (BC) 2 (S 0 → S n ) ∼ λ n max . (38)

Imperfect edges and perfect nodes

We devote this section to the case of imperfect edges and perfect nodes, since the Brecht-Colbourn ladder was initially investigated in this configuration [START_REF] Brecht | Lower bounds for two-terminal network reliability[END_REF][START_REF] Brecht | Improving reliability bounds in computer networks[END_REF]. We immediately find Rel

(BC;ρ=1) 2 (S 0 → S n ) = (0 1 0) •        p 2 1 p 2 p p p 2 -p 2 -p p (1 -2 p)        n •        0 1 0        , (39)
so that the 25-node case [START_REF] Brecht | Improving reliability bounds in computer networks[END_REF]

The coefficients are already quite large, even though the number of nodes remains limited. To the best of our knowledge, the exact two-terminal reliability polynomial was calculated only for a 10-node ladder [START_REF] Brecht | Lower bounds for two-terminal network reliability[END_REF]; we recover this result by taking n = 9 in eq. ( 39).

The three distinct real eigenvalues λ i (i = 1, 2, 3) of the transfer matrix appearing in eq. ( 39), one of which is negative, are displayed as a function of p in Fig. 7.

Their analytical expression is (ξ ∈ {1, e 2 i π/3 , e -2 i π/3 }) where

λ = 1 3 p (2 -p) + 1 3   ξ A + i √ 27 √ B 2 1/3 + ξ * A -i √ 27 √ B 2 1/3   , (41)
A = -p 2 9 -43 p + 60 p 2 -39 p 3 + 11 p 4 , (42)
B = (1 -p) 2 p 3 4 + 9 p + 16 p 2 -88 p 3 + 98 p 4 -32 p 5 -8 p 6 + 5 p 7 ; [START_REF] Kuo | Determining terminal pair reliability based on edge expansion diagrams using OBDD[END_REF] note that B is always positive for 0 < p < 1.

The generating function for the Brecht-Colbourn ladder with perfect nodes is simply

G (ρ=1) BC (z) = 1 -p (1 -p) z + p 3 (1 -p) z 2 1 -p (2 -p) z -p (1 -p) 2 (1 + p) z 2 + p 2 (1 -p) 2 z 3 . ( 44
)
From its partial fraction decomposition, which is necessarily of the form

G (ρ=1) BC (z) = 3 i=1 α i 1 -λ i z
because the eigenvalues are distinct, we deduce after simplification

Rel 2 (S 0 → S n ) = 3 i=1 p (1 -p) 2 -(1 -p) λ i -λ 2 i 3 p (1 -p) 2 -2(1 -p) 2 (1 + p) λ i -(2 -p) λ 2 i α i λ n i .( 45
)
From eq. (45), it is clear that the large n limit of Rel 2 (S 0 → S n ) is a power-law behavior, in which the eigenvalue of maximum modulus quickly prevails over the others when p is close to unity, even for moderate values of n. We can also write Rel

2 (S 0 → S n ) = 2 n-1 i=0 F i p 2 n-1-i (1 -p) i , a well-known
expansion of reliability polynomials [START_REF] Colbourn | The combinatorics of network reliability[END_REF]. The F i 's for the 25-node ladder are given in Table 1 (the maximum value was equal to 8078 in the 10-node ladder [START_REF] Brecht | Lower bounds for two-terminal network reliability[END_REF]). Let us call m = n + 1 the number of nodes. Using linear regressions on the first values of Rel 2 (S 0 → S n ), it is straightforward to find Rel

(m odd) 2 (p) = p m-1 2
(1 -p)

3 m-5 2 + m 2 -12 m -21 8 p m+1 2
(1 -p)

3 m-7 2 + m 4 + 72 m 3 + 350 m 2 -2376 m + 2337 384 p m+3 2 (1 -p) 3 m-9 2 + • • • (46)
Rel

(m even) 2 (p) = m 2 p m 2 (1 -p) 3 m-6 2
+ (m -2) (m 2 + 38 m + 24) 48 p m+2 2 (1 -p) 3 m-8 2
+ (m -2) (m 4 + 122 m 3 + 2304 m 2 -5472 m -13440) 3840 p m+4 2 (1 -p) 3 m-10 2
+ • • • (47)
Finally, the comparison of the exact results with the various lower bounds proposed in [START_REF] Brecht | Improving reliability bounds in computer networks[END_REF] is given in Table 2 and Fig. 8. It shows that the lower bound of Brecht and Colbourn is rather good for p close to unity, but its sharpness decreases for p < 0.8.

Imperfect nodes and perfect edges

The configuration of imperfect nodes and perfect edges, although less studied than the previous one, has nonetheless been considered in several papers [START_REF] Aboelfotoh | Computing 2-terminal reliability for radio-broadcast networks[END_REF][START_REF] Boesch | On residual connectedness network reliability[END_REF][START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF]. The Brecht-Colbourn ladder case has been studied in detail by Graver and Sobel [START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF]. The relevant transfer matrix is now equal to Its characteristic polynomial is x 2 (x 2 -ρ x -ρ (1 -ρ)), which simply leads to the eigenvalues 0 -which plays no role in the final expression of the twoterminal reliability -and

M(p = 1, ρ) =           0 0 ρ 0 ρ ρ 0 ρ 1 ρ ρ ρ -ρ -ρ -ρ -ρ           . (48)
λ ± = 1 2 ρ ± 4 ρ -3 ρ 2 .
The generating function is found to be

G (p=1) BC (z) = ρ 1 -ρ z -ρ (1 -ρ) z 2 = ρ λ + -λ - λ + 1 -λ + z - λ - 1 -λ -z , (49)
which gives

Rel 2 (S 0 → S n ) = ρ √ 4 ρ -3 ρ 2 λ n+1 + -λ n+1 - . (50)
This is almost Graver and Sobel's result [START_REF] Graver | You may rely on the reliability polynomial for much more than you might think[END_REF], obtained through a combinatorial argument. Their final expression differs from ours because their source and destination (in our notation, S 0 and S n ) are perfect.

Generalized fan

When the reliabilities are p et ρ, the transfer matrix of eq. ( 23) is equal to

M (p, ρ) =           p ρ 0 0 0 0 p ρ p ρ p 2 ρ p 2 ρ p 2 ρ 1 p 2 ρ -p 2 ρ -p 2 ρ -p ρ p (1 -2 p) ρ           (51)
and

Rel 2 (S 0 → S n ) = 1 p (1 ρ 0 0) • M (p, ρ) n+1 •           1 0 0 0           , (52)
the 1/p prefactor being a consequence of the condition a 0 ≡ 1 in M 0 . The characteristic polynomial of this matrix factorizes nicely:

P (fan) carac (p, ρ; x) = (x -1) (x -p ρ) x -p (1 -p) ρ 2 , (53)
so that the eigenvalues are 1, p ρ and p (1 -p) ρ, the latter being of degree 2. The presence of 1 among the roots should not be surprising. Indeed, even when n goes to infinity, the two-terminal reliability between S 0 and S n is larger than p ρ 2 , in stark contrast to the Brecht-Colbourn case, where the reliability vanishes. Since a power-law behavior is still expected, the only possibility is that the largest eigenvalue is of modulus 1.

The generating function G (fan) (z) is derived using the recipe described in the Brecht-Colbourn case. The additional convention Rel 2 (S 0 → S 0 ) = ρ leads to

G (fan) (z) = N (fan) (z) D (fan) (z) , (54)
N (fan) (z) = 1 -z [1 + p ρ (1 -p) (2 -p ρ)] + p ρ z 2 [(2 + pρ) (1 -p) +p 2 ρ (p -ρ)] -p 2 (1 -p) 2 ρ 2 z 3 , (55)
D (fan) (z) = (1 -z) (1 -p ρ z) (1 -p (1 -p) ρ z) 2 . ( 56
)
Because all the roots have simple expressions, we expect to find a simple, analytical expression for Rel (fan) 2

(S 0 → S n ). The partial fraction decomposition of eq. ( 54) gives indeed

G (fan) (z) = ρ 2 (1 -p) (1 -p (1 -p) ρ) 2 1 -2 p (1 -p) ρ + p 2 ρ 2 (1 -3 p + p 2 ) 1 -p (1 -p) ρ z +p ρ 2 1 -p ρ (2 -p) 1 -p (1 -p) ρ 1 (1 -p (1 -p) ρ z) 2 + p 2 ρ 3 (1 -p (1 -p) ρ) 2 1 1 -z + ρ (1 -ρ) 1 1 -p ρ z . ( 57
)
The new feature of eq. ( 57) is the (

1 -p (1 -p) ρ z) -2 term. Because 1 (1 -λ z) 2 = ∞ n=0 (n + 1) λ n z n , (58)
the final expression of the two-terminal reliability is

Rel (fan) 2 (S 0 → S n ) = +p n (1 -p) n ρ n+2 n p 1 -p ρ (2 -p) 1 -p (1 -p) ρ + 1 -p ρ (2 -p) + p 2 (1 -p) 2 ρ 2 (1 -p (1 -p) ρ) 2 +p n ρ n+1 (1 -ρ) + p 2 ρ 3 (1 -p (1 -p) ρ) 2 , (59)
where n appears in a prefactor, not only as an exponent. The second term of eq. ( 59) is the asymptotic limit when n → ∞. We see that the reliability of the path S 0 → T → S n is enhanced by 1/(1 -p (1 -p) ρ) 2 . When nodes are perfect, ρ must be set to one in eq. ( 59), and the contribution of the eigenvalue p ρ vanishes (the transfer matrix of eq. ( 27) is 3 × 3). This leads to Rel (fan;ρ=1) 2

(S 0 → S n ) = p n (1 -p) n+2 n p 1 -p (1 -p) + (1 + p 2 ) (1 -p (1 -p)) 2 + p 2 (1 -p (1 -p)) 2 . ( 60
)

Zeros of the two-terminal reliability polynomials

The structure of the different reliability polynomials may be understood by studying the locations of their zeros in the complex plane. Such a study has been fruitfully performed in the case of the chromatic polynomial [START_REF] Biggs | Approximations for chromatic polynomials[END_REF][START_REF] Biggs | Matrix method for chromatic polynomials[END_REF][START_REF] Salas | Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I. General theory and square-lattice chromatic polynomial[END_REF], most notably in the context of the four-color theorem. In reliability studies, some effort has been done to discover general properties for the all-terminal reliability Rel A (p) [START_REF] Chari | Reliability polynomials : a survey[END_REF][START_REF] Colbourn | Some open problems on reliability polynomials[END_REF][START_REF] Oxley | Chromatic, flow and reliability polynomials: the complexity of their coefficients[END_REF], its main byproduct being the Brown-Colbourn conjecture [START_REF] Brown | Roots of the reliability polynomial[END_REF], according to which all the zeros are to be found in the region |1 -p| < 1. Although valid for series-parallel graphs, this remarkable conjecture does not strictly hold in the general case (but not by far) [START_REF] Royle | The Brown-Colbourn conjecture on zeros of reliability polynomials is false[END_REF]. As mentioned in the introduction, the all-reliability polynomial is linked to the Tutte polynomial, an invariant of the graph. It has also been studied extensively by Chang and Shrock for various recursive families of graphs [START_REF] Chang | Reliability polynomials and their asymptotic limits for families of graphs[END_REF], who give the limiting curves where all zeros of the polynomials converge.

In this section, after briefly recalling general results of the literature, we study the roots of Rel 2 (p, ρ) = 0 in the complex plane for a fixed ρ, in order to see whether some insight may also be gained in this case. Admittedly, this polynomial depends on the couple (source, terminal), but structures are still expected. We show that the zeros tend to aggregate along portions of algebraic curves, which can substantially differ even for the two families of graphs under consideration, even though they have the same all-terminal reliability. Moreover, structural transitions occur at ρ = 1 2 .

Calculation of the limiting curves (generalities)

As n grows, the number of zeros of the reliability polynomial in the complex plane increases. Because of the matrix transfer property, we have recursion relations between relability polynomials corresponding to successive values of n. The general treatment of the problem has been done by Beraha, Kahane, and Weiss [START_REF] Beraha | Limits of zeros of recursively defined families of polynomials[END_REF], but may be understood in the following, simplifying way: if the reliability polynomial is of the form i α i λ i (p) n (where λ i are the eigenvalues of the transfer matrix), then at large n, only the two eigenvalues of greater modules, say λ 1 and λ 2 , will prevail, so that the reliability polynomial will vanish when |λ 1 (p)| = |λ 2 (p)| (of course, it might be three or more eigenvalues of equal modulus; the present oversimplification works quite well here). This defines a set of curves in the complex plane, where all zeros should accumulate in the n → ∞ limit. The interested reader should refer to the work of Salas and Sokal [START_REF] Salas | Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I. General theory and square-lattice chromatic polynomial[END_REF] for a very detailed discussion of the convergence to the limiting curves. This behavior is not modified when one or more of the α i 's is a polynomial in n [8], as will become apparent for the generalized fan.

Calculation for the Brecht-Colbourn ladder

The recursion relation obeyed by Rel

(BC) 2 (S 0 → S n ) ≡ Rel (n)
2 is easily deduced from eq. ( 31); it reads

Rel (n) 2 (p) = p (2 -p) ρ Rel (n-1) 2 + p ρ (1 -p ρ -p 2 ρ + p 3 ρ) Rel (n-2) 2 -p 2 (1 -p) ρ 2 (1 -ρ) Rel (n-3) 2 + p 4 (1 -p) ρ 3 (1 -ρ) Rel (n-4) 2 . (61)
and leads to very quick calculations using mathematical softwares such as Mathematica [45]. Note that this recursion relation of order four becomes of order three when ρ = 1. We can then look for solutions of Rel (n) 2 (p) = 0 in the complex plane. Of course, the degree of the polynomial, as well as the magnitude of its coefficients, will increase with n.

Perfect nodes

Let us begin by setting ρ = 1. A first step is to display the roots of Rel (n) 2 (p) = 0. These zeros have been calculated using the NSolve[] routine of Mathematica; because the polynomial coefficients can be very large, a numerical accuracy of several hundred digits is sometimes necessary. Figure 9 shows the location of the zeros of Rel (p) in the complex plane (it corresponds to a graph with 151 nodes and 299 edges).

On the right half of the complex plane, we have a simple, open curve crossing the real axis at D and extremities at C and C * . On the left half, however, we have what looks like a closed curve -intersecting the negative real axis in A and B -as well as some dots on the negative real axis, between A and the origin.

As mentioned above, it is well known that as n increases, the zeros accumulate at particular locations, constituted by segments/portions of algebraic curves. For n = 150, these limits are almost reached, even though the "sampling" is not uniform. We can calculate the limiting curves by considering that the roots of the characteristic polynomial are λ e i θ/2 , λ e -i θ/2 and µ. The coefficients of the characteristic polynomial imply constraints between λ (which may be complex), µ and θ, or more precisely, t = cos θ 2 or T = cos θ, which will be used in the following. For instance, µ = (2 -p) p -2 λ cos θ 2 . After eliminating λ and µ, we obtain a compatibility condition which must be satisfied by p, and T (the polynomial P 3 (p, ρ, T ) is given in eq. (A.3)):

P 3 (p, ρ = 1, T ) = 2 + 9 p -4 p 2 -30 p 3 + 38 p 4 -10 p 5 -6p 6 + 3 p 7 + 2 + 12 p -8 p 2 -34 p 3 + 48 p 4 -18 p 5 -2 p 6 + 2 p 7 T -4 p (1 -p) 2 1 -p + p 2 T 2 -8 p (1 -p) 2 T 3 = 0. ( 62
)
The additional requirement |µ| < |λ| translates into an additional contraint between p and T .

A plot of this parametric set of curves shows indeed that the whole portion of the negative real axis between A and the origin is indeed a solution, so that we could expect more zeros there when n > 150.

A few critical points can also be deduced from eq. ( 62). For instance, D corresponds to a real solution of P 3 (p, ρ = 1, T = -1) = 0, namely p D = 1+ √ 5

2 . C and C * are points of the complex plane defined by p C and its complex conjugate, which are roots of P 3 (p, ρ = 1, T = +1) = 0, that is 4 + 9 p + 16 p 2 -88 p 3 + 98 p 4 -32 p 5 -8 p 6 + 5 p 7 = 0.

(

) 63
This polynomial already appeared in the expression of B. Note that there are more than one pair of complex solutions to this equation, the relevant one is given by p C ≈ 1.011578 + i 0.607394. The determination of the complex numbers p A and p B associated with A and B is a little more elaborate. Both p A and p B are real and negative; they correspond to roots of degree two of eq. ( 62). In order to find them, we must have P 3 (p, ρ = 1, T ) = 0 and ∂P 3 (p, ρ = 1, T ) ∂p = 0. These two relations are satisfied for special values of p (or T ). After substitution and elimination of T using Mathematica, we obtain a product of polynomials, which must cancel for p = p A and p = p B . For the sake of completeness, we provide the needed polynomials in appendix A. A close numerical study allows to identify the relevant polynomials:

• p A ≈ -0.2879878 is solution of P 1 (p, ρ = 1) = 0 (see eq. (A.1)), that is

0 = 1 -p -11 p 2 + 15 p 3 -3 p 4 -2 p 5 -p 6 + p 7 , (64)

Imperfect nodes

We can perform the study for ρ < 1 by following the same lines as above.

Although more cumbersome because there are now four possible roots instead of three, the calculations are interesting nonetheless because we may vary one parameter, ρ. A natural question is: can it affect the global structure of the zeros ? The answer is yes, and the location of the zeros undergoes a kind of "structural transition" for a particular value of ρ, namely 1 2 .

Let us first consider ρ > 1 2 . The location of the zeros is then qualitatively similar to that described in Fig. 9, the whole structure merely expanding from the origin. After comparison with the numerical values for n = 150, D appears to be associated with p D = 1 2 (1 + 1 + 4 ρ ), the relevant solution of P 3 (p, ρ, T = -1) = 0. Likewise, C and C * are given by p C , which is one complex solution of P 3 (p, ρ, T = +1) = 0 (P 3 is given in eq. (A.3)).

The determination of p A and p B is more tedious, because P 3 (p, ρ, T ) is now a polynomial of degree 6 in T . Here again, we must find the common zeros of P 3 (p, ρ, T ) and its derivative with respect to p. The elimination of T , performed using Mathematica, leads to a polynomial in p and ρ, which must vanish. Actually, this polynomial can be factored, and a numerical comparison with the zeros obtained for n = 150 shows that p A is solution of P 1 (p, ρ) = 0 (see eq. (A.1)). Similarly, p B is a solution of P 2 (p, ρ) = 0, where P 2 is given in eq. (A.2). For ρ = 1 2 , p A ≈ -0.4359355, p B ≈ -0.2885759, p C ≈ 0.748541 + i 1.03759, and p D = 2. Note that p A and p B are zeros of polynomials in p of degrees equal to 22 and 30, respectively (having ρ = 1 does not simplify the problem).

For ρ < 1 2 , the above expressions for p A , p B , and p C are still valid, even though C and C * may now belong to the left half-plane. However, on the right halfplane, the structure of zeros undergoes a drastic transformation, as shown in Fig. 10 for ρ = 10 -2 . D is now an angular point, and zeros may be found on the real axis between D and E. After numerical comparisons between structures of zeros and limiting curves have been performed, it appears that p D is now a real root of P 1 (p, ρ) = 0 (actually, the third one, in decreasing order), while p E is another real root of P 3 (p, ρ, T = +1) = 0.

Asymptotic limits when ρ → 0

In this section, we address the asymptotic dependence as ρ decreases to zero of all the critical points A, B, C, D, and E. A first step consists in finding the corresponding p's for (very) small values of ρ. It is not too difficult to observe that these numerical values have a ρ -1/3 dependence. We can then use improve on this knowledge by using the algebraic equations of which they are solutions, making again use of Mathematica for the asymptotic expansions. A comparison with the numerical results determines the true leading term of the expansion; after some work, we obtain

p A (ρ) = - 3 - √ 5 2 ρ 1/3 + 35 + 12 √ 5 90 + O(ρ 1/3 ), (68)
p B (ρ) = - χ ρ 1/3 + α + O(ρ 1/3 ), (69)
where

χ = 1 15    2531 + 15 √ 31593 2 1/3 - -2531 + 15 √ 31593 2 1/3 -8    (70)
is the real root of 5 χ 3 + 8 χ 2 + 8 χ -1 = 0. Numerically, χ ≈ 0.11166155366 and κ = χ 1/3 ≈ 0.48154242495. The next-order calculation provides

p B (ρ) = - κ ρ 1/3 + 1 50 70147451 κ 2 + 22890531 κ -3689542 1685743 κ 2 + 778683 κ -121256 α +O(ρ 1/3 ) (71) ≈ - 0.48154242495 ρ 1/3 + 0.38969988720 + O(ρ 1/3 ). ( 72
)
Proceeding in a similar way for the critical points defining the rightmost structure in the complex plane, we find

p D (ρ) = 3 - √ 5 2 ρ 1/3 + 19 + 4 √ 5 30 + O(ρ 1/3 ) (73)
p E (ρ) = 3 - √ 5 2 ρ 1/3 + 2 15 3 + √ 5 2 5/6 -75 + 35 √ 5 1 ρ 1/6 + 11 + 4 √ 5 30 + O(ρ 1/6 ) (74)
p C (ρ) = e 2 i π/3 3 - √ 5 2 ρ 1/3 + 2 15 3 + √ 5 2 5/6 -75 + 35 √ 5 e i π/3 ρ 1/6 + 11 + 4 √ 5 30 + O(ρ 1/6 ) (75)
Note that the expansion p C (ρ) is nothing but p E (ρ), with the transformation ρ -→ e -2 i π ρ. It corresponds to the second complex root, by decreasing order of the real part.

Calculation for the fan

We expect here much easier calculations, since all the eigenvalues are extremely simple: 1, p ρ, and p (1 -p) ρ. They are, indeed, since the limiting curves can be expressed analytically (see Table 3). It is worth noting that nonetheless, other structure transitions occur at ρ = 1 and ρ = 1 2 . Using the relevant recursion relation between successive reliability polynomials, we can again calculate Rel (fan) 2 (S 0 → S n )(p) rapidly using Mathematica. For ρ = 1, we see on Figure 11 that the limiting curve is now essentially a closed one, even though the zeros appear to belong to two different sets which slowly join as n increases. The presence of n in a prefactor as in eqs. ( 59) and [START_REF] Shooman | Probabilistic reliability: an engineering approach[END_REF] does not affect the general definition of the limiting curves [START_REF] Beraha | Limits of zeros of recursively defined families of polynomials[END_REF]. The limiting curve is very easy to obtain, since we have only two eigenvalues, 1 and p (1 -p). For them to have the same modulus implies p (1 -p) = -e i θ , so that we get p = 1 2 1 ± √ 1 + 4 e i θ .

When ρ is strictly less than 1, the whole structure is altered, as witnessed by Figure 12 for ρ = 0.9999. Portions of circles centered at the origin and at the point (1, 0) are added. The reason for such additional structures comes from the existence of a new eigenvalue p ρ. They persist down to ρ = 1 2 . For ρ < 1 2 , the only eigenvalues that matter are actually 1 and p (1 -p) ρ, so that the structure looks again very much like Fig. 11.

Their derivation being straightforward, we simply give the analytical expressions of the limiting curves in Table 3. When ρ → 0, the structure expands with a scaling factor of ρ -1/2 , in contrast with the ρ -1/3 obtained for the Brecht-Colbourn ladder. (p, ρ) = 0, as a function of ρ, the node reliability. node reliability parametrization validity range

ρ = 1 p = 1 2 1 ± √ 1 + 4 e i θ -1 ≤ cos θ ≤ 1 1 2 < ρ < 1 p = 1 2 1 -1 + 4 ρ e i θ p = 1 2 1 + 1 + 4 ρ e i θ p = 1 ρ e i θ p = 1 + e i θ -1 ≤ cos θ ≤ 1 -1 ≤ cos θ ≤ 1 2 ρ 1 ρ 2 -3 cos θ ≥ 1 2 ρ cos θ ≥ 1 2 ρ 2 -1 0 < ρ ≤ 1 2 p = 1 2 1 ± 1 + 4 ρ e i θ -1 ≤ cos θ ≤ 1 6 All-terminal reliability
As mentioned in the introduction, the all-terminal reliability Rel A is another useful measure of the network availability, giving the probability that all nodes are connected. In this case however, the node reliabilities are a mere overall factor, so that they may be considered equal to 1 for all practical purposes [START_REF] Colbourn | The combinatorics of network reliability[END_REF]. Chang and Shrock [START_REF] Chang | Reliability polynomials and their asymptotic limits for families of graphs[END_REF] gave the explicit expressions of Rel A for various recursive families of graphs, among which the Brecht-Colbourn ladder, with the same reliability p for all edges. The all-terminal reliability of the generalized fan has been calculated by Neufeld and Colbourn [START_REF] Neufeld | The most reliable series-parallel networks[END_REF]. The results are of course identical, because at each step, two edges are added, while the common original graph is the triangle (the complete graph K 3 ). For the sake of completeness, we slightly generalize their result for edges with distinct reliabilities.

Here again, the final, analytical expression can be written in a concise form using transfer matrices. In the context of graph theory, this can be viewed as the factorization of a particular value of the multi-variate Tutte polynomial, considered by Wu [START_REF] Wu | Graph theory in statistical physics[END_REF] and Sokal [START_REF] Sokal | The multivariate Tutte polynomial (alias Potts model) for graphs and matroids[END_REF]. We expect the all-terminal reliability R n = Rel A (S 0 ↔ S n ) for the Brecht-Colbourn ladder to exhibit the same behavior as the two-terminal reliability, with a transfer matrix depending on a n and b n , and a generating function that is a rational fraction of p (the common reliability of links) and z. As mentioned above, this calculation should be somewhat easier because all nodes can be considered perfect without loss of generality [START_REF] Colbourn | The combinatorics of network reliability[END_REF]. We can then use the usual pivotal decomposition to establish a relationship between R n and R n-1 , as represented in Fig. 13. We find

R n = (1 -b n ) a n R n-1 + b n R n-1 (b n-1 → b n-1 // a n ) (76)
Using the ansatz

R n = α n (a n + b n ) + γ n a n b n , we get    α n γ n    =    a n-1 + b n-1 a n-1 b n-1 1 -a n-1 -2 b n-1 a n-1 (1 -2 b n-1 )       α n-1 γ n-1    (77)
with a 1 = γ 1 = 0 and α 1 = 1. Calling M n-1 the transfer matrix of eq. ( 77), we obtain

R n = (1, 0) • M n • M n-1 • • • M 1 •    1 0    (78)
When all reliabilities are equal to p, the transfer matrix is simply

M ′ =    2 p p 2 1 -3 p p (1 -2 p)    (79)
The eigenvalues of

M ′ are ζ ± = p 2 3 -2 p ± 5 -8 p + 4 p 2 , so that the generating function is G R (z) = p z 2 1 -p (3 -2 p) z + p 2 (1 -p) z 2 (80)
and

R n = 1 √ 5 -8 p + 4 p 2 ζ n-1 + -ζ n-1 - n ≥ 2 (81)
The last results were obtained in [START_REF] Chang | Reliability polynomials and their asymptotic limits for families of graphs[END_REF], while the same expression can be found in the paper by Neufeld and Colbourn [START_REF] Neufeld | The most reliable series-parallel networks[END_REF].

Conclusion and Perspectives

We have given the exact solution of the two-and all-terminal reliabilities for the Brecht-Colbourn ladder and the generalized fan for arbitrary size and individual element reliability. While simple, these graphs correspond nonetheless to realistic network architectures, especially in telecommunication networks for IP transport. Node and edge failures are put on an equal footing, and the simple formulae relying on transfer matrices may be directly implemented. We have also given the analytical solution of the two-and all-terminal reliabilities, when reliabilities are p and ρ for edges and nodes, along with their rational generating functions. The locations of the zeros of the two-terminal reliability polynomials differ for the two families of graphs considered in this paper, even though their all-terminal reliability is identical. They possess structures in the Re(p) < 0 region, and exhibit transitions for particular values of ρ.

Even though the delta-star transformation has also been successfully applied to the case of simple ladders [START_REF] Tanguy | Exact solutions for the two-and all-terminal reliabilities of a simple ladder network[END_REF], it may not be so easy to use in more complicated networks. However, it seems quite clear that a similar decomposition through transfer matrices of two-terminal reliabilities should occur for ladders of greater width too. In order to make such calculations useful for applications, imperfect nodes as well as imperfect edges must be considered. All is needed is a recursion relation between successive graphs, when one "elementary brick" is added. This implies a new expression for the deletion-contraction theorem, in which the linearity with respect to all individual edge or node reliabilities must be preserved, whereas -to our knowledge -edge reliabilities are often renormalized to account for the unreliability of the nodes they connect [START_REF] Aggarwal | A simple method for reliability evaluation of a communication system[END_REF][START_REF] Theologou | Factoring & reductions for networks with imperfect vertices[END_REF][START_REF] Torrieri | Calculation of node-pair reliability in large networks with unreliable nodes[END_REF]. This new expression will be given elsewhere, along with an application to other recursive families of graphs such as the K 4 ladder and the K 3 cylinder [START_REF] Tanguy | Transfer matrix method for two-and all-terminal reliabilities in ladder networks[END_REF].

What should we expect ? Basically, the same kind of behavior as detailed in the present work, with a factorization of the reliability in terms of transfer matrices, the dimension of which substantially increase to reflect the interplay of different edges/nodes in the overall reliability, and the underlying algebraic structure of the graph (one cannot escape the intrinsic complexity of the problem...).

There are obviously many directions in which this work may be further extended, for instance in the estimates of bounds. The first one is to use the present results, or their future extensions [START_REF] Tanguy | Transfer matrix method for two-and all-terminal reliabilities in ladder networks[END_REF][START_REF] Tanguy | [END_REF], as possible upper or lower bounds to more complex graphs. If a graph under consideration looks likeor made as such -a special instance of a recursive family of graphs, we expect the generating function to be a rational fraction again. The dimension of the corresponding transfer matrix may be probed by trying to find recursion relations between successive reliability polynomials. Of course, if the dimension of the corresponding transfer matrix is large -which is most likely to happen -the degree of the numerator and denominator of the fraction may be too large for a complete solution to be obtained easily. Even so, the knowledge that the true generating function is rational may be an indication that an approximate generating function might still be quite useful, because Padé approximants [START_REF] Baker | Padé approximants[END_REF][START_REF] Press | Numerical recipes in C : the art of scientific computing[END_REF] are known for their devilish knack of getting very close to the exact function. This will be addressed elsewhere [START_REF] Tanguy | [END_REF]. Our calculations may also provide some information on some combinatorial issues, such as the enumeration of self-avoiding walks on lattices of restricted width.

Other quantities of interest may be deduced from the general expression of the network reliability, among them the sensitivity of a equipment [START_REF] Tanguy | Exact solutions for the two-and all-terminal reliabilities of a simple ladder network[END_REF], the influence of scheduled maintenance on the overall network availability, and the failure frequency [START_REF] Hayashi | System failure-frequency analysis using a differential operator[END_REF][START_REF] Singh | System reliability modelling and evaluation[END_REF], which can all be deduced from various partial derivatives of the two-and all-terminal reliabilities [START_REF] Tanguy | Dispersive effects in network reliability[END_REF]. Since the reliability of each equipment appears in only one transfer matrix, the computation of all these network parameters is straightforward. One should also be aware that the reliability of each equipment is not known with absolute accuracy. The consequence of this uncertainty on the overall reliability has been addressed by Coit and collaborators in the case of series-parallel reducible networks [START_REF] Coit | System-reliability confidence-intervals for complex-systems with estimated component-reliability[END_REF][START_REF] Coit | System optimization with component reliability estimation uncertainty : a multi-criteria approach[END_REF]. Our transfer matrix factorization makes this topic another instance of a product of random matrices, definitely a vast field in mathematical physics [START_REF] Crisanti | Products of random matrices in statistical physics[END_REF].

Finally, the exact results found for classes of arbitrarily large networks may prove useful for testing different algorithms (Monte Carlo, genetic, OBDD, etc) in numerically exacting configurations, where edge and node unreliabilities must both be taken into account.

A Polynomials used in the determination of critical points for the zeros of Rel 2 (p) (Brecht-Colbourn ladder)

A.1 P 1 (p, ρ) There is no such factorization in the case T = 1:

P 1 (p, ρ) = ρ -p 1 + 9 ρ + 3 ρ 2 + p 2 ρ

Fig. 1 .

 1 Fig. 1. The Brecht-Colbourn ladder.

Fig. 2 .

 2 Fig. 2. The generalized fan.

Fig. 3 .

 3 Fig. 3. Triangle-star transformation for unreliable nodes. A, B, and C are the node reliabilities, with a, b, and c the edge reliabilities of the initial network, and p A , p B , p C , and O, those of the transformed network.

Fig. 5 .

 5 Fig. 5. Triangle-star transformation for the generalized fan.

  , ρ), for arbitrary n.

Fig. 7 .

 7 Fig. 7. Variation with p of the three eigenvalues for the Brecht-Colbourn ladder with perfect nodes (see eq. (41)).

Fig. 8 .

 8 Fig. 8. Comparison of the exact value () with lower bounds given in ref.[START_REF] Brecht | Improving reliability bounds in computer networks[END_REF] for the 25-node ladder:( ) Kruskal-Katona ( ) Min Cost ( ) Brecht-Colbourn.

Fig. 9 .

 9 Fig. 9. Localization of the complex roots p of the two-terminal reliability polynomial for a Brecht-Colbourn ladder of 151 perfect nodes and 299 edges.

  attained for T ≈ 0.138176, a root of 0 = -1 + 11 T -27 T 2 -26 T 3 + 140 T 4 + 240 T 5 + 144 T 6 + 32 T 7 .(65) • p B ≈ -0.1849482 is solution of P 2 (p, ρ = 1) = 0 (see eq. (A.2)), i.e., 0 = 1 -4 p -9 p 2 + 101 p 3 -413 p 4 + 1019 p 5 -1761 p 6 +2151 p 7 -1864 p 8 + 1097 p 9 -386 p 10 + 60 p 11 , (66) attained for T ≈ -0.9511957, one of the solutions of 0 = 3040707 + 12576464 T + 15322821 T 2 -4376828 T 3 -22559186 T 4 -10112842 T 5 + 9510320 T 6 + 7762048 T 7 -1337920 T 8 -2068608 T 9 + 8192 T 10 + 204800 T 11 (67)

Fig. 10 .

 10 Fig. 10. Localization of the complex roots p of the two-terminal reliability polynomial for a Brecht-Colbourn ladder of 151 nodes and 299 edges, when ρ = 10 -2 .

Fig. 11 .

 11 Fig. 11. Location of the roots of Rel

  = 0 for the fan, with ρ = 1.

Fig. 12 .

 12 Fig. 12. Location of the roots of Rel

  = 0 for the fan, with ρ = 0.9999.

Fig. 13 .

 13 Fig. 13. Deletion-contraction simplification for the all-terminal reliability of the Brecht-Colbourn ladder.

-p 9 ρ 4 -331984 ρ 5 + 16780 ρ 6 +p 10 ρ 4 +375501 ρ 5 + 2506 ρ 6 +p 11 ρ 4 -4185113 ρ 5 + 12850 ρ 6 +p 12 ρ 3 -21210055 ρ 4 + 27622695 ρ 5 - 3 -119321953 ρ 4 - 3 +737559653 ρ 4 + 137144016 ρ 5 -24588235 ρ 6 + 1508228 ρ 7 +p 16 ρ 3 +534128347 ρ 4 -99647028 ρ 5 + 3934654 ρ 6 + 455372 ρ 7 -p 17 ρ 3 +1365985483 ρ 4 - 4 -232309325 ρ 5 - 3 +252124085 ρ 4 - 3 +1464568704 ρ 4 - 7 -p 21 ρ 3 +3038379428 ρ 4 -2084661610 ρ 5 + 338855326 ρ 6 + 82890944 ρ 7 +p 22 ρ 3 -2443698651 ρ 4 + 202709670 ρ 5 + 224730742 ρ 6 -p 23 ρ 3 -1932786432 ρ 4 -295096153 ρ 5 + 454945390 ρ 6 +p 24 ρ 3 -752045795 ρ 4 -1022894704 ρ 5 + 711726527 ρ 6 -p 25 ρ 3 -1614449937 ρ 4 + 878716880 ρ 5 +p 26 ρ 7 3 -1758220080 ρ 4 + 866894232 ρ 5 -p 27 ρ 7 3 -1446294368 ρ 4 + 687560517 ρ 5 +p 28 ρ 8 4 -p 29 ρ 8 4 -p 31 ρ 9 - 3 - 3 p 3 +540 p 34 ( 1 - 2 +p ρ 5 + 12 T 4 +p 2 4 +p 3 - 36 - 4 +p 2 ρ 2 4 T + 8 T 2 - 8 T 3 - 6 +p 3 ρ 3 - 10 - 40 T - 40 T 2 + 8 T 3 + 16 T 4 +p 58 + 5 +p 2 6 +p 3 6 +p 4 6 +p 5 5 +p 6 4 +p 4 ρ 4 - 6 +p - 12 - 4 +p - 22 - 2 T + 28 T 2 + 8 T 3 +p 30 + 46 T + 16 T 2 +p - 6 - 10 T - 4 T 2 +p 5 ρ 5 - 3 - 4 +p 43 + 14 T - 28 T 2 - 8 T 3 +p - 33 - 48 T - 16 T 2 +p 6 + 10 T + 4 T 2 (A. 3 )

 945610456114561234534345671634567173445343472134567223456233456243456253457345734584849333341251242433644828363104040283164585263646556446124222282833046261042534431428283334816261023 -10125 -611502 ρ -1935829 ρ 2 -7279427 ρ 3 + 440373 ρ -455796 -3964687 ρ -23412205 ρ 2 -3663927 ρ 3 -1452867 ρ 204255 + 5324974 ρ + 53128592 ρ 2 + 28420289 ρ 3 + 5054943 ρ -42525 -4776213 ρ -87000246 ρ 2 -104194583 ρ 279589 ρ 6 + 23497 ρ 7 +p 13 ρ 2798298 + 103839446 ρ + 248730949 ρ 2 + 91081790 ρ 214483 ρ 5 + 2402 ρ 6 +p 14 ρ -987660 -90012828 ρ -421343630 ρ 2 -300983008 ρ 3 +354546288 ρ 4 + 19055623 ρ 5 -2902607 ρ 6 + 156356 ρ 7 -p 15 ρ -164025 -55522953 ρ -523811627 ρ 2 -718737692 ρ -23264478 -483102731 ρ -1256125498 ρ 2 + 1050744677 ρ -5993055 -328891636 ρ -1637004249 ρ 2 + 897069980 ρ 226306853 ρ 5 -13885678 ρ 6 + 5675792 ρ 7 +p 18 ρ -729000 -161715291 ρ -1608420692 ρ 2 + 82688597 ρ 3 + 2449767599 ρ 139531559 ρ 6 + 32366472 ρ 7 + 274104 ρ 8 -p 19 ρ -54779328 -1192868328 ρ -1036350248 ρ 2 + 3126514952 ρ 530576442 ρ 5 + 110376920 ρ 6 + 3523400 ρ 7 +p 20 ρ -11563290 -661113157 ρ -1778966082 ρ 2 + 2728489572 ρ 1261931324 ρ 5 + 243789711 ρ 6 + 21533484 ρ -1166400 -267060831 ρ -1769360761 ρ 2 + 1310882671 ρ -74824812 -1221905422 ρ -276377214 ρ 2 + 4066473373 ρ -13126860 -609332834 ρ -1166508009 ρ 2 + 3871377708 ρ -1103625 -218082828 ρ -1184923715 ρ 2 + 2650067734 ρ -53743284 -754572613 ρ + 1226487190 ρ 2 + 416790514 ρ -8258625 -336506619 ρ + 274671788 ρ 2 + 1010093115 ρ -605475 -106456428 ρ -91817943 ρ 2 + 978393477 ρ -23082921 -120749456 ρ + 640575958 ρ 2 -928058750 ρ 3 + 438708098 ρ -3116070 -61389864 ρ + 311935039 ρ 2 -469461042 ρ 3 + 224128938 ρ 4 +p 30 ρ 8 -200475 -19494900 ρ + 116248678 ρ 2 -186770845 ρ 3 + 90668832 ρ 4042170 + 33260499 ρ -57626524 ρ 2 + 28477028 ρ 3 +p 32 ρ 9 -510300 + 7194033 ρ -13394778 ρ 2 + 6717655 ρ 33 ρ 9 -10125 + 376209 ρ -740598 ρ 2 + 374614 ρ ρ) ρ 10 (216 -221 ρ) -6075 p 35 (1ρ) 2 ρ 10 . (A.2) A.3 P 3 (p, ρ, T ) P 3 (p, ρ, T ) = 2 + 2 T + p -6 -10 T -4 T -8 T 3 + p -29 -52 T + 24 T 2 + 64 T 3 + 16 T 78 + 138 T -52 T 2 -176 T 3 -64 T 60 T + 48 T 2 + 120 T 3 + 48 T 16 T 4 + p -8 + 8 T -24 T 2 + 48 T 4 +p 2 56 -22 T + 44 T 2 + 192 T 3 + 128 T 4 + 64 T 5 +p 3 -262 -336 T + 40 T 3 -256 T 4 -288 T 5 -64 T 6 +p 4 248 + 384 T -120 T 2 -384 T 3 + 128 T 4 + 384 T 5 + 128 T 6 +p 5 -66 -110 T + 52 T 2 + 160 T 3 -32 T 4 -160 T 5 -64 T 164 T + 264 T 2 + 24 T 3 -256 T 4 -128 T -206 -378 T -800 T 2 -656 T 3 + 416 T 4 + 640 T 5 + 192 T 448 + 890 T + 1296 T 2 + 1080 T 3 -256 T 4 -864 T 5 -384 T -237 -668 T -1188 T 2 -920 T 3 -32 T 4 + 320 T 5 + 192 T -151 -70 T + 760 T 2 + 904 T 3 + 256 T 4 + 32 T 162 + 230 T -300 T 2 -560 T 3 -192 T 4 +p 7 -36 -60 T + 48 T 2 + 120 T 3 + 48 T 10 -54 T -104 T 2 -56 T 3 + 80 T 4 + 64 T 5 +p 54 + 274 T + 492 T 2 + 400 T 3 -144 T 4 -416 T 5 -192 T 578 T -1244 T 2 -904 T 3 + 48 T 4 + 576 T 5 + 384 T 6 +p -206 + 456 T + 2000 T 2 + 1688 T 3 + 304 T 4 -160 T 5 -192 T 6 +p 156 -356 T -2060 T 2 -2120 T 3 -592 T 4 -64 T 5 +p 92 + 462 T + 1228 T 2 + 1272 T 3 + 400 T 4 +p -88 -270 T -372 T 2 -288 T 3 -96 T 20 T -56 T 2 -64 T 3 -16 T 4 + 64 T 5 + 64 T 6 +p 11 + 160 T + 432 T 2 + 376 T 3 + 80 T 4 -96 T 5 -128 T 6 +p -84 -488 T -1116 T 2 -984 T 3 -240 T 4 + 64 T 6 +p 240 + 850 T + 1416 T 2 + 1224 T 3 + 336 T 4 + 32 T 5 +p -252 -790 T -960 T 2 -712 T 3 -208 T 4 +p 74 + 318 T + 328 T 2 + 168 T 3 + 48 T When T = -1, we can further simplify the above expression P 3 (p, ρ, T = -1) = (1 -p) p ρ 1 + p (1 -p) ρ 2 1 -ρ + ρ (1 -p) 3 2 (A.4)

P 3 ( 4 - 3 -2 p 2 ρ 2 6 - 7 -2 p 4 ρ 4 40 -

 3436740 p, ρ, T = 1) = 20 p + p ρ 9 + 23 p -76 p 2 + 120 p 12 p -231 p 2 + 583 p 3 -384 p 4 + 110 p 5 +p 3 ρ 3 -66 + 126 p -792 p 2 + 2210 p 3 -2533 p 4 + 1731 p 5 -660 p 6 + 120 p 234 p + 865 p 2 -1945 p 3 + 2518 p 4 -1727 p 5 + 557 p 6 -6 p 7 -46 p 8 + 10 p 9 +p 5 ρ 5 -31 + 835 p -2848 p 2 + 4098 p 3 -2922 p 4 + 936 p 5 + 21 p 6 -97 p 7 + 20 p 8 (A.5)

Table 1

 1 Values of the F i 's for the two-terminal reliability polynomial of the 25-node Brecht-Colbourn ladder.

	i	F i	i	F i	i	F i	i	F i
	0	1	9	1125395882 18 762855455898 27 3042073238
	1	47 10	3974128827 19 800820887863 28	635100751
	2	1079 11	12199394435 20 725278875430 29	105465538
	3	16103 12	32708854487 21 562806091836 30	13648753
	4	175418 13	76833130394 22 371300292894 31	1334810
	5	1484837 14 158368734141 23 206539411448 32	93929
	6	10151340 15 286502593795 24	96061397122 33	4368
	7	57524387 16 454444238576 25	37052347922 34	113
	8 275139029 17 630595957484 26	11756780232 35	1

Table 2

 2 Comparison of various lower bounds with the exact two-terminal reliability of a 25-node Brecht-Colbourn ladder[START_REF] Brecht | Improving reliability bounds in computer networks[END_REF].

	p	Kruskal-Katona MinCost(edp) Brecht-Colbourn	exact
	0.75	0.031682	0.054681	0.054681	0.625163
	0.80	0.068803	0.119917	0.430912	0.773696
	0.82	0.092654	0.161200	0.558991	0.824038
	0.84	0.124041	0.214282	0.669269	0.867950
	0.86	0.165305	0.281396	0.761945	0.905042
	0.88	0.219694	0.364529	0.837486	0.935251
	0.90	0.291856	0.464826	0.896659	0.958806
	0.91	0.336579	0.521297	0.920440	0.968231
	0.92	0.388392	0.581555	0.940574	0.976194
	0.93	0.448415	0.644934	0.957259	0.982785
	0.94	0.517724	0.710375	0.970720	0.988109
	0.95	0.597041	0.776313	0.981207	0.992275
	0.96	0.686113	0.840514	0.989003	0.995400
	0.97	0.782518	0.899895	0.994420	0.997608
	0.98	0.879474	0.950274	0.997801	0.999024
	0.99	0.961964	0.986085	0.999524	0.999778

Table 3

 3 Analytical expressions of the limiting aggregation curves for the location of p such that Rel

	(fan),n→∞
	2

  41 + 37 ρ -11 ρ 2 +p 3 ρ -39 -195 ρ + 99 ρ 2 -4 ρ 3 +p 4 ρ 16 + 147 ρ -411 ρ 2 + 43 ρ 3 + 11 ρ 4 -p 5 ρ 2 -54 -2300 ρ + 123 ρ 2 + 67 ρ 3 + 7 ρ 4 -p 6 ρ 2 126 + 4700 ρ + 1865 ρ 2 + 559 ρ 3 -59 ρ 4 + 13 ρ 5 +p 7 ρ 2 41 + 4859 ρ + 2324 ρ 2 + 6400 ρ 3 + 1135 ρ 4 + 189 ρ 5 + 14 ρ 6 +p 8 ρ 3 -2701 + 4149 ρ -11762 ρ 2 -8744 ρ 3 -2515 ρ 4 -311 ρ 5 + 4 ρ 6 -p 9 ρ 3 -781 + 12546 ρ -6054 ρ 2 -14564 ρ 3 -11548 ρ 4 -3012 ρ 5 -124 ρ 6 + 8 ρ 7 -p 10 ρ 3 96 -13197 ρ -3996 ρ 2 + 4727 ρ 3 + 17901 ρ 4 + 11943 ρ 5 + 1464 ρ 6 + 4 ρ 7 +p 11 ρ 4 -7185 -3814 ρ -10626 ρ 2 + 5695 ρ 3 + 21337 ρ 4 + 5871 ρ 5 + 304 ρ 6 + p 2 1375 -1139 ρ + 235 ρ 2 +p 3 -4548 + 6619 ρ -2306 ρ 2 + 380 ρ 3 +p 4 7551 -22762 ρ + 7011 ρ 2 -2415 ρ 3 + 335 ρ 4 +p 5 -6210 + 53479 ρ + 2160 ρ 2 + 7102 ρ 3 -1462 ρ 4 + 154 ρ 5 +p 6 2025 -85209 ρ -79460 ρ 2 -18121 ρ 3 -11141 ρ 4 + 223 ρ 5 + 29 ρ 6 +p 7 ρ + 277027 ρ + 106511 ρ 2 + 202610 ρ 3 -36581 ρ 4 + 1170 ρ 5 +p 8 ρ -46170 -521894 ρ -587852 ρ 2 -1536749 ρ 3 + 263741 ρ 4 -39391 ρ 5 + 547 ρ 6

	P 2 (p, ρ) =
	9 + 2 p (-93 + 37 ρ)

-p 12 ρ 4 -2040 + 3598 ρ -10478 ρ 2 -17573 ρ 3 + 19235 ρ 4 + 11669 ρ 5 + 1219 ρ 6 +p 13 ρ 4 -240 + 6353 ρ + 3091 ρ 2 -30176 ρ 3 + 6625 ρ 4 + 14726 ρ 5 + 2128 ρ 6 -p 14 ρ 5 3613 + 12361 ρ -25852 ρ 2 -5221 ρ 3 + 14188 ρ 4 + 2147 ρ 5 +p 15 ρ 5 947 + 11148 ρ -14935 ρ 2 -8341 ρ 3 + 9720 ρ 4 + 2095 ρ 5 -p 16 ρ 5 96 + 5829 ρ -7507 ρ 2 -1909 ρ 3 + 690 ρ 4 + 3066 ρ 5 +2 p 17 ρ 6 993 -2513 ρ + 3568 ρ 2 -4056 ρ 3 + 2046 ρ 4 -p 18 ρ 6 418 -3991 ρ + 10333 ρ 2 -10532 ρ 3 + 3785 ρ 4 +p 19 ρ 6 41 -2397 ρ + 7184 ρ 2 -7257 ρ 3 + 2430 ρ 4 +3 p 20 (1ρ) ρ 7 299 -684 ρ + 367 ρ 2 -p 21 (1ρ) ρ 7 185 -519 ρ + 322 ρ 2 +p 22 (1ρ) ρ 7 (1 -2 ρ) (16 -15 ρ) -19 p 23 (1ρ) 2 ρ 8 + 8 p 24 (1ρ) 2 ρ 8p 25 (1ρ) 2 ρ 8 (A.1)

A.2 P 2 (p, ρ)

Acknowledgments

I am indebted to Élisabeth Didelet for giving me the opportunity to study reliability issues in depth, and to Joël Le Meur, François Gallant, Veluppillai Chandrakumar, Adam Ouorou, and Éric Gourdin for encouragement and support. Useful information from Prof. J. Graver is gratefully acknowledged. I would also like to thank Annie Druault-Vicard, Christine Leroy, Hervé Coutelle, and Gilles Petitdemange for very useful discussions.