close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
.
kazanskij ordena lenina i ordena trudowogo
krasnogo znameni gosudarstwennyj
uniwersitet
IMENI w. i. ulxqnowa{lenina
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
algoritmy re{eniq optimizacionnyh zada~
na grafah
u^EBNOE POSOBIE
kAZANX
kAZANSKIJ GOSUDARSTWENNYJ UNIWERSITET
2006
.
sodervanie
1. oSNOWNYE OPREDELENIQ I OBOZNA^ENIQ
sTR.
4
2. pOSTROENIE KRAT^AJ[IH PUTEJ
11
3. oSTOWY MINIMALXNOGO WESA
22
4. zADA^A O NAIBOLX[EM PAROSO^ETANII W
DWUDOLXNOM GRAFE
30
5. nAIMENX[EE WER[INNOE POKRYTIE W DWUDOLXNOM GRAFE 40
6. CBALANSIROWANNAQ ZADA^A POSTROENIQ NAIBOLX[EGO
PAROSO^ETANIQ MINIMALXNOGO WESA W DWUDOLXNOM GRAFE
7. nESBALANSIROWANNAQ ZADA^A POSTROENIQ NAIBOLX[EGO
44
PAROSO^ETANIQ MINIMALXNOGO WESA W DWUDOLXNOM GRAFE
55
oTWETY
59
lITERATURA
65
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
1.
oSNOWNYE OPREDELENIQ I OBOZNA^ENIQ
w POSOBII PRIWODQTSQ I [email protected] ALGORITMY RE[ENIQ
NEKOTORYH IZWESTNYH OPTIMIZACIONNYH ZADA^, KOTORYE STAWQTSQ W TERMINAH TEORII GRAFOW. pREVDE, ^EM PRISTUPITX K
POSTANOWKE \TIH ZADA^ I OPISANI@ METODOW, PRIWEDEM NEKOTORYE NEOBHODIMYE W DALXNEJ[EM OPREDELENIQ I OBOZNA^ENIQ,
MNOGIE IZ KOTORYH [email protected] TRADICIONNYMI DLQ TEORII GRAFOW I DISKRETNOJ OPTIMIZACII.
pOD GRAFOM G(V; R) BUDEM PONIMATX SOWOKUPNOSTX KONE^NOGO MNOVESTWA V \LEMENTOW, NAZYWAEMYH WER[INAMI ILI UZLAMI GRAFA, I KONE^NOGO MNOVESTWA R, SOSTAWLENNOGO IZ UPORQDO^ENNYH I (ILI) NEUPORQDO^ENNYH PAR \LEMENTOW MNOVESTWA V ,
NAZYWAEMYH REBRAMI GRAFA. ~EREZ jV j, jRj BUDEM OBOZNA^ATX
KOLI^ESTWO \LEMENTOW W MNOVESTWAH V , R SOOTWETSTWENNO. bUDEM S^ITATX, ^TO, WO-PERWYH, SITUACIQ, KOGDA V = I ODNOWREMENNO R =
6 W GRAFE NEDOPUSTIMA; WO-WTORYH, UPORQDO^ENNYE I NEUPORQDO^ENNYE PARY IZ R MOGUT SOSTOQTX KAK IZ RAZNYH, TAK I SOWPADA@]IH \LEMENTOW MNOVESTWA V ; W-TRETXIH,
KAVDOMU \LEMENTU IZ V MOVET SOOTWETSTWOWATX W R NE BOLEE
ODNOJ PARY, A KAVDYM DWUM OTLI^NYM DRUG OT DRUGA \LEMENTAM IZ V W MNOVESTWE R MOVET SOOTWETSTWOWATX NE BOLEE DWUH
UPORQDO^ENNYH PAR ILI ODNOJ NEUPORQDO^ENNOJ PARY.
pUSTX W MNOVESTWE R NEKOTORAQ PARA r SOOTWETSTWUET \LEMENTAM a; b 2 V , a =
6 b. pUSTX PARA r UPORQDO^ENA, NAPRIMER,
a { PERWYJ, A b { WTOROJ \LEMENTY PARY, TOGDA PARU r BUDEM ZAPISYWATX W WIDE (a; b), (?
a;!b) ILI (b;?a). eSLI W PARE r
PERWOJ QWLQETSQ WER[INA b, A WTOROJ { a, TO PARU BUDEM OBOZNA^ATX (b; a), (?
b;!a) ILI (a;?b). uPORQDO^ENNU@ PARU IZ R NAZY4
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
[email protected] ORIENTIROWANNYM REBROM GRAFA. eSLI ORIENTIROWANNOE
REBRO IMEET WID (a; b), TO a I b [email protected], SOOTWETSTWENNO, NA^ALXNOJ I KONE^NOJ WER[INAMI REBRA. oTMETIM, ^TO R MOVET
SODERVATX ODNO IZ ORIENTIROWANNYH REBER (a; b) ILI (b; a), A
TAKVE OBA \TIH REBRA ODNOWREMENNO.
pUSTX TEPERX WYBRANNAQ IZ R PARA r NE QWLQETSQ UPORQDO^ENNOJ, T. E. PORQDOK WER[IN a, b, OBRAZU@]IH EE, NE IMEET
ZNA^ENIQ. tAKU@ PARU \LEMENTOW a, b BUDEM ZAPISYWATX W KRUGLYH SKOBKAH W PROIZWOLXNOM PORQDKE, T. E. W WIDE (a; b) LIBO
(b; a), S^ITAQ, ^TO (a; b) = (b; a). sAMO REBRO r BUDEM NAZYWATX
NEORIENTIROWANNYM. eSLI REBRO r ZAPISANO W WIDE (a; b), TO
WER[INY a I b BUDEM NAZYWATX, SOOTWETSTWENNO, NA^ALXNOJ I
KONE^NOJ WER[INAMI REBRA r.
gRAFI^ESKI, KAK OBY^NO PRINQTO, WER[INY GRAFA BUDEM
IZOBRAVATX TO^KAMI (KRUGAMI), A REBRA { SOEDINQ@]IMI \TI
TO^KI LINIQMI. eSLI REBRO r 2 R ORIENTIROWANO, NAPRIMER,
r = (a; b) = (?
a;!b), TO NA RISUNKE EGO [email protected] LINIEJ SO
STRELKOJ OT TO^KI a K TO^KE b. eSLI VE REBRO r = (a; b) NEORIENTIROWANO, TO TO^KI a, b NA RISUNKE [email protected] LINIEJ BEZ
STRELKI. eSLI \LEMENTAM a; b 2 V W MNOVESTWE R NE SOOTWETSTWUET NI ODNOJ PARY, TO SOEDINQ@]EJ LINII MEVDU TO^KAMI
a, b NA RISUNKE NET.
pUSTX TEPERX PARE r 2 R SOOTWETSTWUET TOLXKO ODIN \LEMENT a 2 V . tOGDA REBRO r NAZYWAETSQ PETLEJ WER[INY a W
GRAFE. uSLOWIMSQ DLQ OB]NOSTI IZLOVENIQ S^ITATX, ^TO TAKAQ
PARA TOVE MOVET BYTX KAK UPORQDO^ENNOJ, TAK I NEUPORQDO^ENNOJ. w PERWOM SLU^AE PARU r BUDEM ZAPISYWATX W WIDE (?!
a; a),
I PETL@ r NAZYWATX ORIENTIROWANNOJ, A WO WTOROM SLU^AE POLAGATX r = (a; a) I NAZYWATX PETL@ r NEORIENTIROWANNOJ. nA
5
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
RISUNKE ORIENTIROWANNAQ ILI NEORIENTIROWANNAQ PETLQ IZOBRAVAETSQ LINIEJ OT TO^KI a K TO^KE a SO STRELKOJ ILI BEZ
STRELKI SOOTWETSTWENNO.
eSLI KAVDYM DWUM OTLI^NYM DRUG OT DRUGA \LEMENTAM
a; b 2 V W MNOVESTWE R SOOTWETSTWUET NEORIENTIROWANNOE REBRO (a; b) LIBO PARA PROTIWOPOLOVNO ORIENTIROWANNYH REBER
(?
a;!b), (?
b;!a), TO GRAF NAZYWAETSQ POLNYM.
eSLI V = I R = , TO GRAF G(V; R) BUDEM NAZYWATX
PUSTYM I OBOZNA^ATX G .
gRAF NAZYWAETSQ ORIENTIROWANNYM ILI NEORIENTIROWANNYM, ESLI WSE REBRA GRAFA, SOOTWETSTWENNO ORIENTIROWANY
ILI NEORIENTIROWANY, I NAZYWAETSQ SME[ANNYM, ESLI SREDI
REBER ESTX KAK ORIENTIROWANNYE, TAK I NEORIENTIROWANNYE.
gRAF G(V ; R) NAZYWAETSQ PODGRAFOM GRAFA G(V; R), ESLI
V V , R R.
pUSTX \LEMENTAM a; b 2 V SOOTWETSTWUET ORIENTIROWANNOE
ILI NEORIENTIROWANNOE REBRO r = (a; b) 2 R. tOGDA WER[INY
a I b BUDEM NAZYWATX SMEVNYMI (SOSEDNIMI) W GRAFE, A TAKVE
KONCEWYMI WER[INAMI REBRA r. bUDEM GOWORITX, ^TO WER[INA I REBRO W GRAFE INCIDENTNY DRUG DRUGU ([email protected] DRUG
DRUGA), ESLI WER[INA QWLQETSQ DLQ REBRA KONCEWOJ. eSLI DWA
REBRA INCIDENTNY ODNOJ I TOJ VE WER[INE, TO REBRA [email protected] INCIDENTNYMI DRUG DRUGU.
pUSTX G = G(V; R), R =
6 , | PROIZWOLXNYJ, T. E. ORIENTIROWANNYJ, NEORIENTIROWANNYJ ILI SME[ANNYJ, GRAF, R1
{ PODMNOVESTWO WSEH ORIENTIROWANNYH REBER MNOVESTWA R, A
R2 = R n R1. pUSTX0 R1 =
6 . pOSTROIM MNOVESTWO NEORIENTIROWANNYH REBER R1, SOOTWETSTWU@]IH MNOVESTWU R1, SLEDU@]IM OBRAZOM. dLQ KAVDOJ PARY \LEMENTOW a; b 2 V TAKIH,
6
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
^TO a, b [email protected] SMEVNYMI WER[INAMI HOTQ BY ODNOGO REBRA (?
a;!b) ILI (?
b;!a) IZ R1, W MNOVESTWO R01 0WKL@^AETSQ
ODNO
0
NEORIENTIROWANNOE REBRO (a; b). pOLOVIM
R = R1 [ R2. eSLI
R1 = , TO ESTESTWENNO POLOVITX R0 = R. ~EREZ G0 = G(V; R0 )
OBOZNA^IM GRAF0 , POLU^ENNYJ PUTEM ZAMENY W GRAFE G MNOVESTWA
R NA R . qSNO, ^TO ESLI G { NEORIENTIROWANNYJ GRAF,
TO G0 = G.
pUSTX n = jV j, I = f1; :::; ng. oBOZNA^IM WER[INY GRAFA G
^EREZ0 v1,..., v .0 pUSTX IZ 0 NEORIENTIROWANNYH REBER MNOVESTWA R GRAFA G = G(V; R ) POSTROENO KONE^NOE UPORQDO^ENNOE
MNOVESTWO
n
C = C (v 1 ; v p ) = ((v 1 ; v 2 ); (v 2 ; v 3 ); :::; (v p?1; v p )), (1.1)
i
i
i
i
i
i
i
i
GDE i1; :::i 2 I , p 2, S, WOOB]E GOWORQ, POWTORQ@]IMISQ
\LEMENTAMI TAKOE, ^TO KONE^NAQ WER[INA [email protected] REBRA, KROME POSLEDNEGO, SOWPADAET S NA^ALXNOJ WER[INOJ SLEDU@]EGO
REBRA. tOGDA MNOVESTWO (1.1) NAZOWEM CEPX@ (MAR[RUTOM) W
GRAFE G. bUDEM GOWORITX, ^TO \TA CEPX SOEDINQET WER[INY
v 1 , v p I PROHODIT ^EREZ WER[INY v 1 ,..., v p , PRI^EM, WER[INY v 1 , v p NAZOWEM, SOOTWETSTWENNO, NA^ALXNOJ I KONE^NOJ, A
v 2 ,...,v p?1 { PROMEVUTO^NYMI WER[INAMI CEPI C . tE WER[INY v 2 V , i 2 I , KOTORYE WHODQT W UPORQDO^ENNOE MNOVESTWO
?!
V (C ) = (v 1 ; v 2 ; :::; v p) BUDEM NAZYWATX OPREDELQ@]IMI CEPX
C I OBOZNA^ATX ^EREZ V (C ). eSLI W MNOVESTWE ?!
V (C ) WER[INA
v j WSTRE^AETSQ k RAZ, GDE k 1, TO BUDEM GOWORITX, ^TO CEPX
(1.1) PROHODIT ^EREZ \TU WER[INU k RAZ.
zAMETIM, ^TO CEPX FAKTI^ESKI ZADAET PORQDOK OBHODA OPREDELQ@]IH EE WER[IN, NEZAWISIMO OT ORIENTACII INCIDENTNYH
p
i
i
i
i
i
i
i
i
i
i
i
i
7
i
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
IM REBER. kROME TOGO, NA^ALXNAQ I KONE^NAQ WER[INY CEPI MOGUT BYTX ODNOWREMENNO I PROMEVUTO^NYMI WER[INAMI \TOJ
CEPI.
pUSTX SME[ANNYJ GRAF G ZADAN NA RIS
. 1, A SOOTWETSTWU0
@]IJ EMU NEORIENTIROWANNYJ GRAF G { NA RIS. 2. tOGDA
s1 = s1(v4; v1) = ((v4; v5); (v5; v3); (v3; v1)) { CEPX W GRAFE G BEZ
POWTORENIQ REBER, KOTORAQ PROHODIT ^EREZ KAVDU@ IZ OPREDELQ@]IH EE WER[IN PO ODNOMU RAZU. oTMETIM, ^TO ?!
V (C1) =
(v4; v5; v3; v1), V (C1) = fv4; v5; v3; v1g. cEPX C2 = C2(v4; v3) =
((v4; v6); (v6; v5); (v5; v5); (v5; v4); (v4; v3)) DWAVDY PROHODIT ^EREZ WER[INY v4, v5, PRI^EM, WER[INA v4 QWLQETSQ ODNOWREMENNO NA^ALXNOJ I PROMEVUTO^NOJ, ?!
V (C2) = (v4; v6; v5; v5; v4; v3),
V (C2) = fv4; v6; v5; v3g. w CEPI C3 = C3(v2; v1) = ((v2; v4);
(v4; v5); (v5; v4); (v4; v1)) DWAVDY WSTRE^AETSQ REBRO (v4; v5) I WER[INA v4. eSTESTWENNO, ^TO CEPI C1, C2, C3 [email protected] CEPQMI I
W GRAFE, IZOBRAVENNOM NA RIS. 2.
v 6
?v
1
2
v
v
1
2
-
v
v
6
-
v
v
rIS. 1
v
v
v
v
3
5
4
6
3
5
4
6
rIS. 2
8
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
dALEE, ESLI NA^ALXNAQ WER[INA CEPI SOWPADAET S EE KONE^NOJ WER[INOJ, TO CEPX NAZYWAETSQ CIKLI^ESKOJ. tAK, W GRAFE
NA RIS. 1 CEPI C4 = C4(v2; v2) = ((v2; v4); (v4; v5); (v5; v3); (v3; v4);
(v4; v2)), C5 = C5(v4; v4) = ((v4; v6); (v6; v4)), C6 = C6(v3; v3) =
((v3; v4); (v4; v5); (v5; v3)), C7 = C7(v2; v2) = ((v2; v2)) [email protected]
CIKLI^ESKIMI. cIKLOM NAZOWEM CIKLI^ESKU@ CEPX BEZ POWTORENIQ REBER, W KOTOROJ NA^ALXNAQ, A ZNA^IT, I KONE^NAQ WER[INA NE QWLQETSQ ODNOWREMENNO PROMEVUTO^NOJ, A ^EREZ KAVDU@
SWO@ PROMEVUTO^NU@ WER[INU \TA CEPX PROHODIT TOLXKO ODIN
RAZ. nAPRIMER, CIKLI^ESKIE CEPI C4, C5 NE [email protected] CIKLAMI,
TAK KAK C4 DWAVDY PROHODIT ^EREZ WER[INU v4, A W C5 DWAVDY WHODIT REBRO (v4; v6). cIKLI^ESKIE CEPI C6, C7, O^EWIDNO,
[email protected] CIKLAMI.
cEPX, PROHODQ]AQ ^EREZ KAVDU@ OPREDELQ@]U@ EE WER[INU TOLXKO ODIN RAZ, NAZYWAETSQ PROSTOJ. tAK, CEPX C1 W GRAFE
NA RIS. 1 QWLQETSQ PROSTOJ.
eSLI DLQ [email protected] REBRA (v j ; v j+1 ) CEPI (1.1), WHODQ]EGO W
0
!
R1, W MNOVESTWE R1 ESTX ORIENTIROWANNOE REBRO (?
v????
j ; v j+1 ), ILI
W (1.1) NET REBER, WHODQ]IH W R01, TO TAKU@ CEPX BUDEM NAZYWATX ORIENTIROWANNOJ W GRAFE G. tAK, CEPI C1, C3, C7 [email protected] ORIENTIROWANNYMI W GRAFE G NA RIS. 1, A CEPI C2, C4,
C5, C6 NE [email protected] ORIENTIROWANNIMI W GRAFE G. o^EWIDNO,
^TO W NEORIENTIROWANNOM GRAFE [email protected] CEPX QWLQETSQ ORIENTIROWANNOJ
. cEPI C1 { C7 [email protected] ORIENTIROWANNYMI W GRAFE
G0 NA RIS. 2.
bUDEM NAZYWATX ORIENTIROWANNU@ CEPX S NA^ALXNOJ WER[INOJ v 1 I KONE^NOJ v p PUTEM IZ v 1 W v p I OBOZNA^ATX TAKVE
^EREZ P (v 1 ; v p ), ORIENTIROWANNU@ CIKLI^ESKU@ CEPX { CIKLI^ESKIM PUTEM, ORIENTIROWANNYJ CIKL { KONTUROM, A ORIi
i
i
i
i
i
i
i
9
i
i
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
ENTIROWANNOE REBRO { DUGOJ. pROSTU@ CEPX, KOTORAQ QWLQETSQ
PUTEM, BUDEM NAZYWATX PROSTYM PUTEM. nAPRIMER, W SME[ANNOM GRAFE, IZOBRAVENNOM NA RIS. 1, CEPX C1 QWLQETSQ PROSTYM
PUTEM, CEPI C7 I C8 = C8(v5; v5) = ((v5; v4); (v4; v3); (v3; v5)) [email protected] KONTURAMI, A CEPX C9 = C9(v4; v4) = ((v4; v5); (v5; v3);
(v3; v5); (v5; v6); (v6; v4)) { ORIENTIROWANNYJ CIKLI^ESKIJ PUTX,
NO NE KONTUR.
dALEE, GOWORQT, ^TO WER[INA a SWQZANA S WER[INOJ b (DOSTIVIMA IZ WER[INY b) ILI, ^TO WER[INY a, b GRAFA SWQZANY,
ESLI W \TOM GRAFE SU]ESTWUET CEPX, DLQ KOTOROJ ODNA IZ \TIH
WER[IN BUDET NA^ALXNOJ, A WTORAQ { KONE^NOJ WER[INAMI CEPI. gRAF NAZYWAETSQ SWQZNYM, ESLI [email protected] DWE EGO WER[INY
SWQZANY. gRAF, W KOTOROM NE SU]ESTWUET CIKLOW, NAZYWAETSQ ACIKLI^ESKIM. nEORIENTIROWANNYJ SWQZNYJ ACIKLI^ESKIJ
GRAF NAZYWAETSQ DEREWOM. gRAF NA RIS. 1 NE QWLQETSQ ACIKLI^ESKIM, NO QWLQETSQ SWQZNYM, A EGO PODGRAF, IZOBRAVENNYJ NA
RIS. 3, BUDET DEREWOM.
v
?
v
1
2
v
6
v
3
4
rIS. 3
10
v
v
5
6
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
2.
pOSTROENIE KRAT^AJ[IH PUTEJ
pUSTX G = G(V; R) | PROIZWOLXNYJ GRAF, n = jV j, m =
jRj. pUSTX KAVDOMU REBRU (a; b) 2 R GRAFA POSTAWLENO W SOOTWETSTWIE ^ISLO l(a; b). nAZOWEM ^ISLO l(a; b) DLINOJ (WESOM)
REBRA (a; b). gRAF, W KOTOROM DLQ [email protected] REBRA OPREDELENA DLINA (WES), NAZOWEM WZWE[ENNYM. pUSTX P = P (a; b) { PUTX W
GRAFE G IZ WER[INY a W WER[INU b. nAZOWEM DLINOJ PUTI P
SUMMU DLIN WSEH REBER, WHODQ]IH W P I OBOZNA^IM \TU DLINU
^EREZ l(P ).
pUSTX s; t 2 V , s =
6 t, (s; t) { MNOVESTWO WSEH PROSTYH
PUTEJ W GRAFE IZ WER[INY s W WER[INU t. pOLOVIM
l(P ).
(s; t) = Arg 2min
( )
P
s;t
tOGDA [email protected] \LEMENT MNOVESTWA (s; t) NAZYWAETSQ KRAT^AJ[IM PUTEM IZ WER[INY s W WER[INU t, A POD ZADA^EJ OTYSKANIQ KRAT^AJ[EGO PUTI IZ s W t W WZWE[ENNOM GRAFE [email protected]
OTYSKANIE HOTQ BY ODNOGO PUTI P 2 (s; t).
oBOZNA^IM ^EREZ P PUTX W GRAFE G, NE SODERVA]IJ NI
ODNOGO REBRA. eSLI NUVNO POD^ERKNUTX, ^TO PUTI IZ WER[INY
a W WER[INU b [email protected], TO BUDEM ZAPISYWATX P (a; b) = P .
sFORMULIRUEM PERWYJ IZ PRIWODIMYH ZDESX ALGORITMOW
RE[ENIQ POSTAWLENNOJ ZADA^I S USLOWIEM, ^TO DLINY WSEH REBER GRAFA NEOTRICATELXNY.
(dEJKSTRA, 1959).
pOLAGAEM y1 = s, V1 = V , P1 = P 8 v 2 V1, l11 = 0, l1 = +1
8 v 2 V1 n fy1g.
pUSTX UVE IZWESTNY y , V , P , l 8 v 2 V , I k 1.
aLGORITM
2.1
y
v
pOLOVIM
k
k
11
v
k
v
k
v
k
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
V +1 = V n fy g.
dLQ WSEH v 2 V +1 , S^ITAQ, ^TO l(y ; v) = +1 PRI (y ; v) 62 R,
NAHODIM
l +1 = minfl ; l k + l(y ; v)g
I POLAGAEM P +1 = P , ESLI l l k + l(y ; v), I
P +1 = (P k ; (y ; v)), W PROTIWNOM SLU^AE. dALEE POLAGAEM
y +1 = arg 2min l +1.
k
k
k
k
k
v
v
y
k
k
k
v
k
y
v
k
k
k
k
v
v
y
k
k
k
k
k
v
k
v
k+1
V
k
eSLI y +1 = t, TO ALGORITM ZAKAN^IWAET RABOTU, I P (s; t) =
k+1 .
P +1
y
k
k
nETRUDNO PROWERITX, ^TO TRUDOEMKOSTX ALGORITMA 2.1 SOSTAWLQET O(n2 ) OPERACIJ. oBOSNOWANIE ALGORITMA MOVNO NAJTI, NAPRIMER, W RABOTAH ( [1], STR. 343, [2], STR. 178, [3], STR.
45, [7]).
pOD^ERKNEM E]E RAZ, ^TO ALGORITMOM 2.1 KRAT^AJ[IJ PUTX
W GRAFE G = G(V; R) IZ ZADANNOJ WER[INY s W ZADANNU@ WER[INU t MOVNO POSTROITX TOLXKO W SLU^AE, ESLI l(a; b) 0 DLQ
WSEH (a; b) 2 R. pRI NEWYPOLNENII UKAZANNYH USLOWIJ PUTX IZ
s W t BUDET POSTROEN, NO EGO OPTIMALXNOSTX NE GARANTIROWANA.
pOSKOLXKU NA k-OJ ITERACII IZ MNOVESTWA V UDALQETSQ
WER[INA y , TO NA PREDYDU]EJ ITERACII POSTROENIE PUTI P k
IZ WER[INY s W WER[INU y I OTYSKANIE EGO DLINY l k BYLO
ZAWER[ENO.
k+1 =
k+1 {
eSLI NA k-OJ ITERACII ALGORITMA P +1
6 P , TO P +1
KRAT^AJ[IJ PUTX IZ WER[INY s W WER[INU y +1 , A l k+1+1 { EGO
k+1 = P , TO l k+1 = +1,
DLINA, PRI^EM l k+1+1 =
6 +1. eSLI P +1
+1
k
y
k
k
y
k
k
y
y
k
k
12
y
y
k
k
y
k
y
k
k
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
I \TO OZNA^AET OTSUTSTWIE W GRAFE PUTI IZ s W y +1. tAKIM
OBRAZOM, ESLI W REZULXTATE RABOTY ALGORITMA P (s; t) = P ,
TO W GRAFE NE SU]ESTWUET NI ODNOGO, W TOM ^ISLE I PROSTOGO,
PUTI IZ s W t, I ZADA^A NE IMEET RE[ENIQ.
dALEE, U^ITYWAQ SDELANNYE WY[E ZAME^ANIQ, POKAVEM, KAK
ALGORITMOM 2.1 MOVNO OTYSKIWATX KRAT^AJ[IE PUTI IZ ZADANNOJ WER[INY s NE TOLXKO W WER[INU t, NO I WO WSE DRUGIE
WER[INY GRAFA. nAPOMNIM, ^TO KRITERIEM OSTANOWKI RABOTY
ALGORITMA SLUVIT WYPOLNENIE RAWENSTWA y +1 = t. iZMENIM
\TOT KRITERIJ SLEDU@]IM OBRAZOM. pUSTX PRI RE[ENII ZADA^I POSTROENIQ KRAT^AJ[EGO PUTI ALGORITMOM 2.1 PRODELYWAETSQ n ITERACIJ, T. E. OSTANOWKA EGO RABOTY PROISHODIT PRI
k = n. tOGDA y =
6 y 8 i; j = 2; :::; n, i =6 j , I POSTROENNYE PUTI
P2 2 ,..., P n
BUDUT KRAT^AJ[IMI IZ WER[INY y1 = s W WER[INY y2, ..., y SOOTWETSTWENNO. eSTESTWENNO, ^TO SREDI WER[IN y2, ..., y ESTX I
WER[INA t. aLGORITM 2.1 S TAKIM IZMENENNYM KRITERIEM OSTANOWKI NAZOWEM MODIFICIROWANNYM ALGORITMOM 2.1. zAMETIM,
^TO TRUDOEMKOSTX MODIFICIROWANNOGO ALGORITMA 2.1 SOWPADAET S TRUDOEMKOSTX@ ISHODNOGO ALGORITMA.
bUDEM FIKSIROWATX TEPERX W GRAFE G(V; R) W KA^ESTWE s POSLEDOWATELXNO WSE WER[INY MNOVESTWA V I PRIMENQTX KAVDYJ
RAZ MODIFICIROWANNYJ ALGORITM 2.1 DLQ OTYSKANIQ KRAT^AJ[IH PUTEJ IZ s WO WSE OSTALXNYE WER[INY. tOGDA ZA O(n3)
OPERACIJ \TIM ALGORITMOM BUDUT NAJDENY KRAT^AJ[IE PUTI
MEVDU WSEMI PARAMI WER[IN GRAFA G.
bUDEM DALEE, GDE \TO UDOBNO, S^ITATX, ^TO WER[INY GRAFA
G PRONUMEROWANY OT 1 DO n I NA RISUNKAH [email protected] SWOIMI
NOMERAMI.
k
k
i
j
y
y
n
n
n
13
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pRIMER. aLGORITMOM 2.1 TREBUETSQ NAJTI KRAT^AJ[IJ PUTX
IZ WER[INY 1 W WER[INU 6 W SME[ANNOM GRAFE, IZOBRAVENNOM
NA RIS. 4, ESLI l(1; 2) = 4, l(1; 3) = 2, l(2; 5) = 3, l(3; 4) = 2,
l(3; 5) = 4, l(4; 2) = 1, l(4; 6) = 0, l(5; 6) = 3, l(6; 1) = 10.
1
2
4
Q
3
QQ
1
QQs
3
5
6
rIS. 4
rE[ENIE. pERWONA^ALXNO
POLAGAEM y1
=
1,
1
V1 = f1; 2; 3; 4; 5; 6g, P1 = P 8 v 2 V1, l1 = 0, l1 = +1 8
v 2 V1 n fy1g.
pRI k = 1 POLOVIM V2 = V1 nf1g = f2; 3; 4; 5; 6g. pOSKOLXKU
(1; 4); (1; 5); (1; 6) 62 R, TO S^ITAEM l(1; 4) = l(1; 5) = l(1; 6) =
+1 I NAHODIM l22 = minfl12; l11 + l(1; 2)g = minf+1; 0 + 4g = 4,
P22 = (P11; (1; 2)) = (1; 2), l23 = minfl13; l11+l(1; 3)g = minf+1; 0+
2g = 2, P23 = (P11; (1; 3)) = (1; 3), l24 = minfl14; l11 + l(1; 4)g =
minf+1; 0 + 1g = +1, P24 = P14 = P , l25 = minfl15; l11 +
l(1; 5)g = minf+1; 0 + 1g = +1, P25 = P15 = P , l26 =
minfl16; l11 + l(1; 6)g = minf+1; 0 + 1g = +1, P26 = P16 = P ,
y2 = 3. tAK KAK y2 =
6 t, TO PEREHODIM K SLEDU@]EMU [AGU.
pRI k = 2 POLOVIM V3 = V2 n f3g = f2; 4; 5; 6g. pOSKOLXKU (3; 2); (3; 6) 62 R, TO S^ITAEM l(3; 2) = l(3; 6) = +1 I NAHODIM l32 = minfl22; l23 + l(3; 2)g = minf4; 2 + 1g = 4, P32 =
P22 = (1; 2), l34 = minfl24; l23 + l(3; 4)g = minf+1; 2 + 2g = 4,
P34 = (P23; (3; 4)) = ((1; 3); (3; 4)), l35 = minfl25; l23 + l(3; 5)g =
minf+1; 2 + 4g = 6, P35 = (P23; (3; 5)) = ((1; 3); (3; 5)), l36 =
y
v
14
v
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
minfl26; l23 + l(3; 6)g = minf+1; 2 + 1g = +1, P36 = P26 = P ,
pOSKOLXKU l32 = 4 I l34 = 4, TO W KA^ESTWE y3 MOVNO WZQTX KAK
WER[INU 2, TAK I WER[INU 4. pUSTX y3 = 2.
pRI k = 3 POLOVIM V4 = V3 n f2g = f4; 5; 6g. pOSKOLXKU
(2; 4); (2; 6) 62 R, TO S^ITAEM l(2; 4) = l(2; 6) = +1 I NAHODIM
l44 = minfl34; l32 + l(2; 4)g = minf4; 2 + 1g = 4, P44 = P34 =
((1; 3); (3; 4)), l45 = minfl35; l32 + l(2; 5)g = minf6; 4 + 3g = 6, P45 =
P35 = ((1; 3); (3; 5)), l46 = minfl36; l32+l(2; 6)g = minf+1; 4+1g =
+1, P46 = P36 = P , y4 = 4.
pRI k = 4 POLOVIM V5 = V4 n f4g = f5; 6g. pOSKOLXKU
(4; 5) 62 R, TO S^ITAEM l(4; 5) = +1 I NAHODIM l55 = minfl45; l44 +
l(4; 5)g = minf6; 4 + 1g = 6, P55 = P45 = ((1; 3); (3; 5)), l56 =
minfl46; l44 + l(4; 6)g = minf+1; 4 + 0g = 4, P56 = (P44; (4; 6)) =
((1; 3); (3; 4); (4; 6)), y5 = 6, SLEDOWATELXNO, ALGORITM ZAKAN^IWAET RABOTU, I P (1; 6) = P56 = (P44; (4; 6)) = ((1; 3); (3; 4); (4; 6)).
2.1. w GRAFE, IZOBRAVENNOM NA RIS. 4 (DLINY REBER
UKAZANY W PRIMERE), POSTROITX ALGORITMOM 2.1 KRAT^AJ[IJ
PUTX IZ WER[INY s W WER[INU t I NAJTI EGO DLINU, ESLI: 1)
s = 4, t = 1; 2) s = 4, t = 3; 3) s = 6, t = 2; 4) s = 6, t = 3.
zADANIE
zADANIE 2.2. w GRAFE, IZOBRAVENNOM NA RIS. 2, S DLINAMI
REBER l(v1; v2) = 1, l(v1; v3) = 2, l(v1; v4) = 3, l(v2; v2) = 4,
l(v2; v4) = 4, l(v3; v4) = 0, l(v3; v5) = 5, l(v4; v5) = 6, l(v4; v6) = 2,
l(v5; v5) = 2, l(v5; v6) = 2 POSTROITX ALGORITMOM 2.1 KRAT^AJ-
[IJ PUTX IZ WER[INY s W WER[INU t I NAJTI EGO DLINU, ESLI:
1) s = v1, t = v5; 2) s = v1, t = v6; 3) s = v2, t = v5; 4) s = v2,
t = v6; 5) s = v3, t = v5; 6) s = v4, t = v5.
15
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pRIWEDEM NIVE E]E ODIN ALGORITM RE[ENIQ ISHODNOJ ZADA^I, KOTORYJ POZWOLQET STROITX W WZWE[ENNOM GRAFE G KRAT^AJ[IE PUTI MEVDU WSEMI PARAMI OTLI^NYH DRUG OT DRUGA
WER[IN MNOVESTWA V . zAMETIM, ^TO W OTLI^IE OT PREDYDU]EGO ALGORITMA TEPERX PRI POSTROENII OPTIMALXNYH PUTEJ
NE BUDET TREBOWATXSQ WYPOLNENIE USLOWIQ NEOTRICATELXNOSTI
DLIN REBER. oDNAKO, PRI \TOM W GRAFE G NE DOLVNO BYTX CIKLI^ESKIH PUTEJ OTRICATELXNOJ DLINY. dOGOWORIMSQ DLQ PROSTOTY OPISANIQ ALGORITMA OTOVDESTWLQTX WER[INY GRAFA G S
NOMERAMI 1; :::n, T. E. FAKTI^ESKI POLOVIM V = f1; :::; ng.
aLGORITM
2.2
(fLOJD, 1962).
dLQ KAVDOJ PARY OTLI^NYH DRUG OT DRUGA NOMEROW i; j 2 V
POLOVIM l0 = l(i; j ), P0 = ((i; j )), ESLI (i; j ) 2 R, I l0 = +1,
P0 = P W PROTIWNOM SLU^AE. kROME TOGO, DLQ KAVDOGO
i 2 V , POLAGAEM l0 = 0, P0 = P .
pUSTX IZWESTNY l ?1, P ?1 , i; j 2 V , I 1 k n. dLQ WSEH
i; j 2 V , i 6= j , NAHODIM
ij
ij
ij
ij
ii
ii
ij
k
ij
k
l = minfl ?1; l ?1 + l ?1g
ij
ij
k
k
ik
k
kj
k
I POLAGAEM P = P ?1 , ESLI l l ?1+l ?1, I P = (P ?1 ; P ?1 )
W PROTIWNOM SLU^AE. dLQ WSEH i 2 V POLAGAEM l = l ?1,
P = P ?1 .
pRI k = n + 1 ALGORITM ZAKAN^IWAET RABOTU, I P (i; j ) =
P 8 i; j 2 V .
ij
k
ij
k
ij
ik
k
k
kj
k
ij
k
ik
k
ii
k
ii
k
kj
k
ii
k
ii
k
ij
n
nETRUDNO PROWERITX, ^TO TRUDOEMKOSTX ALGORITMA 2.2 SOSTAWLQET O(n3) OPERACIJ, T. E. SOWPADAET S TRUDOEMKOSTX@
OTYSKANIQ KRAT^AJ[IH PUTEJ MEVDU WSEMI PARAMI OTLI^NYH
16
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
DRUG OT DRUGA WER[IN S POMO]X@ MODIFICIROWANNOGO ALGORITMA 2.1. oBOSNOWANIE ALGORITMA 2.2 MOVNO NAJTI, NAPRIMER, W RABOTAH ( [1], STR. 350, [3], STR. 53, [6], STR. 198, [11]).
eSTESTWENNO, ^TO ALGORITM 2.2 POSTROIT, W ^ASTNOSTI, I PUTX
MEVDU DWUMQ FIKSIROWANNYMI WER[INAMI s; t 2 V , ODNAKO PRI
\TOM PONADOBITSQ O(n3) OPERACIJ. pO\TOMU PRI NEOTRICATELXNYH DLINAH REBER DLQ RE[ENIQ ^ASTNOJ ZADA^I NAHOVDENIQ
KRAT^AJ[EGO PUTI IZ s W t LU^[E PRIMENQTX ALGORITM 2.1.
eSLI W REZULXTATE RABOTY ALGORITMA OKAZALOSX, ^TO P =
P I l = +1 DLQ NEKOTORYH i; j 2 V , i =
6 j , TO W GRAFE
G [email protected] PUTI IZ WER[INY i W WER[INU j . oTMETIM,
^TO W GRAFE G MOGUT PRISUTSTWOWATX ORIENTIROWANNYE ILI
NEORIENTIROWANNYE PETLI (?
i;!i) ILI (i; i) S NEOTRICATELXNYMI
DLINAMI. oDNAKO, NEZAWISIMO OT WELI^INY \TIH WESOW NA WSEH
ITERACIQH ALGORITMA l = 0, P = P , T. E. PETLI PRAKTI^ESKI NE [email protected] W POSTROENII ISKOMYH PUTEJ.
dALEE, DLQ UDOBSTWA REZULXTATY WY^ISLENIJ NA KAVDOM
[AGE BUDEM ZAPISYWATX W TABLICE, SOOTWETSTWU@]EJ \TOMU
[AGU. dLQ KAVDOJ PARY i; j 2 V W KLETKU, STOQ]U@ W i-OJ
STROKE I j -OM STOLBCE TABLICY k-GO [AGA (k = 0; :::; n) ZANOSITSQ PUTX P IZ WER[INY i W WER[INU j I ZNA^ENIE l (SM.
RIS. 5).
oTMETIM, ^TO NA k-OJ ITERACII, k 1, NET NEOBHODIMOSTI
PERES^ITYWATX KLETKI k-J STROKI I k-GO STOLBCA PREDYDU]EJ
TABLICY, POSKOLXKU l ?1 = 0, I PRI i = k [email protected] RAWENSTWA l = minfl ?1; l ?1 + l ?1g = l ?1, P = P ?1 , j = 1; :::n,
A PRI j = k { RAWENSTWA l = minfl ?1; l ?1 + l ?1g = l ?1,
P = P ?1 , i = 1; :::; n.
ij
n
ij
n
ii
ii
k
k
ij
ij
k
k
kk
k
ij
k
kj
kj
kk
kj
kj
k
k
k
k
ik
k
k
ij
ik
k
ik
k
17
kj
k
k
ik
k
kk
k
ik
k
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
j
i
1
1
P 11
l11
n
P1
l1
k
pp pp
p p
k
n
k
n
k
p p p
p p p
pp
p
p p p
n
P1
l1
n
k
n
pp
p
k
P
l
nn
k
nn
k
rIS. 5
w PRIMERAH DLINU l(a; b) REBRA (a; b) BUDEM UKAZYWATX NA
RISUNKE OKOLO \TOGO REBRA.
pRIMER. aLGORITMOM 2.2 TREBUETSQ NAJTI
KRAT^AJ[IE PUTI
MEVDU WSEMI PARAMI WER[IN W SME[ANNOM GRAFE, IZOBRAVENNOM NA RIS. 6.
2
JJ -2
2
J^
1
3
1 rIS. 6
rE[ENIE.
WID:
nA^ALXNAQ TABLICA PRI k = 0 IMEET SLEDU@]IJ
18
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
j
i
1
P
0
(2,1)
2
(3,1)
1
1
2
3
2
(1,2)
2
P
0
P
+1
3
(1,3)
1
(2,3)
-2
P
0
o^EWIDNO, ^TO SODERVIMOE KLETOK, STOQ]IH NA GLAWNOJ DIAGONALI TABLICY, MENQTXSQ OT [AGA K [AGU NE BUDET.
pRI k = 1 SOGLASNO ZAME^ANI@ SODERVIMOE KLETOK 1-J
STROKI I 1-GO STOLBCA OSTANETSQ TAKIM VE, KAK W TABLICE,
POSTROENNOJ NA PREDYDU]EM [AGE, l123 = minfl023; l021 + l013g =
minf?2; 2 + 1g = ?2, P123 = P023 = (2; 3), l132 = minfl032; l031 +
l012g = minf+1; 1 + 2g = 3, P132 = (P031; P012) = ((3; 1); (1; 2)).
tABLICA, SOOTWETSTWU@]AQ 1-MU [AGU, IMEET WID:
j
i
1
2
3
1
P
0
(2,1)
2
(3,1)
1
2
(1,2)
2
P
0
((3,1),(1,2))
3
19
3
(1,3)
1
(2,3)
-2
P
0
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pRI k = 2 SODERVIMOE KLETOK 2-J STROKI I 2-GO STOLBCA
OSTANETSQ TAKIM VE, KAK W TABLICE, POSTROENNOJ NA PREDYDU]EM [AGE,
l213 = minfl113; l112+l123g = minf1; 2+(?2)g = 0, P213 = (P112; P123) =
((1; 2); (2; 3)),
l231 = minfl131; l132 + l121g = minf1; 3 + 2g = 1, P231 = P131 = (3; 1).
rEZULXTATY WY^ISLENIJ \TOGO [AGA ZANESENY W SLEDU@]U@
TABLICU:
j
i
1
2
3
1
P
0
(2,1)
2
(3,1)
1
2
(1,2)
2
P
0
((3,1),(1,2))
3
3
((1,2),(2,3))
0
(2,3)
-2
P
0
pRI k = 3 SODERVIMOE KLETOK 3-J STROKI I 3-GO STOLBCA
OSTANETSQ TAKIM VE, KAK W TABLICE, POSTROENNOJ NA PREDYDU]EM [AGE,
l312 = minfl212; l213 + l232g = minf2; 0 + 3g = 2, P312 = P212 = (1; 2),
l321 = minfl221; l223+l231g = minf2; ?2+1g = ?1, P321 = (P223; P231) =
((2; 3); (3; 1)). sOOTWETSTWU@]AQ \TOMU [AGU TABLICA IMEET
WID:
20
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
j
i
1
2
3
1
2
(1,2)
P
0
2
((2,3),(3,1)) P -1
0
(3,1)
((3,1),(1,2))
1
3
3
((1,2),(2,3))
0
(2,3)
-2
P
0
pRI k = 4 ALGORITM ZAKAN^IWAET RABOTU. kRAT^AJ[IE PUTI I IH DLINY UKAZANY W POSLEDNEJ TABLICE.
zADANIE 2.3. w GRAFAH, IZOBRAVENNYH NA RIS. 7, ALGORITMOM
2.2 NAJTI KRAT^AJ[IE PUTI MEVDU WSEMI PARAMI WER[IN I
DLINY \TIH PUTEJ.
1)
2) 1 -3 - 3
3) 1 4 3
1
2
4 -3 -3
1
3 4
2
2 2
=
2
3
2
4
2
4
1
2
4
4) 5) 1 4 3
1 5
3
6 6
1
7
-3
2
4
2
-4
4
rIS. 7
21
2 6)
3
1
3
43 7
-3
?-4
+ -
4
2
4
-1
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
3.
oSTOWY MINIMALXNOGO WESA
pREVDE, ^EM SFORMULIROWATX ZADA^U OTYSKANIQ W GRAFE
OSTOWA MINIMALXNOGO WESA, KOTOROJ POSWQ]EN \TOT PARAGRAF,
PRIWEDEM NEKOTORYE WSPOMOGATELXNYE UTWERVDENIQ.
pUSTX DALEE G = G(V; R) { NEKOTORYJ NEORIENTIROWANNYJ
GRAF, n = jV j, m = jRj.
tEOREMA 3.1 ([1], STR. 53, [2], STR. 145). dLQ GRAFA G = G(V; R)
SLEDU@]IE UTWERVDENIQ \KWIWALENTNY:
1) G { DEREWO;
2) G { SWQZNYJ GRAF, DLQ KOTOROGO m = n ? 1;
3) G { ACIKLI^ESKIJ GRAF, DLQ KOTOROGO m = n ? 1;
4) [email protected] DWE NESOWPADA@]IE WER[INY GRAFA G SOEDINQET
EDINSTWENNNAQ PROSTAQ CEPX;
5) G { ACIKLI^ESKIJ GRAF TAKOJ, ^TO DLQ [email protected] NESMEVNYH
WER[IN a; b 2 V GRAF G(V; R [ f(a; b)g) IMEET EDINSTWENNYJ
CIKL.
sLEDSTWIE
3.1.
eSLI m > n ? 1, TO GRAF G SODERVIT HOTQ
sLEDSTWIE
3.2.
eSLI m < n ? 1, TO GRAF G NE SWQZEN.
BY ODIN CIKL.
sLEDSTWIE 3.3. eSLI GRAF G QWLQETSQ SWQZNYM, TO SPRAWEDLIWY NERAWENSTWA n ? 1 m n2.
dALEE, PODGRAF G(V ; R) GRAFA G = G(V; R) NAZYWAETSQ OSTOWNYM, ESLI V = V .
22
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
oSTOWOM (POKRYWA@]IM DEREWOM, KARKASOM) SWQZNOGO GRAFA G NAZYWAETSQ EGO OSTOWNYJ PODGRAF, QWLQ@]IJSQ DEREWOM.
tAK, DLQ GRAFA G, IZOBRAVENNOGO NA RIS. 2, OSTOWAMI, NAPRIMER, BUDUT PODGRAFY, IZOBRAVENNYE NA RIS. 8.
v
v
1
2
v
v
3
4
v
v
5
v
v
v
v
1
6
3
2
rIS. 8
4
v
v
5
6
eSLI GRAF G QWLQETSQ SWQZNYM, TO ^ISLO
REBER, KOTORYE NEOBHODIMO UDALITX IZ R DLQ POLU^ENIQ OSTOWA, RAWNO m ? n + 1.
sLEDSTWIE
3.4.
pUSTX TEPERX NEORIENTIROWANNYJ GRAF G QWLQETSQ SWQZNYM I WZWE[ENNYM, D(G) { MNOVESTWO WSEH OSTOWOW GRAFA G,
l(G) { SUMMA WESOW WSEH REBER OSTOWA G 2 D(G),
D(G) = Arg min l(G).
G
2 ( )
D G
iZWESTNO, ^TO DLQ POLNOGO GRAFA jD(G)j = n ?2 . pOD ZADA^EJ
POSTROENIQ OSTOWA MINIMALXNOGO WESA W GRAFE G BUDEM PONIMATX OTYSKANIE [email protected] \LEMENTA G 2 D (G).
pOSTAWLENNAQ ZADA^A ^ASTO WSTRE^AETSQ NA PRAKTIKE.
nAPRIMER, NEKOTOROE MNOVESTWO V NASELENNYH PUNKTOW TREBUETSQ SOEDINITX DRUG S DRUGOM NAPRQMU@ ILI ^EREZ PROMEVUTO^NYE PUNKTY TELEFONNOJ SETX@ TAK, ^TOBY OB]AQ DLINA TELEFONNOJ SETI BYLA MINIMALXNA. qSNO, ^TO \TU ZADA^U
n
23
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
MOVNO SFORMULIROWATX W TERMINAH TEORII GRAFOW, KAK ZADA^U
POSTROENIQ W POLNOM GRAFE S WER[INAMI V OSTOWA MINIMALXNOGO WESA.
dLQ OTYSKANIQ W GRAFE OSTOWA MINIMALXNOGO WESA SU][email protected] \FFEKTIWNYE ALGORITMY, IDEI I OBOSNOWANIQ KOTORYH
[email protected] UTWERVDENIQ TEOREMY 3.1 I EE SLEDSTWIJ. pRIWEDEM I OBSUDIM NIVE DWA IZ NIH.
(kRASKAL, 1956).
pERWONA^ALXNO POLAGAEM R = R nf(a; b) 2 R : a = bg, R0 = ,
G0 = G(V; R0).
pUSTX POSTROEN GRAF G = G(V; R ), I 0 k < n ? 1.
wYBIRAEM REBRO r +1 MINIMALXNOGO WESA SREDI REBER MNOVESTWA R n R , KOTORYE NE [email protected] CIKLOW S REBRAMI GRAFA
G . pOLAGAEM R +1 = R [ fr +1g, G +1 = G(V; R +1 ). pRI
k = n ? 1 ALGORITM ZAKAN^IWAET RABOTU, I G ?1 { OSTOW
MINIMALXNOGO WESA W GRAFE G.
aLGORITM
3.1
c
k
k
k
c
k
k
k
k
k
k
k
n
zAMETIM, ^TO PRI 0 k < n ? 2 GRAFY G [email protected] NESWQZNYMI, TAK KAK jR j < n ? 1. sWQZNYM STANOWITSQ TOLXKO
GRAF G ?1 , POSTROENNYJ NA POSLEDNEM [AGE k = n ? 2.
nETRUDNO PROWERITX, ^TO TRUDOEMKOSTX ALGORITMA 3.1 SOSTAWLQET O(mn2 ) OPERACIJ. oBOSNOWANIE ALGORITMA 3.1 MOVNO
NAJTI, NAPRIMER, W ( [1], STR. 60, [3], STR. 25, [10]). oTMETIM,
^TO W ALGORITME 3.1 PROWERKU NA NALI^IE CIKLA PRI DOBAWLENII REBRA W MNOVESTWO R NA KAVDOJ ITERACII MOVNO PROIZWESTI, NAPRIMER, S POMO]X@ ALGORITMA 2.1. pOQSNIM \TO.
pUSTX NA k-J ITERACII ALGORITMA 3.1 REBRO r = (a; b) 2 R n R
IMEET MINIMALXNYJ WES. pRIMENIM ALGORITM 2.1 DLQ POSTROENIQ KRAT^AJ[EGO PUTI IZ a W b (ILI IZ b W a) W GRAFE G .
k
k
n
k
c
k
k
24
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
pUSTX W REZULXTATE RABOTY ALGORITMA 2.1 P (a; b) 6= . tOGDA
W GRAFE G ESTX CEPX, SOEDINQ@]AQ WER[INY a, b, I PRI DOBAWLENII K MNOVESTWU R REBRA r SOGLASNO TEOREME 3.1 W NOWOM
GRAFE G +1 POQWITSQ CIKL. sLEDOWATELXNO, REBRO r NE MOVET
BYTX DOBAWLENO K R , T. E. NE MOVET BYTX WYBRANO W KA^ESTWE
r +1 . eSLI VE P (a; b) = , TO W GRAFE G NET NI ODNOJ CEPI, SOEDINQ@]EJ WER[INY a I b, A ZNA^IT, MOVNO POLOVITX
r +1 = (a; b) NA k-OJ ITERACII ALGORITMA 3.1.
k
k
k
k
k
k
k
w GRAFE, IZOBRAVENNOM NA RIS. 9, ALGORITMOM 3.1
POSTROITX OSTOW MINIMALXNOGO WESA. wES KAVDOGO REBRA UKAZAN NA RISUNKE RQDOM S \TIM REBROM.
pRIMER.
2
1
4
4 7 3
3
3
4 5
2
5
1 rIS. 9
rE[ENIE. oTMETIM, ^TO WSE POSLEDOWATELXNO STROQ]IESQ ALGORITMOM GRAFY G = G(V; R ), k = 0; :::; 4 BUDUT IZOBRAVATXSQ NA RIS. 10. pERWONA^ALXNO POLAGAEM R = R, R0 = ,
G0 = G(V; R0).
pRI k = 0, O^EWIDNO, r1 = (2; 5), R1 = f(2; 5)g G1 =
G(V; R1).
pRI k = 1 POLAGAEM r2 = (1; 4), R2 = f(2; 5); (1; 4)g G2 =
G(V; R2).
pUSTX k = 2. tOGDA DWA REBRA { (1; 2), (4; 5) [email protected] MINIMALXNYJ WES I NE [email protected] CIKLOW S REBRAMI GRAFA G2 .
k
k
c
25
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pO\TOMU, WYBRAW [email protected] IZ \TIH REBER, NAPRIMER, r3 = (1; 2),
POLOVIM R3 = f(2; 5); (1; 4); (1; 2)g G3 = G(V; R3).
1
4
3
2
5
G
1
4
3
2
5
1 G
2
1
4
3
3
2
5
1 0
2
1
4
3
2
5
1 G
2
1
4
3
3
4
2
5
1 1
G3
2
rIS. 10
G4
pRI k = 3 REBRO (4; 5) IMEET MINIMALXNYJ WES SREDI REBER MNOVESTWA R n R3, NO OBRAZUET CIKL S REBRAMI GRAFA G3.
c
26
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
pO\TOMU W KA^ESTWE r4 WYBIRAEM LIBO REBRO (1; 3), LIBO (2; 3).
pOLOVIM R4 = f(2; 5); (1; 4); (1; 2); (2; 3)g G4 = G(V; R4 ). pRI
k = 4 ALGORITM ZAKAN^IWAET RABOTU, PO\TOMU G4 { OSTOW MINIMALXNOGO WESA, PRI^EM, l(G4) = P l(a; b) = 10.
( )2 4
o^EWIDNO, ^TO RE[ENIE \TOJ ZADA^I NE EDINSTWENNO.
a;b
R
3.2 (pRIM, 1957).
pERWONA^ALXNO W MNOVESTWE R WYBIRAEM, ISKL@^AQ PETLI,
REBRO r1 MINIMALXNOGO WESA. w MNOVESTWO V1 WKL@^AEM
OBE KONCEWYE WER[INY REBRA r1. pOLAGAEM R1 = fr1g,
G1 = G(V1 ; R1).
pUSTX POSTROEN GRAF G = G(V ; R ), I 1 k < n ? 1.
CREDI REBER GRAFA G, U KOTORYH ODNA IZ KONCEWYH WER[IN
PRINADLEVIT MNOVESTWU V , A WTORAQ { MNOVESTWU V n V ,
WYBIRAEM REBRO r +1 MINIMALXNOGO WESA. zADAEM MNOVESTWO
V +1 OB_EDINENIEM V S TOJ IZ KONCEWYH WER[IN REBRA r +1,
KOTORAQ NE WHODIT W V . pOLAGAEM R +1 = R [fr +1g, G +1 =
G(V +1 ; R +1 ). pRI k = n ? 1 ALGORITM ZAKAN^IWAET RABOTU,
I G ?1 { OSTOW MINIMALXNOGO WESA W GRAFE G.
aLGORITM
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
k
n
zAMETIM, ^TO [email protected] IZ POSTROENNYH W ALGORITME GRAFOW
G , 1 k n ? 1, QWLQETSQ SWQZNYM SOGLASNO SLEDSTWI@ 3.3,
TAK KAK jR j = jV j ? 1.
tRUDOEMKOSTX ALGORITMA 3.2 SOSTAWLQET O(mn2 ) OPERACIJ.
oBOSNOWANIE ALGORITMA MOVNO NAJTI W ( [1], STR. 61). oPISANIE ALGORITMOW 3.1, 3.2 PRIWEDENO TAKVE W ( [2], STR. 281, [5],
STR. 358).
k
k
pRIMER.
k
w GRAFE, IZOBRAVENNOM NA RIS. 9, ALGORITMOM 3.2
27
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
POSTROITX OSTOW MINIMALXNOGO WESA. wES KAVDOGO REBRA UKAZAN NA RISUNKE RQDOM S \TIM REBROM.
rE[ENIE. sTROQ]IESQ POSLEDOWATELXNO ALGORITMOM 3.2 GRAFY G SM. NA RIS. 11. pERWONA^ALXNO r1 = (2; 5), V1 = f2; 5g,
R1 = f(2; 5)g, G1 = G(V1 ; R1).
pRI k = 1 WYBIRAEM REBRO r2 MINIMALXNOGO SREDI REBER
(1; 2), (4; 5), (2; 3), (3; 5) ODNA KONCEWAQ WER[INA KOTORYH IZ
MNOVESTWA V1 = f2; 5g, DRUGAQ { IZ V nV1 = f1; 3; 4g. pUSTX r2 =
(1; 2), TOGDA V2 = f1; 2; 5g, R2 = f(2; 5); (1; 2)g, G2 = G(V2 ; R2).
k
2
1
3
2
1
G1
2
1
G3
1
3
2
5
1
G
2
1
4
4 3
3
2
5
1 5
4
5
2
G4
rIS. 11
pRI k = 2, O^EWIDNO, r3 = (1; 4), V3 = f1; 2; 4; 5g, R3 =
f(2; 5); (1; 2); (1; 4)g, G3 = G(V3; R3).
28
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
pUSTX k = 3. wYBIRAEM REBRO r4 MINIMALXNOGO WESA SREDI
REBER (1; 3), (2; 3), (3; 4), (3; 5), T. K. V3 = f1; 2; 4; 5g, V n V3 =
f3g. wYBIRAEM [email protected] IZ REBER (1; 3), (2; 3) W KA^ESTWE r4 I
POLAGAEM V4 = f1; 2; 3; 4; 5g, R4 = f(2; 5); (1; 2); (1; 4); (2; 3)g,
G4 = G(V4 ; R4).
pRI k = 4 ALGORITM ZAKAN^IWAET PRABOTU, I G4 { OSTOW
MINIMALXNOGO WESA, PRI^EM, l(G4) =
l(a; b) = 10.
( )2 4
a;b
R
w GRAFAH, IZOBRAVENNYH NA RIS. 12, POSTROITX
OSTOWY MINIMALXNOGO WESA G ALGORITMAMI 3.1, 3.2.
zADANIE
3.1.
2 2
1
3
1
5 5
3 1
3)
2 2
6
3
1
5 4
3 1
1)
4
3 6
5 2
4
7 6
2
5 2
rIS. 12
29
2 2
4
2 4
4
1
3
5
5 3 4 5 1
3
5
3 24 1
3
2
4
6
6 7 2)
1
4)
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
4.
zADA^A O NAIBOLX[EM PAROSO^ETANII
W DWUDOLXNOM GRAFE
pUSTX G = G(V; R) { NEORIENTIROWANNYJ GRAF BEZ PETELX.
eSLI PODMNOVESTWO REBER M R TAKOWO, ^TO [email protected] DWA
EGO REBRA NEINCIDENTNY DRUG DRUGU, TO M [email protected] PAROSO^ETANIEM W GRAFE G. bUDEM S^ITATX, ^TO [email protected] REBRO GRAFA G QWLQETSQ PAROSO^ETANIEM W \TOM GRAFE. w GRAFE, IZOBRAVENNOM NA RIS. 13, PAROSO^ETANIQMI [email protected], NAPRIMER,
MNOVESTWA M 1 = f(v1; v2); (v4; v5)g, M 2 = f(v1; v3); (v4; v6)g,
M 3 = f(v1; v2); (v3; v4); (v5; v6); (v7; v8)g, M 4 = f(v1; v4)g.
v
v
1
2
v
v
3
4
v
v
5
6
v
v
7
8
rIS. 13
pUSTX M (G) { MNOVESTWO WSEH PAROSO^ETANIJ W GRAFE G.
qSNO, ^TO ESLI R 6= , TO M (G) 6= . pAROSO^ETANIE W GRAFE
G, KOTOROE SODERVIT NAIBOLX[EE ^ISLO REBER, BUDEM NAZYWATX
NAIBOLX[IM PAROSO^ETANIEM W GRAFE G. nAIBOLX[EE PAROSO^ETANIE W GRAFE MOVET BYTX NE EDINSTWENNYM. pUSTX
M (G) = Arg max
jM j.
2 ( )
M
M G
pOD ZADA^EJ POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ W NEORIENTIROWANNOM GRAFE G BUDEM PONIMATX ZADA^U OTYSKANIQ [email protected] \LEMENTA M IZ MNOVESTWA M (G). nETRUDNO PROWERITX,
30
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
^TO DLQ GRAFA NA RIS. 13, NAPRIMER, M 3 2 M (G), M 5 =
f(v1; v3); (v2; v4); (v5; v6); (v7; v8)g 2 M (G).
pUSTX M 2 M (G). pROSTAQ CEPX GRAFA G NAZYWAETSQ ^EREDU@]EJSQ OTNOSITELXNO M , ESLI EE REBRA S NE^ETNYMI NOMERAMI WHODQT W M , A S ^ETNYMI { W R n M , ILI NAOBOROT {
^ETNYE PO NOMERU REBRA WHODQT W M , A NE^ETNYE { W R n M .
bUDEM OBOZNA^ATX TAKU@ CEPX ^EREZ C (M ). dOGOWORIMSQ, ^TO
CEPX, SOSTOQ]AQ IZ [email protected] REBRA GRAFA G, BUDET TAKVE NAZYWATXSQ ^EREDU@]EJSQ OTNOSITELXNO M . rEBRA CEPI C (M )
NAZOWEM NASY]ENNYMI ILI NENASY]ENNYMI PAROSO^ETANIEM
M , ESLI ONI PRINADLEVAT ILI, SOOTWETSTWENNO, NE PRINADLEVAT M . wER[INY GRAFA G, INCIDENTNYE REBRAM IZ M , BUDEM
NAZYWATX NASY]ENNYMI, A WSE OSTALXNYE { NENASY]ENNYMI
PAROSO^ETANIEM M . w GRAFE, IZOBRAVENNYM NA RIS. 13, ^EREDU@]IMISQ CEPQMI OTNOSITELXNO PAROSO^ETANIQ M 1, NAPRIMER,
[email protected] CEPI C1(M 1) = ((v1; v2); (v2; v4); (v4; v5)), C2(M 1) =
((v1; v2); (v2; v4); (v4; v5); (v5; v6)), C3(M 1) = ((v4; v2); (v2; v1)),
C4(M 1) = ((v3; v4); (v4; v5); (v5; v6)), C5(M 1) = ((v7; v8)). dLQ CEPI C2(M 1) REBRA (v1; v2), (v4; v5) [email protected] NASY]ENNYMI PAROSO^ETANIEM M 1 , A (v2; v4), (v5; v6) { NENASY]ENNYMI \TIM
PAROSO^ETANIEM. wER[INY v1, v2, v4, v5 GRAFA BUDUT NASY]ENNYMI PAROSO^ETANIEM M 1, A v3, v6, v7, v8 { NENASY]ENNYMI
\TIM PAROSO^ETANIEM.
uWELI^IWA@]EJ PAROSO^ETANIE M CEPX@ W GRAFE G NAZOWEM ^EREDU@][email protected] OTNOSITELXNO M CEPX, SOEDINQ@]U@ DWE
NESOWPADA@]IE NENASY]ENNYE PAROSO^ETANIEM M WER[INY
GRAFA G. oBOZNA^IM TAKU@ CEPX ^EREZ C +(M ). o^EWIDNO,
^TO KOLI^ESTWO REBER UWELI^IWA@]EJ CEPI NE^ETNO.
nAPRIMER, W GRAFE, IZOBRAVENNOM NA RIS. 13,
UWELI^IWA@]IMI PAROSO^ETANIE M 1 CEPQMI [email protected]
31
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
C1+(M 1) = C4(M 1), C2+(M 1) = C5(M 1).
sU]ESTWOWANIE UWELI^IWA@]EJ PAROSO^ETANIE M CEPI DAET WOZMOVNOSTX POSTROITX NA OSNOWE M NOWOE PAROSO^ETANIE
S BOLX[IM ^ISLOM REBER. pUSTX M 2 M (G), C +(M ) { UWELI^IWA@]AQ M CEPX W GRAFE G. tOGDA NA OSNOWE M MOVNO
POSTROITX NOWOE PAROSO^ETANIE M , UDALIW IZ M WSE NASY]ENNYE REBRA CEPI C +(M ) I DOBAWIW WSE NENASY]ENNYE REBRA
\TOJ CEPI. o^EWIDNO, ^TO jM j = jM j + 1. nAPRIMER, NA OSNOWE
M 1, ISPOLXZUQ UWELI^IWA@]U@ CEPX C1+(M 1), POSTROIM NOWOE
PAROSO^ETANIE M 1 = f(v1; v2); (v3; v4); (v5; v6)g S BOLX[IM ^ISLOM REBER, ^EM W M 1.
tEOREMA
4.1
([2], STR. 372, [3], STR. 179, [4], STR. 225). dLQ
TOGO, ^TOBY WYPOLNQLOSX WKL@^ENIE
M 2 M (G),
NEOBHODIMO I DOSTATO^NO, ^TOBY W GRAFE G NE SU]ESTWOWALO
UWELI^IWA@]EJ PAROSO^ETANIE M CEPI.
iZ PRIWEDENNYH REZULXTATOW SLEDUET PROCEDURA OTYSKANIQ
W GRAFE NAIBOLX[EGO PAROSO^ETANIQ. nA^INAQ S PROIZWOLXNOGO
PAROSO^ETANIQ, S POMO]X@ UWELI^IWA@]EJ EGO CEPI UKAZANNYM WY[E SPOSOBOM STROITSQ NOWOE PAROSO^ETANIE, SODERVA]EE NA ODNO REBRO BOLX[E, ^EM PREDYDU]EE. pROCESS PRODOLVAETSQ DO TEH POR, POKA W GRAFE DLQ TEKU]EGO PAROSO^ETANIQ
BUDET SU]ESTWOWATX UWELI^IWA@]AQ CEPX. tEOREMA 4.1 DAET
KRITERIJ OSTANOWKI \TOGO ITERACIONNOGO PROCESSA.
oPISANNAQ PROCEDURA BUDET DALEE PRIMENQTXSQ DLQ POSTROENIQ NAIBOLX[IH PAROSO^ETANIJ W TAK NAZYWAEMYH DWUDOLXNYH GRAFAH. nEORIENTIROWANNYJ GRAF G = G(V; R) NAZYWA32
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
ETSQ DWUDOLXNYM, ESLI SU]ESTWUET TAKOE PODMNOVESTWO WER[IN X V , ^TO DLQ KAVDOGO REBRA GRAFA ODNA EGO KONCEWAQ
WER[INA PRINADLEVIT X , A WTORAQ { MNOVESTWU Y = V n X .
mNOVESTWA X , Y BUDEM NAZYWATX DOLQMI GRAFA G, A SAM DWUDOLXNYJ GRAF G ZAPISYWATX W WIDE G = (X [ Y; R). zAMETIM,
^TO SOGLASNO OPREDELENI@ W DWUDOLXNOM GRAFE PETLI NEDOPUSTIMY. kROME TOGO, OTMETIM, ^TO ODNA IZ DOLEJ GRAFA MOVET
BYTX PUSTYM MNOVESTWOM. nA RIS. 14 PRIWEDENY PRIMERY DWUDOLXNYH GRAFOW.
v1
v2
v1
X = fv1; v2g;
v2
Y =
v6
v3
v4
v2
v1
v3
v1
v
3
v
5
X = fv1; v2; v3g;
Y = fv4; v5g
v
v
2
v
v
5
4
X = fv1g;
Y = fv2; v3; v4; v5; v6g
4
X = fv1; v2g;
Y = fv3; v4g
rIS. 14
pUSTX G = G(X [ Y; R) { NEORIENTIROWANNYJ DWUDOLXNYJ
GRAF, I M { PAROSO^ETANIE W \TOM GRAFE. nA OSNOWE MNOVESTW
NEORIENTIROWANNYH DUG R, M POSTROIM MNOVESTWO R ORIENTIROWANNYH DUG SLEDU@]IM OBRAZOM. pOLOVIM R1 = f(?!
x; y) :
?!
x 2 X; y 2 Y; (x; y) 2 R n M g, R2 = f(y; x) : x 2 X; y 2
Y; (x; y) 2 M g, R = R1 [ R2 . tEPERX NA OSNOWE GRAFA G POSTROIM SOOTWETSTWU@]IJ EMU I EGO PAROSO^ETANI@ M ORIENTIROWANNYJ GRAF G = G(V; R ). oTMETIM, ^TO W G REBRA
M
M
M
M
M
M
M
M
33
M
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
MNOVESTWA R2 , SOOTWETSTWU@]EGO PAROSO^ETANI@ M ISHODNOGO GRAFA G, ORIENTIROWANY OT DOLI Y K DOLE X , A OSTALXNYE
REBRA GRAFA G ORIENTIROWANY OT X K Y .
bUDEM OBOZNA^ATX ^EREZ X , Y MNOVESTWA NENASY]ENNYH PAROSO^ETANIEM M WER[IN DOLEJ X , Y GRAFA G SOOTWETSTWENNO.
nA RIS. 15 IZOBRAVEN NEORIENTIROWANNYJ DWUDOLXNYJ GRAF
G = G(X [Y; R), GDE X = fv1; v2; v3g, Y = fv4; v5; v6; v7g, I SOOTWETSTWU@]IJ EMU I EGO PAROSO^ETANI@ M = f(v1; v5); (v3; v4)g
ORIENTIROWANNYJ GRAF G . oTMETIM, ^TO DLQ WYBRANNOGO PA??!
ROSO^ETANIQ X = fv2g, Y = fv6; v7g, R1 = f(v??!
1; v4); (v2; v6);
(??!
v3; v5); (??!
v3; v7)g, R2 = f(??!
v4; v3); (??!
v5; v1)g.
M
M
M
M
M
M
M
M
M
v
v
v
1
2
3
G
v
v
v
v
-
v
v
Z}ZZ ?
Z?Z
v
v
?
Z?Z*
?ZZ~
v
v
QQ QQQs
v
4
5
6
7
1
4
2
5
3
6
G
7
M
rIS. 15
4.2 ([1], STR. 356). pUSTX G { NEORIENTIROWANNYJ
DWUDOLXNYJ GRAF, M 2 M (G). dLQ TOGO, ^TOBY W GRAFE G SU]ESTWOWALA CEPX C +(M ), UWELI^IWA@]AQ PAROSO^ETANIE M ,
tEOREMA
34
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
NEOBHODIMO I DOSTATO^NO, ^TOBY W SOOTWETSTWU@]EM ORIENTIROWANNOM GRAFE G SU]ESTWOWAL NEPUSTOJ PUTX IZ WER[INY MNOVESTWA X W WER[INU MNOVESTWA Y .
M
M
M
pUSTX
!
v 1 ; v 2 ); :::; (?
v?????
P = P (v 1 ; v m ) = ((???!
m?1 ; v m ))
{ PUTX W GRAFE G IZ WER[INY v 1 2 X W WER[INU v m 2 Y .
tOGDA CEPX
s = s (v 1 ; v m ) = ((v 1 ; v 2 ); :::; (v m?1 ; v m )),
W GRAFE G, GDE NEORIENTIROWANNYE REBRA (v j ; v j+1 ),
!
j = 1; :::; m ? 1, [email protected] REBRAM (?
v????
j ; v j+1 ) PUTI P ,
QWLQETSQ UWELI^IWA@]EJ PAROSO^ETANIE M .
tEOREMA
4.3
i
i
i
M
i
i
i
i
M
i
i
i
i
M
i
i
i
i
i
i
i
kAK UVE OTME^ALOSX WY[E, NA OSNOWE CEPI C +(M ) LEGKO
STROITSQ NOWOE PAROSO^ETANIE W GRAFE S BOLX[IM ^ISLOM REBER, ^EM W M , PO\TOMU SPOSOB OTYSKANIQ CEPEJ C +(M ) FAKTI^ESKI I OPREDELQET SPOSOB NAHOVDENIQ NOWYH PAROSO^ETANIJ
W GRAFE. wOPROS O WOZMOVNOSTI ILI NEWOZMOVNOSTI POSTROENIQ DLQ M UWELI^IWA@]EJ CEPI C +(M ) RE[AETSQ NA OSNOWE
TEOREMY 4.2. eSLI W SOOTWETSTWU@]EM GRAFU G ORIENTIROWANNOM GRAFE G NAJDETSQ PUTX IZ WER[INY MNOVESTWA X
W WER[INU MNOVESTWA Y , TO ISKOMAQ CEPX C +(M ) SU]ESTWUET. w PROTIWNOM SLU^AE SOGLASNO TEOREME 4.1 PAROSO^ETANIE
M QWLQETSQ NAIBOLX[IM W GRAFE G. pOSTROENIE W G UKAZANNOGO PUTI LIBO WYQWLENIE EGO OTSUTSTWIQ MOVNO PROWESTI, W
^ASTNOSTI, ALGORITMOM 2.1, POLAGAQ, NAPRIMER, l(a; b) = 0 8
(a; b) 2 R .
M
M
M
M
M
35
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
tAKIM OBRAZOM, NA OSNOWE TEOREM 4.1, 4.2, 4.3 RAZRABOTAN
SLEDU@]IJ ALGORITM POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ
M W NEORIENTIROWANNOM DWUDOLXNOM GRAFE G.
aLGORITM 4.1. pERWONA^ALXNO WYBIRAEM PAROSO^ETANIE M1 2
M (G).
pUSTX NAJDENO PAROSO^ETANIE M , I k 1. sTROIM ORIENTIROWANNYJ GRAF G k , SOOTWETSTWU@]IJ GRAFU G I PAROSO^ETANI@ M , OTYSKIWAEM MNOVESTWA X k , Y k . eSLI HOTQ BY ODNO IZ MNOVESTW X k , Y k PUSTO ILI P (a; b) = P 8
a 2 X k , b 2 Y k , TO M = M , I ALGORITM ZAKAN^IWAET RABOTU. w PROTIWNOM SLU^AE PROIZWOLXNO WYBIRAEM NEPUSTOJ
PUTX P IZ WER[INY MNOVESTWA X k W WER[INU MNOVESTWA
Y k , OTMENQEM ORIENTACI@ WSEH REBER \TOGO PUTI I WKL@^A
0
00
EM WSE0 IH W MNOVESTWO
C . dALEE POLAGAEM M +1 = M [ M ,
00
GDE M = M n C , M = C n M .
k
M
M
k
M
M
M
M
M
k
M
k
M
k
k
k
k
k
k
k
k
k
k
pOQSNIM, ^TO NA k-OM [AGE ALGORITMA MNOVESTWA M 0 , M 00
MOVEM ZAPISATX W WIDE
k
k
M 0 = M n f(a; b) 2 C : (a; b) 2 M g,
k
k
k
k
M 00 = f(a; b) 2 C : (a; b) 62 M g.
k
k
k
tRUDOEMKOSTX ALGORITMA 4.1 SOSTAWLQET O(n4 ) OPERACIJ,
GDE n = jV j. oPISANIE I OBOSNOWANIE ALGORITMA PRIWODQTSQ,
NAPRIMER, W ([1], STR. 357, [2], STR. 382, [3], STR. 181, [8]).
pRIMER. aLGORITMOM 4.1
M W DWUDOLXNOM GRAFE G,
NAJTI NAIBOLX[EE PAROSO^ETANIE
IZOBRAVENNOM NA RIS. 16.
36
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
rE[ENIE. w GRAFE G PROIZWOLXNO
M1, NAPRIMER, M1 = f(1; 4)g.
WYBIRAEM PAROSO^ETANIE
pRI k = 1 STROIM ORIENTIROWANNYJ GRAF G 1 , SOOTWETSTWU@]IJ GRAFU G I PAROSO^ETANI@ M1 (SM. RIS. 17).
pOSKOLXKU X 1 = f2; 3g, Y 1 = f5; 6g, TO W GRAFE G 1 WYBIRAEM, NAPRIMER, NEPUSTOJ PUTX P1 = P1 (2; 5) = ((?
2!
; 4)0 ; (?
4!
; 1); (?
100!
; 5)),
POLAGAEM C1 = f(2; 4); (400; 1); (1; 5)g, A ZNA^IT, M1 = , M1 =
f(2; 4); (1; 5)g, I M2 = M1 .
pRI k = 2 STROIM ORIENTIROWANNYJ GRAF G 2 SOOTWETSTWU@]IJ GRAFU G I PAROSO^ETANI@ M2 (SM. RIS. 18), NAHODIM
X 2 = f3g, Y 2 = f6g. tAK KAK W GRAFE G 2 NET PUTI IZ WER[INY MNOVESTWA X 2 W WER[INU MNOVESTWA Y 2 , TO ALGORITM
ZAKAN^IWAET RABOTU, I M = M2 = f(2; 4); (1; 5)g { RE[ENIE ZADA^I. qSNO, ^TO NAJDENNOE NAIBOLX[EE PAROSO^ETANIE W GRAFE
G NE QWLQETSQ EDINSTWENNYM.
M
M
M
M
M
M
M
M
M
1
2
3
G
4
5
6
rIS. 16
M
1
4
*
H
H
@@ HHHj7
2 @ 5
@
@R
3
6
G M
1
rIS. 17
-
1
4
HYHH7
@@ HH
+ @ 5
2
@ @R
6
3
G 2
M
rIS. 18
zADANIE 4.1. w GRAFAH, IZOBRAVENNYH NA RIS. 19, ALGORITMOM
4.1 NAJTI NAIBOLX[IE PAROSO^ETANIQ M , WYBIRAQ W KA^ESTWE
NA^ALXNYH PAROSO^ETANIJ SOOTWETSTWENNO:
37
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
1) M1 = f(1; 5)g;
2) M1 = f(1; 6); (2; 5)g;
3) M1 = f(1; 7); (3; 8)g;
4) M1 = f(1; 6); (2; 8)g;
5) M1 = f(3; 7)g;
6) M1 = f(2; 5)g.
2
3
4
4) 1
2
3
4
1) 1
5
6
7
8
5
6
7
8
2
3
4
5) 1
2
3
4
3)
5
1
6
2
7
3
8
4
6)
5
1
6
2
7
3
2) 1
5
6
7
8
4
5
6
7
rIS. 19
zADA^I POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ W DWUDOLXNYH GRAFAH ^ASTO [email protected] NA PRAKTIKE. pRIWEDEM ODIN
38
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
PRIMER. pUSTX ESTX m RABO^IH MEST S NOMERAMI 1; :::; m, I n ISPOLNITELEJ, PRONUMEROWANNYH OT 1 DO n, KOTORYE [email protected]
NA \TI RABO^IE MESTA. eSLI i-J ISPOLNITELX MOVET WYPOLNITX
RABOTU S NOMEROM j , TO NAZNA^ENIE (i; j ), PRI KOTOROM i-J ISPOLNITELX POLU^AET j -@ RABOTU, BUDEM NAZYWATX DOPUSTIMYM.
tREBUETSQ PROWESTI KAK MOVNO BOLX[E NAZNA^ENIJ ISPOLNITELEJ NA RABO^IE MESTA S USLOWIEM, ^TO WSE NAZNA^ENIQ BUDUT
DOPUSTIMYMI.
dLQ RE[ENIQ ZADA^I POSTROIM DWUDOLXNYJ GRAF G = G(X [
Y ), W KOTOROM X = f1; :::; ng, Y = f1; :::; mg, A MNOVESTWO R
SOSTOIT IZ REBER (i; j ) TAKIH, ^TO i 2 X , j 2 Y I NAZNA^ENIE (i; j ) DOPUSTIMO, PRI^EM, KAVDOMU DOPUSTIMOMU NAZNA^ENI@ SOOTWETSTWUET REBRO W GRAFE. tOGDA [email protected] PAROSO^ETANIE M W \TOM GRAFE O^EWIDNYM OBRAZOM ZADAET DOPUSTIMYE
NAZNA^ENIQ ISPOLNITELEJ NA RABO^IE MESTA, A OTYSKANIE NAIBOLX[EGO PAROSO^ETANIQ M W GRAFE G RE[IT POSTAWLENNU@
PRAKTI^ESKU@ OPTIMIZACIONNU@ ZADA^U. pO\TOMU ZADA^U POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ W DWUDOLXNOM GRAFE [email protected] ^ASTO ZADA^EJ O NAZNA^ENIQH.
39
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
5.
nAIMENX[EE WER[INNOE POKRYTIE
W DWUDOLXNOM GRAFE
pODMNOVESTWO V 0 V NAZYWAETSQ WER[INNYM POKRYTIEM GRAFA G = G(V; R), ESLI [email protected]
REBRO GRAFA G INCIDENT0
NO HOTQ BY ODNOJ WER[INE IZ V . w GRAFE, IZOBRAVENNOM NA
RIS. 1, WER[INNYMI POKRYTIQMI BUDUT, NAPRIMER, MNOVESTWA
fv2; v3; v4; v5g, fv1; v2; v4; v5g, fv2; v3; v4; v5; v6g. o^EWIDNO, ^TO
WSE WER[INY GRAFA, IME@]IE PETLI, DOLVNY WOJTI W WER[INNOE POKRYTIE.
pUSTX V (G) { MNOVESTWO WSEH WER[INNYH POKRYTIJ GRAFA
G. pOLOVIM
V (G) = Arg 0min jV 0 j.
2 ( )
V
V
G
|LEMENT V 2 V (G) BUDEM NAZYWATX NAIMENX[IM WER[INNYM POKRYTIEM GRAFA G, A POD ZADA^EJ OTYSKANIQ W GRAFE
G NAIMENX[EGO WER[INNOGO POKRYTIQ BUDEM PONIMATX ZADA^U
NAHOVDENIQ [email protected] \LEMENTA MNOVESTWA V (G).
tEOREMA 5.1 ([3], STR. 174). dLQ NEORIENTIROWANNOGO DWUDOLX-
NOGO GRAFA ^ISLO WER[IN, WHODQ]IH W EGO NAIMENX[EE WER[INNOE POKRYTIE, SOWPADAET S ^ISLOM REBER, WHODQ]IH W EGO
NAIBOLX[EE PAROSO^ETANIE.
pUSTX DALEE G = G(X [ Y; R) { NEORIENTIROWANNYJ DWUDOLXNYJ GRAF, n = jX j + jY j, M { NAIBOLX[EE PAROSO^ETANIE
W \TOM GRAFE, G { SOOTWETSTWU@]IJ GRAFU G I PAROSO^ETANI@ M ORIENTIROWANNYJ GRAF, SPOSOB POSTROENIQ KOTOROGO
UKAZAN W RAZD. 4.
M
40
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
oBOZNA^IM ^EREZ
X +(G ) PODMNOVESTWO TEH WER[IN MNO
VESTWA X n X , W KOTORYE SU][email protected] NEPUSTYE PUTI HO TQ BY IZ ODNOJ WER[INY MNOVESTWA X , A ^EREZ X ? (G )
{ PODMNOVESTWO TEH WER[IN IZ X n X , W KOTORYE PUTI IZ
WSEH WER[IN
X [email protected] aNALOGI^NO, ^EREZ Y + (G ) I
?
Y (G ) OBOZNA^IM PODMNOVESTWA WER[IN IZ Y n Y , W KOTORYE SU][email protected] PUTI I, SOOTWETSTWENNO
, NE SU]ESTWUET PUTEJ
IZ WER[IN
TOGO VE MNOVESTWA X . o^EWIDNO, ^TO MNOVESTWA
X , X + (G ), X ?(G ) (Y , Y + (G ), Y ?(G )) POPARNO
+ (G ) [ X ? (G ) [
NE [email protected]
,
I
,
KROME
TOGO
,
X
=
X
X (Y = Y + (G ) [ Y ? (G ) [ Y ). tAK, W GRAFE, IZOBRA = f(1; 5); (2; 4)g QWLQETVENNOM NA RIS. 18, PAROSO^ETANIE M
+ (G ) = f2g, X ? (G ) = f1g,
SQ NAIBOLX[IM
,
A
ZNA^IT
,
X
Y + (G ) = f4g, Y ? (G ) = f5g.
mNOVESTWA X + (G ), X ? (G ), Y + (G ), Y ?(G ) BUDUT ISPOLXZOWATXSQ DALEE W ALGORITMAH RE[ENIQ ZADA^ SLEDU @]IH RAZDELOW
. w ^ASTNOSTI, \LEMENTY MNOVESTW X ? (G ),
Y + (G ) [email protected] PRI POSTROENII NAIMENX[IH WER[INNYH
POKRYTIJ GRAFA. pO\TOMU NEOBHODIMO
IMETX PROCEDURU OTYS
KANIQ \TIH MNOVESTW W GRAFE G . pOKAVEM, KAKIM OBRAZOM
UKAZANNYE MNOVESTWA MOGUT BYTX NAJDENY S POMO]X@ UVE
OPISANNYH WY[E METODOW POSTROENIQ KRAT^AJ[IH PUTEJ, NAPRIMER, S POMO]X@ ALGORITMA 2.2, PRIMENENNOGO K GRAFU G .
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
pROCEDURA 5.1. pOLOVIM l(a; b) = 0 8 (a; b) 2 R
I POSTROIM W WZWE[ENNOM GRAFE G ALGORITMOM 2.2 PUTI MEVDU
KAVDOJ PAROJ EGO WER[IN. tE WER[INY MNOVESTWA X n X ,
W KOTORYE ALGORITM
POSTROIL PUSTYE PUTI IZ WSEH WER[IN
MNOVESTWA X OB_EDINIM W X ? (G ), T. E. POLOVIM
M
M
M
M
M
41
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
X ? (G ) = fx 2 X n X : P (a; x) = P 8 a 2 X g. (5.1)
wER[INY MNOVESTWA Y nY , W KOTORYE ALGORITM
POSTROIL
PUSTYE PUTI IZ WSEH WER[IN MNOVESTWA X OB_EDINIM W
Y ? (G ), T. E. POLOVIM
Y ?(G ) = fy 2 Y n Y : P (a; y) = P 8 a 2 X g. (5.2)
|LEMENTAMI MNOVESTW X + (G ), Y + (G ) BUDUT
, SOOTWETSTWENNO, WER[INY MNOVESTW X n X , Y n Y , W KOTORYE
ALGORITMOM 2.2 POSTROENY NEPUSTYE PUTI HOTQ BY IZ ODNOJ
WER[INY MNOVESTWA X , T. E. POLOVIM
X + (G ) = fx 2 X n X : 9 a 2 X ; P (a; x) 6= P g, (5.3)
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
Y + (G ) = fy 2 Y n Y
M
M
M
: 9 a 2 X ; P (a; y) 6= P g.
M
(5.4)
zAMETIM, ^TO
X + (G ) = (X n X ) n X ? (G ),
(5.5)
Y + (G ) = (Y n Y ) n Y ? (G ).
(5.6)
kROME TOGO
, O^EWIDNO
, ^TO TRUDOEMKOSTX
OTYSKANIQ MNOVESTW
+
?
+
?
X (G ), X (G ), Y (G ), Y (G ) PROCEDUROJ 5.1 SOOTWETSTWUET TRUDOEMKOSTI ALGORITMA 2.2, T. E. SOSTAWLQET O(n3 )
OPERACIJ.
M
M
M
M
tEOREMA
M
5.2
mNOVESTWO
M
M
M
M
M
([1], STR. 358, [2], STR. 416, [3], STR. 174).
X ? (G ) [ Y + (G )
M
M
42
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
QWLQETSQ NAIMENX[IM WER[INNYM POKRYTIEM GRAFA G.
iZ TEOREMY 5.2 SLEDUET ALGORITM POSTROENIQ NAIMENX[EGO WER[INNOGO POKRYTIQ V W DWUDOLXNOM NEORIENTIROWANNOM
GRAFE S ISPOLXZOWANIEM PROCEDURY POSTROENIQ NAIBOLX[EGO
PAROSO^ETANIQ M .
oTYSKIWAEM NAIBOLX[EE PAROSO^ETANIE M W GRAFE G. sTROIM SOOTWETSTWU@]IJ
GRAFU G I PAROSO^E
TANI@ M
ORIENTIROWANNYJ GRAF G , A TAKVE MNOVESTWA
X ? (G ), Y +(G ), I POLAGAEM
V = X ? (G ) [ Y + (G ).
aLGORITM
5.1.
M
M
M
M
M
nETRUDNO PROWERITX, ^TO TRUDOEMKOSTX ALGORITMA 5.1 SOSTAWLQET O(n4 ) OPERACIJ.
aLGORITMOM 5.1 TREBUETSQ NAJTI NAIMENX[EE WER[INNOE POKRYTIE V W DWUDOLXNOM GRAFE G, IZOBRAVENNOM NA
RIS. 16.
pRIMER.
rE[ENIE. aLGORITMOM 4.1 W GRAFE G OTYSKIWAEM NAIBOLX[EE PAROSO^ETANIE M = f(2; 4); (1 ; 5)g. sTROIM SOOTWETSTWU@]IJ ORIENTIROWANNYJ GRAF G (SM. RIS. 18). nAHODIM MNOVESTWA X ? (G ) = f1g, Y + (G ) = f4g, I POLAGAEM V =
X ? (G ) [ Y + (G ) = f1; 4g.
M
M
M
M
M
zADANIE 5.1. w GRAFAH, IZOBRAVENNYH NA RIS. 19, ALGORITMOM
5.1 NAJTI NAIMENX[IE WER[INNYE POKRYTIQ V .
43
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
6.
sBALANSIROWANNAQ ZADA^A POSTROENIQ NAIBOLX[EGO
PAROSO^ETANIQ MINIMALXNOGO WESA W DWUDOLXNOM
GRAFE.
pUSTX G = G(X [ Y; R) { NEORIENTIROWANNYJ DWUDOLXNYJ
WZWE[ENNYJ GRAF, l(x; y) { WES REBRA (x; y) 2 R, M (G) { MNOVESTWO WSEH PAROSO^ETANIJ GRAFA G, A M (G) { MNOVESTWO
NAIBOLX[IH PAROSO^ETANIJ \TOGO GRAFA. dLQ KAVDOGO PAROSO^ETANIQ M 2 M (G) ZADADIM EGO WES l(M ) SLEDU@]IM OBRAZOM:
l(M ) = P l(x; y).
( )2
x;y
M
pOD ZADA^EJ POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ MINIMALXNOGO WESA W GRAFE G BUDEM PONIMATX ZADA^U OTYSKANIQ
[email protected] \LEMENTA
M 2 Arg 2min( ) l(M ).
(6.1)
M
M
G
zADA^A (6.1) IMEET PRAKTI^ESKOE PRIMENENIE. w ZAKL@^ENIE RAZDELA 4 BYLA POSTAWLENA ZADA^A O NAZNA^ENIQH, SFORMULIROWANNAQ W TERMINAH TEORII GRAFOW. pUSTX W \TOJ ZADA^E KAVDOMU DOPUSTIMOMU NAZNA^ENI@ (i; j ) PRIPISAN NEKOTORYJ WES l(i; j ), I TREBUETSQ PROIZWESTI KAK MOVNO BOLX[E DOPUSTIMYH NAZNA^ENIJ ISPOLNITELEJ NA RABO^IE MESTA, ^TOBY
SUMMARNYJ WES PROIZWEDENNYH NAZNA^ENIJ BYL MINIMALXNYM.
o^EWIDNO, ^TO TAKOJ WARIANT ZADA^I O NAZNA^ENIQH MOVNO
SFORMULIROWATX W WIDE ZADA^I POSTROENIQ W DWUDOLXNOM GRAFE NAIBOLX[EGO PAROSO^ETANIQ MINIMALXNOGO WESA. pO\TOMU
ZADA^U (6.1) [email protected] TAKVE WZWE[ENNOJ ZADA^EJ O NAZNA^ENIQH.
44
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
dALEE. ESLI DOLI GRAFA G SODERVAT RAZNOE ^ISLO WER[IN,
T. E. jX j =
6 jY j, TO ZADA^U (6.1) [email protected] NESBALANSIROWANNOJ.
nESBALANSIROWANNAQ ZADA^A POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ MINIMALXNOGO WESA BUDET OBSUVDATXSQ I RE[ATXSQ W
SLEDU@]EM RAZDELE POSOBIQ. eSLI DOLI X , Y SODERVAT ODINAKOWOE ^ISLO WER[IN, TO ZADA^U (6.1) BUDEM NAZYWATX SBALANSIROWANNOJ. [email protected] NIVE W NASTOQ]EM RAZDELE S^ITAEM, ^TO
jX j = jY j,
(6.2)
I, ESLI SPECIALXNO NE OGOWORENO, GRAF G QWLQETSQ POLNYM.
pUSTX n = jX j, m = jRj. dLQ POLNOGO GRAFA G O^EWIDNO
RAWENSTWO
m = n2.
(6.3)
pRIWEDEM NIVE NEKOTORYE ZAME^ANIQ, KASA@]IESQ SWOJSTW ZADA^I (6.1) S USLOWIQMI (6.2), (6.3).
nETRUDNO WIDETX, ^TO
jM j = n 8 M 2 M (G),
I [email protected] n-\LEMENTNOE PAROSO^ETANIE GRAFA G QWLQETSQ EGO
NAIBOLX[IM PAROSO^ETANIEM. pO\TOMU ZADA^U (6.1) S USLOWIQMI (6.2), (6.3) MOVNO SFORMULIROWATX KAK ZADA^U OTYSKANIQ
MINIMALXNOGO PO WESU n-\LEMENTNOGO PAROSO^ETANIQ W GRAFE
G.
zAME^ANIE
6.1.
pOSKOLXKU KAVDOJ WER[INE GRAFA G INCIDENTNO ODNO I TOLXKO ODNO REBRO n-\LEMENTNOGO PAROSO^ETANIQ
\TOGO GRAFA, TO MNOVESTWO Arg 2min( ) l(M ) RE[ENIJ ZADA^I
zAME^ANIE
6.2.
M
45
M
G
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
(6.1) S USLOWIQMI (6.2), (6.3) NE IZMENITSQ, ESLI WESA WSEH REBER GRAFA G, INCIDENTNYH ODNOJ I TOJ VE WER[INE, UWELI^ITX
ILI UMENX[ITX NA ODNO I TO VE ^ISLO.
eSLI
l(x; y) 0 8 (x; y) 2 R,
(6.4)
I n-\LEMENTNOE PAROSO^ETANIE M 2 M (G) TAKOWO, ^TO l(M ) =
0, TO M 2 Arg 2min( ) l(M ).
zAME^ANIE
6.3.
M
M
G
sOGLASNO ZAME^ANI@ 6.2 PRI NEWYPOLNENII DLQ GRAFA G
USLOWIJ (6.4) MOVNO UWELI^ITX ZNA^ENIQ l(x; y) DLQ WSEH (x; y) 2
R NA ODNO I TO VE ^ISLO TAK, ^TO NOWYE WESA WSEH REBER STANUT NEOTRICATELXNYMI, A MNOVESTWO RE[ENIJ ZADA^I (6.1) PRI
\TOM NE IZMENITSQ. tAKAQ PROCEDURA IZMENENIQ WESOW S U^ETOM
RAWENSTWA (6.3) POTREBUET O(n2 ) OPERACIJ. pO\TOMU, NE OGRANI^IWAQ OB]NOSTI ZADA^I (6.1), BUDEM S^ITATX POKA, ^TO DLQ
GRAFA G [email protected] USLOWIQ (6.4).
nA OSNOWE ZAME^ANIJ 6.1, 6.2, 6.3 SFORMULIRUEM DALEE ALGORITM RE[ENIQ ZADA^I (6.1) S USLOWIQMI (6.2) { (6.4). bUDEM
DLQ UDOBSTWA OPISANIQ ALGORITMA S^ITATX, ^TO WER[INY MNOVESTWA X ZADANY NOMERAMI 1; :::; n, A WER[INY MNOVESTWA Y {
NOMERAMI n + 1; :::; 2n, T. E. X = f1; :::; ng, Y = fn + 1; :::; 2ng.
pOLOVIM V = X [ Y , l = l(i; j ) 8 i 2 X , j 2 Y .
ij
aLGORITM
POLAGAEM
6.1.
dLQ KAVDOGO i 2 X WY^ISLQEM = min
l ,I
2
i
l = l ? 8 i 2 X, j 2 Y .
ij
ij
i
46
j
Y
ij
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
dLQ KAVDOGO j 2 Y WY^ISLQEM = min
l , I POLAGAEM
2
j
i
X
ij
l0 = l ? 8 i 2 X , j 2 Y .
sTROIM GRAF G0 = G(V; R0), GDE R0 = f(i; j ) 2 R : l0 = 0g.
pUSTX UVE NAJDENY ^ISLA l , i 2 X , j 2 Y , POSTROEN
GRAF G , I k 0. nAHODIM W GRAFE G NAIBOLX[EE PAROSO^ETANIE M . eSLI jM j = n, TO ALGORITM ZAKAN^IWAET RABOTU,
I M = M . w PROTIWNOM SLU^AE DLQ GRAFA G OTYSKIWAEM
+
(NAPRIMER, PROCEDUROJ 5.1) MNOVESTWA X k , X = X + (G k ),
?
+
?
X = X ? (G k ), Y k , Y = Y + (G k ), Y = Y ? (G k ), NAHODIM
l = minfl : i 2 X + [ X k ; j 2 Y ? [ Y k g.
dALEE POLAGAEM
l +1 = l
DLQ WSEH i 2 X + [ X k , j 2 Y + I WSEH i 2 X ? , j 2 Y ? [ Y k ,
l +1 = l + l
DLQ WSEH i 2 X ? , j 2 Y +, I
l +1 = l ? l
DLQ WSEH i 2 X + [ X k , j 2 Y ? [ Y k . sTROIM GRAF G +1 =
G(V; R +1 ), GDE R +1 = f(i; j ) 2 R : l +1 = 0g.
ij
ij
j
ij
k
ij
k
k
k
k
k
k
M
M
k
M
M
M
k
k
M
k
k
M
ij
M
k
k
k
k
ij
ij
M
M
k
k
k
k
k
ij
ij
k
k
ij
k
k
k
ij
M
k
M
k
k
k
k
k
ij
tRUDOEMKOSTX ALGORITMA 6.1 SOSTAWLQET O(n4) OPERACIJ.
oPISANIE ALGORITMA MOVNO NAJTI, NAPRIMER, W ([1], STR. 359,
[3], STR. 193, [9]).
47
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pUSTX NA KAVDOM [AGE ALGORITMA 6.1 NAIBOLX[EE PAROSO^ETANIE M NAHODITSQ ALGORITMOM 4.1. tOGDA
PRI POSTROENII M , k 1, WO IZBEVANIE LI[NIH WY^ISLENIJ
W KA^ESTWE NA^ALXNOGO PAROSO^ETANIQ W ALGORITME 4.1 UDOBNO
WYBIRATX MNOVESTWO M ?1.
zAME^ANIE
6.4.
k
k
k
kAK UVE OTME^ENO WY[E, USLOWIE (6.4), PRI
KOTOROM OPISAN ALGORITM 6.1, NE QWLQETSQ PRINCIPIALXNYM
DLQ ZADA^I (6.1). pUSTX DLQ GRAFA G USLOWIQ (6.2), (6.3) WYPOLNENY, A (6.4) NE WYPOLNENO. tOGDA PERED NA^ALOM RABOTY
ALGORITMA POLOVIM
l = l(i; j ) + (6.5)
DLQ WSEH (i; j ) 2 R, GDE
( max
jl(i; j )j, R? = f(i; j ) 2 R : l(i; j ) < 0g. (6.6)
)2 ?
zAME^ANIE
6.5.
ij
i;j
R
zAME^ANIE 6.6. pUSTX ISHODNYJ GRAF G = G(X [ Y; R) NE
QWLQETSQ POLNYM. pOSTROIM NA OSNOWE R MNOVESTWO REBER R~
SLEDU@]IM OBRAZOM. dLQ WSEH WER[IN i 2 X , j 2 Y TAKIH,
^TO W R OTSUTSTWUET SOOTWETSTWU@]AQ IM PARA, W MNOVESTWO R~ WKL@^AETSQ NEORIENTIROWANNOE REBRO (i; j ). pOLOVIM
Rb = R [ R~ . tOGDA POLNYJ GRAF Gb = G(X [ Y; Rb ) NAZOWEM SOOTWETSTWU@]IM ISHODNOMU NEPOLNOMU GRAFU G.
pOKAVEM, KAKIM OBRAZOM MOVNO RE[ATX SBALANSIROWANNU@ ZADA^U (6.1) DLQ NEPOLNOGO GRAFA G, S^ITAQ
PRI \TOM, ^TO USLOWIE (6.4) MOVET DLQ NEGO NE WYPOLNQTXSQ.
sOGLASNO ZAME^ANI@ 6.6 POSTROIM DLQ ISHODNOGO GRAFA G SOOTWETSTWU@]IJ EMU POLNYJ GRAF Gb = G(X [ Y; Rb ), I ZADADIM
zAME^ANIE
6.7.
48
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
WESA REBER GRAFA Gb SLEDU@]IM OBRAZOM. eSLI (i; j ) 2 R, TO WES
REBRA (i; j ) GRAFA Gb OSTAETSQ RAWNYM
l(i; j ). eSLI (i; j ) 2 Rb n R,
P
jl(i; j )j. dALEE, PERED NATO POLAGAEM l(i; j ) = , GDE >
( )2
^ALOM RABOTY ALGORITMA 6.1 ZADADIM ZNA^ENIQ l DLQ WSEH
(i; j ) 2 Rb SOGLASNO RAWENSTWU (6.5), W KOTOROM = 0, ESLI
R? = , I OPREDELENO NERAWENSTWOM (6.6) W PROTIWNOM SLU^AE. pUSTX TEPERX DLQ GRAFA Gb ALGORITMOM 6.1 NA k-OM [AGE
POSTROENO NAIBOLX[EE PAROSO^ETANIE MINIMALXNOGO WESA M .
pOLOVIM
M = M \ R,
T. E. FAKTI^ESKI UDALIM IZ M REBRA (i; j ) 2 Rb nR, ESLI TAKIE W
M SU][email protected] nETRUDNO POKAZATX, ^TO POSTROENNOE MNOVESTWO M QWLQETSQ NAIBOLX[IM PAROSO^ETANIEM MINIMALXNOGO
WESA W ISHODNOM GRAFE G.
i;j
R
ij
k
k
k
k
pRI RE[ENII, S ISPOLXZOWANIEM ALGORITMA 6.1, KONKRETNYH
ZADA^ ZNA^ENIQ WESOW l(i; j ), i 2 X , j 2 Y , BUDEM ZADAWATX W
TABLICE L, IME@]EJ WID
Y n+1
X
1 l(1; n + 1)
pp
p
pp
p
n l(n; n + 1)
p p p
p p p
pp
p
p p p
49
2n
l(1; 2n)
pp
p
l(n; 2n)
,
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
A ZNA^ENIQ l , POLU^ENNYE NA k-OM [AGE (k 0), BUDEM ZAPISYWATX W ANALOGI^NU@ TABLICU L . eSLI GRAF G NE QWLQETSQ POLNYM, I, NAPRIMER, REBRO (i; j ) W NEM OTSUTSTWUET, TO W
TABLICE WESOW GRAFA G SOOTWETSTWU@]U@ KLETKU (i; j ) BUDEM
OSTAWLQTX PUSTOJ.
k
ij
k
w DWUDOLXNOM POLNOM GRAFE G S TABLICEJ WESOW
L, IZOBRAVENNYH NA RIS. 20, ALGORITMOM 6.1 POSTROITX NAIBOLX[EE PAROSO^ETANIE MINIMALXNOGO WESA M .
pRIMER
1
2
3
4
6.1.
G
5
6
7
8
XY
1
2
3
4
5
1
2
3
1
6 7 8
1 4 1
3 8 3
7 11 9
4 6 8
L
rIS. 20
rE[ENIE. wY^ITAEM IZ KAVDOJ STROKI TABLICY L MINIMALXNYJ \LEMENT \TOJ STROKI. zATEM IZ KAVDOGO STOLBCA WY^ITAEM
MINIMALXNYJ \LEMENT \TOGO STOLBCA. pOLU^ENNYE ^ISLA l0 ,
i = 1; :::; 4, j = 5; :::; 8, ZANOSIM W TABLICU L0 (RIS. 21), POLAGAEM R0 = f(1; 5); (1; 6); (1; 7); (1; 8); (2; 5); (3; 5); (4; 5)g, I STROIM
GRAF G0 = G(V; R0) (RIS. 21).
pRI k = 0 ALGORITMOM 4.1 W GRAFE G0 NAHODIM NAIBOLX[EE PAROSO^ETANIE M0 = f(1; 6); (2; 5)g. tAK KAK jM0j =
6 4, TO
+
0
W GRAFE G0 OTYSKIWAEM MNOVESTWA X = f3; 4g, X0 = f2g
ij
M
50
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
X0? = f1g, Y 0 = f7; 8g, Y0+ = f5g Y0? = f6g, I WY^ISLQEM ZNA^ENIE l = minfl0 : i = 2; 3; 4; j = 6; 7; 8g = 1. sTROIM
TABLICU L1 (RIS. 22), POLAGAQ l1 = l0 DLQ WSEH i = 2; 3; 4,
j = 5 I WSEH i = 1, j = 6; 7; 8; l1 = l0 + 1 DLQ i = 1, j = 5;
l1 = l0 ? 1 DLQ WSEH i = 2; 3; 4, j = 6; 7; 8. oPREDELQEM MNOVESTWO R1 = f(i; j ) 2 R : l1 = 0g, I STROIM GRAF G1 = G(V; R1)
(RIS. 22).
M
ij
ij
ij
ij
ij
ij
ij
ij
Y
X
1
2
3
4
5
0
0
0
0
6
0
1
4
3
7
0
3
5
2
8
0
1
6
7
L0
XY
1
2
3
4
5
1
0
0
0
L1
6
0
0
3
2
rIS. 21
7
0
2
4
1
8
0
0
5
6
rIS. 22
51
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
G0
G1
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
pRI k = 1 ALGORITMOM 4.1 W GRAFE G1 NAHODIM NAIBOLX[EE PAROSO^ETANIE M1 = f(1; 6); (2; 8); (3; 5)g, ISPOLXZUQ M0 W
KA^ESTWE NA^ALXNOGO PAROSO^ETANIQ. pOSKOLXKU jM1j =
6 4, TO
W GRAFE G1 OTYSKIWAEM MNOVESTWA X 1 = f4g, X1+ = f3g
X1? = f1; 2g, Y 1 = f7g, Y1+ = f5g Y ? = f6; 8g, I WY^ISLQEM ZNA^ENIE l = minfl1 : i = 3; 4; j = 6; 7; 8g = 1. sTROIM
TABLICU L2 (RIS. 23), POLAGAQ l2 = l1 DLQ i = 3; 4, j = 5 I
DLQ WSEH i = 1; 2, j = 6; 7; 8; l2 = l1 + 1 DLQ i = 1; 2, j = 5;
l2 = l1 ? 1 DLQ WSEH i = 3; 4, j = 6; 7; 8. dALEE OPREDELQEM MNOVESTWO R2 = f(i; j ) 2 R : l2 = 0g, I STROIM GRAF G2 = G(V; R2)
(RIS. 23).
M
M
k
ij
ij
ij
ij
ij
ij
ij
ij
XY
1
2
3
4
5
2
1
0
0
6
0
0
2
1
7
0
2
3
0
1
2
3
4
8
0
0
4
5
5
6
7
8
G2
L2
rIS. 23
pRI k = 2 ALGORITMOM 4.1 W GRAFE G2 NAHODIM NAIBOLX[EE
PAROSO^ETANIE M2 = f(1; 6); (2; 8); (3; 5); (4; 7)g, ISPOLXZUQ M1 W
KA^ESTWE NA^ALXNOGO PAROSO^ETANIQ. tAK KAK jM2j = 4, TO ALGORITM ZAKAN^IWAET RABOTU, I M = M2 2 Arg 2min( ) l(M ),
l(M ) = P l(i; j ) = 13.
M
( )2
i;j
M
52
M
G
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
w DWUDOLXNOM NEPOLNOM GRAFE G, IZOBRAVENNOM NA RIS. 16, S TABLICEJ WESOW L, IZOBRAVENNOJ NA RIS. 24,
POSTROITX NAIBOLX[EE PAROSO^ETANIE MINIMALXNOGO WESA M ,
ISPOLXZUQ ALGORITM 6.1.
pRIMER
Y
X
1
2
3
6.2.
Y
X
1
2
3
4 5 6
-1 -3 -1
0
-2
4
-1
0
-2
5
-3
8
8
6
-1
8
8
Y
X
1
2
3
4 5 6
2 0 2
3 11 11
1 11 11
rIS. 24
rIS. 25
rIS. 26
rE[ENIE. sOGLASNO ZAME^ANI@ 6.6 STROIM SOOTWETSTWU@]IJ
GRAFU G = G(X [ Y; R) POLNYJ GRAF Gb = G(X [ Y; Rb ), GDE
Rb = R [ R~ , R~ = f(2; 5); (2; 6); (3;P5); (3; 6)g. pOLAGAEM l(2; 5) =
l(2; 6) = l(3; 5) = l(3; 6) = 8 >
jl(i; j )j = 7, KAK UKAZANO W
( )2
ZAME^ANII 6.7. tABLICA WESOW GRAFA Gb IZOBRAVENA NA RIS. 25.
pOSKOLXKU DLQ WESOW REBER GRAFA Gb NE WYPOLNQETSQ USLOWIE
(6.4), TO PERED NA^ALOM RABOTY ALGORITMA 6.1 POLOVIM l =
l(i; j ) + 3 DLQ WSEH (i; j ) 2 Rb SOGLASNO (6.5), (6.6). tABLICA WY^ISLENNYH ZNA^ENIJ l PRIWEDENA NA RIS. 26. dALEE NAHODIM
c MINIMALXNOGO WESA ALGORITMOM
W GRAFE Gb PAROSO^ETANIE M
c = f(1; 5); (3; 4); (2; 6)g. sO6.1. nETRUDNO PROWERITX, ^TO M
GLASNO ZAME^ANI@ 6.7 PAROSO^ETANIE M = f(1; 5); (3; 4)g QWLQETSQ RE[ENIEM ISHODNOJ ZADA^I, I l(M ) = ?5.
zADANIE 6.1. w DWUDOLXNYH GRAFAH S TABLICAMI WESOW, ZADANNYH NA RIS. 27, NAJTI NAIBOLX[IE PAROSO^ETANIQ M MINIMALXNOGO WESA, ISPOLXZUQ ALGORITM 6.1.
i;j
R
ij
ij
53
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
1) XY 6
1 3
2 1
3 2
4 1
5 1
7 8 9
1 3 2
8 12 10
3 7 5
9 10 8
8 9 10
10
1
7
4
5
4
2) XY 6
1 2
2 1
3 1
4 2
5 4
7
1
0
2
4
2
8 9 10
3 3 4
2 4 2
4 4 4
3 3 3
4 3 3
3) XY 6
1 5
2
3 5
4 1
5 10
7 8 9 10
6 7
2
8 12 1 7
9 7 2 4
0
0
2 9 1
4) XY 6
1
2
3 5
4 -1
5
7
8
5) XY 6 7 8
1
10
2 9 7 11
3 7 -1 6
4 2 1 3
5 5 9 7
9
1
0
-2
3
2
6) XY 6
1 3
2 7
3 4
4
5
10
5
6
1
rIS. 27
54
9 7
-2 0
8 9
7
6
2
3
9 10
2
1
2 4
0 -2
0 4
8 9 10
3 5 4
8 12 10
5 7 8
4
8
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
nESBALANSIROWANNAQ ZADA^A POSTROENIQ
NAIBOLX[EGO PAROSO^ETANIQ MINIMALXNOGO WESA W
DWUDOLXNOM GRAFE
7.
dLQ NEORIENTIROWANNOGO DWUDOLXNOGO WZWE[ENNOGO GRAFA
G = G(X [ Y; R) S WESAMI l(x; y) REBER (x; y) 2 R W PREDYDU]EM RAZDELE BYLA SFORMULIROWANA ZADA^A (6.1) POSTROENIQ
NAIBOLX[EGO PAROSO^ETANIQ MINIMALXNOGO WESA. tAM VE [email protected] METODY RE[ENIQ \TOJ ZADA^I DLQ SLU^AQ, KOGDA
jX j = jY j.
pOKAVEM TEPERX KAKIM OBRAZOM, ISPOLXZUQ ALGORITM 6.1,
MOVNO RE[ATX NESBALANSIROWANNU@ ZADA^U (6.1), T. E. OPI[EM SPOSOBY POSTROENIQ NAIBOLX[EGO PAROSO^ETANIQ M MINIMALXNOGO WESA W TOM VE GRAFE G S USLOWIEM, ^TO
jX j =6 jY j.
pUSTX W DOPOLNENIE K WYSKAZANNYM TREBOWANIQM GRAF G
QWLQETSQ POLNYM, I DLQ WESOW EGO REBER [email protected] NERAWENSTWA (6.4). pOLOVIM n1 = jX j, n2 = jY j. pOSTROIM NIVE
NA OSNOWE GRAFA G DOBAWLENIEM K NEMU NOWYH WER[IN I REBER POLNYJ DWUDOLXNYJ WZWE[ENNYJ GRAF G, U KOTOROGO ^ISLO
WER[IN W DOLQH BUDET ODINAKOWYM.
pRONUMERUEM WER[INY MNOVESTWA X OT 1 DO n1, WER[INY
MNOVESTWA Y { OT n1 + 1 DO n1 + n2, I POLOVIM
G = G(X [ Y ; R),
GDE X = X , Y = Y [ fn1 + n2 + 1; :::; n1 + n2 + (n1 ? n2)g,
R = R [ f(i; j ) : i 2 X; j 2 Y n Y g, ESLI
n1 > n2,
55
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
I X = X [ fn1 + n2 + 1; :::; n1 + n2 + (n2 ? n1)g, Y = Y , R =
R [ f(i; j ) : i 2 X n X; j 2 Y g, ESLI
n1 < n2.
wESA REBER (i; j ) 2 R GRAFA G OSTAWIM TEMI VE, ^TO I W
GRAFE G, A DLQ WSEH (i; j ) 2 R n R POLOVIM l(i; j ) = const,
NAPRIMER, l(i; j ) = 0. o^EWIDNO, ^TO DWUDOLXNYJ WZWE[ENNYJ
GRAF G QWLQETSQ POLNYM.
dALEE W GRAFE GALGORITMOM 6.1 STROITSQ NAIBOLX[EE PAROSO^ETANIE
M
MINIMALXNOGO
WESA.
tOGDA
M = M n f(i; j ) 62 Rg { RE[ENIE ISHODNOJ ZADA^I.
tRUDOEMKOSTX TAKOGO METODA RE[ENIQ NESBALANSIROWANNOJ
ZADA^I SOWPADAET S TRUDOEMKOSTX@ ALGORITMA 6.1, I SOSTAWLQET O(n4) OPERACIJ, GDE n = maxfn1; n2g.
eSLI DLQ POLNOGO GRAFA G USLOWIE (6.4) NE WYPOLNQETSQ,
TO UKAZANNYM WY[E SPOSOBOM STROIM SOOTWETSTWU@]IJ EMU
POLNYJ WZWE[ENNYJ GRAF G I NAHODIM ALGORITMOM 6.1 RE[ENIE M , A ZNA^IT, I M , SLEDUQ ZAME^ANI@ 6.5 PREDYDU]EGO RAZDELA. w SLU^AE, ESLI GRAF G NE QWLQETSQ POLNYM, DLQ
OTYSKANIQ EGO NAIBOLX[EGO PAROSO^ETANIQ M MINIMALXNOGO
WESA, SOGLASNO ZAME^ANIQM 6.6, 6.7 RAZDELA 6, ZADAEM POLNYJ
WZWE[ENNYJ GRAF Gb I K POSTROENNOMU NA EGO OSNOWE GRAFU G
PRIMENQEM ALGORITM 6.1.
w PRIMERAH WESA REBER ISHODNOGO GRAFA G I WSPOMOGATELXNOGO GRAFA G BUDEM ZADAWATX, KAK I W PREDYDU]EM RAZDELE, W
WIDE TABLIC.
pRIMER. w DWUDOLXNOM
POLNOM GRAFE G S MNOVESTWAMI X =
f1; :::; 4g, Y = f5; :::; 10g I TABLICEJ WESOW, IZOBRAVENNOJ NA
56
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
RIS. 28, POSTROITX NAIBOLX[EE PAROSO^ETANIE MINIMALXNOGO
WESA M .
XY 5 6 7 8 9 10
1
2
3
4
-2
6
4
2
1
2
-1
0
2 -2 3
3 5 5
4 3 2
4 5 6
1
6
2
3
rIS. 28
rE[ENIE. dOBAWLQQ K GRAFU G DWE WER[INY I 12 REBER, STROIM SOOTWETSTWU@]IJ EMU GRAF G = G(X [ Y ; R), W KOTOROM
X = f1; 2; 3; 4; 11; 12g, Y = f5; 6; 7; 8; 9; 10g, R = R [ f(i; j ) : i =
11; 12; j = 5; 6; 7; 8; 9; 10g, I POLAGAEM l(i; j ) = 0 8 (i; j ) 2 R n R.
tABLICA WESOW GRAFA G IZOBRAVENA NA RIS. 29.
XY
1
2
3
4
11
12
5
-2
6
4
2
0
0
6
1
2
-1
0
0
0
7 8 9 10
2 -2 3 1
3 5 5 6
4 3 2 2
4 5 6 3
0 0 0 0
0 0 0 0
rIS. 29
57
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
nAHODIM TEPERX W GRAFE G NAIBOLX[EE PAROSO^ETANIE M MINIMALXNOGO WESA ALGORITMOM 6.1 S U^ETOM
ZAME^ANIQ 6.5.
nETRUDNO PROWERITX, ^TO, NAPRIMER, M = f(1; 8); (2; 7); (3; 6);
(4; 5); (5; 11); (6; 12)g. tOGDA M = f(1; 8)
; (2; 7); (3; 6); (4; 5)g {
P
RE[ENIE ISHODNOJ ZADA^I, I l(M ) =
l(i; j ) = 2.
( )2
i;j
M
w DWUDOLXNYH GRAFAH S TABLICAMI WESOW, IZOBRAVENNYH NA RIS. 30, NAJTI NAIBOLX[IE PAROSO^ETANIQ M MINIMALXNOGO WESA.
1) XY 4 5 6 7 8
2) XY 4 5 6 7 8
zADANIE
7.1.
1 8 9 10 1
2 10 8 12 1
3 5 9 7 2
3) XY 6
1 3
2 7
3 4
4 5
5 4
7
6
2
5
7
4
1
2
3
9
8
2
2 7 5 4
1 12 10 7
4 4 3 2
8 4) XY 6 7 8 5) XY
3
1 8 -1 3
1
8
2
5
2
3
2
3
4
-1
4
5
2
5
rIS. 30
58
6
2
8
-1
5
4
7
0
5
-2
3
5
8
-1
2
-3
0
-1
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
otwety
zADANIE 2.1.
1) P (4; 1) = ((4; 6); (6; 5); (5; 3); (3; 1)),
l(P (4; 1)) = 9;
2) P (4; 3) = ((4; 6); (6; 5); (5; 3)), l(P (4; 3)) = 7;
3) P (6; 2) = ((6; 4); (4; 2)), l(P (6; 2)) = 1;
4) P (6; 3) = ((6; 5); (5; 3)), l(P (6; 3)) = 7.
zADANIE 2.2.
1) P (v1; v5) = ((v1; v3); (v3; v4); (v4; v6); (v6; v5)),
l(P (v1; v5)) = 7;
2) P (v1; v6) = ((v1; v3); (v3; v4); (v4; v6)), l(P (v1; v6)) = 5;
3) P (v2; v5) = ((v2; v1); (v1; v3); (v3; v4); (v4; v6); (v6; v5)),
l(P (v2; v5)) = 7;
4) P (v2; v6) = ((v2; v1); (v1; v3); (v3; v4); (v4; v6)),
l(P (v2; v6)) = 5;
5) P (v3; v5) = ((v3; v4); (v4; v6); (v6; v5)), l(P (v3; v5)) = 4;
6) P (v4; v5) = ((v4; v6); (v6; v5)), l(P (v4; v5)) = 4.
59
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
zADANIE
1) i j
1
2
3
2) i j
1
2
3
4
2.3.
1
2
P
((1,3),(3,2))
0
3
(2,1)
P
-3
0
((3,2),(2,1)) (3,2)
-1
2
1
3
(1,3)
1
((2,1),(1,3))
-2
P
0
2
3
4
((1,3),(3,2)) (1,3)
((1,3),(3,4))
P
0
-3
1
-1
(2,1)
((2,1),(1,3)) ((2,1),(1,3),(3,4))
P
3
0
0
2
((3,4),(4,1)) (3,2)
P
(3,4)
4
4
0
2
((4,1),(1,3),(3,2))
(4,1)
((4,1),(1,3)) P 3
-1
0
2
60
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
3) i j
1
2
3
4
4)
i
1
2
3
4
j
4
2
3
((1,3),(3,2)) (1,3)
((1,3),(3,2),(2,4))
P
2
0
1
4
(2,1)
((2,4),(4,3))(2,4)
P
1
2
0
3
((3,2),(2,4))
((3,2),(2,1))
(3,2)
P
-1
-3
0
-2
((4,3),(3,2),(2,1))((4,3),(3,2)) (4,3)
P
1
-1
2
0
1
1
2
3
4
(1,2)
((1,2),(2,4),(4,3))((1,2),(2,4))
P
0
0
3
7
((2,4),(4,3),(3,1))P ((2,4),(4,3)) (2,4)
-3
0
-7
-4
(3,1)
((3,1),(1,2)) P
((3,1),(1,2),(2,4))
4
0
11
7
((4,3),(3,1))
((4,3),(3,1),(1,2))(4,3)
P
-3
1
8
0
61
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
5) i j
1
P
10
(2,1)
21
((3,4),(4,1))
3 -1
(4,1)
43
6) i j
1
2
3
4
2
3
4
((1,3),(3,4))
(1,2)
(1,3)
1
5
1
((2,1),(1,3)) ((2,1),(1,3),(3,4))
P
0
6
2
((3,4),(4,2)) P
(3,4)
0
-4
0
(4,2)
((4,1),(1,3)) P 4
8
0
1
2
3
((1,3),(3,2)) (1,3)
P
0
2
-1
((2,4),(4,1)) P
((2,4),(4,1),(1,3))
4
2
0
((3,2),(2,4), (3,2)
P
(4,1))
-3
0
-1
(4,1)
((4,1),(1,3), ((4,1),(1,3))
3
2 (3,2)) 5
62
4
((1,3),(3,2),(2,4))
-2
(2,4)
-1
((3,2),(2,4))
-4
P
0
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
zADANIE 3.1.
1) l(G) = 9;
2) l(G) = 10;
3) l(G) = 12;
4) l(G) = 13;
zADANIE 4.1.
1) jM j = 3;
2) jM j = 4;
3) jM j = 3;
4) jM j = 4;
5) jM j = 3;
6) jM j = 3.
zADANIE 5.1.
1) jV j = 3;
2) jV j = 4;
3) jV j = 3;
4) jV j = 4;
5) jV j = 3;
6) jV j = 3.
zADANIE 6.1.
1) jM j = 5, l(M ) = 19;
2) jM j = 5, l(M ) = 10;
3) jM j = 5, l(M ) = 13;
63
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
4) jM j = 4, l(M ) = 8;
5) jM j = 5, l(M ) = 12;
6) jM j = 4, l(M ) = 13.
zADANIE 7.1.
1) jM j = 3, l(M ) = 11;
2) jM j = 3, l(M ) = 7;
3) jM j = 3, l(M ) = 9;
4) jM j = 2, l(M ) = ?2;
5) jM j = 3, l(M ) = ?2;
64
aLGORITMY RE[ENIQ OPTIMIZACIONNYH ZADA^ : : :
lITERATURA
[1] eMELI^EW w. a., mELXNIKOW o. i., sARWANOW w. i., tY[KEWI^
r. i. lEKCII PO TEORII GRAFOW.{ m:. nAUKA. { gL. RED. FIZ.MAT. LIT., 1990. { 384 S. { ISBN 5-02-013992-0.
[2] kRISTOFIDES n. tEORIQ GRAFOW. aLGORITMI^ESKIJ PODHOD.{
m.: mIR, 1978. { 432 S.
[3] mAJNIKA |. aLGORITMY OPTIMIZACII NA SETQH I GRAFAH.{ m.:
mIR, 1981. { 323 S.
[4] pAPADIMITRIU h., sTAJGLIC k. kOMBINATORNAQ OPTIMIZACIQ. aLGORITMY I SLOVNOSTX. { m.: mIR, 1985. { 512 S.
[5] rEJNGOLXD |., nIWERGELXT `., dEO n. kOMBINATORNYE ALGORITMY. tEORIQ I PRAKTIKA. { m.: mIR, 1980. { 476 S.
[6] hU t. cELO^ISLENNOE PROGRAMMIROWANIE I POTOKI W SETQH. {
m.: mIR, 1974. { 519 S.
[7] Dijkstr a E. W. A Note on Two Problems in Connecxion with
Graphs, Numer. Math., 1.{ N 3.{ 1959. { Pp. 269 { 271.
[8] Edmonds J. Paths, Trees and Flowers, Can. J. Math. { Vol. 17. {
1965. { Pp. 449 { 467.
65
i. q. zABOTIN, w. r. fAZYLOW, o. n. {ULXGINA
[9] Edmonds J., Johnson E. Matching: A Well Solved Class of
Integer Linear Programs, Combinatorial Structures and Their
Applications, Gordon and Breach, New York.{ 1970. { Pp. 89
{ 92.
[10] Kruskal J. B. On the Shortest Spanning Subtree of a Graph and
the Traveling Selesman Problem, Proc. AMS, 7. { 1956. { Pp. 48
{ 50.
[11] Floyd R. Z. Algorithm 97, Shortest Path, Comm. ACM, 5.{ 1962.
{ Pp. 345.
66
zABOTIN iGORX qROSLAWI^,
fAZYLOW wALERIJ rAUFOWI^,
{ULXGINA oKSANA nIKOLAEWNA
aLGORITMY RE[ENIQ OPTIMIZACIONNYH
ZADA^ NA GRAFAH
u^EBNOE POSOBIE
pODPISANO W PE^ATX 16.03.06.
bUMAGA OFSETNAQ. fORMAT 6084 1/16. gARNITURA "tAJMS".
pE^ATX RIZOGRAFI^ESKAQ. uSL. PE^. L. 3,95.
u^.-IZD. L. 4,25. tIRAV 150 \KZ. zAKAZ 3/100.
iZDATELXSTWO
"kAZANSKIJ GOSUDARSTWENNYJ UNIWERSITET
IM. w. i. uLXQNOWA-lENINA"
oTPE^ATANO S GOTOWOGO ORIGINAL-MAKETA
W TIPOGRAFII IZDATELXSKOGO CENTRA
kAZANSKOGO GOSUDARSTWENNOGO UNIWERSITETA
IM. w. i. uLXQNOWA-lENINA
420008, G. kAZANX, UL. uNIWERSITETSKAQ, 17
TEL. 31-53-59, 92-65-60
1/--страниц
Пожаловаться на содержимое документа