Cutii de Coates și Maison

6.11. Earls de Coates și Mason

În această secțiune, luăm în considerare o abordare grafic-teoretică a soluției de ecuații algebrice liniare. Se discută două metode strâns legate de Coates [6.10] și cu Mason [6.11, 6.12].







6.11.1. Metoda Coates

Luați în considerare un sistem liniar descris de un sistem de ecuații

unde este o matrice de ordine nondegenerată, un vector de coloană cu variabile necunoscute. B - vector-coloană a elementelor - variabilă de intrare.

Soluția poate fi scrisă în formular

unde este complementul algebric al elementului matrice A.

Fie A matricea obținută prin adăugarea lui -B la partea dreaptă a matricei A și apoi la partea inferioară a matricei verificate a rândului zero. Asociem un grafic orientat ponderat cu matricea A.

Să presupunem că are un vârf. Dacă, atunci, trebuie să existe un arc cu greutate. Evident, A este o matrice de adjuvant transpusă. Un grafic este denumit graf de flux Coates sau pur și simplu un grafic Coates asociat cu matricea A. De asemenea, vom spune că graficul Coates este legat de sistemul de ecuații (6.26).

Să luăm în considerare, ca exemplu, sistemul de ecuații

În acest caz, matricea A are forma

Graful Coates asociat sistemului de ecuații (6.28) este prezentat în Fig. 6.12, a.

Rețineți că fiecare vârf (1 i și) al graficului poate fi considerat ca reprezentând ecuația din sistem (6.26). De exemplu, în ecuația (6.26) poate fi obținut prin egalarea cu zero suma produselor ale greutăților arce care intră în partea superioară a variabilelor corespunzătoare nodurile din care se bazează pe aceste arce. În plus, eliminând vârful din grafic, se poate obține graficul Coates asociat cu matricea A. În cazul sistemului de ecuații (6.28), graficul Coates este prezentat în Fig. 6.12, b.

Deoarece A - transpune matricea de adiacență și matricea în sine și matricea transpusă au determinanți egali, Teorema 6.27 rezultă că

unde - 1-factorul graficului este produsul de greutate al subgrafului, a este numărul de contururi din el. Astfel numitorul expresiei (6.27) poate fi exprimată prin factorii de ponderare ai lucrărilor de grafice la ieșire o expresie similară pentru numărătorul cu formula (6.27) necesare pentru exprimarea JL.

Fig. 6.12. a este graficul Coates δ este un grafic; c este conexiunea 1-factorială a graficului

1-factorial compus vertex la vertexul din grafic este un subgraf Spanning care cuprinde a) o cale P direcționată de la vertex la vertexul set de bucle-vertex disjunctă conținând toate nodurile cu excepția contururile incluse în compusul -factorial cale, de exemplu, cu un vârf de vârfuri (Figura 6.12, a) este prezentată în Fig. 6.12, c.

THEOREM 6.28. Fie graficul Coates asociat cu matricea A de ordine Apoi

2) Graficul obținut după îndepărtarea vârfului este o conexiune 1-factorială la vârfurile cu numărul de vârfuri al respectivelor contururi, respectiv.

Dovada. 1. Rezultă din teorema 6.27.

2. Rețineți că determinantul matricei obținută din matricea A prin înlocuirea coloană cu coloană care constă din zero, elemente cu excepția faptului că este egal cu 1. Vom nota această matrice prin Coates Apoi graficul este obținut din graficul inițial prin eliminarea nodurilor tuturor outgoing (inclusiv bucle incidente sus), și introducerea arcului cu greutate 1. acum, din Teorema 6.27 obținem

unde este factorul grafic - numărul de bucle în

Fiecare On-factor necesar ar trebui să conțină o introducere la greutatea arcului I. Înlăturarea arcului de factorul pe, vom obține conexiunea -factorial grafic Acest lucru este ușor de a verifica dacă între graficul din grafic, există o corespondență, că, întrucât numărul de contururilor din compusul -factorial este una mai mică decât aceea din expresiile (6.30), obținem







Să luăm acum în considerare numitorul expresiei (6.27). Această sumă este egală cu determinantul matricei obținută din matricea A pentru coloana de înlocuire B. Este ușor să se asocieze cu - matricea obținută din matricea A prin îndepărtarea rând și coloană):

Din partea 2 a teoremei 6.28 obținem

în care: - numărul de circuite în conexiunea în graficul -factorial expresiile Combinand (6.31) și (6.32), obținem

Din expresiile (6.29) și (6.33) obținem următoarea teoremă:

THEOREM 6.29. Dacă matricea coeficienților A este nondegenerată, soluția de ecuație (6.26) este definită după cum urmează:

1. - Legătura 1-factorială a unui vârf cu un vârf în grafic

2. 1-factor al graficului.

3. - numărul de cicluri în t și, respectiv, H.

