Компьютерная математика, Теория графов, часть 2, Волчанская Т.В., Князьков В.С., 2002

Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002.

  Пособие содержит материал практического изучения основ современной дискретной математики. Приведены основные понятия из теории графов и сетей. Рассматриваются вопросы различных способов описания графов, операции над графами, задачи связности и достижимости в графах. Причем, особое внимание уделено машинным методам представления информации и компьютерным алгоритмам решения задач.
Значительное место уделено решению оптимизационных задач на графах, таких как поиск кратчайших путей в графах и разбиение графов на максимальные сильно связные подграфы.
Учебное пособие предназначено для студентов младших курсов специальностей 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 - Яндекс.Диск.




Теги: учебник по математике :: математика :: Волчанская :: Князьков :: теория графов