Основные определения. Граф является одним из способов описания бинарного отношения, рассмотренного в предыдущем разделе

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

Определение. Графом G называют пару <A, U>,
где

А={a₁,a₂,...,a_n} –множество вершин графа;

UÍ AxA ={(a_i,a_j)} – множество его дуг.

Как и всякое бинарное отношение, граф представляется матрицей nxn, где n = | A |, которую называют матрицей смежности. Граф имеет следующую графическую интерпретацию: сопоставим каждому элементу множества А (вершинам) кружок на плоскости рисунка и соединим кружки, сопоставленные вершинам a _i и a _j, стрелкой, направленной из первого кружочка во второй, если пара (a_i,a_j) Í U. Граф, определённый таким образом, называют ориентированным графом (орграфом) или графом Бержа.

Таблица 2.1

Говорят, что дуга (a_i,a_j) исходит из вершины a_i и заходит в вершину a_j. Вершину a _i называют началом, a _j - концом дуги. Эти вершины называются смежными, или инцидентными дуге (a_i,a_j). Две дуги смежны, если они имеют общую граничную вершину.

Пример. Граф G =(A,U), где A ={1,2,3,4,5}, и U задано матрицей смежности табл. 2.1., изображен на рис.2.1.

Число дуг, исходящих из вершины a _i, называют степенью ее исхода d _i ^-, заходящих в a _i – степенью захода d _i⁺ , сумма степеней исхода и захода (d _i = d _i ^-+ d _i ⁺) – степенью вершины i. Так, вершина 3 имеет степень захода, равную 2, степень исхода – 2. Степень вершины равна 4.

Теорема. В графе число вершин с нечетной степенью четно.

Доказательство основано на том, что любая дуга связана с двумя вершинами, значит, сумма степеней всех вершин вдвое больше числа вершин, т.е. всегда четна.

Для подмножества вершин ‘A Í A множество дуг, исходящих из ‘A, обозначают ‘A ^-,а множество дуг, заходящих в ‘A - ‘A ⁺.

В рассматриваемом выше примере для ‘A ={4,5} ‘A ^-={ U ₄, U ₁₀}, ‘A ⁺={ U ₂ }.

Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей дуги, называют путем между вершиной – началом первой дуги (началом пути) и вершиной – концом последней дуги (концом пути). Число дуг в последовательности принимается за длину пути.

В приведенном примере путь между 1 и 4 вершинами состоит из дуг U ₇, U ₆, U ₂, U ₁. Между этими же вершинами существует путь U ₇, U ₈, U ₇, U ₆, U ₂, U ₄, U ₆, U ₂, U ₁. Первый путь имеет длину 4, второй – 9.

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

Путь, в котором начало и конец совпадают, называется контуром. Для контура используются те же понятия, что и для пути: контур может быть простым или составным, элементарным или неэлементарным. Начальная (она же и конечная) вершина контура считается входящей только один раз, хотя в записи она будет встречаться дважды. В примере путь U ₇, U₆, U ₃ является контуром, так как он начинается и кончается в вершине 1.

Контур единичной длины называется петлей. В примере дуга U ₉ образует петлю.

Граф называется сильносвязанным, если любая пара вершин в нем связана путем с началом в первой и концом во второй вершине.

Приведенный в примере граф является сильносвязанным. Если сменить ориентацию дуги (3,5) на противоположную, то полученный граф сильносвязанным не будет. В нем ни одна вершина не будет связана путем с вершиной 5.

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

Введем еще одну трактовку графа. Будем считать, что U описывает отображение множества А в себя. Тогда множество вершин, связанных с подмножеством ‘A Í A по исходящим дугам (конечные вершины дуг из ‘A ^-), будет образом множества ‘ A (обозначается U (‘A)), множество вершин, связанных по заходящим дугам (начальные вершины дуг из ‘A ⁺), – прообразом ‘A (обозначается U ^– (‘A)). В примере для подмножества
'A ={3, 5} U (‘ A)= {1, 2, 4}, U ^–(‘ A)={2,4}. В зависимости от задачи будем использовать обе эти трактовки: U как множество дуг и U как отображение.

Дата добавления: 2014-01-07