Основные понятия теории графов.

Гамильтоновы графы.

Эйлеровы графы.

Связность графов.

Операции над графами.

Основные понятия теории графов.

Тема 1. Основные понятия теории графов.

Теорию графов начали разрабатывать для решения задач о геометрических конфигурациях, состоящих из точек и линии. В этих задачах, несущественно, какими видами линии (дугами, прямыми) и какой длины соединены такие конфигурации, а важно лишь то, что какая линия соединяет какие либо две из заданных точек.

Таким образом граф можно представить как совокупность двух множеств V-точек и U-линии, между элементами которых определено отношение инцидентности, т.е каждый элемент u Î U инцидентен равно двум элементам v1,v2 Î V (или каждая вершина инцидентна какому-либо ребру) : G=<V,U>.

Элементы множества V называются вершинами графа G (или узлами), элементы множества U-его ребрами. Вершины и ребра графа называют также его элементами и вместо vÎV и u ÎU пишут vÎG и uÎG.

Первая работа по графам была опубликована в 1736 году Леонардом Эйлером. В ней объяснялось решение задачи о кенигсбергских мостах: можно ли совершить прогулку по городу, чтобы, выйдя из любого места вернуться в него, пройдя только один раз по любому месту?

Эйлер Леонард (1707-1783 г. г) швейцарский математик, механик, физик и астроном. Автор более 800 работ по различным разделам математики и другим наукам.

Рисунок 1

Ясно, что по условию задачи не имеет значения, как проходит путь по частям суши a,b,c,d, на которых расположен город, поэтому их можно представить вершинами (Рис.1). А так как связи между частями суши осуществляется только через семь мостов, то каждый из них отображается ребром, соединяющий соответствующие вершины. В результате получится граф, показанный на рисунке. Исследуя этот граф, Эйлер дал отрицательный ответ на свой вопрос более того, он доказал, что подобный маршрут имеет только на таком графе, каждая из вершин которого связана с четным числом ребер.

В середине 19 века Г.Кирхгоф применил графы для анализа электрических цепей. Как математическая дисциплина теория графов сформировалась к середине 30-х годов 20 века. Ее основатели- Д.Кениг, Л.С. Потрягин, А.А Зыков, В.Г.Визинг и другие. С помощью теории графов наряду с головоломками и играми решаются многие важные практические задачи, в которых имеется некоторое множество объектов, тем или иным образом связанных друг с другом. Это могут быть сети автомобильных дорог, телефонные и другие коммуникационные сети, системы нефтепроводов и т.п.

Теория графов как раздел дискретной математики успешно применяется в задачах управления производством и при проектировании сети ЭВМ, разработке современных электронных модулей и проектирование физических систем с сосредоточенными параметрами (акустических, механических, электрических), решение задач автоматизированного проектирования и при решении проблем генетики. Теория графов является основой математического обеспечения современных систем обработки информации. Успешно используется эта теория и в ядерных исследованиях (диаграммная техника Фейнмана).

Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии.

Быстрое развитие теории графов получила с созданием электронно-вычислительной техники, которая позволяла решить многие задачи алгоритмизации.

Пусть на плоскости заданно некоторое множество вершин Х и множество U соединяющих их дуг. Графом называется бинарные отношения множества Х и множеств U: G=(X, U), или, иначе f: XàY. Здесь f- это отображение инциденции.

Граф называется ориентированным, если указанно направление дуг и неориентированным, если такое направление не указанно (например, карта дорог).

Граф называется петлей, если его начало и конец совпадают.

Две вершины называются смежными, если существует соединяющая их дуга.

Ребро Uj называется инцидентным вершине Xi, если оно выходит или входит в вершину.

Степенью (валентностью) вершины называется число инцидентных ей ребер. Кратность пары вершин называется число соединяющих их ребер или дуг.

Подграфом Ga графа G называется граф, в который входит лишь часть вершин графа G вместе с дугами их соединяющих.

Частым графом Gb графа называется граф, в который входит часть дуг графа G вместе с вершинами их соединяющих. Карта шоссейных дорог это граф.

Путем в графе G называется такая последовательность дуг, в которой конец каждой последующей дуги совпадает с началом предыдущей. Длиной пути называется число входящих в этот путь дуг. Путь может быть конечным и бесконечным. Путь, в котором никакая дуга не встречается дважды, называется элементарным.

Контур-это конечный путь, у которого начальная и конечная вершины совпадают. Контур называется элементарным, если все его вершины различны (кроме начальной и конечной). Контур единичной дуги называется петлей.

В неориентированном графе понятие дуга, путь, контур заменяются соответственно на ребро, цепь, цикл.

Ребро- отрезок, соединяющий две вершины, цепь- последовательность ребер.

Цикл - конечная цепь, у которой начальная и конечная вершина совпадают.

Граф называется связанным, если любые его две вершины можно соединить цепью. Граф сильно связан, если для его двух любых вершин Xi <>Xj существует путь, идущий из Xi и Xj.

Граф, который не является связанным, может быть разбит на конечное число связных графов, называемых компонентами или частями.

Ребро графа G называется мостом, если граф, полученный из G путем удаления этого ребра, имеет больше компонент связности, чем граф G.

Точка сочленения графа называется вершина, удаление которой приводит к увеличению числа его компонента связности.

Неразделимым называется связанный граф, не имеющий точек сочленения.

Блоком графа называют максимальный неразделимый подграф.

Дерево это конечный, связный, неориентированный граф, не имеющий циклов. Характеристическое свойство деревьев состоит в том, что любые две вершины дерева соединены единственной цепью.

Теория деревьев была, в основном, разработана Кирхгофом. Он применил ее для решения систем линейных уравнений, описывающих работу электрических цепей.

Кирхгоф Густав (1824-1887г.г.) это немецкий физик, механик, математик.

Развитие теории графов (деревьев) связанно с именем немецкого химика Кели, который успешно применил ее для решения задач органической химии (для изучения изомеров углеводородов с заданным числом атомов).

Совокупность деревьев называется лесом.

Если все вершины графа принадлежат дереву, то он называется покрывающим. Пусть дано множество вершин графа. Одну из вершин, например X1, примем за начальную, которую назовем корнем дерева. Из этой вершины проведем ребра к остальным вершинам X2 X3 и т.д. Простейшее дерево состоит из двух вершин, соединенных ребром.

Если добавить ребро, то добавляется и вершина. Таким образом, дерево с n вершинами имеет n-1 ребро. Дерево имеет корень в вершине Bj, если существует путь от X1 к каждой из вершин. Ребра графа, принадлежащие дереву, называют ветвями, остальные ребра называют хордами.

Граф называется планарным, если он может быть изображен на плоскости таким образом, что его ребра будут пересекаться только в планарных вершинах.

Дерево, являющееся подграфом графа G,называется покрывающим граф G,если оно содержит все его вершины.

Пусть имеется X1, X2… Xn вершин и U1, U2… Un дуг, их соединяющих. Матрицей смежности S порядка n называется матрица, состоящая из чисел Sij, равных сумме чисел ориентированных ребер, идущих из Xi в X j (или чисел неориентированных ребер, соединяющих эти вершины). Если дуга отсутствует, то Sij=0.

Матрица смежности для ориентированного и неориентированного графа, вообще говоря, имеет разный вид.

Запишем матрицу смежности S, для ориентированного графа, изображенного на рисунке 2

Рис.2.Ориентированный граф.

Матрицей инциденции Т размера m*n называется матрица, состоящая из чисел:

Tij=1,если дуга U_j выходит из вершины Х_i;

-1,если дуга U_j входит в вершину Х_i;

0, если такой дуги нет.