Файл: Журавлев Флеров Дискретный анализ МФТИ 1991.pdf

Ìèíèñòåðñòâî îáùåãî è ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ ÐÔ

Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò

(ãîñóäàðñòâåííûé óíèâåðñèòåò)

Þ.È. Æóðàâë¼â, Þ.À. Ôë¼ðîâ

ÄÈÑÊÐÅÒÍÛÉ ÀÍÀËÈÇ

×.1

Ðåêîìåíäîâàíî Ó÷åáíî-ìåòîäè÷åñêèì ñîâåòîì

Ìîñêîâñêîãî ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà

(ãîñóäàðñòâåííîãî óíèâåðñèòåòà)

â êà÷åñòâå ó÷åáíîãî ïîñîáèÿ äëÿ ñòóäåíòîâ âûñøèõ ó÷åáíûõ çàâåäåíèé

ïî ñïåöèàëüíîñòè Ïðèêëàäíàÿ ìàòåìàòèêà è ôèçèêà

Ìîñêâà 1999

2

Æ 91

ÓÄÊ 519.1

Ðåöåíçåíòû:

êàôåäðà ìàòåìàòè÷åñêîé êèáåðíåòèêè ÂÌÊ

ÌÃÓ èì. Ëîìîíîñîâà

÷ë.êîðð. ÐÀÍ Ê.Â. Ðóäàêîâ

Æóðàâë¼â Þ.È., Ôë¼ðîâ Þ.À.

Æ 91 Äèñêðåòíûé àíàëèç. ×. 1: ó÷åáíîå ïîñîáèå/ÌÔÒÈ.Ì., 1999. 136 ñ.

ISBN 5-7417-0108-6

Ñîäåðæèò ìàòåðèàë, èçëàãàåìûé â ïåðâîì ñåìåñòðå êóðñà äèñêðåòíîãî àíàëèçà: êîì-

áèíàòîðèêå, ýëåìåíòû àëãåáðû ëîãèêè, íà÷àëüíûå ñâåäåíèÿ òåîðèè ãðàôîâ. Âêëþ÷åíû

êàê îñíîâîïîëàãàþùèå ðàçäåëû, ïðåäíàçíà÷åííûå äëÿ ïåðâîíà÷àëüíîãî îçíàêîìëåíèÿ

ñ òåîðèåé, òàê è ìàòåðèàë ïîâûøåííîé òðóäíîñòè, íåïîñðåäñòâåííî â ëåêöèÿõ íå èçëà-

ãàåìûé. Ðàññìîòðåíû îöåíêè ñëîæíîñòè ðåøåíèé ìíîãèõ çàäà÷.

Ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ I êóðñà ôàêóëüòåòà ïðèêëàäíîé ìàòåìàòèêè è ýêîíî-

ìèêè Ìîñêîâñêîãî ôèçèêî-òåõíè÷åñêîãî èíñòèòóòà. Ìîæåò áûòü èñïîëüçîâàíî ñòóäåí-

òàìè äëÿ èçó÷åíèÿ ñîîòâåòñòâóþùèõ ðàçäåëîâ ïðîãðàììû, ïðåïîäàâàòåëÿìè äëÿ ïîä-

ãîòîâêè óïðàæíåíèé, çàäàíèé, ñåìèíàðñêèõ çàíÿòèé, ýêçàìåíàöèîííîãî ìàòåðèàëà, à

òàêæå äëÿ ñàìîñòîÿòåëüíîãî îçíàêîìëåíèÿ è èçó÷åíèÿ îñíîâíûõ ðàçäåëîâ äèñêðåòíîãî

àíàëèçà

Áèáëèîãð.: 14 íàçâ.

Ó÷åáíîå èçäàíèå

Æóðàâë¼â Þðèé Èâàíîâè÷

Ôë¼ðîâ Þðèé Àðñåíèåâè÷

ÄÈÑÊÐÅÒÍÛÉ ÀÍÀËÈÇ

×.1

Ðåäàêòîð È. À. Âîëêîâà

Ëèöåíçèÿ ËР 040060 îò 21.08.96

Ïîäïèñàíî â ïå÷àòü 07.05.99. Ôîðìàò 60

×

901/16.

Ïå÷àòü îôñåòíàÿ. Óñë. ï.ë. 8,5. Ó÷.-èçä.ë. 8,75. Òèðàæ 400 ýêç. Çàêàç N

Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò

(ãîñóäàðñòâåííûé óíèâåðñèòåò)

Ëàáîðàòîðèÿ îáðàáîòêè ó÷åáíîé è íàó÷íîé èíôîðìàöèè

141700, Ìîñê. îáë., ã. Äîëãîïðóäíûé, Èíñòèòóòñêèé ïåð., 9

ISBN 5-7417-0108-6

c

ÌÔÒÈ, 1999

c

Þ.È. Æóðàâë¼â,

Þ.À. Ôë¼ðîâ, 1999

Îãëàâëåíèå

1 Ýëåìåíòû êîìáèíàòîðèêè

5

1.1 Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2 Äâà ïðèíöèïà êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . .

6

1.3 Ôóíêöèè è ðàçìåùåíèÿ . . . . . . . . . . . . . . . . . . . . . .

6

1.3.1 ×èñëà Ñòèðëèíãà ïåðâîãî ðîäà . . . . . . . . . . . . .

9

1.3.2 Öèêëè÷åñêàÿ ñòðóêòóðà ïåðåñòàíîâîê . . . . . . . . .

9

1.3.3 Óïîðÿäî÷åííûå ðàçìåùåíèÿ . . . . . . . . . . . . . . .

11

1.3.4 Ñî÷åòàíèÿ è áèíîìèàëüíûå êîýôôèöèåíòû . . . . . .

14

1.3.5 Ïîëèíîìèàëüíûå êîýôôèöèåíòû . . . . . . . . . . . .

25

1.4 Ðàçáèåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

1.4.1 ×èñëî ðàçáèåíèé . . . . . . . . . . . . . . . . . . . . .

27

1.4.2 ×èñëà Áåëëà . . . . . . . . . . . . . . . . . . . . . . . .

30

1.5 Ïðèíöèï âêëþ÷åíèé-èñêëþ÷åíèé . . . . . . . . . . . . . . . .

31

1.5.1 Çàäà÷à î ÷èñëå áåñïîðÿäêîâ (Çàäà÷à î âñòðå÷àõ) . . .

35

1.5.2 Êîëè÷åñòâî ñþðúåêòèâíûõ îòîáðàæåíèé . . . . . . .

37

1.5.3 Ïåðåñòàíîâêè ñ îãðàíè÷åíèÿìè íà ìåñòîïîëîæåíèå .

38

1.6 Ñèñòåìû ïðåäñòàâèòåëåé ìíîæåñòâ . . . . . . . . . . . . . . .

43

1.6.1 Ñèñòåìû ðàçëè÷íûõ ïðåäñòàâèòåëåé . . . . . . . . . .

43

1.6.2 Ñèñòåìû îáùèõ ïðåäñòàâèòåëåé . . . . . . . . . . . . .

47

2 Ôóíêöèè àëãåáðû ëîãèêè

49

2.1 Ýëåìåíòàðíûå âûñêàçûâàíèÿ . . . . . . . . . . . . . . . . . .

52

2.2 Ýëåìåíòàðíûå ëîãè÷åñêèå îïåðàöèè(ôóíêöèè) . . . . . . . .

53

2.3 Àëãåáðàè÷åñêèå ñâîéñòâà ýëåìåíòàðíûõ îïåðàöèé . . . . . .

58

2.4 Ðàçëîæåíèå ôóíêöèé àëãåáðû ëîãèêè ïî ïåðåìåííûì . . . .

60

2.5 Ôóíêöèîíàëüíàÿ ïîëíîòà ñèñòåì ôóíêöèé . . . . . . . . . .

65

2.5.1 Çàìêíóòûå êëàññû . . . . . . . . . . . . . . . . . . . .

67

3

4

ÎÃËÀÂËÅÍÈÅ

2.5.2 Êðèòåðèé ïîëíîòû . . . . . . . . . . . . . . . . . . . .

74

2.5.3 Ïðåäñòàâëåíèå î ðåçóëüòàòàõ Ïîñòà . . . . . . . . . .

80

3 Ýëåìåíòû òåîðèè ãðàôîâ

83

3.1 Ñòåïåíè âåðøèí . . . . . . . . . . . . . . . . . . . . . . . . . .

85

3.2 Î ìàøèííîì ïðåäñòàâëåíèè ãðàôà . . . . . . . . . . . . . . .

86

3.3 Ïîèñê â ãðàôå . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

3.3.1 Ïîèñê â ãëóáèíó â ãðàôå . . . . . . . . . . . . . . . . .

89

3.3.2 Ïîèñê â øèðèíó â ãðàôå . . . . . . . . . . . . . . . . .

91

3.4 Ïóòè è öèêëû . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

3.5 Ñâÿçíîñòü . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

3.6 Äåðåâüÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

3.6.1 Îñòîâíîå äåðåâî (êàðêàñ) . . . . . . . . . . . . . . . . 100

3.7 Ýéëåðîâû ïóòè è öèêëû . . . . . . . . . . . . . . . . . . . . . 104

