<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1></div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

Vơ ¼nh Háav é Minh TuƠn, Thuêt toĂnathựctẳmtêp ờnnhtrong

cỹc Ôicừa ỗ th lữùng phƠn 3

Nguyạn Th ThanhVƠn, PhÔm Th Mai BÊo, ng ThnhTrung, Nguyạn

Thá Lởc v Said Elnaffar, pdửngphữỡngphĂp phƯntỷhỳuhÔnvợiphữỡng

phĂp tẳm kiámtối ữu ton cửc cho bitoĂn Êo iằn tƠm ỗ 12

Nguyạn TƠn n, Mổ hẳnh hằ thống dỹ bĂo ựng dửng mÔng nỡron mớ thỷ

nghiằmtrản số liằuthới tiát cừa tnh Vắnh Phúc 24

Nguyạn Thnh Quang v Dữỡng XuƠn GiĂp, MởtsốtẵnhchĐt vÃathực

nhiÃu bián tronglẵ thuyát cỡ sGr

ă

obner 33

Dữỡng Quang Phũng, TrƯn Minh ực v TrƯn ực Lữủng, Tờng hủp

vnghiảncựu tẵnh chĐt xúctĂc quang hõacừa hÔt nanoTiO

2

pha tÔpLatrong
phÊn ựng oxi hõa benzen, phenol bơng Ănh sĂng tỷngoÔi 44

TrƯn Th Hỗng VƠn, Nguyạn Viát Hũng, Lả ực Liảm v Lả Th

Duyản, XĂcnhhm lữủngvátselen trongmởt sốhÊisÊn bơngphữỡngphĂp

Von-Ampe hỏa tan catot 54

TrƯn CổngViằt v Nguyạn Chẵ ực, NghiảncựuxĂcnhhmlữủngcrom

trong mởt số mău rau v nữợc nổng nghiằp Tứ Sỡn, Bưc Ninh bơng phữỡng

phĂp phờ hĐp thử nguyản tỷ trongngồn lỷa(F-AAS) 64

Nguyạn Hoi Nam v TrƯn Vôn Chung, Chá tÔo vêt liằu hĐp phử hai

thnhphƯn FeOOH/SiO

2

theo phữỡngphĂp nhiằt thừy phƠn 71

Nguyạn LƠn Hũng Sỡn v Nguyạn Tián ực, Mởtsố dăn liằuvà hailoi

chimKhữợumo Ưuen vKhữợuƯutrưngphƠnban KheRộ,khubÊo tỗn

thiản nhiảnTƠy Yản Tỷ, tnh Bưc Giang 82

ộ Vôn Nhữủng, Bũi Minh Hỗng v Vữỡng Th nh, ThnhphƯn loi

cừa mởt số hồthuởc bở C¡nh cùng (Coleoptera)v  gi¡tràch¿ thà sinh th¡i cõa

chóng ð thà trĐn TamÊo, tnh Vắnh Phúc 89

Bũi Minh Hỗng, Nguyạn PhữỡngThÊo v PhÔm Thu Lan, Nghiản cựu

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

TổmHe (Penaeidae) vũng ven bin tnh Bán Tre nôm 2008 v 2009 107

Nguyạn ThanhTũng,Nguyạn ThNhivộVônNhữủng, ThnhphƯn

loiv c im phƠn bố cừa giun Đt huyằn Vụng Liảm, tnh Vắnh Long 112

Nguyạn Vôn Thuên v Nguyạn Th M Hơng, Thnh phƯn loi v c

imphƠn bốcừa giun Đt tnh TiÃn Giang 121

Mai Vôn Hững, Nghiản cựu mởt số chực nông phời cừa sinh viản trữớngÔi

hồcGiĂodửc, Ôi hồc Quốcgia HNởi 130

TrƯn Th Thanh HuyÃn, Lả Th Thừy v Nguyạn Nhữ Khanh, Sỹ bián

ởnghmlữủngprolinliảnquan ánkhÊnông chuhÔn giaioÔncƠynon cừa

20giống vứng (Sesamum indicumL.)trong iÃu kiằn hÔn nhƠn tÔo 137

