Re: Embedding of a graph
- To: mathgroup at smc.vnet.net
- Subject: [mg43309] Re: Embedding of a graph
- From: "Eckhard Hennig" <aidev at n-o-s-p-a-m.kaninkolo.de>
- Date: Sun, 24 Aug 2003 04:55:06 -0400 (EDT)
- References: <bi7mns$ov9$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"Oliver Friedrich" <oliver.friedrich at tzm.de> schrieb im Newsbeitrag news:bi7mns$ov9$1 at smc.vnet.net... > A second thing: From a given network graph I want to find a complete tree > of the graph (to establish minimum mesh equations), how is that possible? Hi Oliver, to determine spanning tree of a network graph, follow these steps: 1. Set up the nodal incidence matrix A of your graph. Example: A = {{1, 1, 1, 0, 0, 0}, {0, 0, -1, 1, 0, 1}, {0, -1, 0, 0, 1, 0}} 2. Transform A into echelon form Ae by row exchange and/or elimination: (* Swap rows 2 and 3, multiply rows by -1: *) Ae = {{1, 1, 1, 0, 0, 0}, {0, 1, 0, 0, -1, 0}, {0, 0, 1, -1, 0, -1}, 3. Select one column from each step level of Ae. The corresponding branches constitute a spanning tree. In this case, a tree would be given by branches 1, 2, and any one of the branches 3..6. Let's choose a tree T composed of the branches associated with columns 1, 2, and 3. Next, if you want to set up loop (mesh) equations, you have to calculate a fundamental loop matrix from Ae for the selected tree. To achieve this, do a complete back substitution of Ae: (* Subtract row 2 from row 1, the subtract row 3 from row 1: *) Aeb = {{1, 0, 0, 1, 1, 1}, {0, 1, 0, 0, -1, 0}, {0, 0, 1, -1, 0, -1}, The loop matrix B associated with T is now given by the negative transpose of the dependent columns (columns 3..6 =: Bf) augmented with an identity matrix I of proper dimension: B = {-Bf^T, I} In this case we have Bf = columns 3..6 of Aeb = {{1, 1, 1}, {0, -1, 0}, {-1, 0, -1}} Thus, -Bf^T = {{-1, 0, 1}, {-1, 1, 0}, {-1, 0, 1}} The loop matrix B you need to write KVL is obtained by appending a 3x3 identity matrix to -Bf^T: B = {{-1, 0, 1, 1, 0, 0}, {-1, 1, 0, 0, 1, 0}, {-1, 0, 1, 0, 0, 1}} To validate the result, check if A and B satisfy the orthogonality relation A.B^T = 0: A.Transpose[B] {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}} Best regards, Eckhard P.S.: An excellent reading on these topic is the book "Computer-aided analysis of electronic circuits: algorithms and computational techniques" by Chua and Lin. -- Dr.-Ing. Eckhard Hennig www.kaninkolo.de/ai aidev \at kaninkolo \dot de