Граф является одним из способов описания бинарного отношения, рассмотренного в предыдущем разделе. Легко видеть, что бинарное отношение на множестве - наиболее общее описание связей между элементами множества, указывающее факт наличия или отсутствия связи между парами элементов из множества независимо от характера связи.
Определение. Графом G называют пару <A, U>, где
А={a1,a2,... ,an}-} –множество, называемое множество вершин графа;
UÍ AxA ={(ai,aj)} - – множество, называемое множество его дуг.
Как и всякое бинарное отношение, граф представляется матрицей nxn, где n = |A|, которую называютемой матрицей смежности. Граф имеет следующую графическую интерпретацию: сопоставим каждому элементу множества А (вершинам) кружок на плоскости рисунка и соединим кружки, сопоставленные вершинам ai и aj, стрелкой, направленной из первого кружочка во второй, если пара (ai,aj)ÍU.
Граф, определённый таким образом, называют ориентированным графом (орграфом) или графом Бержа.
Таблица 3.1
Говорят, что дуга (ai,aj) исходит из вершины ai и заходит в вершину aj. Вершину aiназывают началом, aj - концом дуги. Эти вершиныназываются смежными, или инцидентными дуге (ai,aj). Две дуги смежны, если они имеют общую граничную вершину.
ПримерПример. Для гГрафа G =(A,U), где на рис.3.1 A={1,2,3,4,5}, и U задано матрицей смежности табл. 3.1., изображен на рис.3.1.
Число дуг, исходящих из вершины ai, называется называют степенью ее исхода di-, заходящих в ai - – степенью захода di+, сумма степеней исхода и захода (di=di-+di +) -– степенью вершины i. Так, вершина 3 имеет степень захода, равную 2, степень исхода - – 2. Степень вершины равна 4.
Табл.3.1
Теорема.В графе число вершин с нечетной степенью четно.
Доказательство основано на том, что любая дуга связана с двумя вершинами, значит, сумма степеней всех вершин вдвое больше числа вершин, т.е. всегда четночетна.
Для подмножества вершин ‘A ÍA множество дуг, исходящих из ‘A, обозначают ‘A-,а множество дуг, заходящих в ‘A - ‘A+ .
В рассматриваемом выше примере для ‘A={4,5} ‘A-={U4,U10},‘A+={U2}.
Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом последующей дуги, называют путем между вершиной - – началом первой дуги (началом пути) и вершиной - – концом последней дуги (концом пути). Число дуг в последовательности принимается за длину пути.
В приведенном примере путь между 1 и 4 вершинами состоит из дуг U7, U6, U2, U1. Между этими же вершинами существует путь U7,U8, U7, U6, U2, U4, U6, U2, U1. Первый путь имеет длину 4, второй -– длину 9.
Путь назовем простым, если в нем никакая дуга не повторяется дважды, иначе путь будетназовём составнымсоставным. В примере первый путь - простой, второй - составной. Путь назовем элементарным, если в нем никакая вершина не встречается дважды. Любой составной путь не является элементарным, простой путь может быть как элементарным, так и не элементарным.
Путь, в котором начало и конец совпадают, называется контуром. Для контура используются те же понятия, что и для пути: контур может быть простым или составным, элементарным или неэлементарным. Начальная и (она же и конечная) вершина контура считается входящей только один раз, хотя в записи она будет встречаться дважды. В примере путь U7, U6, U3 является контуром, так как он начинается и кончается в вершине 1.
Контур единичной длины называется петлей. В примере дуга U9 образует петлю.
Граф называется сильносвязанным, если любая пара вершин в нем связана путем с началом в первой и концом во второй вершине.
Приведенный в примере граф является сильносвязанным. Если сменить ориентацию дуги (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 как отображение.