Nguyạn ThKimChữỡng, PhữỡngphĂpphƠntẵchlữu vỹcsổng phửcvửqui

hoÔch sỷdửng Đt 143

Nguyạn ThĂm, Nguyạn Hong Sỡn v Nguyạn ông ở, ĂnhgiĂtờng

hủp ti nguyản nữợc lữu vỹc sổng Hữỡng v à xuĐt cĂc giÊi phĂp khai thĂc

nguỗnnữợc trản quan im phĂt trin bÃn vỳng 155

o Khang, TĂc ởng cừa iÃu kiằn a lẵ án têp quĂn canh tĂc cừa ngữới

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

Natural Sci.,2010, Vol.55, No.3, pp. 3-11

THUŠT TON A THÙC TœM TŠP ÊN NH TRONG CĩC I

CếA ầ TH LìẽNG PHN

Vụ ẳnh Hỏa

Trữớng Ôi hồc Sữ phÔm H Nởi

ộ Minh TuƠn

Trữớng Cao ng Sữ phÔm Nam nh

1. M Ưu

Trong bi ny chúng tổi ch sỷ dửng ỡn ỗ th vổ hữợng, cĂc kẵ hiằu chẵnh

và ỗ th ữủc sỷ dửng theo [5] cừa Sachs. Cho trữợc mởt ỡn ỗ th vổ hữợng

G

= (

V, E

)

.

G

ữủc gồi l ỗ th lữùng phƠn náu têp nh

V

cõ mởt phƠn hoÔch

(

A, B

)

sao cho cÔnh tũy ỵ cừa

G

nối mởt nh cừa

A

vợi mởt nh cừa

B

, trong
trữớnghủp

G

l ỗ th lữùng phƠn taviát

G

= (

A, B

;

E

)

.Mởt têp hủp nh

T

cừa

G

ữủc nõiltêp nh ởc lêpnáu hainh bĐt kẳ cừa nõkhổng kà nhau. BitoĂn
xĂcnhchsố ờnnhtrongcừa

G

,kẵhiằul

(

G

)

lbitoĂnxĂcnhsốlợnnhĐt
cĂc nh ổi mởt khổng kà nhau trong

G

. B i to¡n x¡c ành ch¿ sè ên nh trong
cừa ỗth

G

chotrữợcl bitoĂn NondeterministicPolynomialTime (

NP C

) [4].

Nhêp: ỡn ỗth vổ hữợng

G

v sốtỹ nhiản

k

.

CƠu họi:Cõ tỗn tÔi

k

nh ổimởt khổng kà nhau trong

G

khổng?

McdũcõởphựctÔp cao,TajzanvTrojanowski[6]ÃxuĐtmởtthuêttoĂn

xĂc nh chsố ờnnh trong cừa ỡn ỗ th vổhữợng.

Nôm1959, Gallai[3] Â nh nghắa mởt thổng số mợi choỗ th

G

. Mởt têp
hủp

R

cĂc nh ữủc gồi l têp hủp nh phừ cÔnh náu nhữ cÔnh tũy ỵ cõ ẵt nhĐt
mởt nh thuởc

R

. Sốnhọ nhĐt cõ th cĂc nh phừ cÔnh cừa

G

kẵ hiằu l

(

G

)

.

Trong ỗth Petersen

G

(Hẳnh 1) tacõ

α

(

G

) = 4

v 

γ

(

G

) = 6

.

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

1

2

3

4

5

6

7

8

9

10

H¼nh 1. ỗ th Petersen

2. Nởi dung nghiản cựu

2.1. Mởt vi kát quÊ cỡ s

Mối quan hằ giỳa

(

G

)

v

(

G

)

ữủcGallaiphĂt hiằn trong [3].
nh lẵ 2.1. Cho trữợc ỡn ỗ th vổ hữợng

G

= (

V, E

)

ta cõ:

|

V

|

=

(

G

) +

(

G

)

.

ối vợi ỗth lữùng phƠn, Konig Âchựng minh trong [1]kátquÊ sau:

nh lẵ 2.2. Trongỗ th lữùng phƠn

G

= (

X, Y

;

E

)

