Browse Prior Art Database

Algorithms for Finding the Terminal Characteristics of a Linear Network Symbolically

IP.com Disclosure Number: IPCOM000086446D
Original Publication Date: 1976-Sep-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Hsieh, HY: AUTHOR [+2]

Abstract

Described is the manner of obtaining the terminal properties of a network, i.e., a macromodel, from its topological configuration symbolically. The three algorithms used are:. 1. Algorithm for finding all trees of an undirected graph. 2. Algorithm for the rapid evaluation of the relative signs of tree pairs. 3. Algorithm to obtain the terminal characteristics of a linear active network employing the symbolic tree generation technique. Consider the graph reduction procedure steps to obtain (1). The graph G in the figure, using the symbolic edge description is: G = 12AB13CA14A*23CB24B*34C*.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Algorithms for Finding the Terminal Characteristics of a Linear Network Symbolically

Described is the manner of obtaining the terminal properties of a network, i.e., a macromodel, from its topological configuration symbolically. The three algorithms used are:.
1. Algorithm for finding all trees of an undirected graph.
2. Algorithm for the rapid evaluation of the relative

signs of tree pairs.
3. Algorithm to obtain the terminal characteristics of a

linear active network employing the symbolic tree

generation technique.

Consider the graph reduction procedure steps to obtain (1).

The graph G in the figure, using the symbolic edge description is: G = 12AB13CA14A*23CB24B*34C*.

Subgraph G(1) becomes, using the symbolic edge description after removing edge 14, G(1) = 12AB13CA23CB24B*34C *.

Subgraph G(2) is accomplished using the symbolic description by (a) removing the vertex information from the description of edge 14, (b) replacing the principal vertex of edge 14 (A) with (*) everywhere in G and rearranging so that * appears in fourth position, and (c) removing from the symbolic subgraph description the entire edge description whenever a (**) appears as the node designation of the edge. Therefore, for G(2): G(2) = 12B*13C*1423CB24B*34C* Similarly: G(3) = 12AB13CA23CB24B* G(4) = 12AB13A*23B*24B*34 G(5) = 12AB13CA23CB G(6) = 12A*13CA23C*24 The procedure cannot be applied to G(5) since it does contain an *. Also obtained is: G(7) = 13CA23C*24 G(8) = 1213C*23C*24 Finally, obtained are the trees: T(1) = 132324 (from G(7)) T(2) = 121324 (from G(8)) T(3) = 122324.

Consider algorithm 2. The relative sign S, associated with a tree-pair can be determined by computing the number of interchanges I(1) and I(2), necessary to change the column order of each tree in the tree-pair, respectively, to agree w...