Библиографический список. 1. Новиков Ф. А. Дискретная математика для программистов

1. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000. 304 c.

2. Математика. Общий курс. СПб.: Изд-во ”Лань”, 2002. 960 c.

3. Кузнецов О.П., Адельсон-Вельский Г.И. Дискретная математика

для инженера. М.: Энергоатомиздат, 1997. 344 c.

4. Кабанов А.Н. Математические модели и алгоритмы оптимизации дискретных систем: Учеб. пособие./ Рязан.радиотехн.ин-т. Рязань, 1987. 64 c.

5. Емеличев В.А., Мельников О.И. Лекции по теории графов. М.: Наука, 1990. 384 с.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ……………………………………………………………………. 1

1. Теоретико-множественные основы

описания дискретных систем………………………………….1

1.1. Основные понятия теории множеств [1,2]…………………………..1

1.2. Операции над множествами…………………………………………. 2

1.3. Тождества алгебры множеств………………………………………...3

1.4. Упорядоченные множества элементов. Cтруктура

и споcобы представления многомерных матриц [3,4]……………. 4

1.5. Основные операции над многомерными матрицами……………… 6

2. Основные определения теории графов…………………….. 17

2.1. Понятие о графе. Способы задания графа [4,5]……………….…… 17

2.2. Достижимость и обратная достижимость вершин графа…….…… 20

2.3. Разбиение графа на подграфы………………………………….…… 23

3. Алгоритмы оптимизации на графовых моделях…....… 26

3.1. Решение задачи о максимальном потоке методом расстановки

пометок на графе (алгоритм Форда-Фалкерсона)…………….…... 26

3.2. Решение задачи о максимальном потоке в табличной форме…… 30

3.3. Решение задачи о максимальном потоке в графе

на основе линейного программирования……………………..…… 32

3.4. Решение задачи о кратчайшем пути в транспортной сети

непосредственно по графу…………………………………….….... 34

3.5. Решение задач о кратчайших путях в табличной форме….….….. 34

3.6. Кратчайший остов графа………………………………….….……. 37

3.7. Задача о назначениях……………………………………….……... 43

3.8. Задача о наименьшем покрытии………………………….……… 47

Кабанов Анатолий Николаевич

Теоретико-множественные и структурно-математические

основы описания дискретных систем

Редактор М.Е. Цветкова

Корректор Н.А. Орлова

Лицензия № 020446

Подписано в печать Формат бумаги 60 х 84 1/16.

Бумага газетная. Печать трафаретная. Усл.печ.л. 3,25.

Уч.-изд. л. 3,25. Тираж 100 экз. Заказ

Рязанская государственная радиотехническая академия.

390005, Рязань, ул. Гагарина, 59/1.

Редакционно-издательский центр РГРТА.