Ecuația (6.34) se numește formula coeficientului Coates. Se ilustrează aplicarea acestei formule, rezolvând ecuația (6.28) cu privire la

Factorii 1 ai graficului (Figura 6.12, b), legați cu matricea A din ecuația (6.28), sunt prezentați mai jos cu produsele lor de greutate. Diferitele contururi în factorul-diferă în ordinea vârfurilor din paranteze

Calculăm numărul de exprimare (6.34):

Dăm legătura factorială (Figura 6.12, a). Acum, vârful se află în paranteze, întins pe calea orientată.

Calculăm numărul de exprimare (6.34):

6.11.2. Metoda lui Mason

Pentru a ilustra metoda Mason, rescriim ecuația (6.26) în formă

Aceste ecuații pot fi reprezentate în formă de matrice, după cum urmează: unde A - ordinea matricea definită anterior - matricea identității variabilelor vector coloană ordine

Fig. 6.13. a este graficul Mason. b este un grafic.

Earl Coates numit Earl Mason grafic flux de semnal sau doar Mason legat de matrice A și este notat cu, de exemplu, în fig. 6.13 dăm graficul Mason și graficul asociat sistemului de ecuații (6.28).

Fiecare vertex dintr-un grafic poate fi considerat o variabilă. Dacă există un arc între noduri, atunci putem presupune că variabila contribuie la variabila X). Cu alte cuvinte, este egal cu suma produselor de greutăți ale arcurilor care intră în vârf și de variabilele corespunzătoare vârfurilor din care provin aceste arce. Astfel, graficul Mason este o reprezentare grafică convenabilă a fluxului de variabile în sistem.

Rețineți că pentru a obține graficul Coates dintr-un grafic Mason dat din greutatea fiecărui buclă, pur și simplu scădem unul și

Mason fiecare vârf al graficului fără bucle introduce o buclă cu o greutate de -1. Cu alte cuvinte, Coates grafic poate fi obținut din grafic Mason simplu introducerea la fiecare buclă vertex cu greutate -1. Notăm mulțimea de greutate bucle -1 fiind adăugat pentru a construi un grafic prin 5. Rețineți că graficul construit în acest mod va avea la fiecare nod, cel mult două, și în același timp, cel puțin o buclă.

Luați în considerare graficul Meson asociat cu matricea A; permiteți graficului să fie graficul Coates corespunzător. Fie ca un factor 1 al graficului să aibă bucle din set. Să - numărul total de contururi H. După îndepărtare, bucle suplimentare ale setului 5 primi inițial graficul subgrafic Q fiind un set de căi-vertex disjuncte. În plus, cu

Rețineți că dacă, atunci Q este un subgraf gol care are, prin definiție, greutate. Prin urmare, în acest caz

De asemenea, ușor de văzut că fiecare grafic subgrafic Q este un set de bucle-vertex disjuncte din grafic corespunde unui factor unic, care se obține prin introducerea în partea de sus, care nu sunt incluse în Q, bucle (dintr-o pluralitate de S) -1 greutate.

Prin teorema 6.27, avem

Ultimul pas în această derivare rezultă din expresiile (6.35) și (6.36). Expresia (6.37) poate fi reprezentată în formular

unde este produsul de greutate al unui subgraf care este un set de contururi k vertex-disjoint.

Astfel, am exprimat numitorul expresiei (6.27) în produsele de greutate ale subgrafelor corespunzătoare ale graficului Mason.

Noi numim determinantul graficului și notat cu A. Apoi, folosind expresia (6.33) și procedând în același mod ca și în derivarea (6,38), exprimăm numărătorul

unde calea orientată de la vârf la vârful graficului este determinantul subgrafului aceluiași grafic,

vertex-disjoint cu o cale orientată. Astfel, ajungem la următoarea afirmație:

THEOREM 6.30. Dacă matricea coeficienților A în expresia (6.26) este nondegenerată, atunci

în cazul în care o cale îndreptată în graficul din partea de sus la partea de sus - determinantul subgraful căii orientate spre vârf-disjuncte la determinant al graficului

Ecuația (6.39) se numește formula de câștig a lui Mason. În literatura de specialitate privind teoria sistemelor - calea dreaptă de la vârf la vârful conturului se numește bucle de feedback. Se ilustrează aplicarea formulei (6.39) la soluția de ecuație (6.28) cu privire la

Dăm mai multe seturi de contururi vertex-disjoint (fig.6.13, b) și produsele lor de greutate.

Calculăm numitorul expresiei (6.39):

Dăm diferite căi orientate (Figura 6.13, a) de la vârf la vârf împreună cu produsele lor de greutate:

Contururile care sunt vertex-disjoint cu căi drepte sunt, respectiv, buclele. prin urmare

. Contururi care nu intersectează vertex-intersectarea cu căi drepte, adică,

Astfel, numerotatorul expresiei (6.39) are forma Prin urmare







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: