Составители:
Рубрика:
81
ÎÃËÀÂËÅÍÈÅ
Ââåäåíèå .................................................................................................... 3
1. ÎÑÍÎÂÍÛÅ ÎÏÐÅÄÅËÅÍÈß È ÏÎÍßÒÈß .................................. 5
1.1. Ýëåìåíòû òåîðèè ìíîæåñòâ ........................................................ 5
1.2. Îñíîâíûå ïîíÿòèÿ äëÿ ãðàôîâ .................................................... 8
1.3. Îñíîâíûå ïîíÿòèÿ äëÿ íåîðèåíòèðîâàííûõ ãðàôîâ ................ 10
1.4. Îñíîâíûå ïîíÿòèÿ äëÿ îðèåíòèðîâàííûõ ãðàôîâ .................... 23
1.5. Ðåàëèçàöèÿ àëãîðèòìîâ òåîðèè ãðàôîâ íà ÝÂÌ....................... 34
2. ÇÀÄÀ×È Î ÏÓÒßÕ Â ÎÐÃÐÀÔÅ ........................................................ 36
2.1. Ñóùåñòâîâàíèå ïóòåé â îðãðàôå ................................................ 36
2.2. Ïåðåñ÷åò ïóòåé â îðãðàôå ............................................................ 38
2.3. Ïóòü ñ íàèìåíüøèì ÷èñëîì äóã. Ïîèñê òðàíçèòèâíîãî
çàìûêàíèÿ âåðøèí ........................................................................ 40
3. ÇÀÄÀ×È ÎÁ ÎÏÒÈÌÀËÜÍÛÕ ÐÀÑÑÒÎßÍÈßÕ ............................ 44
3.1. Ïîèñê ìèíèìàëüíûõ ïóòåé â ãðàôå............................................ 46
3.2. Ïîèñê ìàêñèìàëüíîãî ïóòè â ãðàôå áåç êîíòóðîâ .................... 52
4. ÇÀÄÀ×À ÂÛÁÎÐÀ ÏÐÅÄÏÎ×ÒÈÒÅËÜÍÛÕ ÂÀÐÈÀÍÒÎÂ
ÈÑÑËÅÄÓÅÌÎÉ ÑÈÑÒÅÌÛ ................................................................ 53
4.1. Îáùàÿ ïîñòàíîâêà çàäà÷è ............................................................ 53
4.2. Ïîëó÷åíèå ñðàâíèìûõ îöåíîê .................................................... 54
4.3. Ïîëó÷åíèå ãðóïïîâûõ îöåíîê ..................................................... 55
4.4. Ôîðìàëèçàöèÿ çàäà÷è âûáîðà ïðåäïî÷òèòåëüíûõ îáúåêòîâ.... 57
4.5. Ìåòîäû è àëãîðèòìû âûáîðà ïðåäïî÷òèòåëüíûõ îáúåêòîâ..... 62
4.6. Ðàçáèåíèå àöèêëè÷åñêîãî ãðàôà íà óðîâíè............................... 67
4.7. Âûäåëåíèå ÿäåð ãðàôà .................................................................. 72
Áèáëèîãðàôè÷åñêèé ñïèñîê .................................................................... 80
