Единое окно доступа к образовательным ресурсам

Дискретная математика: Основы теории графов и алгоритмизация задач: Учебное пособие

Голосов: 13

Рассмотрены основные определения и понятия теории графов, необходимые для решения некоторых прикладных задач дискретной математики (определение оптимальных расстояний между множеством объектов, поиск критического пути в задаче сетевого планирования и управления, выбор предпочтительных вариантов системы по множеству критериев). Обсуждаются подходы к разработке компьютерных алгоритмов задач па основе моделей теории графов.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
                                                 ÎÃËÀÂËÅÍÈÅ

Ââåäåíèå ....................................................................................................    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




                                                                                                                81


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




                           Ïðîêóøåâ Ëåâ Àíòîíîâè÷




                     ÄÈÑÊÐÅÒÍÀß ÌÀÒÅÌÀÒÈÊÀ
                Îñíîâû òåîðèè ãðàôîâ è àëãîðèòìèçàöèè çàäà÷


                                  Ó÷åáíîå ïîñîáèå




                                 Ðåäàêòîð Ã. Ä. Áàêàñòîâà
                  Êîìïüþòåðíàÿ âåðñòêà Þ. Ñ. Áàðäóêîâîé, À. Í. Êîëåøêî



Ëèöåíçèÿ ËÐ ¹ 020341 îò 07.05.97. Ñäàíî â íàáîð 26.09.00. Ïîäïèñàíî ê ïå÷àòè 20.12.00.
Ôîðìàò 60×84 1/16. Áóìàãà òèï. ¹3. Ïå÷àòü îôñåòíàÿ. Óñë. ïå÷. ë. 2,9. Óñë. êð.-îòò. 3,0.
Ó÷. -èçä. ë. 3,15. Òèðàæ 100 ýêç. Çàêàç ¹



                                 Ðåäàêöèîííî-èçäàòåëüñêèé îòäåë
                        Ëàáîðàòîðèÿ êîìïüþòåðíî-èçäàòåëüñêèõ òåõíîëîãèé
                                 Îòäåë îïåðàòèâíîé ïîëèãðàôèè
                                           ÑÏáÃÓÀÏ
                           190000, Ñàíêò-Ïåòåðáóðã, óë. Á. Ìîðñêàÿ, 67



    
Яндекс цитирования Яндекс.Метрика