Пособие содержит материал практического изучения основ современной дискретной математики. Приведены основные понятия из теории графов и сетей. Рассматриваются вопросы различных способов описания графов, операции над графами, задачи связности и достижимости в графах. Причем, особое внимание уделено машинным методам представления информации и компьютерным алгоритмам решения задач.
Значительное место уделено решению оптимизационных задач на графах, таких как поиск кратчайших путей в графах и разбиение графов на максимальные сильно связные подграфы.
Учебное пособие предназначено для студентов младших курсов специальностей 20.18.00 , 22.04.00 и других специальностей, изучающих дисциплины “Дискретная математика” и “Прикладная математика”.
Матричный метод разбиения.
Метод разбиения графа на максимальные сильно связные подграфы по матрицам достижимости R и контрдостижимости Q состоит в следующем [5].
1. По матрице смежности строится матрица достижимости R. Используя операцию транспонирования, находим матрицу контрдостижимости Q.
2. Находится матрица C = { сij }, i,j=1,2,3,...,n, где n-число вершин исходного графа , а каждый элемент Cij = rij ∧ gij , т.е. матрица C получается поэлементным логическим умножением матриц R и Q : С = R ∧ Q.
3. Элементы, имеющие одинаковые строки и столбцы в матрице С группируем перестановкой строк и столбцов, получаем блочно диагональную матрицу Св, где каждая группа элементов и есть максимальный сильно связный
подграф.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯОШИБКА
1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
1.2. СПОСОБЫ ОПИСАНИЯ ГРАФОВ
1.2.1. Теоретико-множественное представление графов
1.2.2. Задание графов соответствием
1.2.3. Матричное представление графов
1.3. ОПЕРАЦИИ НАД ГРАФАМИ
2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ
2.1. МНОГОЗНАЧНЫЕ ОТОБРАЖЕНИЯ
2.1.1. Прямые отображения
2.1.2. Обратные отображения
2.2. ТРАНЗИТИВНЫЕ ЗАМЫКАНИЯ
2.2.1. Прямое транзитивное замыкание
2.2.2. Обратное транзитивное замыкание
2.2.3. Нахождение транзитивных замыканий по матрице смежности
2.3. ДОСТИЖИМОСТЬ И КОНТРДОСТИЖИМОСТЬ
3. ГРАФЫ И ПОДГРАФЫ
3.1 ТИПЫ ГРАФОВ.
3.1.1.Теорема о двудольности
Доказательство.
3.2.ВИДЫ ПОДГРАФОВ
3.3.СИЛЬНО СВЯЗНЫЕ ГРАФЫ И КОМПОНЕНТЫ ГРАФА
4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО СВЯЗНЫЕ ПОДГРАФЫ
4.1 МЕТОД МАЛЬГРАНЖА
4.2. МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ
5. ПУТИ И ЦИКЛЫ В ГРАФАХ
5.1. ПУТИ И МАРШРУТЫ
5.2. МАТРИЧНЫЙ МЕТОД НАХОЖДЕНИЯ ПУТЕЙ В ГРАФАХ
5.3. ВЕС И ДЛИНА ПУТИ
5.4. АЛГОРИТМ ДЕЙКСТРЫ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ
5.5. ОРЦИКЛЫ И ЦИКЛЫ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Приложения
Приложение 1. АЛГОРИТМ НАХОЖДЕНИЯ ХАРАКТЕРИСТИК ГРАФА
Приложение 2. Построение транзитивных замыканий
Приложение 3. Построение матриц достижимости и контрдостижимости
Приложение 4. Разбиение графа на подграфы по методу Мальгранжа
Приложение 5. МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ.
ОТВЕТЫ
УПРАЖНЕНИЙ К ГЛАВЕ 1
УПРАЖНЕНИЙ К ГЛАВЕ 2
УПРАЖНЕНИЙ К ГЛАВЕ 3
УПРАЖНЕНИЙ К ГЛАВЕ 4
УПРАЖНЕНИЙ К ГЛАВЕ 5.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Компьютерная математика, Теория графов, часть 2, Волчанская Т.В., Князьков В.С., 2002 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать книгу Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002 - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по математике :: математика :: Волчанская :: Князьков :: теория графов
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Курс лекций по высшей математике, часть 1, Дубинина Л.Я., Никулина Л.С., Пивоварова И.В., 2001
- Курс лекций по высшей математике, часть 2, Дубинина Л.Я., Никулина Л.С., Пивоварова И.В., 2002
- Математические беседы для студентов, Ленг С., 2000
- Курс математического анализа, Никольский С.М., 2000
Предыдущие статьи:
- Квантовая механика для математиков, Тахтаджян Л.А., 2011
- Избранные главы истории математики, Малаховский В.С., 2002
- Занимательная математика, Множества и отношения, Дунаев В.В., 2008
- Теория функций комплексного переменного и операционное исчисление, Галкин С.В., 2011