Ralph P. Grimaldi

Mathematics Department

Rose-Hulman Institute of Technology

Terre Haute, Indiana 47803-3999

Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: Many communication networks can be modeled by undirected connected graphs where each vertex represents a communication center and each edge a transmission link between two such centers. In this model of a communication system we assume that each edge (link) functions independently of all other edges. Associated with each edge of the network is its probability of functioning correctly. Under these circumstances we are interested in measuring two properties of the network: its redundancy (the expected number of functioning spanning trees for the network), and its reliability (the probability that the network has at least one spanning tree of operating edges). We investigate these properties using the computer algebra package Maple.

Key Words: computer algebra, redundancy, reliability, spanning trees