1. Основные понятия теории графов
Основным объектом этой теории является граф. Наглядно граф можно представить как некоторое множество точек плоскости или пространства и множество отрезков кривых или прямых линий, соединяющих все или некоторые из этих точек. Формально граф G определяется заданием двух множеств X и U и обозначается G=(XU). Элементы xB1B, xB2B, …, xBn B множества X называются вершинами и изображаются точками. Элементами uB1B, uB2B, …, uBm множества U являются пары связанных между собой элементов множества X и изображаются отрезками. Взаимное расположение, форма и длины отрезков значения не имеют. Если в паре вершин xBi Bи B BxBj Bуказано направление связи, то есть указано, какая вершина является первой, то отрезок UB1 Bназывается дугой, а если ориентация не указана, - ребром.
Если в графе G все элементы множества U изображаются дугами, то граф называется ориентированным (орграф), если ребрами, - неориентированным.
На практике используются графы, в которых множества X и U состоят из конечного числа элементов, то есть конечные графы. На рисунке располагать вершины графа можно произвольно. Также произвольно выбирается и форма соединяющих их линий. Поэтому один и тот же граф (граф с одной и той же информацией) может быть представлен в различных видах. Такие графы называются изоморфными.
Смежными называют вершины графа, если они различны и существует дуга (ребро), которая соединяет эти вершины. Если две дуги (ребра) имеют общую концевую вершину, то такие дуги (ребра) смежные.
Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей, называется путем в орграфе. Путь, проходящий через все вершины и при этом только один раз, называется гамильтоновым. Путь, включающий все дуги графа, и при этом только по одному разу, называется эйлеровым. Полным путем называют любую непрерывную последовательность вершин и дуг, идущих от начальной вершины к конечной. Конечный путь, у которого начальная вершина совпадает с конечной, называется контуром.
Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным.
В экономике чаще всего используются два вида графов: дерево и сеть.
Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.
Если граф, вообще говоря, не связный, не содержит циклов, то каждая связная его часть будет деревом. Такой граф называется лесом.
В приложении теории графов к практическим задачам дугам (ребрам) графа сопоставляют какие-то числовые характеристики. Например, пропускная способность транспортной магистрали, запас какого-либо ресурса, продолжительность выполнения какой-либо работы и т.д. Таким образом, дугам графа приписаны определенные веса и граф G называется взвешенным.