, số lợn nhĐt cĂc cÔnh ổi mởt
khổng cõ nh chung úng bơng số nhọ nhĐt cĂc nh phừ cĂc cÔnh cừa

G

, tực l

(

G

) =

(

G

)

.

Kát quÊny cừa Konig l trữớnghủp riảng cừa nh lẵMenger [2]:

nh lẵ 2.3. Sốlợn nhĐtcĂc ữớng ổimởt khổng cõnh chung trong nốihai nh

u

v

v

khổngkà nhau cừa mởt ỡnỗ th vổ hữợng chotrữợc úng bơngsố nhọ nhĐt
cĂc nh phƠn cĂch hai nh

u

v

v

.

Tứ nhlẵ 2.1v nh lẵ2.2, tacõkát quÊsau:

nh lẵ 2.4. Trong ỗ th lữùng phƠn

G

= (

X, Y

;

E

)

vợi

n

nh, ta cõ

(

G

) +

(

G

) =

n.

Nhữvêy,tronglợpỗthlữùngphƠn, viằcxĂcnhch sốờnnh trongữủc

ữa và xĂcnh số lợnnhĐt cĂc cÔnh ổimởt khổng kà nhau. Vẳ bitoĂn xĂcnh

số lợn nhĐt cĂc cÔnh ổi mởt khổng kà nhau trong ỗ th lữùng phƠn cõ th giÊi

ữủc bi thuêt toĂn Ford-Fulkersonvợi ởphực tÔp

O

(|

V

|

2

_.

_|

_E

_|)

,nản ta cõth xĂc

nhữủc chsố ờnnh trongcừa ỗ th lữùngphƠn

G

= (

X, Y

;

E

)

vợimởt thuêt
toĂn cõởphực tÔp

O

(|

V

|

2

_.

_|

_E

_|)

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

2.2. XĂc nh têp ờn nh trong cỹc Ôi

Lữu ỵ rơng,ngay cÊkhi biátchsốờn nhtrong cừa ỗth, thẳ văncỏn mởt

vĐn à nỳa l phÊi xĂc nh mởt têp ờn nh lợn nhĐt cõ th. Viằc biát ch số ờn

nhtrong chgiúp chúng taxĂcnh ữủc mởttêp hủpcĂc nh ổimởtkhổng kÃ

nhau cho trữợc cõ phÊi l têp hđp ên ành câ sè ¿nh nhi·u nh§t hay khỉng. Sau

Ơy chúng tổi à xuĐt mởt thuêt toĂn xĂc nh têp ờn nh trong cõ nhiÃu nh

nhĐt trong ỗth dỹa trản mởt têp cõnhiÃu cÔnh ổimởt khổng kà nhau nhĐt.

Thuêt toĂn: GiÊsỷ

S

l têp hủp cõ

(

G

) =

k

cÔnh ổi mởt khổng kà nhau trong
ỗ th lữùng phƠn

G

= (

X, Y

;

E

)

. Tatổ mu cĂc cÔnh cừa

S

mu ọ, v cĂc cÔnh

cỏn lÔi cừa ỗ th mu xanh. Ănh số cĂc nh thuởc

X

ml nh cừa mởt cÔnh
ọ l

x1

, x2, . . . , x

k

v  c¡c ¿nh cõa

Y

k· vỵi

x1, x2, . . . , x

k

qua cÔnh mu ọ l

y1, y2, . . . , y

k

. °t

A

=

X

− {

x1

, x2

, . . . , x

k

}

v 

B

=

Y

− {

y1, y2, . . . , y

k

}

. Ta gåi
÷íng m  c¡c cÔnh cừa nõ an mu nhau (khổng cõ hai cÔnh liảntiáp nhau cũng

mu) lữớng an mu.

TaphƠn cĂc ữớngan mu thnh 3 loÔi:

ữớng an mu loÔi 1: ữớng bưt Ưu bơng cÔnh mu ọ v kát thúc bơng

cÔnh mu ọ.

ữớng anmu loÔi2: ữớngbưt Ưu bơngcÔnh muxanh v kátthúc bơng

cÔnh ọ. nh bưt Ưu l nhthuởcA.

ữớng anmu loÔi3: ữớngbưt Ưu bơngcÔnh muxanh v kátthúc bơng

cÔnh ọ. nh bưt Ưu l nhthuởcB.

Thuêt toĂn:

Bữợc1.DũngthuêttoĂnữớngmtẳmữủcbởghpcỹcÔi:

(

x1, y1

)

,

(

x2, y2

)

,
...,

(

x

k

, y

k

)

.°t

X

0

₌

_{

_x

1

, x

2

, ..., x

k

}

,

Y

0

₌

_{

_y

1

, y

2

, ..., y

k

}

v

A

=

X

X

0

,

B

=

Y

Y

0

.

Bữợc 2. Nhỳng nh thuởc

A, B

tổmu 1.

Bữợc 3. Khi tÔo. CĂc nh thuởc X' v Y'cõ mu 0 (chữa ữủctổ mu).

Bữợc 4. Xt tĐt cÊ cĂc nh

u

A

kà vợi ẵt nhĐt mởt nh thuởc

Y

0

cõ mu

0. XƠy dỹng cƠy

BF S

(

u

)

chựa tĐt cÊcĂc ữớng an m u xu§t ph¡t tø

u

chùa c¡c
¿nh câ m u 0. CƠy ny chựa tĐt cÊ cĂc ữớng an mu loÔi 2. Do ¿nh

u

câm u
1 n¶n nhúng ¿nh thuëc

Y

0

câ m u 2 v  nhúng ¿nh trong

X

0

câ m°t trong c¥y s

cõmu 1.

Bữợc 5. Xt tĐtcÊ cĂc nh

v

B

kà vợi ẵt nhĐt mởt nh thuởc

X

0

cõmu

0.XƠy dỹng cƠy

BF S

(

v

)

chựa tĐt cÊcĂc ữớng an muxuĐtphĂt tứ

vu

chựa cĂc
nhcõ mu0.CƠy ny chựa tĐtcÊcĂc ữớngan mu loÔi2.Do nh

v

cõmu 1
nản nhỳngnh thuëc

X

0

câm u 2 v  nhúng¿nh trong

Y

0

câ m°t trongc¥y s³câ

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

Bữợc 6. XttĐtcÊ cĂcnh

x

j

X

0

cõmu 0(

j

= 1

, ..., k

),nâ÷đcg¡n m u

1v  ¿nh

y

j

g¡n m u 2.

Gåi

M

l  têp cĂc nh tổ mu 1. Khi õ

M

chẵnh l têp ờn nh trong lợn
nhĐtcƯn tẳm.

Vẵ dử: Xt

K2

,

4

.

X

=

{

x1, y1

}

,

Y

=

{

y1, y2, y3, y4

}

. Thüc hi»n thuªt toĂn tacõ.
Bữợc 1. Bởghpcỹc Ôi

(

x1, y1

)

,

(

x2, y2

)

.

X

0

₌

_{

_x1

_{, x2}

_}

,

Y

0

₌

_{

_{y1, y2}

_}

.

A

=

,

B

=

{

y3, y4

}

.

Bữợc 2. nh

y3, y4

cõ mu 1.

Bữợc 3. CĂc nh

x

1

, x

2

, y

1

, y

2

cõmu 0.
Bữợc 4. Khổngcõ nh no thuởc

A

.

Bữợc 5. Xtnh

y3

B

. Ta cõcƠy

BF S

(

y3

)

.

y

3

x

1

x

2

y

1

y

2

Hẳnh 2.

Khi õnh

y3, y1, y2

cõ mu 1.¿nh

x1, x2

câm u 2.

X²t ¿nh

y4

∈

B

. Khi âkhæng cõ nh no cõmu 0 kÃvợi

y4

.
Bữợc 6. Do khổng cỏn nh no cừa

X

0

cõmu 0 nản thuêt toĂn kátthúc.

Têpởc lêplợnnhĐt l:

M

=

{

y3, y4, y1, y2

}

.

BƠy giớ tachựng minh tẵnh úng ưn cừa thuêt toĂn:

Chựng minh.

ã

Ta xƠy dỹngtêp

M

:

V

=

X

Y

.

K

=

