Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Flow graph (mathematics)
open-in-new
<h2 id="deriving-a-flow-graph-from-equations">Deriving a flow graph from equations</h2> <p>An example of a flow graph connected to some starting equations is presented. </p><p>The set of equations should be consistent and linearly independent. An example of such a set is:<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p> [ 1 2 0 0 1 1 5 − 1 − 1 ] [ x 1 x 2 x 3 ] = [ 5 5 0 ] {\displaystyle {\begin{bmatrix}1&2&0\\0&1&1\\5&-1&-1\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}5\\5\\0\end{bmatrix}}} <p>Consistency and independence of the equations in the set is established because the determinant of coefficients is non-zero, so a solution can be found using <a href="/facts/Cramer%27s_rule/aUt4Cena">Cramer's rule</a>. </p><p>Using the examples from the subsection <a href="/facts/Signal-flow_graph/Tg5fNxgo">Elements of signal-flow graphs</a>, we construct the graph In the figure, a signal-flow graph in this case. To check that the graph does represent the equations given, go to node <i>x1</i>. Look at the arrows incoming to this node (colored green for emphasis) and the weights attached to them. The equation for <i>x1</i> is satisfied by equating it to the sum of the nodes attached to the incoming arrows multiplied by the weights attached to these arrows. Likewise, the red arrows and their weights provide the equation for <i>x2</i>, and the blue arrows for <i>x3</i>. </p><p>Another example is the general case of three simultaneous equations with unspecified coefficients:<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p> [ c 11 c 12 c 13 c 21 c 22 c 23 c 31 c 32 c 33 ] [ x 1 x 2 x 3 ] = [ y 1 y 2 y 3 ] {\displaystyle {\begin{bmatrix}c_{11}&c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}} <p>To set up the flow graph, the equations are recast so each identifies a single variable by adding it to each side. For example: </p> ( c 11 + 1 ) x 1 + c 12 x 2 + c 13 x 3 − y 1 = x 1 . {\displaystyle \left(c_{11}+1\right)x_{1}+c_{12}x_{2}+c_{13}x_{3}-y_{1}=x_{1}\ .} <p>Using the diagram and summing the incident branches into <i>x1</i> this equation is seen to be satisfied. </p><p>As all three variables enter these recast equations in a symmetrical fashion, the symmetry is retained in the graph by placing each variable at the corner of an equilateral triangle. Rotating the figure 120° simply permutes the indices. This construction can be extended to more variables by placing the node for each variable at the vertex of a regular polygon with as many vertices as there are variables. </p><p>Of course, to be meaningful the coefficients are restricted to values such that the equations are independent and consistent. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Coates_graph/bUDCA6u4">Coates graph</a></li> <li><a href="/facts/Signal-flow_graph/Tg5fNxgo">Signal-flow graph</a></li></ul> <h2 id="further-reading">Further reading</h2> <ul><li>Richard A. Brualdi, Dragos Cvetkovic (2008). <a href="https://books.google.com/books?id=pwx6t8QfZU8C&pg=PA63">"Determinants"</a>. <i>A Combinatorial Approach to Matrix Theory and Its Applications</i>. Chapman & Hall/CRC. pp. 63 <i>ff</i>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781420082234. A discussion of the Coates and the Mason flow graphs.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>J. R. Abrahams, G. P. Coverley (1965). "Chapter 1: Elements of a flow graph". Signal flow analysis. Elsevier. p. 1. ISBN 9781483180700. <a href="9781483180700" target="_blank">9781483180700</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Ernest J Henley, RA Williams (1973). "Basic concepts". Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis. Academic Press. p. 2. ISBN 9780080956077. <a href="9780080956077" target="_blank">9780080956077</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>J. R. Abrahams, G. P. Coverley (1965). "Chapter 1: Elements of a flow graph". Signal flow analysis. Elsevier. p. 1. ISBN 9781483180700. <a href="9781483180700" target="_blank">9781483180700</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Mason, Samuel J. (September 1953). "Feedback Theory - Some Properties of Signal Flow Graphs" (PDF). Proceedings of the IRE. 41 (9): 1144–1156. doi:10.1109/jrproc.1953.274449. S2CID 17565263. Archived from the original (PDF) on 2018-02-19. Retrieved 2015-01-09. <a href="https://web.archive.org/web/20180219004940/http://ecee.colorado.edu/~ecen5014/Mason-IRE-1953.pdf" target="_blank">https://web.archive.org/web/20180219004940/http://ecee.colorado.edu/~ecen5014/Mason-IRE-1953.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>SJ Mason (July 1956). "Feedback Theory-Further Properties of Signal Flow Graphs" (PDF). Proceedings of the IRE. 44 (7): 920–926. doi:10.1109/JRPROC.1956.275147. hdl:1721.1/4778. S2CID 18184015. On-line version found at MIT Research Laboratory of Electronics. <a href="http://dspace.mit.edu/bitstream/1721.1/4778/1/RLE-TR-303-15342712.pdf" target="_blank">http://dspace.mit.edu/bitstream/1721.1/4778/1/RLE-TR-303-15342712.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Wai-Kai Chen (May 1964). "Some applications of linear graphs" (PDF). Coordinated Science Laboratory, University of Illinois, Urbana. <a href="http://www.amarketplaceofideas.com/wp-content/uploads/2008/11/6016231.pdf" target="_blank">http://www.amarketplaceofideas.com/wp-content/uploads/2008/11/6016231.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>RF Hoskins (2014). "Flow-graph and signal flow-graph analysis of linear systems". In SR Deards (ed.). Recent Developments in Network Theory: Proceedings of the Symposium Held at the College of Aeronautics, Cranfield, September 1961. Elsevier. ISBN 9781483223568. <a href="9781483223568" target="_blank">9781483223568</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Ernest J Henley, RA Williams (1973). "Basic concepts". Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis. Academic Press. p. 2. ISBN 9780080956077. <a href="9780080956077" target="_blank">9780080956077</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Kazuo Murota (2009). Matrices and Matroids for Systems Analysis. Springer Science & Business Media. p. 47. ISBN 9783642039942. <a href="9783642039942" target="_blank">9783642039942</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>J. R. Abrahams, G. P. Coverley (1965). "Chapter 1: Elements of a flow graph". Signal flow analysis. Elsevier. p. 1. ISBN 9781483180700. <a href="9781483180700" target="_blank">9781483180700</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Ernest J Henley, RA Williams (1973). "Basic concepts". Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis. Academic Press. p. 2. ISBN 9780080956077. <a href="9780080956077" target="_blank">9780080956077</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Gary Chartrand (2012). Introductory Graph Theory (Republication of Graphs as Mathematical Models, 1977 ed.). Courier Corporation. p. 19. ISBN 9780486134949. <a href="9780486134949" target="_blank">9780486134949</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Ernest J Henley, RA Williams (1973). "Basic concepts". Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis. Academic Press. p. 2. ISBN 9780080956077. <a href="9780080956077" target="_blank">9780080956077</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Frank Harary (January 1967). "Graphs and Matrices" (PDF). SIAM Review. 9 (2). Archived from the original (PDF) on 2016-03-04. Retrieved 2015-01-09. <a href="https://web.archive.org/web/20160304040548/http://poncelet.math.nthu.edu.tw/disk5/js/geometry/harary.pdf" target="_blank">https://web.archive.org/web/20160304040548/http://poncelet.math.nthu.edu.tw/disk5/js/geometry/harary.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>K. Thulasiraman, M. N. S. Swamy (2011). Graphs: Theory and Algorithms. John Wiley & Sons. pp. 163 ff. ISBN 9781118030257. <a href="9781118030257" target="_blank">9781118030257</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Ernest J Henley, RA Williams (1973). "Basic concepts". Graph theory in modern engineering; computer aided design, control, optimization, reliability analysis. Academic Press. p. 2. ISBN 9780080956077. <a href="9780080956077" target="_blank">9780080956077</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Narsingh Deo (2004). Graph Theory with Applications to Engineering and Computer Science (Reprint of 1974 ed.). Prentice-Hall of India. p. 417. ISBN 9788120301450. <a href="9788120301450" target="_blank">9788120301450</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> </ol>