Читать онлайн «Методы решения систем с разреженными матрицами. Теория графов: Учебное пособие»

Министерство образования Российской Федерации ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПММ Кафедра вычислительной математики МЕТОДЫ РЕШЕНИЯ СИСТЕМ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ ТЕОРИЯ ГРАФОВ Методические указания к спецкурсу для студентов 3-го курса дневного и вечернего отделений ПММ СОСТАВИТЕЛИ: Глушакова Т. Н. Блатов И. А. Воронеж – 2000  2 СОДЕРЖАНИЕ §1. Основные понятия…………………………………………………... 3 §2. Симметричная перестановка………………………………………. . 6 §3. Разбиение на уровни смежности…... ……………………………... . . 6 §4. Алгоритм Катхилл – Макки уменьшения ширины ленты………... 7 §5. Алгоритм уменьшения профиля разреженной матрицы……. ……9 §6. Алгоритм отыскания псевдопериферийной вершины графа……10 §7. Алгоритм отыскания вершины с большим значением эксцент- риситета……………………………………………………………. . 11 §8. Некоторые понятия из теории графов……………………. . ……... 12 §9. Алгоритм минимальной степени………………………. . ………... 14 §10. Древовидное разбиение симметричной матрицы (метод фак- тор-деревьев)……………………………………………………… 17 §11. Метод вложенных сечений………………. . ………………………21 §12. Метод параллельных сечений. ……………. ……………………... 25 Список задач. …... ……………………. ……………………………31 Лабораторный практикум. ………………………………………. . 35 Список сокращений…………………………. ……………………. 35 Литература……………………………………. ……………………36  3 Часть II. . Теория графов (Способы уменьшения заполнения в методах Гаусса и Холецкого. Прогнозирование заполнения для симметричных положительно определённых матриц) §1. . Основные понятия Все рассматриваемые ниже алгоритмы относятся к символическому этапу обработки симметричных положительно определённых матриц. Основным инструментом при разработке таких алгоритмов является теория графов. Между разреженными матрицами и графами существует естественное взаимно- однозначное соответствие. Граф G задаётся совокупностью вершин V и совокупностью рёбер E: G(V,E). Каждое ребро r ∈ E определяется парой вершин u, v из V: r = (u,v), где u,v ∈V. Опр. Если мы не различаем рёбра (u,v) и (v,u), т. е. считаем, что (u,v) = (v,u), то граф называется неориентированным, а если различаем, то ориентированным (орграф). Опр. Граф называется помеченным (пронумерованным), если каждой его вершине присвоен порядковый номер. Между графами и матрицами существует взаимно однозначное соответствие. Пусть А = {aij} – симметричная матрица (n×n). Каждой i-той строке матрицы (i=1,. . ,n) поставим в соответствие вершину vi и каждому ненулевому элементу aij поставим в соответствие ребро (vi,vj). Таким образом, получим граф G(V,E). Так как матрица симметрична, т. е. aij = aji, то граф является неориентированным. Пара (vi,vj) будет являться ребром в том и только том случае, когда aij ≠ 0. Если матрица А симметрична и положительно определена, то все её диагональные элементы aii ≠ 0, поэтому диагональному элементу aii ≠ 0 соответствует в этом случае петля (vi,vi) и предположение о том, что aii ≠ 0 для ∀i, отвечает тому, что граф содержит все петли.