Бесплатная библиотека - 1 338 003 изданий в библиотеке

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

Книга Компьютерная математика, Теория графов, Часть 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.

Рейтинг: 4.8 баллов / 2537 оценок
Формат: Книга
Уже скачали: 12909 раз

Похожие Книги

Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!

Вы не зарегистрированы!

Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.

Войти Регистрация

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.