Grafy przeplywowe.pdf
(
336 KB
)
Pobierz
Microsoft Word - Grafy Przep³ywowe v11.doc
Obwody i Układy
M
ateriały
P
omocnicze
Analiza układów za pomocą grafów przepływowych
v.1.1
1.
Wstęp. Pojęcie grafu przepływowego.
Niech pewien system liniowy będzie opisany układem liniowych równań algebraicznych
ax ax b
ax ax b
+ =
+ =
12 2
1
(1.1)
21 1
22 2
2
x x
- zmienne reprezentujące wielkości występujące w układzie
Przepiszmy układ (1.1) w zmienionej postaci
x
=++ +=+ +
1
12 2
1 0
1 1
12 2
1 0
(1.2)
x ax a 1x cx ax ax cx
= + + + = + +
2
21 1
22
2
2 0
21 1
2 2
2 0
gdzie:
x
- parametr, który może być uważany jako wielkość wejściowa układu, przy czym:
bc x bc x
1
= − = −
1 0 2
,
2 0
(1.3)
Można zauważyć, że każdej z niewiadomych
x
1
,
x
2
zostało przypisane jedno równanie,
w którym wielkość ta stanowi kombinację liniową wszystkich niewiadomych oraz parametru
x
0
.
1)
Układ równań w postaci (1.2) można zobrazować
graficznie za pomocą tzw. grafu przepływowego
(Rys. 1.1). W ujęciu tym każdej wielkości
(niewiadomej) przyporządkowany zostaje węzeł
(wierzchołek) grafu, natomiast operacje między
wielkościami symbolizowane są za pomocą
zorientowanych gałęzi (krawędzi) rozpiętych między
węzłem początkowym i końcowym.
c
2
x
0
c
1
x
1
a
21
x
2
a
1
a
12
a
2
Rys. 1.1
Wartość wielkości przyporządkowanej do wierzchołka stanowiącego węzeł końcowy kilku
gałęzi, równa jest sumie iloczynów transmitancji oraz wartości wielkości odpowiadających
węzłom początkowym tych gałęzi.
Powyższe stwierdzenie określa jednocześnie jedną z możliwych metod tworzenia grafu
przepływowego, jako
geometrycznej reprezentacji równań
opisujących system liniowy.
Struktura grafu odzwierciedla zatem jedynie związki między sygnałami i nie należy utożsamiać
jej ze strukturą realnie istniejących połączeń, między poszczególnymi elementami układu.
Modelowanie równań opisujących układ w postaci grafu przepływowego nie jest celem
samym w sobie. Stanowi ono podstawę do dalszej analizy zależności między wielkościami
układu, a w szczególności między wielkościami wejściowymi i wyjściowymi. Możemy zatem
stwierdzić, że metoda ta najpełniej sprawdza się dla tzw. układów transmisyjnych,
rozpatrywanych w konwencji wejście-wyjście, w których jednym z głównych zadań analizy jest
wyznaczanie transmitancji.
Przyjmując, że wielkościom wejściowym i wyjściowym układu, zostały przyporządkowane
określone wierzchołki grafu, to w celu wyznaczenia transmitancji dokonać należy redukcji
innych węzłów grafu oraz wyeliminować wszystkie połączenia między węzłami wyjściowymi. W
ten sposób gałęziom łączącym pozostałe po redukcji węzły, będą bezpośrednio przypisane
poszukiwane transmitancje.
1)
Oczywiste jest, że przejście od układu
(
1.1
)
do
(
1.2
)
nie jest jednoznaczne.
- 1 -
11 1
gdzie:
,
12
( )
( )
a 1xaxcx axaxcx
1
11
Obwody i Układy
M
ateriały
P
omocnicze
Analiza układów za pomocą grafów przepływowych
v.1.1
2.
Podstawowe określenia. Zasady redukcji grafów.
Grafem przepływowym
nazywamy skończony, spójny zbiór wierzchołków (węzłów)
połączonych zorientowanymi krawędziami (gałęziami).
Gałąź grafu
reprezentuje operację (transmitancje) między wielkościami.
Węzeł grafu
reprezentuje wielkość lub sygnał o wartości równej sumie sygnałów
przekazywanych przez gałęzie, których dany węzeł jest węzłem końcowym.
Rozróżniamy następujące rodzaje węzłów:
a)
Węzeł, który nie jest węzłem końcowym żadnej z gałęzi nazywamy
węzłem źródłowym
,
odgrywa on rolę pobudzenia lub sygnału wejściowego;
b)
Węzeł, który nie jest węzłem początkowym żadnej z gałęzi nazywamy
węzłem
odbiorczym
,
odpowiada on sygnałom wyjściowym układu.
c)
Węzły nie będące węzłami źródłowymi ani odbiorczymi nazywamy
węzłami pośrednimi
.
Każdemu węzłowi pośredniemu można przyporządkować wielkość wyjściową. W tym celu
należy utworzyć dodatkowy węzeł połączony z danym węzłem odpowiednio zorientowaną
gałęzią o transmitancji równej
1
.
W tabeli 2.1 zestawiono podstawowe sposoby eliminacji węzłów pośrednich oraz pętli
własnych węzłów. W każdym przypadku obowiązuje zasada, że wszelki przekształcenie grafu nie
może zmienić transmitancji ścieżek między pozostałymi po redukcji wierzchołkami grafu.
1.
x
1
a
x
2
b
x
3
x
1
ab
x
3
Połączenie szeregowe
x ax x bx
= =
1 3
2
x ab
=
3
1
a
x
1
x
2
Połączenie równoległe
( )
2.
x
1
a + b
x
3
b
x
2
=+
abx
1
3.
x
1
a
2
a
1
x
1
a
1
b
x
4
b
x
5
x
5
a
2
b
x abx abx abx
= + +
x
2
x
2
5
1
1
2
2
3
3
x
3
a
3
x
3
a
3
b
4.
x
1
a
x
2
b
x
3
ab
Eliminacja pętli własnej:
x
1
x
3
c
1-c
x
=
x
1c
3
−
1
x ax cx
=+
2
1
2
5.
x
1
a
2
a
1
x
4
b
x
5
x
1
a
1
b
a
2
b
1-c
x
2
x
5
ab
ab
ab
1-c
1
2
3
x
= +
x x x
1c 1c 1c
+
c
a
3
x
2
5
1
2
3
− −
−
a
3
b
x
3
1-c
x ax ax ax cx
=+++
1 1
2 2
3 3
4
x
3
Tabela 2.1
- 2 -
2
,
ab
4
Obwody i Układy
M
ateriały
P
omocnicze
Analiza układów za pomocą grafów przepływowych
v.1.1
Dodatkowe określenia
Ścieżką
nazywamy zbiór jednakowo zorientowanych gałęzi łączących wybrane węzły
grafu. Ścieżka, podobnie jak gałąź, posiada węzeł początkowy i końcowy.
Pętlą
grafu nazywamy ścieżkę, w której ten sam węzeł jest węzłem początkowym i
końcowym.
Pętlą własną
wierzchołka grafu nazywamy pętlę zawierającą tylko jedną gałąź.
Przykład 1.
Redukcja grafu z jedną pętlą.
Rozważmy eliminację węzła pośredniego w grafie przedstawionym na Rys. 2.1. Zawiera on
trzy węzły, w tym jeden węzeł początkowy i dwa węzły pośrednie. Przyjmując węzeł
x
3
jako
węzeł końcowy wyznaczymy transmitancję określoną stosunkiem sygnału
x
3
do
x
1
.
a)
b)
c)
d)
x
1
a
x
2
b
x
3
x
1
a
x
2
b
x
3
x
1
ab
x
3
ab
h
31
=
1-bc
bc
bc
x
1
x
3
c
Rys. 2.1
Przejście od grafu a) do b) uwzględnia niezmienność transmitancji pętli
x
3
-x
2
-x
3
. Powstałą w ten
sposób pętlę własną eliminujemy stosując zasadę 4 z tabeli 2.1.
Przykład 2.
Eliminacja kaskady pętli.
W stosunku do przykładu poprzedniego, eliminacja pętli własnej węzła
x
3
musi uwzględnić
także transmitancję ścieżki (pętli)
x
4
-x
3
-x
4
. Zgodnie z zasadą 5 (tab.2.1) transmitancje wszystkich
gałęzi dochodzących do węzła
x
3
muszą być podzielone przez
1- ba
2
(Rys. 2.2 d).
a)
Graf wyjściowy
b)
Redukcja pętli
x
3
-x
2
-x
3
c)
Redukcja węzła
x
2
x
1
a
1
x
2
a
2
x
3
a
3
x
4
x
1
a
1
x
2
a
2
x
3
a
3
x
4
x
1
a
1
a
2
x
3
a
3
x
4
b
c
ba
2
c
ba
2
c
d)
Redukcja pętli własnej węzła
x
3
e)
Redukcja pętli
x
4
-x
3
-x
4
a
1
a
2
1 - ba
2
f)
Redukcja węzła
x
3
a
1
a
2
1 - ba
2
x
1
x
3
a
3
x
4
x
1
a
3
x
4
a
1
a
2
1 - ba
2
a
3
a
3
c
1 - ba
2
1 -
a
3
c
1 - ba
2
x
3
x
1
c
1 - ba
2
x
4
Rys. 2.2
Po przekształceniu ostatniego wyrażenia transmitancja wynosi
h
=
−−
123
(2.1)
41
1ba ca
2
3
- 3 -
aaa
Obwody i Układy
M
ateriały
P
omocnicze
Analiza układów za pomocą grafów przepływowych
v.1.1
3.
Wyznaczanie transmitancji układów za pomocą grafów przepływowych.
Przykłady redukcji grafów.
Przykład 3.
Wykorzystując poznane zasady redukcji grafów wyznaczymy jedną z możliwych transmitancji
układu opisanego równaniami (1.2). Wielkość wejściową będzie
x
0
, natomiast wyjściową
x
2
.
a)
Graf wyjściowy (
por. Rys. 1.1
)
b)
Redukcja pętli własnej węzła
x
1
c
2
c
2
c
1
x
1
a
21
x
2
x
1
a
21
x
2
c
1
x
0
x
0
a
1
1-a
1
a
12
a
2
a
2
a
12
1-a
1
c)
Eliminacja pętli
x
2
-x
1
-x
2
c
2
d)
Eliminacja węzła
x
1
c
2
x
1
a
21
x
2
x
2
a
12
a
21
x
0
c
1
a
12
a
21
x
0
c
1
a
21
a
2
+
1
-
a
1
1-a
1
a
2
+
1
-
a
1
1-a
1
e)
Eliminacja połączenia równoległego
f)
Eliminacja pętli własnej węzła
x
2
c
1
a
21
+
c
2
x
2
x
0
h
20
x
2
a
12
a
21
x
0
a
2
+
1
-
a
1
Rys. 3.1
ca
121
+
c
( )
( ) ( )
1a
−
2
ca
+−
1 a c
h
=
1
=
121
1 2
20
aa
1a 1a aa
− − −
1a
−−
−
12 21
1
2
12 21
2
1a
1
Uwzględniając, że
1a a 1a a
−=− −=−
2
11
,
2
22
otrzymujemy
h
=
ca ca
121 211
−
stąd
x hx
= =
ca ca
−
x
(3.1)
20
2
20 0
0
aa aa
−
aa aa
−
11 22
12 21
11 22
12 21
- 4 -
1
-
a
1
121 211
Obwody i Układy
M
ateriały
P
omocnicze
Analiza układów za pomocą grafów przepływowych
v.1.1
Przykład 4.
Przykład redukcji grafu zawierającego dwie pętle oparte o ten sam węzeł.
a)
Graf wyjściowy
b)
Eliminacja pętli
x
2
-x
3
-x
2
c) Eliminacja pętli
ba
2
b
x
1
a
1
x
2
a
2
a
3
x
4
a
1
1 - ba
2
x
2
a
2
a
3
x
4
x
1
a
1
a
2
x
3
a
3
x
4
x
1
ba
2
x
2
c
c
1 - ba
2
c
d)
Eliminacja pętli
x
4
-x
3
-x
4
oraz węzła
x
3
e)
Eliminacja pętli własnej węzła
x
4
x
1
a
1
a
2
a
3
1 - ba
2
x
4
a
1
a
2
a
3
1 - ba
2
h
=
aaa
123
41
ca
2
a
3
1 - ba
2
ca
2
a
3
1 - ba
2
1ba caa
−−
1
-
2
2 3
x
1
x
4
Rys. 3.2
Przykład 5.
a)
Graf wyjściowy
b)
Eliminacja pętli własnej
g
c)
Eliminacja węzła
x
2
a
x
3
a
1
x
2
e
x
3
x
3
x
2
e
a
1
g
d
f
1
f
1
ec
d
b
b
f
c
bc
x
4
c
dc
x
1
x
1
x
4
x
1
x
4
a
1 - g
f
1 - g
a
1
=
f
1
=
d)
Eliminacja węzła
x
3
e)
f)
Eliminacja pętli własnej
p
x
1
bc
x
4
dc + f
1
ec
x
1
q
x
4
h
41
=
q
1 - p
a
1
ec
p
x
1
x
4
q = bc + a
1
ec
p = dc + f
1
ec
Rys. 3.3
bc
+
aec
( )
( )( )
bc a e c
+
1g
−
bc 1 g aec
−+
h
=
1
=
=
(3.2)
41
( )
1dcf c
fec
1dc1g f c
− −−
1
1dc
1g
−+
−
- 5 -
−+
Plik z chomika:
sylwiam76
Inne pliki z tego folderu:
Jaworski J - Teoria grafów.7z
(550 KB)
Korzan B - Grafy, hipergrafy i sieci.pdf
(25380 KB)
Wilson R - Wprowadzenie do teorii grafow. wyd 2.pdf
(25288 KB)
Algorytmy grafowe.pdf
(430 KB)
Grafy - zagadnienia.rar
(1228 KB)
Inne foldery tego chomika:
_Rozwiązania
Analiza
Analiza matematyczna i algebra
Ciekawostki
Logika i Teoria Mnogosci
Zgłoś jeśli
naruszono regulamin