Элементы теории графов

Лекция 4 ММ ТП в маш.

Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных отрезков U, соединяющих все или некоторые из вершин и называемых дугами (ребрами). Математически граф G можно определить как пару множеств X и U:

(4.1)

Рисунок 4.1 Общий вид графа

На рисунке 1 изображен граф, вершинами которого являются точки a, b, c, d, t, g, h, а дугами – отрезки (а, а), (с, b), (c, e), (d, c), (d, d), (e, d), (g, h).

Иногда удобно дать графу другое определение. Можно считать, что множество направленных дуг U, соединяющих элементы множества Х, отображает это множество само на себя. Поэтому можно считать граф заданным, если дано множество его вершин Х и способ отражения Г множества Х в Х. Тогда граф G есть пара (Х, Г), состоящая из множества Х и отображения Г, заданного на этом множестве

(4.2)

Для графа, изображенного на рисунке 1, отображение осуществляется следующим образом:

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

Подграфом G_Δ графа называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины. Например, на рисунке 1 это область, очерченная пунктиром. Математически подграф

где

Частичным графом G_Δ по отношению к графу называется граф, содержащий только часть дуг графа G,, то есть определяемый условием

, где .

На рисунке 1 граф, образованный жирными дугами образует частичный граф.

Пример. Пусть - карта дорог РФ. Тогда карта дорог Оренбургской области есть подграф, а карта дорог федерального значения есть частичный граф.

Дуга, соединяющая вершины a и b и направленная от а к b, обозначается .

Путем в графе называют такую последовательность дуг , в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь , последовательными вершинами которого являются вершины a, b, …m, обозначается через .

Длиной пути называется число равное числу дуг, составляющих путь . Иногда каждой дуге u_i приписывается некоторое число , называемое длиной дуги. Тогда длина пути определяется как суммы длин дуг, составляющих путь

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

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

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

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

Дугу называют инцидентной вершине х, если она заходит в эту вершину или выходит из нее.

Обозначим через х₁,х₂, …, х_п вершины графа, а через и₁, и₂, … и_т его дуги. Введем числа

Квадратная матрица порядка называется матрицей смежности графа.

Введем числа

Матрица порядка называется матрицей инциденций для дуг графа. Матрицы инциденций применимы только для графов без петель. В случае наличия в графе петель эту матрицу следует расчленить на две полуматрицы: