Алгоритм метода последовательных приближений в два круга
Последовательных приближении метод, метод решения математических задач при помощи такой последовательности приближении, которая сходится к решению и строится рекуррентно (т. е. каждое новое приближение вычисляют, исходя из предыдущего; начальное приближение выбирается в достаточной степени произвольно). П. п. м. применяется для приближённого нахождения корней алгебраических и трансцендентных уравнений, для доказательства существования решения и приближённого нахождения решений дифференциальных, интегральных и интегро-дифференциальных уравнений, для качественной характеристики реш-я и в ряде др. математических задач.
Граф
Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые (а может быть, и все) пары вершин. При этом пары вершин могут соединяться несколькими ребрами.
Примеры графов: множество городов (вершины графа), например Московской области, и соединяющие их дороги (ребра графа); элементы электрической схемы и провода, соединяющие их.
Граф называется ориентированным, если на ребрах задана ориентация, т. е. указан порядок прохождения вершин. У графов могут быть приписаны ребрам какие-либо веса (или символы), а также графы, в которых выделены особые вершины, называются полюсами.
Графов теория находит применение в теории программирования и при построении вычислительных машин, в изучении физических, химических и технологических процессов, в решении задач планирования, и т. д. Г. т. включает большое число разнообразных задач. Среди сложившихся разделов Г. т. следует отметить задачи, относящиеся к анализу графов, определению различных харак-к их строения; реш-е транспортных задач, связанных с перев-vи грузов по сети. Решен ряд задач по синтезу графов с заданными св-и. Имеет прикладное и теорет-е значение задача о выяснении возможности располож-я графа на плоскости без самопересечений его рёбер (т. е. является ли данный граф плоским), задача о разбиении графа на мин-ое число плоских графов.
Разновидности графов
Простой граф граф без кратных ребер и петель. Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.Нуль-граф - граф (X,U), состоящий только из изолированных вершин.Однородный граф - если степени всех вершин графа одинаковы и P+(x)= P- (x) =0.Симметрический граф - граф, в котором две любые смежные вершины соединены только двумя противоположно ориентированными дугами. Антисимметрический - в к-м каждая пара смежных вершин соединена только в одном направлении.Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг.
Мультиграф - граф, в котором хотя бы две смежные вершины соединены более чем одной дугой. Наибольшее число дуг, соединяющих смежные вершины графа называется кратностью.
34 Подграф графа это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Всякий подграф может быть получен из графа удалением некоторых вершин и ребер.
Подграфом графа G(X,U) называется граф G(A,UA), определяемый следующим образом:
1. Вершинами A подграфа G(A,UA) является некоторое подмножество вершин графа G(X,U);
2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,UA).
Частичным графом для графа G(X,U) называется граф G(X,U), в котором содержатся все вершины и некоторое подмножество дуг исходного графа. Частичный подграф - это частичный граф от подграфа.
Фактором графа G(X,U) называется частичный граф G(X,U), в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги.
Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг.