|
|
yī gè wù jiàn ( rú yī wéi、 èr wéi huò sān wéi zhōng de tú xiàng huò xìn hào ) de duìchèn qún shì zhǐ zài fù hé hán shù yùn suàn xià bù biàn de suǒ yòu děng jù tóng gòu suǒ gòu chéng de qún。 qí wéi suǒ kǎo lǜ zhī kōng jiān de děng jù tóng gòu qún zhōng de yī gè zǐ qún。
( ruò méi yòu lìng wài shù xù， zé běn wén kě kǎo lǜ zài 'ōu shì kōng jiān nèi de duìchèn qún， dàn cǐ yī gài niàn yì kě yǐ bèi yìng yòng zài gèng guǎng yì de yòng tú shàng， jiàn xià wén。 )
「 wù jiàn 」 kě yǐ shì jǐ hé xíng zhuàng、 tú xiàng jí mó shì， rú bì zhǐ tú yàng。 qí dìng yì néng gòu yǐ xiáng shù tú xiàng huò mó shì de fāng shì， rú jiāng wèi zhì fù shàng yī zǔ yán sè de zhí de hán shù， lái shǐ qí gèng wéi jīng què。 duì rú sān wéi wù tǐ de duìchèn， kě néng yì huì xiǎng yào kǎo liàng qí wù lǐ shàng kě néng de zǔ hé。 kōng jiān zhōng děng jù tóng gòu de qún kě yǐ chǎn shēng yī gè zuò yòng yú cǐ qún běn shēn wù jiàn shàng de qún zuò yòng。
duìchèn qún yòu shí yì chēng wéi quán duìchèn qún， yǐ qiáng diào qí huì chǎn shēng yī gè tú xiàng bù huì gǎi biàn de fǎn zhuǎn dìng wèi zhī děng jù tóng gòu ( rú jìng shè、 huá yí jìng shè hé bù chún xuánzhuàn )。 huì bǎo liú qí dìng wèi zhī tóng jù tóng gòu ( rú píng yí、 xuánzhuàn hé cǐ liǎng zhě de zǔ hé ) de zǐ qún zé chēng wéi qí chún duìchèn qún。 yī wù jiàn de chún duìchèn qún ruò děng tóng yú qí quán duìchèn qún， zé chēng cǐ wù jiàn wéi duì zhǎng de ( yě yīn cǐ bù cún zài shǐ qí bù biàn de fǎn zhuǎn dìng wèi zhī děng jù tóng gòu。 )
rèn hé qí yuán sù yòu zhù xiāng tóng gè bù dòng diǎn de duìchèn qún dōukě yǐ yóu xuǎn dìng qí yuán diǎn wéi bù dòng diǎn lái bèi biǎo shì chéng yī gè zhèng jiāo qún o(n) de zǐ qún， qí duì suǒ yòu de yòu xiàn duìchèn qún jí yòu jiè tú xiàng zhī duìchèn qún jiē wéi zhēn de。
lí sàn duìchèn qún kě yǐ fēn chéng sān zhǒng lèi xíng：
1. yòu xiàn diǎn qún， qí zhǐ bāo hán yòu xuánzhuàn、 jìng shè、 fǎn yǎn hé bù chún xuánzhuàn， qiě shí jì shàng zhǐ shì zhèng jiāo qún o(n) de zǐ qún；
2. wú xiàn jīng gé qún， qí zhǐ bāo kuò píng yí； hé
3. wú xiàn kōng jiān qún， qí jié hé yòu shàng shù liǎng zhǒng lèi xíng de yuán sù， qiě yì bāo hán yòu rú luó xuán zhóu hé huá yí jìng shè děng 'é wài de duìchèn。
lìng wài yì yòu zhù bāo hán rèn yì xiǎo jiǎo dù de xuánzhuàn huò rèn yì xiǎo jù lí de píng yí zhī「 lián xù」 duìchèn qún。 yī gè qiú miàn o(3) de suǒ yòu duìchèn suǒ zǔ chéng de qún jí shì yī zhǒng lián xù duìchèn qún， ér tōng cháng rú cǐ lèi de lián xù duìchèn de qún shì zài lǐ qún zhōng suǒ yán jiū de duì xiàng。 duì 'ōu jǐ lǐ dé qún zǐ qún de fēn lèi huì duì yìng dào duìchèn qún de fēn lèi。
liǎng gè jǐ hé xíng zhuàng bèi rèn wéi shì yòu zhù xiāng tóng de duìchèn xíng， ruò qí duìchèn qún wéi 'ōu jǐ lǐ dé qún e(n)(rn de děng jù tóng gòu qún ) de gòng 'è qún， qí zhōng yī gè qún g de liǎng gè zǐ qún h1 hé h2 wéi gòng 'è de， ruò cún zài yī g nèi de yuán sù g néng shǐ dé h1=g-1h2g。 lì rú：
* liǎng gè sān wéi tú xíng yòu zhù jìng miàn duìchèn， dàn duì yìng zhù bù tóng de jìng miàn。
* liǎng gè sān wéi tú xíng yòu zhù xuánzhuàn duìchèn， dàn duì yìng zhù bù tóng de xuánzhuàn zhóu。
* liǎng gè 'èr wéi tú xíng yòu zhù píng yí duìchèn， gè zài gè de fāng miàn； cǐ liǎng zhě yòu zhù cháng dù xiāng tóng dàn fāng xiàng bù tóng de píng yí xiàng liàng。
yòu shí，「 xiāng tóng duìchèn xíng」 gèng guǎng yì de gài niàn huì bèi shǐ yòng， ér kě yǐ chǎn shēng rú 17 gè bì zhǐ qún zhī lèi de lèi xíng。
dāng kǎo lǜ děng jù tóng gòu qún shí， kě yǐ jiāng qí suō xiàn zài yú děng jù tóng gòu xià zhī tú xiàng de diǎn jiē wéi tuò pū bì hé de。 rú cǐ biàn pái chú liǎo rú yī wéi zhōng yǐ yòu lǐ shǔzhī jù lí píng yí suǒ gòu chéng de qún。 yī gè jù yòu duìchèn qún de「 tú xiàng」 shì bù kě shēn suō de， qiě jí shǐ dá dào rèn yì xiáng jìn de jūn yún， yì bù huì yòu zhēn zhèng de jūn yún。 |
|
qí zài děng tóng gòu xià zhī tú xiàng de diǎn jiē wéi tuò pū bì hé zhī yī wéi děng jù tóng gòu qún yòu：
* dāng rán qún c1
* yóu yī diǎn zhī jìng shè suǒ chǎn shēng zhī yuán sù suǒ zǔ chéng de qún； qí tóng gòu yú c2
* yóu píng yí suǒ chǎn shēng zhī wú xiàn lí sàn qún： qí tóng gòu yú z
* yóu píng yí hé yī diǎn de jìng shè suǒ chǎn shēng zhī wú xiàn lí sàn qún： qí tóng gòu yú z de guǎng yì 'èr miàn tǐ qún dih(z)， yì bèi biāo jì wéi d ∞ ( qí wéi z yǔ c2 de bàn zhí jī )。
* yóu suǒ yòu píng yí ( tóng gòu yú r) suǒ chǎn shēng de qún； zhè gè qún bù néng shì mǒu yī「 tú xiàng」 de duìchèn qún： tā huì shì jūn yún de， yīn cǐ yì néng bèi jìng miàn。 dàn yī gè jūn yún yī wéi xiàng liàng chǎng zé kě yǐ yòu zhè zhǒng duìchèn qún。
* yóu suǒ yǐ píng yí hé yī diǎn zhī jìng shè suǒ zǔ chéng de qún： qí tóng gòu yú r de guǎng yì 'èr miàn tǐ qún dih(r)。
lìng jiàn yī wéi duìchèn qún。 |
|
yǐ gòng 'è lái fēn， èr wéi lí sàn diǎn qún kě yǐ fēn chéng xià liè jǐ zhǒng lèi xíng：
*c1、 c2、 c3、 c4、 … děng xún huán qún， qí zhōng cn bāo hán zhù suǒ yòu rào yī gù dìng diǎn wéi 306/n dù de zhěng bèi shù zhī xuánzhuàn。
*d1、 d2、 d3、 d4、… děng 'èr miàn tǐ qún， qí zhōng dn bāo hán zhù suǒ yòu zài cn zhōng de xuánzhuàn hé n gè tōng guò qí gù dìng diǎn zhī zhóu de jìng shè。
c1 shì yī gè zhǐ bāo hán yòu héng děng yùn suàn de dāng rán qún， qí chǎn shēng yú yī tú xiàng méi yòu rèn hé de duì chēng shí， rú zì mǔ f。 c2 wéi zì mǔ z de duìchèn qún， c3 wéi sān qū tuǐ tú de， c4 wéi wàn de， ér c5、 c6 zé wèiyòu wǔ tiáo jí liù tiáo bì zhī lèi wàn tú xiàng。
d1 wéi yī gè hán yòu héng děng yùn suàn hé dān yī gè jìng shè zhī liǎng gè yuán sù de qún， qí chǎn shēng yú yī jìn yòu yī duìchèn zhóu de tú xiàng zhōng， rú zì mǔ a。 d2( tóng gòu yú kè lāi yīn sì yuán qún ) wéi yī fēi děng biān cháng fāng xíng de duìchèn qún， ér d3、 d4 zé wéi zhèng duō biān xíng de duìchèn qún。
liǎng zhǒng lèi xíng de shí jì duìchèn qún duì qí xuánzhuàn zhōng xīn dōuyòu zhù liǎng gè zì yóu dù， ér zài 'èr miàn tǐ qún zhōng， duō zhù yī gè jìng miàn fāng wèi de zì yóu dù。
shèng yú jù yòu bù dòng diǎn zhī 'èr wéi děng jù tóng gòu qún， qí suǒ yòu zài děng jù tóng gòu xià zhī tú xiàng de diǎn jiē wéi tuò pū bì hé de yòu：
* tè shū zhèng jiāo qún so(2)， qí bāo kuò rào zhù yī gù dìng diǎn de suǒ yòu xuánzhuàn； qí yì chēng wéi yuán qún s1， wéi jué duì zhí wéi 1 zhī fù shù suǒ zǔ chéng de chéng fǎ qún。 qí wéi yuán de「 chún」 duìchèn qún， qiě wéi cn zài lián xù qún zhōng de děng jià。 bù cún zài yī yǐ yuán qún wéi「 quán」 duìchèn qún zhī tú xiàng， dàn duì yú yī xiàng liàng chǎng zé cún zài zhù ( jiàn sān wéi zhōng de lì zǐ )。
* zhèng jiāo qún o(2)， qí bāo kuò suǒ yòu rào yī gù dìng diǎn de xuánzhuàn jí duì tōng guò qí gù dìng diǎn zhī zhóu de jìng shè。 zhè shì yī gè yuán de duìchèn qún。 qí yì bèi kě biāo jì wéi dih(s1)， yīn qí wéi s1 de guǎng yì 'èr miàn tǐ qún。
duì yú wú jiè tú xiàng， qí tā de děng jù tóng gòu qún hái bāo kuò píng yí； qí bì hé duìchèn qún yòu：
*7 gè cǎi dài qún
*17 gè bì zhǐ qún
* duì měi yī gè yī wéi duìchèn qún， qí yú yī fāng xiàng shàng zhī qún de suǒ yòu duìchèn jí zài qí chuí zhí fāng xiàng shàng zhī suǒ yòu píng yí de qún suǒ zǔ chéng zhī duìchèn qún
* tóng shàng， dàn zài jiā shàng dì yī gè fāng xiàng de jìng shè |
|
yǐ gòng 'è lái fēn， qí sān wéi diǎn qún de jí hé bāo kuò 7 zhǒng bāo hán wú xiàn duō gè qún de lèi xíng hé shèng xià de 7 gè diǎn qún。 zài jīng gé xué zhōng， qí bèi jú xiàn zài xū fú hé jīng gé de lí sàn píng yí duìchèn zhōng。 yī bān wú xiàn gè diǎn qún zhōng de jīng tǐ jú xiàn kě yǐ zhǎo chū 32 zhǒng jīng tǐ diǎn qún (27 zhǒng zài 7 zhǒng lèi xíng zhōng， 5 zhǒng zài lìng 7 gè diǎn qún zhōng )。
jiàn sān wéi diǎn qún。
jù yī gù dìng diǎn de lián xù duìchèn qún bāo kuò rú xià：
* méi yòu chuí zhí qí zhóu zhī duìchèn miàn de yuán zhù duìchèn， zhè chū xiàn zài rú píng zǐ děng wù zhī shàng tóu
* yòu chuí zhí qí zhóu zhī duìchèn miàn de yuán zhù duìchèn
* qiú miàn duìchèn
duì wù jiàn hé chún liàng chǎng 'ér yán， yuán zhù duìchèn yì zhǐ qí yòu zhù zhí lì jìng shè miàn。 dàn duì xiàng liàng chǎng zé bù rán： zài xiāng duì yú mǒu yī zhóu de yuán zhù zuò biāo zhōng， mathbf=a_
hooldsymbol{hat
ho}+a_phioldsymbol{hatphi}+a_zoldsymbol{hatz} yòu xiāng duì yú cǐ yī zhóu de yuán zhù duìchèn ruò qiě wéi ruò aρ、 aφ hé az dōuyòu cǐ yī duìchèn， jí qí dū hé φ wú guān。 lìng wài dì， qí cún zài zhù jìng shè duìchèn ruò qiě wéi ruò aφ=0。
duì yú qiú miàn duìchèn， zé bù cún zài zhù rú cǐ chā yì， qí jiē yì zhǐ zhù yòu jìng shè miàn。
méi yòu gù dìng diǎn de lián xù duìchèn qún zé bāo kuò jù yòu rú wú xiàn luó xuán zhī luó xuán zhóu duìchèn de duìchèn qún。 lìng jiàn 'ōu jǐ lǐ dé qún de zǐ qún。 |
|
zài gèng guǎng yì de wén jù zhōng， duìchèn qún kě néng wéi rèn yī zhǒng lèi de biàn huàn qún huò tóng zì gòu qún。 yī dàn zhī dào liǎo suǒ guān zhù de shù xué jié gòu zhī zhǒng lèi， yīnggāi jiù gòu què dìng bǎo liú qí jié gòu zhī yìng shè。 xiāng fǎn dì， zhī dào qí duìchèn jí kě dìng yì qí jié gòu， huò zhì shǎo néng nòng qīng qí nèi zhī bù biàn liàng； zhè shì kàn 'ài 'ěr lán gēn gāng lǐng de yī zhǒng fāng shì。
lì rú， yòu xiàn jǐ hé mǒu xiē mó xíng de zì tóng gòu qún zài yī bān yì sī xià bù shì「 duìchèn qún」， jìn guǎn qí yì huì bǎo liú duìchèn xìng。 qí bǎo liú zhù diǎn jí zú， ér fēi diǎn jí ( huò「 wù jiàn」 ) běn shēn。 jiàn patterngroups。
rú shàng miàn suǒ shù， kōng jiān zì tóng gòu de qún huì xíng chéng yī yú qí nèi wù jiàn zhī qún zuò yòng。
duì yú yī gěi dìng zhī jǐ hé kōng jiān nèi de yī gěi dìng zhī jǐ hé xíng zhuàng， kǎo lǜ rú xià zhī děng jià guān xì： liǎng gè kōng jiān zì tóng gòu wéi děng jià de ruò qiě wéi ruò liǎng gè xíng zhuàng de tú yàng shì xiāng tóng de ( cǐ chù suǒ wèi zhī「 xiāng tóng」 bìng fēiwèi「 zài píng yí hé xuán zhuǎn xià shì xiāng tóng」 de yì sī， ér shì zhǐ「 jīng què dì xiāng tóng」 )。 rán hòu， cǐ yī xiāng tóng zhī děng jià lèi jí wéi cǐ xíng zhuàng de duìchèn qún， qiě měi yī děng jià lèi jiē huì duì yìng dào yī gè cǐ xíng zhuàng de tóng gòu bǎn běn。
zài měi yī duì děng jià lèi zhī jiān dū cún zài zhù yī gè shuāng shè： dì yī gè děng jià lèi zhī dài biǎo de nì yuán sù yǔ dì 'èr gè děng jià lèi zhī dài biǎo fù hé。
zài zhěng gè kōng jiān de yī yòu xiàn zì tóng gòu qún lǐ， qí mù wéi xíng zhuàng zhī duìchèn qún de mù chéng shàng cǐ xíng zhuàng tóng gòu bǎn běn de shù mù。
lì rú：
* ōu shì kōng jiān de děng jù tóng gòu， qí xíng zhuàng wéi cháng fāng xíng： qí cún zài zhù wú xiàn duō gè děng jià lèi； měi yī gè děng jià lèi dū bāo kuò 4 gè děng jù tóng gòu。
* kōng jiān wéi jù 'ōu jǐ lǐ dé dù liàng de lì fāng tǐ； xíng zhuàng bāo kuò hé cǐ kōng jiān tóng yàng dà xiǎo de lì fāng tǐ， qí gè miàn yòu zhù gè shì yán sè huò tú xiàng； cǐ yī kōng jiān de zì tóng gòu wéi 48 gè děng jù tóng gòu； qí zhuàng xíng wéi gè miàn yòu zhù bù tóng yán sè zhī lì fāng tǐ； cǐ xíng zhuàng huì yòu zhù 8 gè děng jù tóng gòu de duìchèn qún， jí 6 gè gè hán 8 gè děng jù tóng gòu de děng jià lèi， měi gè děng jià lèi dōushì cǐ xíng zhuàng de yī gè tóng gòu bǎn běn。
bǐ jiào lā gé lǎng rì dìng lǐ ( qún lùn ) jí qí zhèng míng。 |