Vývojový graf (matematika) - Flow graph (mathematics)
A vývojový graf je forma digraf spojené se sadou lineárních algebraických nebo diferenciálních rovnic:[1][2]
- „Graf toku signálu je síť uzlů (nebo bodů) propojených směrovanými větvemi, představující sadu lineárních algebraických rovnic. Uzly v průtokovém grafu slouží k reprezentaci proměnných nebo parametrů a spojovací větve představují koeficienty vzájemné propojení těchto proměnných. Vývojový graf je spojen s řadou jednoduchých pravidel, která umožňují získat každé možné řešení [související s rovnicemi]. “[1]
Ačkoli tato definice používá pojmy „graf toku signálu“ a „graf toku“ zaměnitelně, termín „graf toku signálu“ se nejčastěji používá k označení Masonův graf toku signálu Mason je původcem této terminologie ve své práci na elektrických sítích.[3][4] Podobně někteří autoři používají termín „vývojový graf“ k přísnému odkazu na Coatesův vývojový graf.[5][6] Podle Henley & Williams:[2]
- „Nomenklatura zdaleka není standardizovaná a ... v dohledné budoucnosti nelze očekávat žádnou standardizaci.“
Označení „vývojový graf“, který zahrnuje jak Masonův graf, tak Coatesův graf, a řadu dalších forem takových grafů[7] se jeví jako užitečné a souhlasí s přístupem Abrahamse a Coverleyho as přístupem Henleyho a Williamse.[1][2]
A řízená síť - také známý jako a toková síť - je konkrétní typ vývojového grafu. A síť je graf se skutečnými čísly spojenými s každou z jeho hran, a pokud je grafem digraf, výsledkem je a řízená síť.[8] Tokový graf je obecnější než směrovaná síť v tom, že mohou být spojeny okraje zisky, zisky pobočky nebo přenosy, nebo dokonce funkce Laplaceova operátoru s, v takovém případě jsou voláni přenosové funkce.[2]
Existuje úzký vztah mezi grafy a maticemi a mezi digrafy a maticemi.[9] „Algebraickou teorii matic lze elegantně získat pomocí teorie grafů“ a naopak pro řešení lineárních algebraických rovnic se používají graficko-teoretické přístupy založené na vývojových grafech.[10]
Odvození vývojového grafu z rovnic


Je uveden příklad vývojového grafu připojeného k některým počátečním rovnicím.
Sada rovnic by měla být konzistentní a lineárně nezávislá. Příkladem takové sady je:[2]
Konzistence a nezávislost rovnic v množině je stanovena, protože determinant koeficientů je nenulový, takže řešení lze nalézt pomocí Cramerovo pravidlo.
Pomocí příkladů z podsekce Prvky grafů toku signálu, sestrojíme graf Na obrázku je v tomto případě graf toku signálu. Chcete-li zkontrolovat, zda graf představuje dané rovnice, přejděte na uzel X1. Podívejte se na šipky přicházející do tohoto uzlu (zvýrazněné zeleně) a váhy k nim připojené. Rovnice pro X1 je spokojen tím, že jej přirovná k součtu uzlů připojených k příchozím šipkám vynásobenému váhami připojenými k těmto šipkám. Rovněž platí červené šipky a jejich váhy X2a modré šipky pro X3.
Dalším příkladem je obecný případ tří simultánních rovnic s nespecifikovanými koeficienty:[11]
Chcete-li nastavit vývojový graf, jsou rovnice přepracovány, takže každá identifikuje jednu proměnnou přidáním na každou stranu. Například:
Pomocí diagramu a sečtením dopadajících větví do X1 tato rovnice je považována za splněnou.
Protože všechny tři proměnné vstupují do těchto přepracovaných rovnic symetrickým způsobem, je symetrie v grafu zachována umístěním každé proměnné do rohu rovnostranného trojúhelníku. Otočení obrázku o 120 ° jednoduše permutuje indexy. Tuto konstrukci lze rozšířit na více proměnných umístěním uzlu pro každou proměnnou na vrchol pravidelného mnohoúhelníku s tolika vrcholy, kolik proměnných existuje.
Aby to bylo smysluplné, koeficienty jsou samozřejmě omezeny na hodnoty, takže rovnice jsou nezávislé a konzistentní.
Viz také
Další čtení
- Richard A. Brualdi, Dragos Cvetkovic (2008). „Determinanty“. Kombinatorický přístup k maticové teorii a jejím aplikacím. Chapman & Hall / CRC. str. 63 ff. ISBN 9781420082234. Diskuse o Coatesových a Masonových vývojových grafech.
Reference
- ^ A b C J. R. Abrahams, G. P. Coverley (2014). "Kapitola 1: Prvky vývojového grafu". Analýza toku signálu. Elsevier. p. 1. ISBN 9781483180700.
- ^ A b C d E Ernest J. Henley, RA Williams (1973). "Základní pojmy". Teorie grafů v moderním strojírenství; počítačem podporovaný návrh, řízení, optimalizace, analýza spolehlivosti. Akademický tisk. p. 2. ISBN 9780080956077.
- ^ Mason, Samuel J. (září 1953). „Teorie zpětné vazby - některé vlastnosti grafů toku signálu“ (PDF). Sborník IRE. 41 (9): 1144–1156. doi:10.1109 / jrproc.1953.274449. S2CID 17565263.
- ^ SJ Mason (červenec 1956). „Teorie zpětné vazby - další vlastnosti grafů toku signálu“ (PDF). Sborník IRE. 44 (7): 920–926. doi:10.1109 / JRPROC.1956.275147. hdl:1721.1/4778. S2CID 18184015. Online verzi najdete na MIT Research Laboratory of Electronics.
- ^ Wai-Kai Chen (květen 1964). "Některé aplikace lineárních grafů" (PDF). Koordinovaná vědecká laboratoř, University of Illinois, Urbana.
- ^ RF Hoskins (2014). „Flow-graph and signal flow-graph analysis of linear systems“. V SR Deards (ed.). Poslední vývoj v teorii sítí: Sborník ze sympozia konaného na letecké akademii v Cranfieldu, září 1961. Elsevier. ISBN 9781483223568.
- ^ Kazuo Murota (2009). Matice a matroidy pro systémovou analýzu. Springer Science & Business Media. p. 47. ISBN 9783642039942.
- ^ Gary Chartrand (2012). Úvodní teorie grafů (Republication of Grafy jako matematické modely, 1977 ed.). Courier Corporation. p. 19. ISBN 9780486134949.
- ^ Frank Harary (leden 1967). „Grafy a matice“ (PDF). Recenze SIAM. 9 (2).
- ^ K. Thulasiraman, M. N. S. Swamy (2011). Grafy: Teorie a algoritmy. John Wiley & Sons. 163 ff. ISBN 9781118030257.
- ^ Narsingh Deo (2004). Teorie grafů s aplikacemi ve strojírenství a informatice (Dotisk z roku 1974 vyd.). Prentice-Hall of India. p. 417. ISBN 9788120301450.