Теоретико-множественное определение графа

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

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

G=(X, U). (2.1)

На рис. 2.1 изображен граф, вершинами которого яв­ляются точки b, с, d, e_y g, h, а дугами — отрезки (с, b), (с, d), (с, е), (d, с), (d, d), (e, d), (g, h). Приме­рами графов являются отношения отцовства и мате­ринства на множестве людей, карта дорог на местности, схема соединений электрических приборов, отношения превосходства одних участников турнира над другими и т. п.

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

G=(X, Г). (2.2)

Рис. 2.1. Общий вид графа

Так, для графа, изображенного на рис. 2.1, отображе­ние определяется следующим образом:

Гb=Æ; Гс={b;d; е); Гd={d;с}; Гe=d; Гg=h; Гh = Æ.

Нетрудно видеть, что данное определение графа пол­ностью совпадает с определением отношения на множе­стве.

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

Подграфом G_A графа G=(X, Г) называется граф, в ко­торый входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти верши­ны, например, очерченная пунктиром область на рис. 2.1. Математический подграф

Ga=(A, Г_а), (2.3)

АХ, Г_а=(Г х). (2.4)

Частичным графом по отношению к графу G = (Х, Г) называется граф, содержащий только часть дуг графа G, т. е. определяемый условием

=(Х,), (2.5)

где

хГх. (2.6)

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

Пример 2.1.Пусть G = (X, Г) -карта шоссейных дорог Украины. Тогда карта шоссейных дорог Киевской области пред­ставляет собой подграф, а карта главных дорог Украины - частичный граф.

Другими важными понятиями являются понятия пути и контура. Ранее было дано определение дуги как направ­ленного отрезка, соединяющего две вершины. Дуга, соеди­няющая вершины а и b и направленная от а к b, обозна­чается и = (а, b).

Путем в графе G называют такую последовательность дуг m=( и₁, и₂, ..., и_к),в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь m, последо­вательными вершинами которого являются вершины а, b, ..., m, обозначается через m==(а, b, ..., m).

Длиной пути m= ( и₁, и₂, ..., и_к) называют число l(m)= k. равное числу дуг, составляющих путь mх. Иногда каждой дуге и_i приписывают некоторое число l( и_i), назы­ваемое длиной дуги. Тогда длина пути определяется как сумма длин дуг, составляющих путь

l(m)=.(2.7)

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

Контур — это конечный путь m= (и₁, и₂, ..., и_к), у которого начальная вершина и₁совпадает с конечной и_k. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный ду­гой вида (а, а), называется пет­лей. Так, на рис. 2.1 (е, d, с, b) — путь, (с, е, d, с) - контур, (d, d) - петля.

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

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

Рис. 2.2. Общий вид графа

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

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

Введем числа:

Квадратная матрица R=[r_i,j] порядка пXп называет­ся матрицей смежности графа.

Введем числа:

Матрица S=[] порядка пXт называется матрицей инциденций для дуг графа.

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

На рис. 2.2 приведен граф без петель, для которого матрицы смежности и инциденций имеют вид: