A NEW NETWORK RECONFIGURATION TECHNIQUE FOR SERVICE RESTORATION IN DISTRIBUTION NETWORKS
N.D.R. Sarma Student Member
V.C. Prasad K.S. Prakasa Rao Senior Member
V. Sankar Student Member Department of Electrical Engineering
Indian Institute of Technology, Delhi Hauz Khas, New Delhi-110016, INDIA ABSTRACT
Whenever a fault occurs in a particular section of a distribution network and on isolation of the fault some of the loads get disconnected and are left unsupplied. Service should be restored to these affected load points as quickly as possible through a network reconfiguration procedure. A new and efficient technique is presented in this paper for this purpose. Network reduction and determination of the interested trees of the reduced network by a specially developed algorithm for finding the required restorative procedures, are the main contributions of this paper.
Keywords : Network reconfiguration, Service restoration, Interested trees.
INTRODUCTION
The topology of a distribution system is described by the branches of the system and each branch is defined as a set of components in series. The main system components are power transformers, lines, cables, busbars, circuit breakers, instrument transformers and isolators.
Though the various components are connected in the form of a meshed network, the distribution system is operated normally in a radial fashion.
A practical distribution system is mainly divided into a primary subsystem consisting only of system supply points and a number of secondary subsystems. To ensure a reliable operation of a distribution system, it is important to restore power to all the customers rapidly on the occurrence of a fault or an abnormality in a certain section of the system. Whenever a fault occurs on some section of the system, the following actions are required to be taken.
Fault Isolation
By opening the appropriate circuit breakers/isolators, the faulted section is to be isolated from the rest of the system as quickly as possible.
91 SM 401-0 PWRD A paper recommended and approved by the IEEE Transmission and Distribution Committee of the IEEE Power Engineering Society for presentat- ion at the IEEE/PES 1991 Summer Meeting, San Diego, California, July 28 - August 1, 1991. Manuscript submitted January 21, 1991; made available for printing July 1, 1991.
Service Restoration
Due to the isolation of the faulted section, some healthy sections may also get disconnected and will be left without supply.
Service is to be restored to these affected sections by closing and/or opening certain switches in the network to see that every load point is supplied through a radial line.
Fault Repair
The faulty section is to be repaired and the time of repair would depend on various factors like the type and location of fault, availability of repair crew, etc..
Restoration to Normal State
Once the fault is repaired, the system is to be restored back to the normal state.
There has been a considerable interest in the recent past in developing various algorithms for network reconfiguration for service restoration in distribution systems [1-12].
Castro et al [1] suggested algorithms which determine fault location and generate switching instructions based on tree searching techniques utilizing switch tables that can be defined by an operator. Castro Jr., et al [2] proposed a method in which they combine two independent processes: a service restoration to dark zones and a load balance between feeders. Electrical operating constraints are included in the analysis using an appropriate fast decoupled load flow. Aoki et al [3] presented an algorithm for load transfer by automatic sectional izing switch operations in distribution systems on a fault occurrence subject to the transformer and Tine-capacity constraints. Aoki et al [4] also developed a method in which loads in an out-of-service area are transferred to the transformers adjacent to the affected area based on current and voltage constraints. Aoki et al in [5] suggested a non-combinatorial algorithm based on the effective gradient method. Aoki et al in [6] presented yet another algorithm for emergency service restoration in which load restoration priority can be considered.
Stankovic and Calovic [7] developed a graph-oriented control algorithm based on linearized system model, where the synthesis of corrective controls was formulated as a combinatorial mixed- integer programming problem. Dialynas and Michos [8] suggested a method based on graph theory which requires the knowledge of all minimal paths leading to each load point from all system service points under various operating conditions. Some heuristic methods were also suggested in the papers [9-12].
In all the above methods the total distribution network after isolating the faulty
1937 section, has been used in restoring the supply
to all the affected consumers.
In this paper an attempt has been made to reduce the network by suitably merging certain set of nodes together and this reduced network can easily be analyzed for finding alternate paths of power supply to the affected load points (nodes). This requires finding all the trees called interested trees consisting of the nodes corresponding to supply points and all load points in the reduced network. A new algorithm is developed for finding all such trees in a graph. The proposed method consists of reducing the original distribution network under faulty conditions, and finding a restorative procedure satisfying voltage and current constraints. This method is illustrated in detail through a representative distribution system example taken from [8].
Some of the terms used in this paper are defined below:
Interested Nodes
Some of the nodes of the given graph which are of specific interest are called as interested nodes. For example, all the nodes corresponding to supply points and all the load points are called as interested nodes in the reduced network. If a node is not an interested node, it will be referred as a noninterested node.
Interested Trees
An interested tree is a subgraph of the given graph which satisfies the following properties:
1. It is connected.
2. It contains all the interested nodes 3. No proper subset of it satisfies the properties 1 and 2 above.
PROPOSED METHQP
The important steps of the proposed method are:
a) Network reduction (by coalescing some nodes)
b) Determination of all the interested trees in the reduced network.
c) To find the restorative procedure satisfying the current and voltage constraints.
The above steps are explained in detail in the following paragraphs:
a) Network Reduction fbv coalescing some nodes)
The system network under consideration may be very large. It is possible to reduce the original network into a smaller network for the purpose of finding all the radial paths from the source points to all the load points. This reduced network can easily be analysed for finding alternate paths of power supply to the load points. After the occurrence of a fault and isolation of the faulty components the system will be divided into some groups of connected components. All the elements of a group which are connected together can be merged
together. For example consider a sample distribution system shown in Fig.1 in which L1 , L3, L7 represent supply points. L10, L11, L55, L56, L57, L58, L59 represent the load points.
A fault is assumed on components 91 and 135.
Isolation of these faulty components from the rest of the system leads to load points L55, L56, L59 without supply. Fig. 2 is the graphical representation of the connection diagram of Fig.1 under the above conditions.
The continuous lines indicate the elements closed and dotted lines indicate the elements which are open. The complete system will be divided into five groups as shown in Fig.2 under these faulty conditions. It may be noted that for the fault under consideration, the loads in the groups 4 and 5 are only affected. Each substation configuration employs an interlocking scheme which does not permit an isolator to be closed if one of the isolators in the same interlocking sequence is already closed. The elements which are in an interlocking sequences in a group where the loads are affected are to remain unaltered in the process of network reduction. Thus the network shown in Fig.2 can be reduced to a network shown in Fig. 3(a). In Fig. 3(a), node ml, is the new node obtained after merging all the nodes of group 1, m2 is obtained after merging all the nodes of group 2 and m3 is the • node obtained after merging all the nodes of group 3. Since elements 136,137 and 138, 139 are in an interlocking scheme, Group 4 is shown by nodes m4 and m5, retaining the element 136, 137, 138 unaltered. Node m4 is obtained after merging the end nodes of the component 134.
Similarly the node m5 is obtained after merging the. end nodes of components 140, 141 and 142.
This node corresponds to the load point L59 of the original network.
Similarly group 5, in which the load points are affected due to the isolation of faulty components, is represented by the nodes m6, m7, m8 and m9, retaining the elements which are in interlocking schemes. The nodes m8 and m9 correspond to the load points L55 and L56 respectively.
In addition, since one is interested in finding paths from any of the sources to the affected load points, the nodes corresponding to the source points in the reduced network can be merged together to form a single source node.
Accordingly in Fig. 3(b), the final reduced network, the node S corresponds to the source node and nodes m5, m8, m9 correspond to the load points. These nodes are the interested nodes of the reduced network.
b) Determination of all the interested trees of the reduced network
In the reduced network, it is required to find all the interested trees. There are many algorithms available in the literature for finding all the spanning trees of a given graph [14]. Such spanning trees contain all nodes of the graph, However no algorithm seems to be available for finding all interested trees in a graph.
It is possible to generate all interested
trees by first generating all the spanning trees of a graph and manipulating each spanning tree according to the definition of the interested tree. This is ineffi- cient because an interested tree may be generated more than once. Further generating all spanning trees and manipulating them is time consuming.
In the next part of this paper, an efficient algorithm "INTERESTED TREES', is
L1 NODE LINE
C.B (CLOSED) C.B (OPEN) w
ISOLATOR (CLOSED) ISOLATOR (OPEN)
CO: TRANSFORMER 1 : SUPPLY POINTS
17 133
L10 Lit 155 |09L56,]7 L57 L58 F i g . l Example system topology
113 159
\\.7 .122123 124 125 j!26^ 128 130 131 132 L53
\ GROUP 3 * - / 1
Elements in interlocking scheme in groups 4 &. 5.
136,137;138,139 96,97; 98,99;
104,105;
Fig. 2 Connection diagram of Fig. 1 after the isolation of faults on 91 and 135
m\ 136 136 m5 139.
m 2 133 1• \ ini
136 138 m5 143
405
9 9 srn5 97 1 104^ . 109 m8
F i g . 3 ( a ) Reduced network F i g . 3 ( b ) F i n a l reduced
o t Fl<3-* network of Fig. 2
proposed for generating a l l the interested trees directly without repetition.
Algorithm to find a l l the interested trees in a graph
Notation
G: The given connected graph whose all the interested trees are to be determined.
i: current level of the stack.
Esi: Set of elements in which the first element of this is either zero or a node number. Other elements are the edges to be shorted in the graph G. This is stored in the ith level of the stack. If the first element is zero, it indicates that all the edges in Esi are to be shorted. If it is N (a noninterested node), it indicates that one more edge incident at N in the original graph, has to be shorted along with the other edges given in Esi.
Eoi: The set of edges to be opened in the graph G. This is stored in the ith level of the stack.
Es': Set of all edges of current Esi Eo': Set of all edges of current Eoi.
G': Resulting graph obtained after opening and shorting the edges given in Eo' and Es' respectively from G. All edges corresponding to self loops, if any are deleted. (Note that G' may or may not contain all interested nodes) EN: The set of edges incident at N in G.
TYPE: A vector of 0's and 1's which denotes the status of noninterested nodes. It is 1 if only one edge incident at it is shorted. It is zero if no edges or atleast two edges incident at it are shorted.
Algorithm "INTERESTED TREES"
Step 1: Set i=o, initialize the first element of Esi as zero. Eoi = {*} (i.e., there are no edges to be shorted and no edges to be opened).
Set G'=G, Eo'=Eoi, Es' = {*} • Set the type of all noninterested nodes to zero i.e., set all elements of vector TYPE to zero.
Step 2: Check for the presence of a non- interested node in G'. If such a node exists go to step A.
Step 3: Find all the spanning trees of G' using any algorithm which generates all spanning trees without repetition. Each of these trees along with the elements of Es' will give interested trees (Lemma 1 ) . Go to step 5.
Step 4: Select a noninterested node N in G'.
Find the set of edges EN incident at N in G.
Perform procedure ALL COMBINATIONS I with G', Es', Eo', N, and EN as inputs and go to next step.
Step 5: Pop the stack. If there are no elements in the stack, go to step 12. Otherwise Es' = all edges in Esi, Eo' = Eoi. Denote the first element of Esi by x. i=i-1.
Step 6: Open the edges given in Eo' from G.
Denote the resulting graph by G'. If all edges at a noninterested node are opened, delete that particular node from G'.
Step 7: Check for the connectivity of G'. If G' is not connected go to step 5.
Step 8: If x is not equal to zero, go to step 10.
Step 9: (i) Set the status of all nodes of G in the vector TYPE to zero.
9.(ii)If there are no edges in Es',go to step 2. Let e = first edge in Es'.
1939
9.(iii): If e is a self loop,go to step 5. Otherwise let v1 and v2 be the end nodes of the edge e in the original graph G. If v1 is a noninterested node, change its status in the vector TYPE (If its status is 0 make it 1. On the other hand if it is 1 make it 0 ) . Similarly, if v2 is a noninterested node, change its status also in the vector TYPE.
9.(iv): Short the edge e in G'. Denote the resulting graph by G'.
9.(v):lf there are no more edges in Es' go to step 9.(vi). Otherwise take the next edge in Es'. Denote this as e and go to step 9.(iii).
9.(vi): If none of the noninterested nodes has status 1 in the vector TYPE, go to step 2.
Otherwise let v be a nonintrested node whose status is 1 in TYPE.
9.(vii):1=1+1. Store v as the first element in Esi. Append Es' to Esi. Eoi = Eo'. Go to steps.
Step 10 (i): Find all the edges incident at node x in the original graph G. Let this set be Ex.
10.(ii):Delete the edges from Ex which are also present in Eo'.
10.(iii ):Short the edges given in Es' as follows:
Let e = first edge in Es'.
1O.(iv): If e is a self loop go to step 5.
Otherwise short it in G'. Delete this edge from Ex, if it is present in Ex. The resulting graph is G'.
10.(v) : If there are no more edges in Es', go to step 11. Otherwise take the next edge in Es'. Denote this as e and go to step 10(1v).
Step 11: Perform procedure ALL COMBINATIONS II with G', Ex, Es' and Eo' and x as inputs and go to step 5.
Step 12: End.
Procedure ALL COMBINATIONS I
{This procedure generates the combinations of edges to be shorted and edges to be opened at a noninterested node which has a status 0.
The inputs to this procedure are G', Es', Eo', N and EN}.
Step a: Delete the edges from EN which are also present in Eo'.
Step b: Delete the edges from EN which are also present in Es'.
Step c: If the number of edges in EN is less than two, go to step (h). Otherwise choose e1, e2 the first two edges in EN (Lemma 2 shows why two edges are enough).
Step d: i = i+1. Store zero as first element in Es. Append e1, e2 and Es' to Esi. Eoi=Eo'.
Step e: i=i+i. Store N as first element in Esi. Append e1 and Es' to Esi. Eoi=Eo'.
Append e2 to Eoi.
step f: i=i+i. Store N as first element in Esi. Append e2 and Es' to Esi. Eoi=Eo'.
Append e1 to Eoi.
Step a: i=i+i. Store zero as first element in Esi. Append Es' to Esi. Eoi=Eo'. Append e1 and e2 to Eoi. Go to step i.
Step h: if the set EN is null, go to step i.
Otherwise i=i+1. Store zero as first element in Esi. Append Es' to Esi. Eoi=Eo'.
Append the single element present in EN to Eoi.
Step i: End.
Procedure ALL COMBINATIONS II
{This procedure generates the combinations of edges to be shorted and edges to be opened at a noninterested node which has a status of
1}.
The inputs to this procedure are G', Es', Eo', x and Ex.
Step a: If Ex is null, go to step d.
Otherwise let e1 be the first edge in Ex.
Step b: i=i+1. Store zero as the first element in Esi. Append e1 and Es' to Esi. Eoi=Eo'.
Step c: i=i+1. Store x as the first element of Esi. Append Es' to Esi. Eoi=Eo'. Append e1 to Eoi.
Step d: End.
The proof of this algorithm is given in appendix I and an illustration is given in appendix II.
c) Findina the restorative procedure satisfying the current and voltage constraints
The above algorithm is used to find all the interested trees of the reduced network.
If any interested tree contains all the elements which are in an interlocking sequence, then it is not a valid interested tree since both the elements which are in interlocking sequence cannot be closed simultaneously. All such invalid interested trees are to be eliminated.
Henceforth the remaining interested trees are only considered. Once the interested trees are determined, the elements to be closed and the elements to be opened for each tree can be found out. This ensures that all the load points are connected to the source point in a radial fashion. The total number of switching operations (the sum of number of elements to be closed and the number of elements to be opened) forms the weight of a tree. Thus the weights of all the interested trees (possible restorative procedures) are obtained. These trees are then arranged in the ascending order of their weights.
To start with, the interested tree (possible restorative procedure) with the minimum weight is chosen. For this procedure, a complete path from the actual source point to the actual load points in the original network is traced. (This is obtained by replacing the merged nodes in the path by the elements which have been shorted in the network reduction process). This constitutes the reconfigured network under system restoration. A Distribution Load Flow (DISTLF) is run for the resulting network with this restorative procedure. Different distribution load flow methodologies are available in the literature.
In the present work the method given in [13] is used. The DISTLF gives us the branch currents and node voltages for a given source node voltage and specified loads at different load points of the above network. If the branch currents and the node voltages in the entire network are within their tolerable limits, the present restorative procedure can be implemented by closing and/or opening of some components, as given by the procedure explained earlier.
If the present restorative procedure does not
result in acceptable branch currents and node voltages in the network, the restorative procedure with next minimum weight is chosen and check for branch current and node voltage limits are carried out as above. This procedure is carried out till a feasible interested tree (restorative procedure) is obtained satisfying both the current and voltage constraints. If none of the above interested trees satisfy the current and voltage constraints, then some partial load shedding is to be resorted to for satisfying the current and voltage constraints in the reconfigured network.
ILLUSTRATION
The proposed method is illustrated with a sample system shown in Fig. 1, which is a part of a distribution system [8]. This is the same example chosen to explain the proposed method in the above section. In Fig. 2 the dotted lines indicate the open components and complete lines indicate the closed components, before the fault. The list of possible restorative procedures along with the components to be closed and opened for a fault on components 91 and 135 is given in Table 1. For procedure number 1 in Table 1, DISTLF solution has been obtained and it has been observed that none of the current and voltage containts are violated in the reconfigured network. Hence this procedure can be implemented by closing the components 139,103 and opening the component 97.
Table 1: Possible restorative procedures for a fault on components 91 and 135.
S. Components Components Components Weight No. in the path to be to be of the in the redu- closed opened path ced network
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
139,104,98,103 104,98,143,117 139,117,104,98 103,104,98,143 103,104,99,143 139,103,104,109 139,103,104,99 103,98,143,117 139,103,98,117 105,103,98,143 103,98,109,143 139,105,103,98 139,103,98,109 103,104,109,143 139,105,99 139,105,109 105,99,143 105,109,143 139,99,109 139,99,117 139,109,117 99,109,143 99,143,117 109,143,117
139,103 143,117 139,137 103,143 103,99,143 139,103,109 139,103,99 103,143,117 139,103,117 105,103,143 103,109,143 139,105,103 139,103,109 103,109,143 139,105,99 139,105,109 105,99,143 105,109,143 139,99,109 139,99,117 139,109,117 99,109,143 99,143,117 109,143,117
97 97 97 97 97,98 97,98 97,98 97,104 97,104 97,104 97,104 97,104 97,104 97,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98 97,104,98
3 3 3 3 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6
CONCLUSIONS
In this paper a new network reconfiguration technique for service restoration in distribution networks is proposed. The proposed method is based on network reduction. All the interested trees of the reduced network will directly give all possible restorative procedures. For this purpose a new algorithm 'INTERESTED TREES' is also developed which directly gives all the interested trees of a graph without repetition. This algorithm has been justified by relevent theorms and Lemmas which have also been proved.
REFERENCES
[1].Carlos H. Castro, Jennings B. Bunch, Terry M. Topka, "Generalized Alrogithms for distribution Feeder Deployment and Sectionalizing, " IEEE Trans, on Power Apparatus and Systems, Vol. PAS-99, No.2, PP. 549-557, March/April 1980.
[2.]. C A . Castro Jr., and A.L.M. Franca,
"Automatic Power Distribution Reconfiguration Algorithm Including Operating Constraints", Proceedings IFAC Conference as Electric Energy Systems, Brazil, pp 155-160, 1985.
[3].K.Aoki, H. Kuwabara, T. Satoh, M. Kanezashi,
"Outage State Optimal Load Allocation by Automatic Sectionalizing Switches Operation in Distribution System," IEEE Trans, on Power Delivery, Vol PWRD-2, No.4, pp 1177-1185, October 1987.
[4]K. Aoki, T. Satoh, M. Itoh, H. Kuwabara, M.
Kanezashi, "Voltage drop Constrained Restoration of Supply by Switch Operation in Distribution Systems", IEEE Trans, on Power Delivery, Vol.
3, No.3, pp 1267- 1274, July 1988.
[5].K.Aoki, K. Nara, M. Itoh, T. Satoh, H.
Kuwabara, "A New Algorithm for Service Restoration in Distribution Systems", IEEE Trans, on Power Delivery, Vol 4, No.3, pp 1832-1839, July 1989.
[6].K. Aoki, K. Nara and T. Satoh, "New Configuration Algorithm for Distribution System-Priority Constrained Emergency Service Restoration", Procedings of IFAC Conference on Power Systems and Plant Control, Seoul, Korea, pp 443-448, 1989.
[7].A.M. Stankovic and M.S. Calovic, "Graph Oriented Algorithm for the Steady-State Security Enhancement in Distribution Networks", IEEE Trans, on Power Delivery, Vol 4, No.1, pp 539-544, Jan. 1989.
[8].E.N. Dialynas, D.G. Michos, "Interactive Modelling of Supply Restoration Procedures in Distribution System Operation," IEEE Trans, on Power Delivery, Vol. 4, No.3, pp 1847-1854, July 1989.
[9]Chen-Ching Liu, Seung Jae Lee, S.S. Venkata,
"An Expert System Operation Aid for Restoration and Loss Reduction of Distribution Systems", IEEE Trans, on Power Delivery, Vol. 3, No.2, pp 619-626, May 1988.
[10].A.L. Morelato and A. Monticelli, "Heuristic Search Approach to Distribution System Restoration," IEEE Trans, on Power Delivery, Vol. 4, No.4, pp 2235-2241, Oct. 1989.
[11]. Z.Z. Zhang, G.S. Hope, O.P. Mallik, "A Knowledge Based Approach to Optimize Switching in Substations," IEEE Trans, on Power Delivery, Vol. 5, No.1, pp 103- 109, Jan. 1990.
[12]. Taylor, David Lubkeman, "Implementation
1941 of Heuristic Search Strategies for Distribution
Feeder Reconfiguration," IEEE Trans, on Power Delivery, Vol 5, No.1, pp 239-246, Jan 1990.
[13].P.s. Nagendra Rao, K.S. Prakasa Rao, "A Fast Load Flow Method for Radial Distribution Systems", Proceedings of Platinum Jubilee Conference on Systems and Signal Processing, Indian Institute of Science, Bangalore, India, pp 471-474, Dec. 1986.
M4].R. Jaykumar, K. Thulasiraman, M.N.S. Swamy,
*'MOD-CHAR : An Implementation of Char's Spanning Tree Enumeration Algorithm and its Complexity Analysis", IEEE Trans, on Circuits and Systems, Vol. 36, No.2 pp 219-228, 1989.
APPENDIX I
PROOFS OF THE ALGORITHM 'INTERESTED TREES' Theorm I: Let Gs be a tree of a graph G such that it contains all interested nodes. Then Gs is an interested tree, if and only if every end node of Gs is an interested node.
Proof: Only if: let Gs be an interested tree.
To prove that every end node of Gs is an interested node. For if this is not true, let noninterested node v be an end node of Gs. Then the edge connected to v can be removed resulting in another interested tree. This violates property 3 of the interested tree showing that any end node of an interested tree is an interested node.
If: Let Gs be a tree of G containing all interested nodes such that each end node of Gs is an interested node. To prove that Gs is an interested tree.
It is obvious that Gs satisfies properties 1 and 2 in the definition of an interested tree.
If property 3 is also true, then Gs is an interested tree. Thus if Gs violates property 3, then let Gs' be a subgraph of Gs satifying all the three properties of the definition.
That is at least one edge of Gs has to be removed to get Gs'. This edge has to be an edge incident at an end node. For this is not true Gs' will be disconnected. But if this edge is removed an interested node is lost showing that Gs' is not an interested tree. This proves that Gs satisfies the property 3 of the definition.
Hence the result.
Corollary: A noninterested node cannot be an end node of an interested tree.
Proof: This is only a restatement of the 'only if part of the theorm I.
Lemma 1: Let Gs be a spanning tree of the reduced graph G' in step 3 of the algorithm.
Let Es' be the set of edges shorted to get the reduced graph. Then the set of edges consisting of the edges Es' and Gs is an interested tree T.
Proof: In the algorithm Es1 contains at least two edges from each noninterested node (procedures I and I I ) . Thus no end node of T can be a noninterested node. T contains all interested nodes. For if this is not true, let v be an interested node missing from T. i.e., no edge incident at v is present in T. i.e.,
in Es' as well as in G'. This is not possible unless all the edges incident at v are eventually eliminated as self loops. But a self loop cannot be formed unless all the edges in a loop except the edge appearing in the self loop are shorted. This requires an edge at v to be shorted to create a self loop. This implies that there is an edge in Es' which is incident at v. Thus if v is not present in G', then it is present as a node of some edge in Es'. If an edge is not eliminated as self loop, then it is anyway present in G'. In either case T contains v. Thus T contains all interested nodes. Further T is a tree. Therefore from Theorm I,T is an interested tree.
Lemma 2: In the algorithm INTERESTED TREES, only two edges have to be shorted at any noninterested node to generate an interested tree containing that node.
Proof: Let N be the noninterested node under consideration. Let e1, e2 be the two edges selected for shorting at N. Let T be an interested tree containing at least three edges say e1, e2, e3 incident at N. Some of the edges of this tree are obtained from shorting. Let Es' be the set of edges falling in this category. Let G' be the reduced graph containing only interested nodes whose spanning trees are generated in the step 3 of the algorithm. If G' contains e3, then all spanning trees containing e3 are generated in step 3 of the algorithm. Thus T is also generated.
Similarly if e3 is considered for shorting at another node then it is not present in G', but it will be present in Es' of the algorithm and so it will be present in T. Thus T is not- generated only if e3 is eliminated as a self loop. This implies that e3 forms a loop with some of the edges in Es'. But this is not possible if e3 is present in T (as a tree does not have loops). Thus e3 cannot be eliminated as self loop if it is present in T. Hence the result.
Theorm IJ: Algorithm INTERESTED TREES generates all interested trees of the given graph without duplication.
Proof: That the algorithm generates interested trees is proved in Lemma 1. It is required to prove that it generates all interested trees without duplication. This is done by considering two cases as follows:
Case (i): First assume that all the nodes of the given graph are interested nodes only. In this case step 3 of the algorithm is executed.
Since an interested tree is a spanning tree also, all interested trees are generated without duplication.
Case (ii): Consider a noninterested node say N of the graph. Let e1, e2,...ep be the set of edges E incident at N. Any interested tree that contains N will have at least two edges of E in it. Thus all interested trees of the graph can be expressed as union of subsets of trees as follows:
{T} = e,e2 {T,} U 6,63(62) {T2} V...
...U e1ep(e2>e3,...ep.1) {Tp_,}
U e2e3 ( el} { Tp+1 } U
eie2"-ep) { T } • A.I
where the edges shown in the brackets should be opened and other edges shown should be shorted to get a graph which gives interested trees denoted in the flower backets.
For example, e^p (e2>e3 eJ>.1){Tp.1} means that e^ep are the edges to be shorted and e2, e3...ep_1 are the edges to be opened to get a graph which gives the interested trees denoted by { V , } .
Similarly (e,,e2,e3,.. .ep){T'} means e,, e2 ep are the edges to be opened to get a graph whose interested trees are denoted by {T1}. These interested trees do not contain the noninterested node N.
It may be noted that in the above equation A.1, the edges to be opened as indicated is required to avoid repetition. Let T be any interested tree of the graph G. If it does not contain N it falls uniquely in to the group {T'}. If it contains N, let eM I e12.. . e,. be the set of edges incident at N and present in T. Without loss of generality let im > im-1 >
... > i2 > i1. To generate this tree, the edges
en> ei2 have to be shorted (Other edges ej3 to e,. of T need not be shorted in view of Lemma 2) There is only one term in the equation corresponding to this. Thus subsets of trees corresponding to the terms in the equation are disjoint i.e., no tree is generated more than once. Further since T is any tree, this shows that all trees are generated. Thus the algorithm generates all trees without repetition provided it implements the equation A.1 properly.
To save memory,equation A.1 is implemented as follows:
{T}F = e ^ C T , } U xe/ej.HT.,} U xe2 (e,) {T3} U (e,e2) {T4} A.2 {T}x = e, {T,} U x (e,) {T2} A.3
Equations A.2 and A.3 are implemented in the algorithm in procedures I and II respectively.
APPENDIX-II
ILLUSTRATION OF THE ALGORITHM "INTERESTED TREES"
Consider the example graph given in Fig.
A2.1 in which nodes 1,3,5 are the interested nodes. This graph is denoted by G. Select the noninterested node 2 in step 2 of the algorithm.
Therefore N=2, EN={1,3,4}. Next when step 4 is executed the following combinations are stored in the stack. Es1 = {0,1,3}, Eo1 = {0}; Es2 = {2,1}, Eo2 = {3}; Es3 = {2,3}, Eo3 = {1}; Es4
= {0}; Eo4 = {1,3}. Now in step 5 i=4 is chosen. Therefore Es' = {<(>}, Eo' = {1,3}, x = 0. Opening the edges in Eo' from G, G' is obtained as shown in Fig. A2.2. G' is connected. Since x=0, Step 9 is executed.
Since Es'={$}, step 2 is executed.
Noninterested node 2 from G' is selected in step 4. Therefore N=2, EN={1,3,4}. After performing the procedure ALL COMBINATIONS I, and when i=4 is selected, Es4 = {0}, Eo4 = {1,3,4}. This leads to the combinations Es4 = {0,2,5}, Eo4 = {1,3,4}; Es5 = {4,2}, Eo5 = {1,3,4,5}; Es6 = {4,5}, Eo6 = {1,3,4,2}; Es7 = {0}, Eo7 = {1,3,4,2,5}. Now i = 7 and i = 6 results the graphs G' which are disconnected.
For i=5, x=4, Es' = {2}, Eo' = {1,3,4,5}. The resulting graph G' obtained after opening the edges of Eo' from G is shown in Fig. A2.3.
Since all the edges incident at 2 in G are opened, node 2 is also deleted from G'. Ex = {2,3,5,7}. Executing the step 10 of the algorithm results in Ex = {7} and G' as shown in Fig. A2.4. Executing step 11 results in Es5
= {0,7,2}, Eo5 = {1,3,4,5}; Es6 = {4,2}, Eo6 =
Fig.A.2.1 Fig.A 2.2 F1g.A2.3 Fig.A2.4 Graph G Fig.A 2.5
{1,3,4,5,7}. For 1=6, when all edges of Eo6 are opened from G, the resulting graph is disconnected. For i=5, x=0, Es' = {7,2}, Eo'
= {1,3,4,5}. Executing steps 6,7,8 and 9 of the algorithm leads to the graph G' shown in Fig. A2.5. It has only one edge 6 and no noninterested nodes of status 1 are present.
So step 2 is executed resulting one spanning tree of G' which has 6 as its edge. Therefore the interested tree T1 = {7,2,6} is generated.
Thus proceeding further according to the algorithm, all the following remaining interested trees of the graph G are obtained : T2 = {2,5,7}, T3 = {2,5,6}, T4 = {2,3,4,6}, T5
= {2,3,4,7}, T6 = {1,4,6}, T2 = {1,4,5,7}, T8
= {1,2,4,7}, T9 = {1,3,6,7}, T10 = {1,3,4,7}, T11 = {1,3,5,7}, T12 = {1,3,5,6}.
N.D.R.Sarma is a research scholar working for his Ph.D. degree in the Deptt., of Elect. Engg.
in IIT Delhi, India. His area of interest is Graph Theory Applications to Power Systems.
V.C.Prasad is a professor in the Deptt. of Elect. Engg., in IIT Delhi. His areas of interests are nonlinear circuits, CAD of networks and VLSI, Reliability and Graph Theory.
K.S.Prakasa Rao is a professor in Deptt. of Elect. Engg., IIT Delhi. His areas of interests are Power System Planning and Operation Studies, and Power System Reliability.
V. Sankar is working as lecturer in Elect. Engg.
at J.N.T.U., College of, Engg., . Ananthapur, India. Presently he is on leave and working for his Ph.D. His areas of interests are Power systems, Reliability studies.
