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

Граф задаётся парой множеств: множества Е, называемого множеством вершин, и множества U, называемого множеством рёбер. Ребро u Î U есть пара (е_i, е_j), где е_i, е_j Î Е , указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро u Î U инцидентно вершинам е_i, е_j. Если порядок рёбер не имеет значения, т.е. u =(е_i, е_j) =(е_j, е_i), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро u = (е_i, е_j) называется ориентированным ребром или дугой. Вершина е_i называется началом дуги, е_j – конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом.

Граф G (E, U) называется конечным, если множество Е вершин конечно.

Граф G (E, U), у которого каждая вершина е_i Î Е соединена рёбрами с остальными вершинами (любые две вершены соединены ребром), называется полным (рис. 3.2).

Рис. 3.2. Полный граф

Если хотя бы две вершины соединены несколькими рёбрами, то такой граф называется мультиграфом. Две вершины е_i, е_j Î Е называются смежными, если они соединены ребром. Число рёбер, инцидентных данной вершине е_j, называется локальной степенью этой вершины р(е_i). Число рёбер r графа G(E,U) определяется выражением.

где n – количество вершин в графе.

Рассмотрим граф, изображённый на рисунке 3.3.

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

Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество рёбер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Ребро (5, 3) является ориентированным ребром или дугой. Число рёбер в графе определяется по значению локальных степеней для каждой вершины:

р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2; р = (3 + 2 + 3 + 2 + 2) / 2 = 6.

Важным в теории графов является понятие части графа G(E,U), который обозначается G'(E',U') Í G(E,U). Множества вершин и ребёр части графа являются подмножествами вершин и рёбер исходного графа Е'Í Е U'Í U. Многие задачи на графах состоят в определении частей графа с заданными свойствами.

Часть графа G'(E',U') Í G(E,U) называется подграфом графа G(E,U), если Е' Í Е, а подмножество U'ÍU образовано только рёбрами, инцидентными вершинам множества Е'.

Маршрутом графа G называется последовательность рёбер S = (u₁, u₂, ¼, u _n), в которой каждые два соседних ребра имеют общую вершину, т.е. u₁ = (е₁, е₂); u₂= (е₂, е₃); ... u _n = (е_n, е_n₊₁). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.

Две вершины е_i и е_j называются связанными, если существует маршрут из е_i в е_j.

Простой цепью,или простым путём, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путём называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, граф, представленный на рисунке 3.4, имеет цикл S =(1, 2,3, 5, 4, 1).

Рис. 3.4. Пример графа, имеющего цикл

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

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

Теория графов используется в информатике и программировании, например, для представления структур данных (деревья), для моделирования сетей (маршрутизации данных в Интернете). В теории алгоритмов, блок-схема алгоритма − это ориентированный граф, указывающий порядок исполнения команд. Вершины такого графа могут быть одного из трёх типов, представленных в таблице 11.

Таблица 11