- •1Графика
- •1.1Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном
- •1.2Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном
- •2Представление разреженных матриц.
- •2.1Форматы представления разреженных матриц
- •2.2Конвертация разреженной матрицы из нормальной формы в формат rr(c)o
- •2.3Конвертация разреженной матрицы, представленной в формате rr(c)u в нормальную форму
- •2.4Транспонирование разреженной матрицы, заданной в формате rr(c)u
- •2.5Сложение двух матриц, заданных в формате rr(c)u.(1-й способ)
- •2.6Сложение двух матриц, заданных в формате rr(c)u.(2-й способ)
- •2.7Умножение двух матриц, заданных в формате rr(c)u.(1-й способ)
- •2.8Умножение двух матриц, заданных в формате rr(c)u.(2-й способ)
- •3Интегральные уравнения.
- •3.1Введение
- •3.2Уравнение Вольтерра первого рода
- •3.3Линейное уравнение Вольтерра второго рода
- •3.4Уравнение Фредгольма второго рода
- •4Методы оптимизации
- •4.1Метод наискорейшего спуска
- •4.2Минимизация функции многих переменных методом конфигураций
- •5Теория графов
- •5.1Способы задания графа
- •5.2Путь с минимальным количеством промежуточных вершин.(волновой алгоритм)
- •5.3Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда)
- •5.4Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена)
- •5.5Построения минимального остовного дерева (Алгоритм Краскала)
- •6Сетевое программирование
5Теория графов
5.1Способы задания графа
Первый способ задания графа (невзвешенного) это задать матрицу связности S размера n*n, где n количество вершин графа, т.е. мощность множества V, при этом элемент si j=1, если существует ребро из i-ой в j-ую вершины и si j=0, если такого ребра нет. Нетрудно видеть, что матрица S- симметрична, если граф неориентированный, и может быть не симметричный в противном случае. При этом полагаем, что si i=0, т.е. в графе нет петель. Такой способ задания графа используется например в волновом алгоритме.
Второй способ используется для задания взвешенного графа, т.е. графа каждому ребру которого соответствует некий параметр - вес. Для определения такого графа используется матрица весов W размер которой n*n, где n количество вершин графа. При этом элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. Если такого ребра нет, то wi j полагаем равным бесконечности (на практике это максимальное число возможное на данном языке программирования). Этот способ задания используется например в алгоритмах поиска пути во взвешенном графе.
5.2Путь с минимальным количеством промежуточных вершин.(волновой алгоритм)
Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе G=(V,E) заданном матрицей связности S. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует волновой алгоритм.
Волновой алгоритм заключается в следующем:
каждой веpшине i пpиписывается два целых числа T[i] - вpеменная метка и P[i] - метка предыдущей вершины пути (начальное значение T[i]=0, P[i]=0 для всех i);
заводятся два списка "фpонта волны" NF и OF, а также пеpеменная T (текyщее вpемя);
OF:={u1}; NF:={}; T:=1;
для каждой из веpшин i, входящих в OF, пpосматpиваются соседние веpшины j, и если T[j] = 0, то T[j]=T, NF=NF + {j}; в переменную P[j] заносится номер i.
если NF = {}, то пyть не сyществyет, переход к шагу 8;
если одна из веpшин совпадает с u2, то найден кpатчайший пyть длины T, переход к шагу 8;
OF:=NF; NF:={}; T:=T+1; возврат к шагу 4.
Восстанавливаем путь проходя массив P.
В качестве OF, NF я использутся массивы размера n (количество вершин в графе), некоторые языки (например Pascal) позволяют работать с объектами типа множества, тогда правильнее использовать именно такую структуру для определения OF, NF.
На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2) и массив Path содержащий последовательность номеров вершин определяющих путь.
5.3Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда)
Процедура находит пути минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.
Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W[i,j]- симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)
Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:
D0=W
dm+1[i,j]=min{dm[i,j], dm[i,(m+1)] + dm[(m+1),j]}, где i<>j; dm+1[i,i]=0.
преобразование проделывается для m=1..n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное dm[i,m]+dm[m,i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.
На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i, если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.
Заметим, что если граф неориентированный, то W а также все матрицы получаемые в результате преобразований симметричны и следовательно достаточно вычислять только элементы расположенные выше главной диагонали.