Основные понятия .

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

При решении многих задач, не существенно связаны ли точки отрезками или криволинейными дугами. Важно лишь то, что каждая линия соединяет какие- либо две из заданного набора точек.

При рассмотрении задач теории графов ограничиваются исследованием совокупности двух конечных множеств V и Х. Элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

Сформулируем определение неориентированного графа:

Непустое множество V = {v₁, v₂,…,v_n} и набор Х пар объектов {v_i, v_i+1}, где v_iV, v_i+1V, называется графом.

Т.к. V и Х конечные множества, то граф называется конечным.

Если пара упорядоченная (v_i, v_i+1), граф называется ориентированным и обозначается D(V,X).

Если пара неупорядоченная {v_i, v_i+1}, то граф называется неориентированным и обозначается G(V,X).

Рассмотрим сначала неориентированные графы.

Как было сказано выше граф изображается диаграммой на плоскости. Приведем пример:

Рис. 13.1

В данном графе есть пара с одинаковыми вершинами {v₃, v₃}. Ребро соответствующее такой паре называется петлей.

Граф также содержит одинаковые пары {v₆, v₅}. Такие пары называются кратными ребрами. Количество одинаковых пар, соответствующих вершинам v_i и v_i+1 называется кратностью ребра. В приведенном примере кратность ребра {v₆, v₅} равна двум.

Граф, содержащий кратные ребра и петли называется псевдографом (рисунок 13.1).

Псевдограф без петель называется мультиграфом (рисунок 13.2).

Мультиграф без кратных ребер называется простым графом (13.3).

Рис. 13.2. Мультиграф. Рис. 13.3. Граф.

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

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