Краткий перечень основных понятий теории графов.
Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы не будут вводиться в рассмотрение) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки − вершины графа − города, линии, соединяющие вершины − ребра − дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города- пункта в другой).
Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V×V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
. 2, равна двум, кратность ребра {v3, v4} − трем.
Псевдограф − граф, в котором есть петли и/или кратные ребра.
Мультиграф − псевдограф без петель.
Граф − мультиграф, в котором ни одна пара не встречается более одного раза.
Граф называется ориентированным, если пары (v,w) являются упорядоченными.
Ребра ориентированного графа называются дугами.
Итак, используемые далее обозначения:
V – множество вершин;
X – множество ребер или дуг;
v (или vi)– вершина или номер вершины;
G, G0 - неориентированный граф;
D, D0 – ориентированный;
{v,w} − ребра неориентированного графа;
{v,v} – обозначение петли;
(v,w) − дуги в ориентированном графе;
v,w - вершины, x,y,z – дуги и ребра;
n(G), n(D) количество вершин графа;
m(G) - количество ребер, m(D) - количество дуг.
Задание 4. Эйлеровы циклы и цепи
Найти Эйлерову цепь в неориентированном графе.
Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.
Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин
1) Выделим из G цикл 1. (так как степени вершин четны, то висячие вершины отсутствуют). Положим l=1, G’=G.
2) Удаляем из G’ ребра, принадлежащие выделенному циклу 1. Полученный псевдограф снова обозначаем как G’. Если в G’ отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G’ цикл l+1 и переходим к шагу 3.
3) Присваиваем l:=l+1 и переходим к шагу 2.
4) По построению выделенные циклы содержат все ребра по одному разу. Если l:=1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.
Пример.
Найдем Эйлерову цепь в неориентированном графе G, изображенном на рис. 10.
Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа G − согласно утверждению 2, для существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе G ровно 2 вершины нечетной степени.
В рассматриваемом графе нечетные степени имеют вершины v3 и v1 (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф G.
Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы i так, чтобы хотя бы один из них начинался или кончался на вершинах v3 или v1.
Пусть цикл 1 составят ребра, проходящие через следующие вершины: v3 v4 v7 v6 v1 v2 v3. Согласно алгоритму, удаляем из G’ все ребра, задействованные в цикле 1. Теперь граф G’ будет таким, как показано на рис. 12.
Составляем следующий цикл 2: v4 v5 v6 v2 v5 v7 v4. Граф G’ после удаления ребер, составляющих цикл 2, изображен на рис. 13.
СПИСОК ЛИТЕРАТУРЫ
1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987. -598 с.
2. Бахвалов Н.С. Численные методы. Часть 1. М.: Наука, 1973. 631 с.
3. Самарский А.А. Введение в численные методы. М.: Наука, 1987. 286 с.
4. Калиткин Н.Н. Численные методы. М.: Наука, 1978. 512 с.
5. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислитель¬ные методы. Т. I, II. М.: Наука, 1987. 600 с.
6. Житников В.П., Шерыхалина Н.М., Ураков А.Р. Линейные некорректные задачи. Верификация численных результатов. Учебное пособие. Уфа: УГАТУ, 2002. 91 с.
7. Smith D.A., Ford W.F. Acceleration of linear and logarithmic convergence. – SIAM J. Numer. Anal., 1979, v. 16. P. 223-240.
8. Smith D. A., Ford W. F. Numerical comparisons of non-linear convergence accelerations. – Mathematics of Computation, 1982, v. 38, 158. P. 481–499.
9. Прудников А.П., Бычков Ю.А., Маричев О.И. Интегралы и ряды. –М.: Наука, 1981. 800 с.