GII TÊCH MẢNG
Trang 42
CHỈÅNG 4

CẠC MA TRÁÛN MẢNG V PHẢM VI ỈÏNG DỦNG

4.1. GIÅÏI THIÃÛU:
Sỉû trçnh by r rng chênh xạc ph håüp våïi mä hçnh toạn hc l bỉåïc âáưu tiãn
trong gii têch mảng âiãûn. Mä hçnh phi diãùn t âỉåüc âàûc âiãøm ca cạc thnh pháưn mảng
âiãûn riãng biãût nhỉ mäúi liãn hãû chi phäúi giỉỵa cạc thnh pháưn trong mảng. Phỉång trçnh
ma tráûn mảng cung cáúp cho mä hçnh toạn hc nhỉỵng thûn låüi trong viãûc gii bàòng mạy
tênh säú.
Cạc thnh pháưn ca ma tráûn mảng phủ thüc vo viãûc chn cạc biãún mäüt cạch
âäüc láûp, cọ thãø l dng hồûc ạp. Vç l âọ, cạc thnh pháưn ca ma tráûn mảng s l täøng
tråí hay täøng dáùn.
Âàûc âiãøm riãng ca cạc th
nh pháưn mảng âiãûn cọ thãø âỉåüc trçnh by thûn låüi
trong hçnh thỉïc hãû thäúng ma tráûn gäúc. Ma tráûn diãùn t âỉåüc âàûc âiãøm tỉång ỉïng ca mäùi
thnh pháưn, khäng cung cáúp nhiãưu thäng tin liãn quan âãún kãút näúi mảng âiãûn. Nọ l cáưn
thiãút, vç váûy biãún âäøi hãû thäúng ma tráûn gäúc thnh ma tráûn mảng l diãùn t âỉåüc cạc âàûc
tênh quan hãû trong lỉåïi âiãûn.
Hçnh thỉïc ca ma tráûn mảng âỉåüc dng trong phỉång trçnh âàûc tênh phủ thüc
vo cáúu trục lm chøn l nụt hay vng. Trong cáúu trục nụt lm chøn biãún âỉåüc chn
l nụt ạp v nụt dng. Trong cáúu trục vng lm chøn biãún âỉåü
c chn l vng âiãûn ạp
v vng dng âiãûn.
Sỉû tảo nãn ma tráûn mảng thêch håüp l pháưn viãûc tênh toạn ca chỉång trçnh mạy tênh säú
cho viãûc gii bi toạn hãû thäúng âiãûn.
4.2. GRAPHS.
Âãø diãùn t cáúu trục hçnh hc ca mảng âiãûn ta cọ thãø thay thãú cạc thnh pháưn ca
mảng âiãûn bàòng cạc âoản âỉåìng thàóng âån khäng kãø âàûc âiãøm ca cạc thnh pháưn.
Nhaùnh cuớa graph lión thọng khọng chổùa trong cỏy õổồỹc goỹi laỡ nhaùnh buỡ cỏy, tỏỷp
hồỹp caùc nhaùnh naỡy khọng nhỏỳt thióỳt phaới lión thọng vồùi nhau õổồỹc goỹi laỡ buỡ cỏy. Buỡ cỏy
laỡ phỏửn buỡ cuớa cỏy. Sọỳ nhaùnh buỡ cỏy l cuớa graph lión thọng coù e nhaùnh laỡ:
l = e - b
Tổỡ phổồng trỗnh (4.1) ta coù
l = e - n + 1 (4.2)
Cỏy vaỡ buỡ cỏy tổồng ổùng cuớa graph cho trong hỗnh 4.1c õổồỹc trỗnh baỡy trong hỗnh 4.2 Nóỳu nhaùnh buỡ cỏy õổồỹc cọỹng thóm vaỡo cỏy thỗ kóỳt quaớ graph bao gọửm mọỹt õổồỡng
kờn õổồỹc goỹi laỡ voỡng. Mọựi nhaùnh buỡ cỏy õổồỹc cọỹng thóm vaỡo seợ taỷo thaỡnh mọỹt hay nhióửu
voỡng. Voỡng chố gọửm coù mọỹt nhaùnh buỡ cỏy õọỹc lỏỷp thỗ goỹi laỡ voỡng cồ baớn. Bồới vỏỷy, sọỳ
G
G
G
(a)