{1

,

2

, ..., k

}

.

GiÊsỷbởghpcỹcÔi

k

cpl

E0

=

{

e1

= (

x1, y1

)

, e2

= (

x2, y2

)

, .., e

k

= (

x

k

, y

k

)}

vỵi

x

i

∈

X, y

i

∈

Y

,

∀

i

= 1

,

2

, .., k

.

A

=

{

x1, x2, ..., x

k

}

,

B

=

{

y1, y2, ..., y

k

}

.

y1

y2

y3

y

k

v

x1

x2

x3

x

k

u

....

....

....

....

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>

Nhỳng cÔnh trong

E

0

l cĂc cÔnh êm, cỏn lÔil cĂc cÔnh nhÔt.
Ch cõúng

k

cÔnh êm lcĂc cÔnh nơm trong

E0

.

Khổngcõ cÔnhnhÔt no nối2 nh cừa

X

A

v

Y

B

[1].

Vẳ náu cõcÔnh

(

u, v

)

E

vợi

u

X

A

v

v

Y

B

thẳ ta cõ th kátnÔp
cÔnh

(

u, v

)

vo

E0

.iÃunymƠuthuăn vợitẵnhcỹc Ôicừa

E0

.NhữvêycÔnh nhÔt
ch cõth cõ dÔng

(

u, v

)

vợi

u

A

hoc

v

B

.

TaxƠy dỹng têp

M

= (

X

A

)

(

Y

B

)

P

lởc lêp.
éõ

P

=

{

p1, p2, ..., p

k

}

A

B

.ữủcxƠy dỹng nhữ sau:
LĐy nh

u

V

. Ta phƠnnh

u

lm3 loÔinhữ sau:

LoÔi1:

u

A

B

vcõữớngmanmutứmởtnhthuởc

(

X

A

)(

Y

B

)

tợi

u

.

LoÔi 2:

u

A

∪

B

v  khỉng câ ÷íng mð an m u n o tø mởt nh thuởc

(

X

A

)

(

Y

B

)

tợi nh

u

.

LoÔi 3:

u

(

X

A

)

(

Y

B

)

.

Náu

u

A

B

ta kẵ hiằu

f

(

u

)

lnh cỏn lÔicừa cÔnh êm chựa

u

.
Khi õ, taxƠy dỹng têp

P

nhữ sau:

u

lmởt nh cừa cÔnh

e

j

;

p

j

=

u

náu

u

lnh loÔi1 v

u

lim Ưu cừa cÔnh êm;

p

j

=

f

(

u

)

náu

u

lnh loÔi1 v

u

lim Ưu cừa cÔnhnhÔt;

p

j

=

x

j

náu

u

lnh loÔi 2.

Khi õ

M

=

P

(

X

A

)

(

Y

B

)

chẵnh l têp cƯn tẳm.

nh nghắa trản l hủp lẵ vẳ nh

u

v

f

(

u

)

khổng th cũng l loÔi 1. Náu
chúng cũng l loÔi1 thẳ khổng mĐt tẵnh tờng quĂt giÊsỷ

u

A

v

f

(

u

)

B

.

Vẳ

u

,

f

(

u

)

l loÔi 1 nản tỗn tÔi

y

Y

−

B

v 

y

i

1

, ..., y

i

m

, y

j

1

, ..., y

j

p

∈

B

v

x

X

A

v

x

i

1

, ..., x

i

m

, x

j

1

, ..., x

j

p

A

nhữ hẳnh v³:

x

y

i

₁

x

i

₁

y

i

₂

y

i

m

x

i

m

f

(

u

)

u

y

x

j

₁

y

j

₁

x

j

₂

x

j

m

y

j

m

u

f

(

u

)

H¼nh 4.

</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>

x

y

_i

₁

x

_i

₁

y

_i

₂

y

_i

_m

x

_i

_m

_f

₍

_u

₎

y

x

_j

₁

y

_j

₁

x

_j

₂

x

_j

_p

y

_j

_p

u

H¼nh 5.

°t

K0

=

{

i1, i2, ..., i

m

, j1, j2, .., j

p

}

.

Khi õÊo mƯu cÔnh taữủc:

