Flowdiagram (matematik) - Flow graph (mathematics)

En flowdiagram er en form for digraph forbundet med et sæt lineære algebraiske eller differentialligninger:

"En signalflowdiagram er et netværk af noder (eller punkter), der er sammenkoblet af rettede grene, der repræsenterer et sæt lineære algebraiske ligninger. Noder i en flowgraf bruges til at repræsentere variablerne eller parametrene, og de forbindende grene repræsenterer koefficienterne relaterer disse variabler til hinanden. Flowdiagrammet er forbundet med et antal enkle regler, der gør det muligt at opnå enhver mulig løsning [relateret til ligningerne]. "

Selvom denne definition bruger udtrykkene "signal-flow-graf" og "flow-graf" om hverandre, bruges udtrykket "signal-flow-graf" oftest til at betegne Mason-signal-flow-grafen , idet Mason er ophavsmanden til denne terminologi i sit arbejde på elektriske netværk. Ligeledes bruger nogle forfattere udtrykket "flowgraf" til at henvise strengt til Coates-flowgrafen . Ifølge Henley & Williams:

"Nomenklaturen er langt fra standardiseret, og ... der kan ikke forventes nogen standardisering i overskuelig fremtid."

En betegnelse "flowgraf", der inkluderer både Mason-grafen og Coates-grafen, og en række andre former for sådanne grafer synes at være nyttige og er enig med Abrahams og Coverleys og med Henley og Williams 'tilgang.

Et rettet netværk - også kendt som et flownetværk - er en bestemt type flowgraf. Et netværk er en graf med reelle tal tilknyttet hver af dets kanter, og hvis grafen er en digraf, er resultatet et rettet netværk . Et rutediagram er mere generel end en rettet netværk, ved, at kanterne kan være forbundet med gevinster, branch gevinster eller transmittanser , eller endda funktioner i Laplace-operatoren s , i hvilket tilfælde de kaldes overføringsfunktioner .

Der er et tæt forhold mellem grafer og matricer og mellem digraphs og matricer. "Den algebraiske teori om matricer kan bringes til udtryk i grafteorien for at opnå resultater elegant", og omvendt anvendes grafteoretiske tilgange baseret på flowdiagrammer til løsning af lineære algebraiske ligninger.

Udledning af en flowdiagram fra ligninger

Et eksempel på en signal-flow-graf

Flowdiagram for tre samtidige ligninger. Kanterne på hver knude er farvet forskelligt bare for at fremhæve dem.

Et eksempel på en flowgraf, der er forbundet med nogle startligninger, præsenteres.

Sætningen med ligninger skal være konsistent og lineært uafhængig. Et eksempel på et sådant sæt er:

${\ 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}}}$

Konsistens og uafhængighed af ligningerne i sættet etableres, fordi determinanten for koefficienter er ikke-nul, så en løsning kan findes ved hjælp af Cramer's regel .

Ved hjælp af eksemplerne fra underafsnittet Elementer af signal-flow grafer konstruerer vi grafen I figuren er der en signal-flow graf i dette tilfælde. For at kontrollere, at grafen repræsenterer ligningerne, skal du gå til node x ₁ . Se på pilene, der kommer ind til denne knude (farvet grøn for at fremhæve) og vægten, der er knyttet til dem. Ligningen for x ₁ tilfredsstilles ved at ligne den med summen af ​​de knudepunkter, der er knyttet til de indgående pile ganget med de vægte, der er knyttet til disse pile. Ligeledes giver de røde pile og deres vægte ligningen til x ₂ , og de blå pile til x ₃ .

Et andet eksempel er det generelle tilfælde af tre samtidige ligninger med uspecificerede koefficienter:

${\ displaystyle {\ begin {bmatrix} c_ {11} & c_ {12} & c_ {13} \\ c_ {21} & c_ {22} & c_ {23} \\ c_ {31} & c_ {32} & c_ {33} \ slut {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \ end {bmatrix}} = {\ start {bmatrix} y_ {1} \\ y_ {2} \\ y_ {3} \ end {bmatrix}}}$

For at opsætte flowgrafen omarbejdes ligningerne, så hver identificerer en enkelt variabel ved at tilføje den til hver side. For eksempel:

${\ displaystyle \ left (c_ {11} +1 \ right) x_ {1} + c_ {12} x_ {2} + c_ {13} x_ {3} -y_ {1} = x_ {1} \.}$

Ved hjælp af diagrammet og opsummering af hændelsesgrenene til x ₁ ses denne ligning være opfyldt.

Da alle tre variabler indtaster disse omarbejdede ligninger på en symmetrisk måde, bevares symmetrien i grafen ved at placere hver variabel i hjørnet af en ligesidet trekant. Drejning af tallet 120 ° tillader simpelthen indekserne. Denne konstruktion kan udvides til flere variabler ved at placere noden for hver variabel i toppen af ​​en regelmæssig polygon med så mange hjørner, som der er variabler.

For at være meningsfulde er koefficienterne naturligvis begrænset til værdier, således at ligningerne er uafhængige og konsistente.

Se også

• Coates-graf
• Signal-flow-graf

Yderligere læsning

• Richard A. Brualdi, Dragos Cvetkovic (2008). "Determinants" . En kombinatorisk tilgang til matrixteori og dens anvendelser . Chapman & Hall / CRC. s. 63 ff . ISBN   9781420082234 . En diskussion af Coates og Mason flow grafer.

Referencer