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

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

Определение 2.12..Графом называется двухосновная модель <V,E;R>, гдеR– бинарное отношение множествVиE, такое, что каждый элементeEнаходится в отношенииRлибо ровно с одним, либо ровно с двумя элементами множестваV. При этом элементы множестваVназываются вершинами графа, элементы множестваEназываются рёбрами графа, а отношениеR– отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными.

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны, обычно граф обозначают как G(V, E).

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

Остановимся подробнее на способах задания графов. Это является важным для их представления при реализации на ЭВМ алгоритмов, применяющих графы как объекты программирования.

Задать граф- значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф G - конечный, для описания его вершин и ребер достаточно их занумеровать. Пусть v₁, v₂, . . . , v_n- вершины графаG; e₁, e₂, . . . , e_m- его ребра. Отношение инцидентности можно определить матрицей ||_ij||, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки - ребрам. Если ребро e_iинцидентно вершине V_j, то_ij= 1, в противном случае_ij= 0. Это так называемаяматрица инцидентностинеориентированного графа G, которая является одним из способов его определения (для неориентированного графа она дана в табл.a).

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

Неориентированный граф.

В матрице инцидентности ||_ij|| ориентированного графа G, если вершинаv_j- начало реб-ра a_i, то_ij= -1; если v_j- конец a_i, то_ij= 1; если a_i- петля, а v_j- инцидентная ей вершина, то_ij= a, где a - любое число,отличное от 1, 0 и -1, в остальных случаях_ij= 0 ( табл. б)).

В каждой строке матрицы инцидентности для неориентированного или ориентированного графа только два элемента отличны от 0 (или один, если ребро является петлей). Поэтому такой способ задания графа оказывается недостаточно экономным. Отношение инцидентности можно еще задать списком реберграфа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему. Для неориентированного графа порядок этих вершин в строке произволен, для ориентированного первым стоит номер или другое наименование начала ребра, а вторым - его конца. В табл. в) и г) приводятся списки ребер для графов, изображенных выше. По списку ребер графа легко построить его матрицу инцидентности. Действительно, каждая строка этого списка соответствует строке матрицы с тем же номером. Для неориентированного графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1, и для ориентированного графа в этой строке первым стоит номер элемента строки матрицы, равного -1, а вторым - номер элемента, равного +1.

Еще одним способом задания графа является матрица смежности- это квадратная матрица ||_ij||, столбцам и строкам которой соответствуют вершины графа. Если существует ребро связывающее вершиныv_iиv_j, то_ij=1, в противном случае_ij=0.

Матрицы смежности, рассмотренных выше графов приведены в табл. д) и е)

д) е)

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

Степень вершины – число инцидентных этой вершине рёбер,S(х).

Граф полный – графG=(V, E), в котором любая пара вершин инцидентна единственному ребру. ОбозначаетсяK_p, гдер=|V|, при этом |E|=p(p-1)/2.

Число рёбер в графе вычисляется по формуле: n=p(p-1)/2, где р – количество вершин.

Теорема 2.1. Сумма степеней вершин любого графа равна удвоенному числу его ребер.

Теорема 2.2. Число нечетных вершин любого графа четно.

Теорема 2.3. Во всяком графе сnвершинами, гдеn2, всегда найдутся две или более вершины с одинаковыми степенями.

Теорема 2.4.Если в графе сnвершинами только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Важными понятиями теории графов являются понятиямаршрутаипути, которые ассоциируются с последовательным перемещением от вершины к вершине по соединяющим их ребрам или дугам.Маршрутдлиныопределяется как последовательностьребер графа таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Замкнутый маршрут приводит в ту же вершину, из которой он начинался. Маршрут, все ребра которого различны, называетсяцепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называетсяциклом, а простая замкнутая цепь – простым циклом. Для маршрута с n вершинами: вершины, v_nназываются связанными данным маршрутом (или просто связанными). Вершинуназывают началом, аv_n– концом маршрута. Числоnназывается длиной маршрута.

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

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

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

Два графа G(V, E) и H(W, I) называются изоморфными, если существует взаимно-однозначное соответствие между множествами вершин V, W и множествами ребер E, I, сохраняющее отношение инцидентности. Можно сказать, что изоморфные графы – это один и тот же граф, в котором вершины названы по-разному.

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

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

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

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

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

С помощью различных операций можно строить графы из более простых, переходить от графа к более простому, разбивать графы на более простые и т.д. Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w - новая вершина) и др. Известны двуместные операции: соединение, сложение, различные виды умножений графов и др. Такие операции используются для анализа и синтеза графов с заданными свойствами.