Nhaùnh cỏy
Nhaùnh buỡ cỏy
e = 7
n = 5
b = 4
l = 3
4
1
2
3
0
GIAI TấCH MANG
Trang 44
voỡng cồ baớn õuùng bũng sọỳ nhaùnh buỡ cỏy cho trong phổồng trỗnh (4.2). Sổỷ õởnh hổồùng
cuớa voỡng cồ baớn õổồỹc choỹn giọỳng nhổ chióửu cuớa nhaùnh buỡ cỏy. Voỡng cồ baớn cuớa graph
cho trong hỗnh 4.2 õổồỹc trỗnh baỡy trong hỗnh 4.3. Vóỳt cừt laỡ tỏỷp hồỹp cuớa caùc nhaùnh, nóỳu boớ õi hoỷc chia graph lión thọng thaỡnh hai graph
con lión thọng. Nhoùm vóỳt cừt coù thóứ choỹn õọỹc lỏỷp duy nhỏỳt nóỳu mọựi vóỳt cừt chố bao gọửm
mọỹt nhaùnh cỏy. Vóỳt cừt õọỹc lỏỷp nhổ vỏỷy goỹi laỡ vóỳt cừt cồ baớn. Sọỳ vóỳt cừt cồ baớn õuùng

4
3
2
1
5
Hỗnh 4.3 : Voỡng cồ baớn õởnh hổồùng theo graph lión thọng
F
GE
4
0
31 2
7
6
4
3
2
1
5
Hỗnh 4.4 : Vóỳt cừt cồ baớn õởnh hổồùng theo graph lión thọng
B
D
C
A
0
1
4
2
3
GII TÊCH MẢNG
Trang 45

trong hçnh 4.2.
Ma tráûn A l hçnh chỉỵ nháût v l duy nháút. Nãúu hng ca A sàõp xãúp theo mäüt cáy riãng
biãût thç ma tráûn trãn cọ thãø phán chia thnh cạc ma tráûn con A
b
cọ kêch thỉåïc b x (n-1)
v A
t
cọ kêch thỉåïc l l x (n-1). Säú hng ca ma tráûn A
b
tỉång ỉïng våïi säú nhạnh cáy v
säú hng ca ma tráûn A
t
tỉång ỉïng våïi säú nhạnh b cáy. Ma tráûn phán chia ca graph
trãn hçnh 4.2 âỉåüc trçnh by nhỉ sau:
 =
1
1
1

-1
-1
-1 1
-11
-1 1
1
-1
4
1 2 3
GIAI TấCH MANG
Trang 46
A
b
laỡ ma trỏỷn vuọng khọng duy nhỏỳt vồùi haỷng (n -1).
4.3.3. Ma trỏỷn hổồùng õổồỡng - nhaùnh cỏy K:
Hổồùng cuớa caùc nhaùnh cỏy õóỳn caùc õổồỡng trong 1 cỏy õổồỹc trỗnh baỡy bũng ma trỏỷn hổồùng
õổồỡng - nhaùnh cỏy. Vồùi 1 õổồỡng õổồỹc õởnh hổồùng tổỡ 1 nuùt qui chióỳu. Caùc phỏửn tổớ cuớa
ma trỏỷn naỡy laỡ:

= 1 (4.3)
Do õoù: K
t
= A
b
-1
(4.4)
4.3.4. Ma trỏỷn vóỳt cừt cồ baớn B.
Lión hóỷ giổợa nhaùnh vồùi vóỳt cừt cồ baớn cuớa graph lión thọng õổồỹc thóứ hióỷn trong
ma trỏỷn vóỳt cừt cồ baớn B. Caùc thaỡnh phỏửn cuớa ma trỏỷn laỡ.
nuù
t
nuù
t
1
2
3
4
5
6
7
e
A =
-1
-1
-1
-1 1
-11
-1 1
1 -1