GII TÍCH MNG
Trang 42
CHƯƠNG 4
CÁC MA TRN MNGPHM VI NG
DNG
4.1. GII THIU:
S trình bày rõ ràng chính xác phù hp vi mô hình toán hc là bước đầu tiên
trong gii tích mng đin. Mô hình phi din t đưc đặc đim ca các thành phn
mng đin riêng bit như mi liên h chi phi gia các thành phn trong mng. Phương
trình ma trn mng cung cp cho mô hình toán hc nhng thun li trong vic gii bng
máy tính s.
Các thành phn ca ma trn mng ph thuc vào vic chn các biến mt cách
độc lp, có th là dòng hoc áp. Vì l đó, các thành phn ca ma trn mng s là tng
tr hay tng dn.
Đặc đim riêng ca các thành phn mng đin có th được trình bày thun li
trong hình thc h thng ma trn gc. Ma trn din t được đặc đim tương ng ca
mi thành phn, không cung cp nhiu thông tin liên quan đến kết ni mng đin. Nó là
cn thiết, vì vy biến đổi h thng ma trn gc thành ma trn mng là din t được các
đặc tính quan h trong lưới đin.
Hình thc ca ma trn mng được dùng trong phương trình đặc tính ph thuc
vào cu trúc làm chun là nút hay vòng. Trong cu trúc nút làm chun biến được chn
là nút áp và nút dòng. Trong cu trúc vòng làm chun biến được chn là vòng đin áp
và vòng dòng đin.
S to nên ma trn mng thích hp là phn vic tính toán ca chương trình máy tính s
cho vic gii bài toán h thng đin.
4.2. GRAPHS.
Để din t cu trúc hình hc ca mng đin ta có th thay thế các thành phn ca
mng đin bng các đon đường thng đơn không k đặc đim ca các thành phn.
Đường thng phân đon được gi là nhánh và phn cui ca chúng được gi là nút. Nút
và nhánh ni lin vi nhau nếu nút là phn cui ca mi nhánh. Nút có th được ni
vi mt hay nhiu nhánh.
Graph cho thy quan hnh hc ni lin gia các nhánh ca mng đin. Tp
hp con ca các graph là các nhánh. Graph được gi là liên thông nếu và ch nếu có
đường ni gia mi cp đim vi nhau. Mi nhánh ca graph liên thông được n định
hướng thì nó s định theo mt hướng nht định. S biu din ca h thng đin và
hướng tương ng ca graph trình bày trong hình 4.1.
Cây là mt graph liên thông cha tt c các nút ca graph nhưng không to thành mt
vòng kín. Các thành phn ca cây được gi là nhánh cây nó là tp hp con các nhánh
ca graph liên thông đã chn trước. S nhánh cây b qui định cho mi cây là:
b = n - 1 (4.1)
Vi: n là s nút ca graph
GII TÍCH MNG
Trang 43
0
2
1
Hình 4.1 : t h thng đin.
(a) Sơ đ mt pha.
(b) Sơ đ th t thun.
(c) Graph đnh hướng.
(c)
7
5
1
2 3
4
3
4
6
(b)
0
2
3
4
(a)
G
G
G
1
Nhánh ca graph liên thông không cha trong cây được gi là nhánh bù cây, tp
hp các nhánh này không nht thiết phi liên thông vi nhau được gi là bù cây. Bù cây
là phn bù ca cây. S nhánh bù cây l ca graph liên thông có e nhánh là:
l = e - b
T phương trình (4.1) ta có
l = e - n + 1 (4.2)
Cây và bù cây tương ng ca graph cho trong hình 4.1c đưc trình bày trong hình 4.2
7
2
6 4
4
e = 7
n = 5
b = 4
l = 3
3
2
1
5
0
3
Nhánh bù cây
Nhánh cây
1
Hình 4.2 : Cây và bù cây ca graph liên thông đnh hướng
Nếu nhánh bù cây được cng thêm vào cây thì kết qu graph bao gm mt
đường kín được gi là vòng. Mi nhánh bù cây được cng thêm vào s to thành mt
hay nhiu vòng. Vòng ch gm có mt nhánh bù cây độc lp thì gi là vòng cơ bn. Bi
vy, s vòng cơ bn đúng bng s nhánh bù cây cho trong phương trình (4.2). S định
GII TÍCH MNG
Trang 44
hướng ca vòng cơ bn được chn ging như chiu ca nhánh bù cây. Vòng cơ bn ca
graph cho trong hình 4.2 được trình bày trong hình 4.3.
7
6 4
3
2
1
5
2 3
E G
F
1
4
0
Hình 4.3 : Vòng cơ bn đnh hướng theo graph liên thông
Vết ct là tp hp ca các nhánh, nếu b đi hoc chia graph liên thông thành hai graph
con liên thông. Nhóm vết ct có th chn độc lp duy nht nếu mi vết ct ch bao gm
mt nhánh cây. Vết ct độc lp như vy gi là vết ct cơ bn. S vết ct cơ bn đúng
bng s nhánh cây. S định hướng ca vết ct cơ bn được chn ging như hướng ca
nhánh cây. Vết ct cơ bn ca graph cho trong hình 4.2 được trình bày trong hình 4.4
7
6 4
3
2
1
5
B
D
C
3
2
A
4
1
0
Hình 4.4 : Vết ct cơ bn đnh hướng theo graph liên thông
4.3. MA TRN THÊM VÀO.
4.3.1. Ma trn thêm vào nhánh - nút Â.
S liên h gia nhánh và nút trong graph liên thông trình bày bi ma trn thêm
vào nhánh nút. Các thành phn ca ma trn được trình bày như sau:
aj = 1 : Nếu nhánh th i và nút th j có chiu hướng t nhánh i vào nút j
aj = -1: Nếu nhánh th i và nút th j có chiu hướng t nhánh i ra khi nút j
a
j = 0 : Nếu nhánh th i và nút th j không có mi liên h vi nhau.
Kích thước ca ma trn là e x n, vi e là s nhánh và n là s nút ca graph. Ma trn
thêm vào nhánh nút cho trong graph hình 4.2 trình bày như trên. Vi:
GII TÍCH MNG
Trang 45
eia
j
ji ...,2,10
4
0
==
=
n 4
0 1 2 3
e
Đ =
1
7
6
5
4
3
2
1
1 -1
1 -1
-1 1
-1
-1
-1
1
-1
1
1
Các ct ca ma trn  là ph thuc tuyến tính. Vì vy hng ca  < n.
4.3.2. Ma trn thêm vào nút A.
Các nút ca graph liên thông có th chn làm nút qui chiếu. Nút qui chiếu có th
thay đổi, nó được xem như mt nút trong graph có th cân nhc khi n định c th mt
nút nào đó làm nút qui chiếu. Ma trn thu được t ma trn  b đi ct tương ng vi
nút chn làm nút qui chiếu là ma trn nhánh - nút A, nó s được gi là ma trn nút. Kích
thước ca ma trn là e x (n-1) và hng là n-1 = b.
Vi: b là s nhánh cây ca graph. Chn nút 0 làm nút qui chiếu th hin trên graph
trong hình 4.2. nút
e 4 1 2
1
2
3
4
5
6
7
A =
-1 1
1 -1
1 -1
-1 1
-1
-1
-1
3
Ma trn A là hình ch nht và là duy nht. Nếu hàng ca A sp xếp theo mt cây riêng
bit thì ma trn trên có th phân chia thành các ma trn con Ab có kích thước b x (n-1)
và At có kích thước là l x (n-1). S hàng ca ma trn Ab tương ng vi s nhánh cây và
s hàng ca ma trn At tương ng vi s nhánh bù cây. Ma trn phân chia ca graph
trên hình 4.2 được trình bày như sau:
GII TÍCH MNG
Trang 46
nút nút
2 3 4
1
2
3
4
5
6
7
e
A =
1
-1
-1
-1 1
-1 1
-1
1 -1
Các nút
Nhánh bù cây Nhánh cây
Ab
At
e
-1
1
=
Ab là ma trn vuông không duy nht vi hng (n -1).
4.3.3. Ma trn hướng đường - nhánh cây K:
Hướng ca các nhánh cây đến các đường trong 1 cây được trình bày bng ma trn
hướng đường - nhánh cây. Vi 1 đường được định hướng t 1 nút qui chiếu. Các phn
t ca ma trn này là:
kij = 1: Nếu nhánh cây i nm trong đường t nút j đến nút qui chiếu và được định hướng
cùng hướng.
k
ij = -1: Nếu nhánh cây i nm trong đưng t nút j đến nút qui chiếu nhưng được
định hướng ngược hướng.
k
ij = 0: Nếu nhánh cây i không nm trong đường t nút j đến nút qui chiếu.
Vi nút 0 là nút qui chiếu ma trn hướng đường - nhánh cây liên kết vi cây được trình
bày hình 4.2 có dng dưới đây.
đường
1
2
3
4
Nhánh cây
K =
-1
-1
-1 -1
-1
4
1 2 3
Đây là ma trn vuông không duy nht vi cp là (n-1). Ma trn hướng - đường nhánh
cây liên h nhánh cây vi các đường nhánh cây ni đến nút qui chiếu và ma trn Ab liên
kết các nhánh cây vi các nút. Vì vy có t l tương ng 1:1 gia các đường và các nút.
A
b.Kt = 1 (4.3)
Do đó: Kt = Ab-1 (4.4)