Некоторые виды графов имеют специальные названия. Полнымграфом называется неориентированный граф, содержащий все возможные ребра для данного множества вершин ( любая вершина смежная любой другой ). Неориентированный граф называютдвудольным, если множество вершинVможно разбить на две частиV₁иV₂таким образом, что концы любого ребра оказываются в разных частях. Остановимся подробнее на основном для теории алгоритмов классе графов –деревьях.

Граф без циклов называется ациклическим. Ациклический связной граф называетсядеревом. Произвольный ациклический граф называется лесом.

Теорема 2.5. (свойства деревьев). ПустьG=(V,E) – неориентированный граф. Тогда следующие свойства равносильны:

1. G– является деревом ( без выделенного корня );

2. для двух любых вершин Gсуществует единственный соединяющий их простой путь;

3. граф Gсвязен, но перестает быть связным, если удалить любое его ребро;

4. граф Gсвязен и;

5. граф Gациклический и;

6. граф Gациклический, но добавление любого ребра к нему порождает цикл.

Деревом в теории графов называется такой граф D=<V, E>, между любыми двумя вершинами которого существует единственная простая цепь, т. е. неориентированный маршрут, у которого вершины и ребра не повторяются. Применительно к ориентированным графам соответствующее определение является более сложным, поскольку основывается на выделении некоторой специальной вершины v₀, которая получила специальное название корневой вершины или просто - корня. В этом случае ориентированный граф D=<V, Е> называется ориентированным деревом или сокращенно - деревом, если между корнем дерева v₀и любой другой вершиной существует единственный путь, берущий начало в v₀. Ниже представлены два примера деревьев: неориентированного дерева а) и ориентированного дерева б).

Дерево с корнем, или корневое дерево(rootedtree), получается, если в дереве выделить одну из вершин, назвав еёкорнем (root).

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

Для случая ориентированного дерева б) вершина v₂является единственным его корнем и имеет специальное обозначение v₀. Единственность корня в ориентированном дереве следует из того факта, что ориентированный путь всегда имеет единственную вершину, которая является его началом. Поскольку в теории графов имеет значение только наличие или отсутствие связей между отдельными вершинами, деревья, как правило, изображаются специальным образом в виде иерархической структуры. При этом корень дерева изображается самой верхней вершиной в данной иерархии. Далее следуют вершины уровня 1, которые связаны с корнем одним ребром или одной дугой. Следующий уровень будет иметь номер 2, поскольку соответствующие вершины должны быть связаны с корнем двумя последовательными ребрами или дугами. Процесс построения иерархического дерева продолжается до тех пор, пока не будут рассмотрены вершины, которые не связаны с другими вершинами, кроме рассмотренных, или из которых не выходит ни одна дуга. В этом случае самые нижние вершины иногда называютлистьямидерева. Важно иметь в виду, что в теории графов дерево "растет" вниз, а не вверх, как в реальной жизни. Изображенные выше деревья можно преобразовать к виду иерархий. Например, неориентированное дерево может быть представлено в виде иерархического дерева следующим образом в). В этом случае корнем иерархии является вершина v₁. Ориентированное дерево также может быть изображено в форме иерархического дерева г), однако такое представление является единственным.

В первом случае вершина v₂образует первый уровень иерархии, вершины v₄и v_{3 -}второй уровень иерархии, вершина v₅- третий и последний уровень иерархии. При этом листьями данного неориентированного дерева являются вершины v₃и v₅. Во втором случае (рис. 2.6, б) вершины v₁и v₅образуют первый уровень иерархии, вершины v₄и v₆- второй уровень иерархии, вершина v₃- третий и последний уровень иерархии.Листьями данного ориентированного дерева являются вершины v₃и v₆.

в) г)

Если (y,x) – последнее ребро на пути из корня вx, тоyназываетсяродителем(parent)x, аxназываетсяребёнком(child)y. Корень является единственной вершиной, у которой нет родителя. Вершины, имеющие общего родителя, называютбратьями. Вершины, имеющие детей, называютсявнутренними. Число детей у вершины корневого дерева называется еёстепенью(degree). Длина пути от корня до произвольной вершиныxназываетсяглубиной(depth) вершиныx. Максимальная глубина вершин дерева называетсявысотой(height) дерева.

Двоичное дерево(binarytree) проще всего определить рекурсивно как конечный набор вершин, который

• либо пуст ( не содержит вершин );

• либо разбит на три непересекающиеся части : вершину, называемую корнем (root), двоичное дерево, называемоелевым поддеревом(leftsubtree) корня, и двоичное дерево, называемоеправым поддеревом(rightsubtree) корня.

Двоичное дерево, не содержащее вершин, называется пустым(empty). Оно иногда обозначаетсяNIL. Изобразимполное двоичное деревовысоты 3.

Глубина 0

Глубина 1

Высота = 3

Глубина 2

Глубина 3

Число внутренних вершин полного k– ичного дерева высотыh равно .

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