close

Вход

Забыли?

вход по аккаунту

?

208

код для вставкиСкачать
Uniformly Optimally Reliable Graphs
D. Gross, J. T. Saccoman
Department of Mathematics and Computer Science, College of Arts and Sciences,
Seton Hall University, South Orange, New Jersey 07079-2696
Received 28 October 1997; accepted 17 December 1997
Abstract: A graph with n nodes and e edges, where the nodes are perfectly reliable and the edges fail
independently with equal probability r, is said to be uniformly optimally reliable (UOR) if it has the greatest
reliability among all graphs with the same number of nodes and edges for all values of r. UOR simple
graphs have been identified in the classes e Å n 0 1, e Å n, e Å n / 1, and e Å n / 2 (Boesch et al.,
Networks 21 (199) 181–194). In this paper, we demonstrate that the UOR simple graphs in these classes
are also UOR when the classes are extended to include multigraphs. q 1998 John Wiley & Sons, Inc.
Networks 31: 217–225, 1998
1. INTRODUCTION AND PRELIMINARIES
Let G Å »V (G), E(G) … denote a graph with node set
V (G) Å { £1 , £2 , . . . , £n } and edge set E(G) Å {x1 , x2 ,
. . . , xe }. We allow there to be more than one edge between a pair of nodes; if this occurs, we refer to each of
them as a multiple edge. A double edge consists of two
multiple edges and a triple edge consists of three multiple
edges. If there is only one edge between a pair of nodes,
it is called a simple edge. The term edge will subsume
both a simple edge and a multiple edge. We use the term
multigraph to refer to a graph that contains at least one
multiple edge but no loops and the term simple graph to
refer to a graph with neither multiple edges nor loops.
Let V(n, e) denote the class of all graphs (simple graphs
or multigraphs) with n nodes and e edges, and Vs (n, e),
the class of all simple graphs with n nodes and e edges.
For other standard graph-theoretic notation and terminology, we refer to Harary [3].
If the graph represents a connected network, we can
discuss a model in which nodes are perfectly reliable and
Correspondence to: D. Gross
edges fail independently with equal probability r, 0 õ r
õ 1. We define the so-called unreliability polynomial,
e
P(G, r ) Å ( iÅ1
mi r i (1 0 r ) e0i , where mi is the number
of edge-disconnecting sets of size i. The reliability of a
graph, therefore, can be defined as R(G, r ) Å 1 0 P(G,
r ). A graph G is said to be uniformly optimally reliable
(UOR) if for each H in its class P(G, r ) ° P(H, r )
[respectively, R(G, r ) ¢ R(H, r )] for all 0 õ r õ 1.
Because P(G, r ) Å 1 whenever G is disconnected, it
suffices to consider only connected graphs.
It is obvious that if a graph minimizes each term mi
among all graphs in its class then it will have the smallest
value of P in its class for all r and, consequently, the
largest value of R. Hence, it is UOR. While all known
examples of UOR graphs would indicate that the converse
is true, a proof of this fact has yet to be found.
In the 1991 paper ‘‘On the Existence of Uniformly
Optimally Reliable Networks,’’ Boesch et al. demonstrated the existence of UOR simple graphs in the classes
Vs (n, n 0 1), Vs (n, n), Vs (n, n / 1), and Vs (n, n / 2)
by finding simple graphs that minimize mi for all i [1].
Wang covered the class Vs (n, n / 3) [5].
Let G 0 x denote the deletion of an edge x from the
graph G, and G/x, the contraction of the edge x, that is,
q 1998 John Wiley & Sons, Inc.
CCC 0028-3045/98/040217-09
217
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
netwa
W: Networks
0815
218
GROSS AND SACCOMAN
the identification of the endnodes of x and the deletion
of all resulting self-loops. The following theorem, which
is credited to Moskowitz [4], applies to many graph invariants. It is stated here in terms of the number of edgedisconnecting sets:
Theorem 1.1. (Factoring Theorem) Suppose that G is a
connected graph and x is a simple edge in G. For all i,
1 ° i ° e, mi (G) Å mi01 (G 0 x) / mi (G/x).
The Factoring Theorem does not apply to factoring on
a multiple edge, since contraction of a multiple edge
would result in a graph having more than one fewer edge
than the original graph. If the class of graphs under consideration was extended to include pseudographs, that is,
both multiple edges and loops are allowed, and the definition of contraction was amended so that only the loop
formed by the actual edge contracted was deleted, then the
Factoring Theorem would hold. Henceforth, any factoring
performed is on simple edges in the graph. In the first
proposition, we show that the placement of a bridge in a
graph has no bearing on mi :
Proposition 1. Let G be a graph with a bridge x, and
G * be the graph obtained by contracting the bridge x and
adding a pendent edge y. Then, mi (G) Å mi (G * ) for all
i, 1 ° i ° e. (See Fig. 1 for an illustration.)
Proof. Factor on the bridge x and the pendent edge y
in the respective graphs G and G *. Since G/x and G * /y
are isomorphic, mi (G/x) Å mi (G * /y) for all i. The deletion graphs G 0 x and G * 0 y are disconnected, so mi01 (G
1
0 x) Å mi01 (G * 0 y) Å ( e0
i01 ) for all i. Thus, mi01 (G
0 x) / mi (G/x) Å mi01 (G * 0 y) / mi (G * /y), i.e.,
mi (G) Å mi (G * ) for all i.
Next, we establish that a graph containing a cycle and
a pendent edge will have mi at least as large as that of a
graph in the same class having a longer cycle and one
fewer pendent edge.
Proposition 2. Let G be a nonacyclic graph with a pendent edge x and let G * be the graph obtained by contracting the pendent edge x and subdividing a cycle edge
Fig. 2. mi (G) ¢ mi (G*); m1 (G) ú m1 (G*).
into two edges. Then, mi (G) ¢ mi (G * ) for all i, 2 ° i °
e, and m1 (G) ú m1 (G * ). (See Fig. 2 for an illustration.)
Proof. Let y be one of the edges formed in the subdivision. We factor on x in G and y in G *. Since G/x and
G * /y are isomorphic, mi (G/x) Å mi (G * /y) for all i.
1
Since G 0 x is disconnected, mi (G 0 x) Å ( e0
i01 ) for all
i. On the other hand, G * 0 y is connected, which implies
that there may be some choices of the remaining edges
1
which do not disconnect. Thus, mi01 (G * 0 y) ° ( e0
i01 )
for all i, and mi (G) Å mi01 (G/x) / mi (G/x) ¢ mi01 (G *
0 y) / mi (G * /y) Å mi (G * ). Since m1 (G) is the number
of bridges, and G * has one fewer bridge than has G,
m1 (G) ú m1 (G * ).
Repeated application of Propositions 1 and 2 imply
that, given any graph G having a bridge, there exists a
bridgeless graph G * in the same class such that P(G *, r )
õ P(G, r ), for all 0 õ r õ 1. The following is an
immediate consequence:
Proposition 3. If there exists a bridgeless graph G in
the class V(n, e) such that P(G, r) ° P(H, r) for all
bridgeless graphs H in the class V(n, e) and for all r,
0 õ r õ 1, then G is UOR.
2. THE CLASSES V(n, n 0 1)
AND V(n, n)
There are no connected multigraphs in the class V(n, n
0 1). Any connected simple graph is a tree, all of which
have mi Å ( n0i 1 ), i ¢ 1. Thus, all connected graphs in
V(n, n 0 1) are UOR.
There are no connected bridgeless multigraphs in the
class V(n, n). The only connected bridgeless simple
graph in this class is Cn , the cycle on n nodes. Thus, Cn
is the unique UOR graph in the class V(n, n).
3. THE CLASS V(n, n / 1)
Fig. 1. mi (G) Å mi (G*).
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
The removal of three or more edges from any graph in
the class V(n, n / 1) always results in a disconnected
netwa
W: Networks
0815
UNIFORMLY OPTIMALLY RELIABLE GRAPHS
219
1
graph; hence, mi Å ( n/
) for any graph in the class and
i
for all i ¢ 3. Thus, the only value that differentiates one
bridgeless graph from another is m2 .
The unique UOR simple graph in the class Vs (n, n
/ 1) is obtained in the following manner [1]:
STEP 1. Start with a triple-edge between two isolated
nodes u and £.
STEP 2. Distribute n 0 2 nodes as equally as possible
among the three edges. (See Fig. 3 for an illustration.)
We refer to each of the three resulting paths joining u
to £ as an edge-path.
The only way to disconnect a UOR simple graph by
the removal of two edges is by deleting two of the edges
along an edge-path. If there are j internal points on one
of these edge-paths, then the number of ways to disconnect in this fashion is ( 2j / 1 ). These edge-paths are subdivided as evenly as possible, so if k Å (n 0 2) mod 3,
then k of the edge-paths have  (n 0 2)/3 internal nodes,
while the other 3 0 k will have  (n 0 2)/3  internal
nodes. These observations are summarized in the following theorem:
Fig. 3. UOR graph in Vs (7, 8).
k Å 2: m2 Å
n04
/1
3
2
/2
n01
/1
3
2
Theorem 3.1. The UOR simple graphs in the class Vs (n,
n / 1) have
m2
n02
3
Å (3 0 k)
/1
/k
n02
3
2
/1
,
2
n(n 0 1)
.
6
By Proposition 3, we only need to compare the UOR
simple graph to the bridgeless multigraphs in this class.
To see that there are only two such multigraphs, namely,
H1 , the cycle on n nodes with one of its edges doubled,
and H2 , the cycle on n 0 1 nodes with a pendent double
edge (see Fig. 4 for an illustration), we need only consider the graphs that result from the deletion of one of
1
1
) õ ( n0
)/1
the multiple edges. Since m2 (H1 ) Å ( n0
2
2
Å m2 (H2 ), H1 is the best multigraph, so it is only necessary to compare it to the UOR simple graph. Indeed, for
k Å 0: m2 (H1 ) 0 m2 (UOR) Å
where k Å (n 0 2) mod 3. Specifically,
Å
(n 0 2) 2
ú 0,
3
when n ú 2;
k Å 0: m2 Å 3
n02
/1
3
Å
2
k Å 1: m2 Å 2
(n / 1)(n 0 2)
.
6
k Å 1, 2: m2 (H1 ) 0 m2 (UOR) Å
(n 0 3)(n 0 1)
ú 0,
3
when n ú 3.
Thus, the graph in Vs (n, n / 1) which is UOR among
all simple graphs remains UOR when we extend the class
to include multigraphs.
n03
/1
3
2
4. THE CLASS V(n, n / 2)
/
n
/1
3
2
8U1F
/ 8U1F$$0815
Å
n(n 0 1)
.
6
05-14-98 08:07:51
The removal of four or more edges from any graph in
the class, V(n, n / 2) always results in a disconnected
graph, so mi Å ( n/i 2 ) for any graph in the class and for
netwa
W: Networks
0815
220
GROSS AND SACCOMAN
m2 Å (6 0 k)
n04
/1
6
/k
n04
/1
6
,
2
2
specifically as follows:
k Å 0: m2 Å 6
n/2
6
n 2 0 2n 0 8
.
12
Å
2
Fig. 4. Multigraphs in V(7, 8).
k Å 1: m2 Å 5
all i ¢ 4. Thus, the only values that differentiate one
bridgeless graph from another are m2 and m3 .
The unique UOR simple graph in the class Vs (n, n
/ 2), n ¢ 4, is obtained in the following manner [1]:
Theorem 4.1. Let k Å (n 0 4) mod 6.
(i) The UOR simple graph in the class Vs (n, n / 2)
has
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
n/7
6
/
2
2
Å
STEP 1. Start with the graph K4 , the complete graph on
4 nodes.
STEP 2. Distribute n 0 4 nodes among the six edges as
follows:
Let k Å (n 0 4) mod 6.
If k Å 0, 1, 5 distribute the n 0 4 nodes among the
six edges of the K4 as evenly as possible;
If k Å 2, i.e., n 0 4 Å 6m / 2, insert m nodes in each
of the six edges of the K4 and the two remaining nodes
in two independent edges (of the original K4 );
If k Å 4, i.e., n 0 4 Å 6m / 4, insert m / 1 nodes in
each of the six edges of the K4 and then remove two nodes
from a pair of independent edges (of the original K4 );
If k Å 3, i.e., n 0 4 Å 6m / 3, insert m nodes in each
of the six edges of the K4 two of the remaining nodes in
two independent edges (of the original K4 ), and the last
node in any one of the remaining four edges (of the
original K4 ). (See Fig. 5 for an illustration.)
We refer to the six paths joining the endnodes of the
original edges of the K4 as edge-paths. The only way to
disconnect a UOR simple graph by the removal of two
edges is to delete two of the edges on an edge-path. On
the other hand, there are three different ways to disconnect
by removing three edges: removing three edges from one
edge-path; removing two from one edge-path and one
from a different edge-path; or removing exactly one edge
from each of the three edge-paths emanating from an
original node of the K4 . The number of ways each can
be done depends on how the n 0 4 nodes are inserted in
the six edges of K4 and is summarized in the following
theorem:
n/1
6
k Å 2: m2 Å 4
n
6
/2
n/6
6
2
k Å 3: m2 Å 3
Å
2
n01
6
/3
2
Å
n02
6
n 2 0 2n
.
12
n/5
6
2
k Å 4: m2 Å 2
n 2 0 2n 0 3
.
12
/4
n 2 0 2n / 1
.
12
n/4
6
2
2
Å
k Å 5: m2 Å
n03
6
2
/5
n 2 0 2n
.
12
n/3
6
2
Å
n 2 0 2n 0 3
.
12
(ii) The UOR simple graph in the class Vs (n, n / 2)
has m3 Å a / b / c, where a is the number of ways
to remove three edges from one edge-path, b is the
number of ways to remove two edges from one edgepath and one edge from a different edge-path, and
c is the number of ways to remove exactly one edge
from each of the three edge-paths emanating from
an original K4 node. The following chart summarizes
this information for m3 :
netwa
W: Networks
0815
UNIFORMLY OPTIMALLY RELIABLE GRAPHS
a
b
6
n/2
6
5
n/1
6
kÅ2
4
n
6
3
3
2
kÅ3
n01
6
3
n/5
6
/3
n01
6
3
kÅ4
n02
6
2
kÅ0
6
n/2
6
5
n/1
6
4
n
6
3
kÅ1
/
3
3
/2
3
3
3
kÅ5
n03
6
/5
2
n/3
6
n03
6
3
2
3
G
5n / 12
/2
6
n02
6
2
3
G
F
2
n/4
6
/4
F
5n 3 / 3n 2 0 30n 0 32
54
k Å 1:
5n 3 / 3n 2 0 18n 0 16
54
3
n/7
6
F
G
F
G
F
G
2
n/6
6
2
n/5
5n / 13
6
/3
6
2
5n / 14
/4
6
5n / 15
/5
6
The values of a / b / c are as follows:
k Å 0:
4
5n / 11
/
6
2
n/6
6
G
c
5n / 10
6
2
n/7
6
F
n/4
6
2
n/3
6
2
5n / 3n 0 18n
54
k Å 3:
5n 3 / 3n 2 0 12n / 4
54
k Å 4:
5n 3 / 3n 2 0 18n 0 16
54
k Å 5:
5n 3 / 3n 2 0 36n
.
54
F
G
2
G
4
5n / 6
6
G
2
F
5n / 8
6
G
4
F
G
2
5n / 9
6
3
n/1
6
2
n/7
n/1
/2
6
6
3
F GF G
F
5n / 7
6
n/2
6
F GF G F G
5n / 5
6
F
F G
n
6
2
n/6
6
F G F G F GF G
n01
6
2
n/5
n01
/2
6
6
n/5
6
2
F GF G
n02
6
n/4
6
2
F G F G F GF G
n03
6
2
n/3
n03
/2
6
6
n/3
6
2
nonnegative integers. If s 0 r Å k ú 0, then f (r, s)
0 f (r / 1, s 0 1) Å k 0 1.
Proposition 6. Let n be a fixed positive integer, and let
r and s be nonnegative integers. Then,
(i) The expression ( r2 ) / ( n0r
2 ) is minimized when r
Å  n/2  .
(ii) The expression ( r2 ) / ( s2 ) / ( n0r20s ) is minimized
when r Å  n/3  and s Å  n/3 .
2
k Å 2:
221
Corollary 4. Let G be the UOR simple graph in Vs (n,
n / 2). Then, m2 (G) ° (n 2 0 2n / 1)/12 and m3 (G)
° (5n 3 / 3n 2 0 12n / 4)/54.
There are four types of constructions that give
bridgeless multigraphs in the class V(n, n / 2). Proposition 6, which follows below, enables us to find the most
reliable multigraph within each type. We first state a
lemma which is used in the proof of the proposition:
Lemma 5. Let f (r, s) Å ( r2 ) / ( s2 ), where r and s are
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
Fig. 5. UOR graphs in Vs (n, n / 2), n Å 10, 11, . . . , 15.
The large nodes are the k additional nodes.
netwa
W: Networks
0815
222
GROSS AND SACCOMAN
Fig. 6. Type1 multigraphs in V(7, 9).
(iii) The expression ( r2 ) / ( n0r
2 ) / r/2 is minimized when
r Å  n/2  .
(i£ ) The expression ( r2 ) / ( s2 ) / ( n0r20s ) / r/2 is minimized when r Å  n/3  and s Å  n/3 .
Proof. Parts (i) and (ii) are well known and the proof
of (iv) is similar to that of (iii), so we only give the
proof of (iii).
(iii) Let s Å n 0 r, and define the function F(r, s)
Å f (r, s) / r/2, where f (r, s) is as defined in Lemma
5. Trivially F(r, s) ° F(s, r), whenever r ° s, so
without loss of generality, we assume that r ° s. Assume
that F(r, s) is minimized and r õ  n/2  . Then, since r
/ s Å n, s ú  n/2 . Thus, s 0 r ¢ 2. Lemma 5 implies
that f (r, s) 0 f (r / 1, s 0 1) ¢ 1. Hence, F(r, s)
0 F(r / 1, s 0 1) Å ( f (r, s) / (r/2)) 0 ( f (r / 1, s
0 1) / (r / 1)/2) ¢ 12, which contradicts the assumption
that F(r, s) is minimized. Therefore, r Å  n/2  .
Next, we describe the four constructions leading to
bridgeless multigraphs in V(n, n / 2). For each construction type, we determine the best multigraph, then find the
best one from among the four, and finally compare the
best multigraph to the UOR simple graph in V(n, n / 2).
A multigraph is of Type1 if it is constructed in the
following manner:
binatorial formulas for m2 and m3 , if in Step 2 of the
construction an original edge was not subdivided, then if
this edge was the one doubled in Step 3, it will be considered an edge-path consisting of two multiple edges which
form a double edge; otherwise, the unsubdivided edge is
considered an edge-path consisting of a single simple
edge. Let r be the number of simple edges on the edgepath containing the double-edge; s, the number of simple
edges on a second edge-path; and n 0 r 0 s, the number
of simple edges on the third edge-path.
The only way to disconnect a Type1 multigraph by the
removal of two edges is to remove two simple edges from
the same edge-path. Thus, m2 Å ( r2 ) / ( s2 ) / ( n0r20s ). By
part (ii) of Proposition 6, we know that m2 is minimized
when r Å  n/3  and s Å  n/3 , i.e., the number of simple
edges on each edge-path is as equal as possible.
There are three ways to disconnect by removing three
edges: remove any three simple edges; remove two simple
edges from the same edge-path and one of the multiple
edges from the double-edge; or remove the double-edge
and a simple edge from the edge-path that contained the
double-edge. Hence, m3 Å ( n3 ) / 2(( r2 ) / ( s2 ) / ( n0r0s
2 ))
/ r. Since the first summand is constant for all graphs
of Type1, applying part (iv) of Proposition 6 yields that
m3 is also minimized when r Å  n/3  and s Å  n/3 .
Thus, the best graph of this type, which we call M1 ,
is constructed as follows: Begin with three edges between
a pair of nodes and distribute n 0 2 nodes as evenly as
possible among the three edges. Next double an edge on
an edge-path that has the most nodes.
The values of m2 and m3 depend on the value of k
Å n mod 3. Specifically,
n
k Å 0: m2 Å 3 3
Å
2
SD
n
m3 Å
3
STEP 1. Start with a three edges between a pair of nodes.
n
3
/6
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
/
2
STEP 2. Insert n 0 2 nodes randomly in the three edges.
STEP 3. Double one of the edges.
Type1 multigraphs include M2 : the n-cycle with one
edge tripled (i.e., insert the nodes into only one edge and
double one of the original edges); M3 : the n-cycle with
two edges doubled (i.e., insert the nodes into only one
edge and double one of the newly-formed edges); M4 :
the chordal n-cycle with a double-edge on the cycle (i.e.,
insert the nodes into two of the original edges and double
one of the newly formed edges); and M5 : the n-cycle
with a double chord (i.e., insert the nodes into two of the
original edges and double the other original edge). (See
Fig. 6 for an illustration.)
We refer to the resulting paths between the original
two nodes as edge-paths. For ease of describing the com-
n 2 0 3n
,
6
n01
3
k Å 1: m2 Å 2
/
n/2
3
2
m3 Å
k Å 2: m2 Å
netwa
SD
n
3
/ 2m2 /
n02
3
SD
n
3
W: Networks
Å
2
2
/ 2m2 /
0815
n 2 0 3n / 2
,
6
n 0 1 n 3 0 n 2 0 2n / 2
Å
;
3
6
n/1
3
/2
2
m3 Å
n n 3 0 n 2 0 2n
Å
;
3
6
Å
n 2 0 3n / 2
,
6
n 0 2 n 3 0 n 2 0 2n
Å
.
3
6
UNIFORMLY OPTIMALLY RELIABLE GRAPHS
223
the three edges. The pendent double edge may be added
anywhere.
It follows immediately from the discussion above that
m2 (M6 ) 0 m2 (M1 ) Å 1, and m3 (M6 ) 0 m3 (M1 ) Å n 0 r
ú 0. Therefore, M1 is the best multigraph among all
multigraphs of Type1 or Type2.
A multigraph is of Type3 if it is constructed in the
following manner:
STEP 1. Start with a path of length 2.
STEP 2. Double each edge.
Fig. 7. Type2 multigraphs in V(7, 9).
STEP 3. Insert n 0 3 nodes randomly in the double edges.
Thus, for any value of n, we obtain (n 2 0 3n)/6
° m2 (M1 ) ° (n 2 0 3n / 2)/6 and (n 3 0 n 2 0 2n)/6
° m3 (M1 ) ° (n 3 0 n 2 0 2n / 2)/6.
A multigraph is of Type2 if it is constructed in the
following manner:
STEP 1. Start with three edges between a pair of nodes.
STEP 2. Insert n 0 3 nodes randomly in the three edges
so that at least two of the edges receive nodes.
STEP 3. Connect a new node to any other node using two
edges, forming a pendent double edge.
If only two of the original three edges are subdivided,
the resultant multigraph, M7 , is a chordal (n 0 1)-cycle
with a pendent double edge. (See Fig. 7 for an illustration.)
We refer to the three paths between the original two
nodes as edge-paths. For ease of describing the combinatorial formulas for m2 and m3 , if in the construction one
of the original three edges is not subdivided, it will be
considered an edge-path consisting of a single simple
edge. Let r be the number of simple edges on the edgepath containing the double edge; s, the number of simple
edges on a second edge-path; and, therefore, n 0 r 0 s,
the number of simple edges on the third edge-path.
There are two ways to disconnect a Type2 multigraph
by the removal of two edges: remove two simple edges
from the same edge-path or remove the pendent double
0s
edge. Thus, m2 Å ( r2 ) / ( s2 ) / ( n0r
) / 1. Again, by part
2
(ii) of Proposition 6, m2 is minimized when r Å  n/3 
and s Å  n/3 , that is, the n 0 3 nodes should be inserted
as evenly as possible along the edge paths.
There are three ways to disconnect by a Type2
multigraph by the removal of three edges: remove any
three simple edges, remove two simple edges from the
same edge-path and one of the multiple edges, or remove
the pendent double edge and any other edge. Hence, m3
0s
Å ( n3 ) / 2(( r2 ) / ( s2 ) / ( n0r
)) / n. Once again, m3 is
2
minimized when r Å  n/3  and s Å  n/3 .
Thus, the best graph of this type, M6 , is constructed
as follows: Start with three edges between a pair of nodes
and distribute n 0 3 nodes as evenly as possible among
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
STEP 4. Double an edge.
If the nodes are inserted in both of the double edges
formed in Step 2, the resulting multigraph, M8 , is a bicycle
(i.e., two cycles with a common node) with one double
edge. If the nodes were inserted in only one of the double
edges formed in Step 2, then if one of the multiple edges
from the other double edge was the one doubled in Step
4, we obtain M9 , an (n 0 1)-cycle with a pendent triple
edge; otherwise, the graph obtained, M10 , is an (n 0 1)cycle with one edge doubled and a pendent double edge.
(See Fig. 8 for an illustration.)
For ease of describing the combinatorial formulas for
m2 and m3 , if the multigraph has a pendent double edge,
we treat it as a cycle consisting of two simple edges, and
if the multigraph has a pendent triple edge, we consider
it to be a cycle of length 2 with one double edge and one
simple edge. Let r be the number of simple edges on the
cycle containing the double edge; then, n 0 r is the number of simple edges on the other cycle.
The only way to disconnect a Type3 multigraph by the
removal of two edges is to remove two simple edges on
one of the cycles. Thus, m2 Å ( r2 ) / ( n0r
2 ). By part (i) of
Proposition 6, m2 is minimized when r Å  n/2  .
There are three ways to disconnect a Type3 multigraph
by removing three edges: remove any three simple edges,
remove two simple edges from the same cycle and a
netwa
Fig. 8. Type3 multigraphs in V(7, 9).
W: Networks
0815
224
GROSS AND SACCOMAN
multiple edge, or remove the double edge and a simple
edge from the cycle containing the double edge. So, m3
Å ( n3 ) / 2(( r2 ) / ( n0r
2 )) / r, which by part (iii) of Proposition 6 is also minimized by r Å  n/2  . Thus, the best
graph of this type, M8 , is obtained as follows: Start with
a path of length two, double each edge, insert the n 0 3
nodes alternately into each double-edge, and double an
edge on the resulting cycle having the most nodes.
The values of m2 and m3 depend on the value of k
Å n mod 2. Specifically,
n
2
k Å 0: m2 Å 2
Å
2
m3 Å
k Å 1: m2 Å
n01
2
2
m3 Å
n 2 0 2n
,
4
SD
n
3
/
SD
n
3
Fig. 9. Type4 multigraphs in V(7, 9).
n
/4 2
/
n n3 0 n
;
Å
2
6
Å
n 2 0 2n / 1
,
4
2
n/1
2
2
/ 2m2 /
n 0 1 n3 0 n
Å
.
2
6
Thus, for any value of n, we obtain m2 (M8 ) ¢ (n 2
0 2n)/4 and m3 (M8 ) Å (n 3 0 n)/6.
Finally, a multigraph is of Type4 if it is constructed in
the following manner:
STEP 1. Start with a tree on four nodes.
STEP 2. Double each edge.
STEP 3. Insert n 0 4 nodes randomly in the double edges,
leaving at least one double edge unchanged.
If the nodes were inserted in two of the double edges,
the resulting multigraph is either a bicycle with a pendent
double edge (M11 , M12 , or M13 ) or two cycles joined
by a double bridge; else, the multigraph consists of an (n
0 2)-cycle with either two pendent double edges (M14
or M15 ) or a pendent doubled path of length two (M16 ).
(See Fig. 9 for an illustration.)
For ease of describing the combinatorial formulas for
m2 and m3 , if the nodes are inserted in only one of the
double edges formed in Step 2, then one of the other
double edges is considered to be a cycle consisting of
two simple edges, while the other is treated as a double
edge (see M14 , M15 , M16 in Fig. 9). Let r be the number
of simple edges on one cycle, and n 0 r, the number of
simple edges on the other cycle.
There are two ways to disconnect a Type4 multigraph
by removing two edges: either remove two simple edges
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
from the same cycle or remove the double edge. Thus,
m2 Å ( r2 ) / ( n0r
2 ) / 1. By part (i) of Proposition 6, m2
is minimized when r Å  n/2  .
There are three ways to disconnect a Type4 multigraph
by removing three edges: remove any three simple edges,
remove two simple edges from the same cycle and a multiple edge, or remove the double edge and any other edge.
Therefore, m3 Å ( 3n ) / 2(( r2 ) / ( n0r
2 )) / n. Again, applying
Proposition 6(i), m3 is minimized when r Å  n/2  .
Thus, the best multigraph of Type4, M11 , is obtained
when the nodes are inserted as evenly as possible into
two of the double edges. It follows immediately from the
discussion above that m2 (M8 ) õ m2 (M11 ), and m3 (M8 )
õ m3 (M11 ), so M8 is the best multigraph among all
multigraphs of Type3 or Type4.
We now compare the values of m2 and m3 for the
multigraphs M1 and M8 . Since m2 (M1 ) ° (n 2 0 3n / 2)/
6 and m2 (M8 ) ¢ (n 2 0 2n)/4, m2 (M8 ) 0 m2 (M1 ) ¢ [(n
0 2)(n / 2)]/12 ú 0 when n ú 2. Since m3 (M1 ) ° (n 3
0 n 2 0 2n / 2)/6 and m3 (M8 ) Å (n 3 0 n)/6, m3 (M8 )
0 m3 (M1 ) ¢ [(n / 2)(n 0 1)]/6 ú 0 when n ú 1.
Hence, M1 is the best multigraph from among all four
types.
Before we compare M1 to the UOR simple graph in
V(n, n / 2), we must demonstrate that the constructions
have included all possible bridgeless multigraphs in the
class. To this end, we consider the graphs formed by
deleting one multiple edge from a bridgeless multigraph
in V(n, n / 2), that is, the graphs in V(n, n / 1) which
have at most one bridge. The bridgeless multigraphs in
V(n, n / 2) are obtained by adding a multiple edge
anywhere if the graph in V(n, n / 1) is bridgeless; otherwise, the bridge must be doubled. We let H denote the
appropriate graph in V(n, n / 1).
If H is a cycle with a double edge, then the addition
of another multiple edge results in either a cycle with two
double edges or a cycle with a triple edge, both of Type1.
If H is a cycle with a pendent double edge, then adding
another multiple edge results in either a cycle with a
netwa
W: Networks
0815
UNIFORMLY OPTIMALLY RELIABLE GRAPHS
pendent triple edge or a cycle with a double edge and a
pendent double edge, both of Type3.
If H is a simple bridgeless graph, then it is either a
chordal n-cycle, a bicycle, or a graph which is three paths,
each of length at least two, between two nodes. If H is a
chordal cycle, doubling any edge yields a graph of Type1.
If H is a bicycle, doubling any edge yields a graph of
Type3. If H consists of three paths between a pair of
nodes, doubling any edge yields a graph of Type1.
If H is a graph formed by adding a pendent edge to a
simple bridgeless, it must be either a chordal n-cycle with
a pendent edge, a bicycle with a pendent edge, or a graph
which is three paths, each of length at least two, between
two nodes, with a pendent edge. Since the graph in V(n,
n / 2) which results from adding the edge to H must be
bridgeless, the pendent edge must be doubled, thereby
resulting in a graph of Type2, Type4, or Type2, respectively.
If H has a bridge between two cycles, then the only
choice is to double the bridge, which gives a graph of
Type4.
If H is a multigraph with a pendent edge, then it is
one of the following: a cycle with a double edge and a
pendent edge, a cycle with a double pendent edge and a
single pendent edge (emanating from either the same or
different nodes), or a cycle with a pendent path of length
two having one of the paths edges doubled. In all these
cases, adding another multiple edge requires doubling the
bridge. This yields, respectively, graphs of Type3, Type4,
Type4, or Type4.
Finally, it remains to compare M1 to the UOR simple
graph. Since m2 (UOR) ° (n 2 0 2n / 1)/12 and m2 (M1 )
ú (n 2 0 3n)/6, m2 (M1 ) 0 m2 (UOR) ú (n 2 0 4n 0 1)/12
ú 0 for n ú 4. Since m3 (UOR) ° (5n 3 / 3n 2 0 12n
/ 4)/54 and m3 (M1 ) ¢ (n 3 0 n 2 0 2n)/6, m3 (M1 )
0 m3 (UOR) ¢ (2n 3 0 6n 2 0 3n 0 2)/27 ú 0 for n ú
3. Thus, the UOR simple graph is better for n ú 4. When
n Å 4, the UOR simple graph is just K4 , which has m2
Å 0 and m3 Å 4, while M1 is the multigraph obtained by
starting with a triple edge, inserting a node in two of the
edges, and then doubling one of the newly formed edges
8U1F
/ 8U1F$$0815
05-14-98 08:07:51
225
Fig. 10. The multigraph M1 for n Å 4.
(see Fig. 10). For this multigraph m2 Å 1 and m3 Å 7,
so the UOR simple graph is better when n Å 4, and,
therefore, it is best over all graphs in V(n, n / 2).
5. CONCLUSION
The work of Boesch et al. [1] gave the constructions for
the UOR simple graphs in sparse classes which have n
0 1, n, n / 1, and n / 2 edges. We have shown that
when the class is enlarged to include multigraphs the
graphs they found are still UOR. The class V(n, n / 3)
was covered by Wang [5]. Consideration of bridgeless
multigraphs in this class involves many more instances.
We conjecture that the UOR graphs Wang found are UOR
even when the class is expanded to include multigraphs.
REFERENCES
[1]
[ 2]
[ 3]
[ 4]
[ 5]
netwa
Boesch, Li, and Suffel, On the existence of uniformly
most reliable networks. Networks 21 (1991) 181–194.
C. Cheng, Maximizing the total number of spanning trees
in a graph: Two related problems in graph theory and
optimization design theory. J. Combin. Theory 31 (1981)
240–248.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA
(1971).
F. Moskowitz, The analysis of redundancy networks.
AIEE Trans. Comm. Electron. 39 (1958) 627–632.
G. Wang, A proof of Boesch’s conjecture. Networks 24
(1994) 277–284.
W: Networks
0815
Документ
Категория
Без категории
Просмотров
3
Размер файла
156 Кб
Теги
208
1/--страниц
Пожаловаться на содержимое документа