Основные понятия теории графов

Основные понятия теории графов. Определение. Множество Х и набор U неупорядоченных пар объектов из Х называется графом Г. Объекты множества Х называются вершинами графа, а наборы объекта U - ребрами графа.

Про ребра будем говорить, что они соединяют вершины и. В случае, если множество Х и набор U состоят из конечного числа объектов и пар, то граф Г называется конечным.

Пусть и - произвольные вершины графа Г. Определение.

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

Определение.

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

Определение. Граф Г называется подграфом Г, если его вершины и ребра принадлежат графу Г. Длиной пути в графе называют сумму длин входящих в этот путь ребер. Определение. Деревом называется конечный связный граф с выделенной вершиной, именуемой корнем, не содержащий циклов. Если в графе можно выделить более одного дерева, которые не связны между собой, то такой граф называют лесом. Рис 2. Лес, имеющий две компоненты связности 2 дерева. Будем далее обозначать через Х - множество вершин и U - множество ребер графа, а сам граф, определяемый этой парой объектов, будем обозначать X,U x X, u U. Обозначим длину дуги u x, y через d u. Кратчайшую длину пути из х в z обозначим D x, z. Очевидно, если кратчайший путь из x в z существует и проходит через промежуточную вершину w, то D x, z D x, w D w, z. Эта формула справедлива для любой промежуточной вершины w рассматриваемого пути, в том числе и для последней, смежной с конечной вершиной w. Поэтому кратчайший путь можно отыскать, последовательно переходя от конечной вершины z в ближайшую смежную и запоминая цепочку построенных вершин конечно, при условии, что хотя бы один путь между вершинами x и z существует и граф не содержит циклов.

Эта идея и является в сущности принципом Р.Беллмана. 2.