3.7.1 Àëãîðèòì ïîñòðîåíèÿ ýéëåðîâà öèêëà . . . . . . . . . 106

3.8 Ãàìèëüòîíîâû ïóòè è öèêëû . . . . . . . . . . . . . . . . . . . 108

3.9 Íàõîæäåíèå êðàò÷àéøèõ ïóòåé â ãðàôå . . . . . . . . . . . . 116

3.9.1 Àëãîðèòì íàõîæäåíèÿ ðàññòîÿíèÿ îò èñòî÷íèêà äî

âñåõ îñòàëüíûõ âåðøèí â îðèåíòèðîâàííîì ãðàôå ñ

íåîòðèöàòåëüíûìè âåñàìè ð¼áåð . . . . . . . . . . . . 117

3.10 Ìàêñèìàëüíûé ïîòîê â ñåòè . . . . . . . . . . . . . . . . . . . 119

Ãëàâà 1

Ýëåìåíòû êîìáèíàòîðèêè

1.1 Ââåäåíèå

Ñåé÷àñ òðóäíî áûëî áû, ïîæàëóé, íàçâàòü ðàçäåë òåîðåòè÷åñêîé èíôîð-

ìàòèêè, â êîòîðîì â òå÷åíèå ïîñëåäíåãî äåñÿòèëåòèÿ áûëè áû äîñòèãíóòû

áîëüøèå óñïåõè, íåæåëè â êîíñòðóèðîâàíèè è àíàëèçå êîìáèíàòîðíûõ àë-

ãîðèòìîâ  âàæíåéøåé ïðîáëåìû êîìáèíàòîðèêè. Ñ îäíîé ñòîðîíû, áûëî

îáíàðóæåíî ìíîãî íîâûõ, áîëåå ýôôåêòèâíûõ ìåòîäîâ ðåøåíèÿ êîìáèíà-

òîðíûõ çàäà÷ ñ ïîìîùüþ ÝÂÌ, ñ äðóãîé ñòîðîíû  ïîëó÷åíû òåîðåòè÷å-

ñêèå ðåçóëüòàòû, ñâèäåòåëüñòâóþùèå âñå áîëåå ÿâíî î òîì, ÷òî äëÿ øèðî-

êîãî êëàññà ïðîáëåì íå ñóùåñòâóåò äîñòàòî÷íî ýôôåêòèâíûõ àëãîðèòìîâ.

Ýôôåêòèâíûå êîìáèíàòîðíûå àëãîðèòìû íàõîäÿò ïðèìåíåíèå âî ìíîãèõ

îáëàñòÿõ íå÷èñëåííîé îáðàáîòêè èíôîðìàöèè, îñîáåííî â äèñêðåòíîé îï-

òèìèçàöèè è â èññëåäîâàíèè îïåðàöèé, â âû÷èñëèòåëüíîé ìàòåìàòèêå. Êî-

ëè÷åñòâî êîìáèíàòîðíûõ çàäà÷ è èõ ðàçíîîáðàçèå áûñòðî ðàñòåò. Ê èõ

ðåøåíèþ ïðÿìî èëè êîñâåííî ïðèâîäÿò ìíîãèå ïðàêòè÷åñêèå çàäà÷è. Âî

ìíîãèõ îáëàñòÿõ ìàòåìàòèêè (òåîðèÿ ãðàôîâ, òåîðèÿ ÷èñåë, òåîðèÿ ãðóïï,

êèáåðíåòèêà, âû÷èñëèòåëüíàÿ ìàòåìàòèêà) èìåþòñÿ çàäà÷è èëè ãðóïïû

çàäà÷, êîìáèíàòîðíûé õàðàêòåð êîòîðûõ óãàäûâàåòñÿ áåç óñèëèé. Ìåæäó

ýòèìè çàäà÷àìè ÷àñòî ìîæíî óñòàíîâèòü ñåòü âçàèìíûõ èíòåðïðåòàöèé,

÷òî ïðèâîäèò ê ìûñëè î íàëè÷èè èõ îáùåé òåîðåòè÷åñêîé îñíîâû. Ïðè

ýòîì îêàçûâàåòñÿ, ÷òî íåñìîòðÿ íà çàìàí÷èâóþ ïðîñòîòó ïîñòàíîâêè, êîì-

áèíàòîðíûå çàäà÷è â áîëüøèíñòâå î÷åíü òðóäíû. Êîìáèíàòîðèêà  ðàç-

äåë ìàòåìàòèêè, â êîòîðîì èçó÷àþòñÿ âîïðîñû î òîì, ñêîëüêî ðàçëè÷íûõ

êîíôèãóðàöèé (êîìáèíàöèé), ïîä÷èíåííûõ òåì èëè èíûì óñëîâèÿì, ìîæ-

5