x

y

i

1

x

i

1

y

i

2

y

i

m

x

i

m

f

(

u

)

y

x

j

1

y

j

1

x

j

2

x

j

p

y

j

p

u

H¼nh 6.

°t

E

0

_{= (}

_E0

₋

_({

_e

j

|

j

∈

K

−

K0

} ∪ {(

u, f

(

u

))}))∪

(

x, y

i

1

)

,

(

x

i

1

, y

i

2

)

, ...,

(

x

i

m

, f

(

u

))

,

(

u, y

j

p

)

, ...,

(

x

j

2

, y

j

1

)

,

(

x

j

1

, y

)

.

Khi â

E

0

côngl mëtbëgh²pv 

|

E

0

_|

₌

_k

₋

₍

_m

₊

_n

_{+ 1) + (}

_m

_{+ 1) + (}

_n

_{+ 1) =}

k

+ 1

> k

=

|

E0

|

mƠu thuăn vợitẵnh cỹc Ôi cừa

E0

.

ã

M

cõ

n

k

nh. Nhữ trản ta  xƠy dỹng ữủc têp

P

v do õ xƠy

dỹng ữủc têp

M

. V số phƯn tỷ cừa

M

l

|

M

|

=

|

X

−

A

|

+

|

Y

−

A

|

+

|

P

|

=

(|

X

| −

k

) + (|

Y

|

k

) +

k

= (|

X

|

+

|

Y

|)

k

=

n

k

.

ã

Chựng minh

M

l têp nh ởc lêp.
Nhên xt:ữớng mtrong

G

cõ 4 dÔng:

- XuĐtphĂt l cÔnh êm, kát thúc lcÔnh êm.

- XuĐt phĂt l cÔnh êm, kát thúc l cÔnh nhÔt vợi nh kát thúc l nh

khổng thuởc

A

B

.

- XuĐt phĂt l cÔnh nhÔt, kát thúc l cÔnh êm vợi nh xuĐt phĂt l nh

khổng thuởc

A

B

.

- XuĐt phĂt l cÔnh nhÔt, kát thúc l cÔnh nhÔt. Vợi nh xuĐt phĂt v kát

thúc l cĂc nh khổng thuởc

A

B

.

