Граф задаётся парой множеств: множества Е, называемого множеством вершин, и множества 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 1, u 2, ¼, u n), в которой каждые два соседних ребра имеют общую вершину, т.е. u 1 = (е 1, е 2); u2= (е 2, е 3); ... u n = (еn, еn+ 1). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.
Две вершины еi и еj называются связанными, если существует маршрут из еi в еj.
Простой цепью,или простым путём, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путём называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, граф, представленный на рисунке 3.4, имеет цикл S =(1, 2,3, 5, 4, 1).
Рис. 3.4. Пример графа, имеющего цикл
Цикл, проходящий по всем рёбрам графа только один раз, называется эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин чётные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.
Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путём. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня.
Теория графов используется в информатике и программировании, например, для представления структур данных (деревья), для моделирования сетей (маршрутизации данных в Интернете). В теории алгоритмов, блок-схема алгоритма − это ориентированный граф, указывающий порядок исполнения команд. Вершины такого графа могут быть одного из трёх типов, представленных в таблице 11.
Таблица 11
