Coates és Maison dobozai
6.11. Earls of Coates és Mason
Ebben a részben a lineáris algebrai egyenletek megoldásának grafikus elméleti megközelítését vizsgáljuk. A Coates [6.10] és a Mason [6.11, 6.12] két egymással szorosan összefüggő módszert tárgyalja.
6.11.1. A Coates-módszer
Vegyünk egy egyenletrendszer által leírt lineáris rendszert
ahol egy nem generált rend mátrix, ismeretlen változók oszlop vektora. B - elemek vektor-oszlopa - bemeneti változó.
A megoldás a formában írható
ahol az A mátrixelem algebrai komplementuma.
Legyen A a mátrix, amelyet az A mátrix jobb oldalához, majd a nulla sor ellenőrzött mátrixának alsó részéhez adunk. Egy súlyozott orientált gráfot egy A. mátrixhoz társítunk.
Tegyük fel, hogy csúcsa van. Ha igen, akkor legyen egy ív, amelynek súlya nyilvánvalóan A egy átültetett szomszédsági mátrix. A gráfot Coates áramlási grafikonnak vagy egyszerűen az A mátrixhoz társított Coates gráfnak nevezzük. Azt is elmondhatjuk, hogy a Coates gráf összefügg az egyenletrendszerrel (6.26).
Vegyünk példaként az egyenletek rendszerét
Ebben az esetben az A mátrixnak van az alakja
Az egyenletek rendszeréhez társított Coates grafikon (6.28) a 3. ábrán látható. 6.12, a.
Felhívjuk a figyelmet arra, hogy a grafikon minden egyes csúcsa (1 i és) a rendszer egyenletének tekinthető (6.26). Például a (6.26) képlet egyenletét úgy kaphatjuk meg, hogy az ívek tömegének olyan értékeit vesszük számításba, amelyek az ívek olyan csúcsaiból érkeznek, amelyek a változók csúcsán jönnek létre. Ezenkívül a csúcs eltávolítása a grafikonból az A mátrixhoz tartozó Coates gráfot kapja. Az egyenletek rendszerének (6.28) esetében a Coates gráf a 3. ábrán látható. 6.12, b.
Mivel A egy átültetett szomszédsági mátrix, maga a mátrix és az átültetett mátrixa azonos determinánssal rendelkezik, a 6.27 tételből következik, hogy
ahol - a grafikon 1-tényezője a subgraph súlyterméke, a a kontúrok száma. Így a kifejezés (6.27) kifejezés nevezője a gráf faktorok tömegtermékeivel fejeződhet ki. A (6.27) képlet számlálójának analóg kifejezéséhez egy AL kifejezésre van szükség.
Ábra. 6.12. a a Coates grafikon δ egy grafikon; c a gráf 1-faktoriális kapcsolata
1-faktoriális vegyületet vertex a vertex a gráf egy feszít®fája részgráf, amely tartalmaz a) egy irányított út P vertex csúcshalmaza a pontfüggetlenek hurkok tartalmazó összes csúcsot, kivéve kontúrok az elérésiútvonal -factorial vegyület, például egy csúcsot csúcsok (6.12. Ábra, a) az 1. ábrán látható. 6.12, c.
TÉMÁM 6.28. Legyen a Coates-grafikon a rend A mátrixához
2) a csúcs eltávolításával kapott gráf 1-faktorikus kapcsolatot mutat a csúcspontokkal, ahol a kontúrok csúcssebessége.
Bizonyítás. 1. A 6.27 tételből következik.
2. Megjegyezzük, hogy a determináns a mátrix kapott az A mátrix helyett oszlopról oszlopra csupa nulla elemek, kivéve, hogy egyenlő 1. Jelöljük ez a mátrix által Coates Ezután a grafikon nyerik az eredeti gráf eltávolításával csúcsai összes kimenő (beleértve a hurkok esemény vertex), és egy ív bevezetésével 1-es tömeggel. Most a 6.27 tételből kapjuk meg
hol van a grafikon tényezője - a hurkok száma
Minden On-faktor feltétlenül tartalmaznia kell egy bevezetést a súlya az ív I. eltávolítása az ív a tényező, megkapjuk -factorial kapcsolat grafikon Ez könnyen ellenőrizhető, hogy a grafikon a grafikonon, van egy levelezés, hogy ahány a -faktív vegyület kontúrjai egy kisebbek, mint a Ezért (6.30)
Tekintsük most a kifejezés számlálóját (6.27). Ez az összeg megegyezik az A mátrixból kapott mátrix meghatározójával az oszlop B-rel való helyettesítésével. Az A mátrixból nyert mátrixhoz könnyen hozzárendelhető a sor és az oszlop törlése):
A 6.28. Tétel 2. részéből származunk
ahol a kontúrok száma a tényleges összefüggésben a gráfban A kifejezések (6.31) és (6.32) kombinálásával
A (6.29) és (6.33) kifejezésekből a következő tételt kapjuk:
TÉMAKÖR 6.29. Ha az A együtthatók mátrixa nem degenerált, akkor a (6.26) egyenlet oldatát a következőképpen határozzuk meg:
1. - A csúcs csúcspontja 1-faktoros kapcsolata a gráfban
2. A grafikon 1-tényezője.
3. - t és H ciklusok száma.
A (6.34) egyenlet a Coates-együttható formula. Ezt a képletet illusztráljuk, a (6.28) egyenletet megoldva
A (6.28.) Egyenlethez tartozó A mátrixhoz kapcsolódó grafikon (6.12. Ábra, b) 1-es tényezőit az alábbiakban ismertetjük tömegtermékeikkel. A -faktorban a különböző kontúrok különböznek a zárójelben lévő csúcsok sorrendjében
Kiszámítjuk a kifejezés számlálóját (6.34):
Adjuk meg a faktoriális csatlakozást (6.12. Ábra, a). Most a csúcs zárójelben van, a tájékozott pályán fekszik.
Kiszámítjuk a kifejezés számlálóját (6.34):
6.11.2. Mason módszere
A Mason-módszer szemléltetéséhez a (6.26) egyenletet átírjuk a formában
Ezeket az egyenleteket a következőképpen lehet mátrix formában ábrázolni: ahol A egy korábban definiált rend mátrix - a változók vektorkategóriájának egy mátrixa
Ábra. 6.13. a a Mason grafikon, b pedig grafikon.
A Coates grafikon Mason áramlások jelgráfjának vagy egyszerűen az A mátrixhoz kapcsolódó Mason grafikonnak nevezhető, és amelyet például az 1. ábrán mutatunk be. 6.13 megadjuk a Mason gráfot és a gráfot az egyenletek rendszerével (6.28).
Minden grafikon csúcsa változónak tekinthető. Ha van egy ív a csúcsok között, akkor feltételezhetjük, hogy a változó hozzájárul az X változóhoz. Más szavakkal, megegyezik az ívek tömegének termékeinek összegével, amelyek belépnek a csúcsra, és azoknak a csúcsoknak megfelelő változók, amelyekből ezek az ívek emanálnak. Így a Mason grafikon a rendszerben lévő változók kényelmes grafikus ábrázolása.
Ne feledje, hogy ahhoz, hogy egy adott Mason-grafikonból szerezzük be a Coates grafikont az egyes hurok súlyából, egyszerűen kivonjuk az egyiket, és
A Mason grafikon hurok nélküli csúcsait egy -1-es súlyú hurok vezette be. Más szóval, a Coates-grafikon a Mason gráfból nyerhető el, ha egyszerűen bevezet egy hurokot, amelynek súlya -1 minden csúcsra. Az ilyen, 1-1-es súlyú hurkok halmazát kell megadnunk, ha egy grafikonot készítünk S-vel. Megjegyezzük, hogy az így létrehozott grafikonnak legfeljebb két csúcsa van mindegyik csúcson és egyidejűleg legalább egy hurokban.
Tekintsük az A mátrixhoz tartozó mezon gráfot; a grafikon legyen a megfelelő Coates-grafikon. Legyen egy 1-tényező a grafikonon, amelyen hurok van a készletből. Legyen H kontúrok teljes száma. Amikor hozzáadjuk a S halmazt a hozzáadott hurkokból, megkapjuk a grafikon Q eredeti szubgrafikáját, amely a csúcs-diszjunkturális kontúrok halmaza. Ezen kívül, a
Megjegyezzük, hogy ha, akkor Q egy üres részgrafikon, amelynek meghatározása szerint súlya van. Ezért ebben az esetben
Szintén könnyen belátható, hogy minden részgráfja, Q gráf egy sor pontfüggetlenek hurkok a gráf felel meg egy egyedi faktor, amelyet úgy kapunk, bevezetésével, hogy a felső, nem tartalmazza Q, szalagkábelek (a több S) -1 tömeg.
A 6.27. Tétel szerint
Az utolsó lépés ebben a deriválásban a (6.35) és (6.36) kifejezésekből következik. A kifejezést (6,37) a formában ábrázolhatjuk
hol van egy subgraph tömegterméke, amely k-csúcs-diszjunkturális kontúrok halmaza.
Így kifejeztük a kifejezés (6.27) kifejezés nevezőjét a Mason grafikon megfelelő szubgrafáinak tömegtermékeiben.
Ezt a grafikon determinánsát nevezzük, és azt A.-vel jelöljük. Ezután (6.33) segítségével és pontosan ugyanúgy vitatkozunk, mint a (6.38) deriválásakor, a számlálót
ahol a gráf csúcsa és csúcspontja közötti orientált pálya meghatározza az ugyanazon grafikon részgrafikáját,
csúcs-diszjunktúra egy orientált útvonalon. Így jutunk el a következő állításhoz:
ELMÉLET 6.30. Ha az A együtthatók mátrixa a (6.26) kifejezésben nem degenerált, akkor
ahol a csúcsponttól a csúcsig terjedő gráf irányított pályája meghatározza a csúcspont-szétválasztásnak a k irányultságú metszésponttal, a gráf meghatározója
A (6.39) egyenlet Mason nyereség formulájának nevezzük. A rendszerek elméletéről szóló irodalomban - a csúcsponttól a csúcspontig terjedő egyenes utat visszacsatolási hurkoknak nevezik. A (6.39) képlet alkalmazásával szemléltetjük a (6.28.) Egyenlet megoldását a
A csúcs-diszjunkturális kontúrokat (6.13, b ábra) és azok súlytermékeit adjuk meg.
Kiszámítjuk a kifejezés nevezőjét (6.39):
Különböző orientált utakat (6.13. Ábra, a) adunk a csúcsról a csúcsra a súlytermékeikkel együtt:
Az egyenletes pályákkal csúcsteres csúcsok a hurkok. ezért
. Azok a kontúrok, amelyek nem keresztezik a csúcspontokat, amelyek metszenek az egyenes úton,
Így a kifejezés (6.39) számlálója így van