Trữớnghủp 4 khổng xÊy ra(náu xÊy rata Êo mu cÔnh,số bở ghp stông

</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

Trữớng hủp 2,3 bÊn chĐt l mởt vẳ chúng Êo chiÃu vợi nhau.

Chẵnhvẳ thá ữớng mtrong

G

ch cõ2 dÔng 1v2.
LĐy

u, v

M, u

6=

v

bĐt kẳ.Tachựng minh

u, v

ởc lêp.
Náu

u, v

cũng l nh loÔi3,ró rng

u, v

ởc lêp(do (1)).
Náu

u, v

cũng l nh loÔi2,thẳ

u, v

A

.Vêy

u, v

ởc lêp.

Náu

u, v

cũng l nh loÔi1, thẳ hoc

u, v

∈

A

ho°c

u, v

∈

B

, khi â rãr ng

u, v

ởclêp.Náu

u

A

,

v

B

tachựng minh

u, v

ởclêp.GiÊsỷngữủclÔi,cõcÔnh

e

= (

u, v

)

E

.

e

khổng thlcÔnhêmữủc,vẳnáu lcÔnh êmthẳ

v

=

f

(

u

)

iÃu
ny mƠu thuăn do

u, f

(

u

)

khổng th cũng l nh loÔi 1. Cỏn náu

e

l cÔnh nhÔt,
xuĐtphĂt tứ

u

taữủc mởt ữớng mdÔng 2.XuĐtphĂt tứ

v

ta cụng ữủc ữớng
mdÔng 2.Rórng

u, v

khổngnơm trảnữớngmcừa nhau.Nối2ữớngmbơng
cÔnh

e

.Taữủcữớng mxuĐtphĂt lcÔnh nhÔt v kát thúc l cÔnhnhÔt, Ơy l
ữớngm dÔng 4.iÃu ny mƠu thuăn vẳ dÔng 4 khổng tỗn tÔi.

Náu

u

loÔi1,

v

loÔi3,ró rng

u, v

ởclêp.
Náu

u

loÔi2,

v

loÔi3,ró rng

u, v

ởclêp.

Náu

u

loÔi2,

v

loÔi 1,khi õ

u

A

. Náu

v

A

thẳ

u, v

ởc lêp. Vêy ch cƯn
xt

v

B

. Náu tỗn tÔi cÔnh

e

= (

u, v

)

∈

E

. Rã r ng

v

6=

f

(

u

)

. Xu§t phĂt tứ

v

ta
xƠy dỹng mởt ữớng m án mởt nh

y

Y

B

. XƠy dỹng ữớng m tứ

u

. Ró
rng

v

khổng nơm trản ữớng ny. Chêp 2 ữớng i ny bi ữớng nối

e

. Do õ

f

(

u

)

nơm trản ữớng mnốinh

u

vợinh

y

Y

B

.

f

(u)

u

v

y

Hẳnh 7.

Vêy

f

(

u

)

P

.iÃu ny mƠu thuăn vợi

u

P

.
Vêy

M

l têp ởc lêp.

ã

Chựng minh

M

l cỹc Ôi.

LĐy

u0

V

M

lmởt nh no õ. Xttêp

M

0

₌

_M

_{

_u0

_}

.

Rórng

u0

A

hoc

B

.KhổngmĐttẵnhtờngquĂtgiÊsỷ

u0

A

doõ

u0

=

x

j

vợi

j

K

. Vẳ

u0

/

M

nản

u0

=

x

j

/

P

.Vêy

y

j

P

.LÔi cõ

(

u0, y

j

) = (

x

j

, y

j

)

E

ð
â

u0

∈

M

0

_{, y}

j

∈

P

⊂

M

⊂

M

0

, n¶n

M

0

khỉng l  têp ởc lêp. Vẳ thá

M

ltêp ởc
lêpcỹc Ôi.

2.3. Thuêt to¡n heuristic x¡c ành mët tªp ên ành trong cõa

mët ỗ th cho trữợc

Trữợchát taxt thuêt toĂn heuristicsau choỗ th 3 lợp.

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

Thuêt toĂnHeuristic:

Bữợc 1. Bọ cĂc cÔnh nối cĂc nh cừa

Y, Z

. ữủc ỗth 2phẵa

G

0

_{= (}

_{X, Y}



Z

;

E

0

₎

_.

Bữợc 2. p dửng thuêt toĂn trản tẳm ữủc têp ởc lêp lợn nhĐt cừa

G

0

l

M1

=

X1

Y1

Z1.

Bữợc 3. Xt ỗ th 2 phẵa

G

00

_{= (}

_{Y1, Z1}

_;

_E

00

₎

sinh tứ ỗ th

G

khi bọ i cĂc
nh khổng thuởc

Y1, Z1

. p dửng tiáp thuêt toĂn trản tẳm ữủc têp ởc lêp lợn
nhĐtl

Y

2

Z

2

.

Khi õtêp

M

=

X1

Y2

Z2

l mởt têp ởc lêp cõsố phƯn tỷ gƯn bơng số
phƯn tỷcừa têp ởc lêplợnnhĐt.

Vẵ dử: Xt ỗth

K2

,

3

,

4

. Vợi

X

=

{

x1, x2

}

,

Y

=

{

y1, y2, y3

}

,

Z

=

{

z1

, z2, z3, z4

}

.
Bữợc 1. Bọ cĂc cÔnh nốicĂc nh cừa

Y, Z

. ữủc ỗth

G

0

₌

_K2

,

7.

Bữợc 2. p dửng thuêt toĂn trản tẳm ữủc têp ởc lêp lợn nhĐt cừa

G

0

l

M1

=

Y

Z

.

(

X1

=

, Y1

=

Y, Z1

=

Z

)

.

Bữợc 3.

G

00

₌

_K3

,

4

. p dửng thuêt toĂn trản tẳm ữủc têp ởc lêplợn nhĐt
l

Z

.

(

Y

2

=

, Z

2

=

Z

)

.

Vêy

M

=

{

z1, z2, z3, z4

}

l  tªp ëc lªp. Trong vẵ dử ny nõ chẵnh l têp ởc
lêplợnnhĐt.Tuy nhiản,trongnhiÃutrữớnghủp, thuêttoĂn chchotamởttêp hủp

ờnnh trong, khổng nhĐt thiát ltêp ờn nh trong lợnnhĐt.

Cõ th thĐy dạ dng l ta cõ th m rởng thuêt toĂn ny cho ỗ th

k

-phẵa

G

= (

X

1

, X

2

, ..., X

k

;

E

)

.Thuêt toĂn heuristicny cõ th Ăpdửng cho tĐtcÊ cĂc ỗ
th vẳ thỹc chĐt mởt ỗ th tũy ỵ luổn l ỗ th

k

-phẵa

G

= (

X1, X2, ..., X

k

;

E

)

, vợi

k

l sưc số cừa ỗth

G

.
Nhên xt:

Náu

G

= (

V, E

)

,

G

0

_{= (}

_{V, E}

0

₎

vợi

E

E

0

thẳ

(

G

)

(

G

0

₎

.

Náu

G

=

K

n

1

,n

2

,...,n

k

thẳ

α

(

G

) = max

{

n1, n2, ..., n

k

}

.

Düa v o 2 nhªn x²t trản ta cõ: Náu

G

= (

X

1

, X

2

, ..., X

k

;

E

)

l ỗ th

k

phẵa
thẳ

(

G

)

max

{

n1, n2, ..., n

k

}

(õ

n1, n2

, ..., n

k

l sè ¿nh cõa

X1, X2, ..., X

k

).
3. Kát luên

Bi toĂnxĂcnhchsốờnnhtrongcừamởt ỗth chotrữợclmởtvĐnÃ

ữủc cĂc khoa hồcquan tƠm vẳ nõcõ nhiÃuựng dửngtrong khoa hồcvkắ thuêt.

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

bi toĂn

NP C

(xem [4]), tực l khõ cõ ữủc thuêt to¡n thíi gian a thùc º gi£i
nâ. Tuy nhi¶n trong lợpỗ th lữùng phƠn, bitoĂn xĂc nh ch số ờnnh trong

ữủc biát l bi toĂn thuởc lợp

P

nhớ cĂc kát quÊ cừa Gallai[3] v cừa Konig [1].
Dũ vêy, khi biát ch số ờn nh trong, vĐn à xĂc nh têp nh ờn nh trong cỹc

Ôivăncỏn phÊigiÊiquyát. TrongbibĂo ny,cĂc tĂc giÊchramởt giÊithuêt vợi

thới gian a thực cõth xĂc nh ữủc mởt têp nh ờnnh trong cỹc Ôicừa

ỗth lữùngphƠn. Thuêt toĂn ữủcmrởng choỗth tũyỵ nhữngchmangtẵnh

heuristicmthổi.

TI LIU THAM KHO

[1] Konig D., 1936. Die Theorie der endlichen und unendlichen Graphen.Leipzig.

[2] DiracG.A.,1966. Shortproof of Menger's theorem. Mathematika13,pp. 42-44.

[3] GallaiT.,1959.

Uber extremePunkt-und-Kantenmengen.AnnalesUniv.Sci.

Bu-dapestinensis de RolandoEotvos, Secto Math. 2,pp. 133-138.

[4] Michael R., Garey - David S. Johnon, 1979. Computers and intractability. A

Guide to the Theory of NP-Completeness.Spring Verlag.

[5] SachsH., 1970. Einfr uhrung in die Theorie der endlichen Graphen. Leipzig.

[6] TajzanR.E.and TrojanowskiR.E.,1977.Findinga maximumindependentset.

SIAM Journalon ComputingVol.6, No.3, pp. 537-546.

[7] />

ABSTRACT

A polynomial algorithm for finding maximum

set of independent vertices in bipartite graphs

The problem of estimating the independent number of a given graph is

well-known as aNPC-problem.But itis aP-problem inthe classof bipartitegraphs.In

this paper, we give an algorithm for finding the maximum set of the independent

vertices in bipartitegraphs.

</div>

<!--links-->