Основные понятия и определения

Чтобы составить наглядное представление о графе, достаточно вообразить некоторое множество точек плоскости или пространства и множество отрезков, соединяющих все или некоторые из этих точек.

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

Граф, образованный ребрами называют неориентированными (рис. 1).

Граф, состоящий из дуг, называют ориентированными (орграфом)(рис.2).

Рассматриваются и смешанные графы – графы, состоящие из ребер и дуг ( рис. 3 ).

Рис. 3. Смешанный граф.

Формально граф G определяется заданием двух множеств X и U, где X – множество вершин, U – множество дуг ( ребер ), т.е. G = ( X, U ).

Для неориентированного графа ( рис. 1 ) множество вершин X и ребер U можно записать так

Для ориентированного графа ( рис. 2 ) множества вершин и дуг записываются следующим образом

или

.

Ребро, начало и конец которого совпадают, называется петлей ( рис.4 ).

Рис. 4. Несвязный неориентированный граф

Вершины называются смежными, или соседними, если существует ребро, их соединяющее

.

Вершины несмежные ( рис. 4 ).

Два ребра называются смежными, если они имеют общую вершину, например, ребра имеют общую вершину ( рис. 1 ).

Ребро называется инцидентным вершине , если оно выходит или входит в вершину.

Степенью вершины называют число инцидентных ей ребер ( дуг ). Степень вершины обозначают: . Например ( рис. 4 ), , поскольку ребро учитывается дважды.

Вершина, степень которой равна нулю, называется изолированной, например .

Вершина, степень которой равна единице, называется висячей или тупиковой, .

Теорема 1.В графе G = ( X, U ) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа, т.е.

,

где n = - число вершин, m = - число ребер графа.

Вершина называется четной ( нечетной ), если ее степень четное ( нечетное ) число.

Теорема 2.Число нечетных вершин любого графа – четно.

Кратностьюпары вершинназывается число соединяющих их ребер или дуг. Например, на рис. 5 ребро имеет кратность равную 3, а ребро - красность, равную 2.

Рис.5

Дугиорграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления. Например, на рис. 6 кратны дуги

.

Рис. 6.

Для орграфа степень входа вершины обозначают , а степень выхода - .

Маршрутом называют последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего. Число ребер в маршруте определяет его длину.

Например, -маршрут, длина которого равна 6 ( рис. 4 ).

Цепью называется маршрут, в котором все ребра попарно различны. Например, -цепь, длина которой равна 4 ( рис. 4 ).

Простой называется цепь, в которой все вершины попарно различны. Например, ( рис. 4 ).

Граф называется связным, если для любых двух его вершин существует цепь, соединяющая эти вершины ( рис. 7 ) и несвязными, если есть хотя бы одна вершина, для которой такой цепи нет ( рис. 4, вершина ).

Рис. 7. Связный граф

Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины.

Диаметромграфа называется максимальное расстояние между его вершинами.

Циклом( простым циклом ) называется цепь ( простая цепь ) начало и коней которой совпадают. Например, последовательность образует цикл ( рис. 4 ).

Подграфомграфа G называется граф с множеством вершин и множеством ребер , такой, что . Например, для графа ( рис. 4 ) подграфом может быть

где = ,а

= .

Подграф называется собственным, если он отличен от самого графа.

Компонентов связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа. Например, граф G ( рис.4 ) имеет две компоненты связности.

Точкой сочленения называется вершина графа, удаление которой повышает число компонент связности. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей ребер.Например, точкой сочленения является вершина ( рис. 4 ), удаление которой приводит к появлению третьей компоненты связности.

Граф G называется полным, если любые две его вершины соединены ребром ( рис. 7 ). Таким образом, полный граф определяется только своими вершинами.

Пусть число вершин полного графа равно n. Тогда степень любой вершины равны ,а число ребер равно числу сочетаний из n по 2, т.е.

Число ребер, согласно теореме 1, равно

Теорема 3.Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную 2.

Ребро связного графа G называется мостом, если после его удаления G станет несвязным и распадается на два связных графа . Например, для связного графа мостами являются ребра и ( рис. 8 ).

Рис. 8

Теорема 4.Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

Поскольку вершины графа можно располагать по своему усмотрению и произвольно выбирать форму линий, их соединяющих, то один и тот же граф можно изобразить по – разному. В этом случае проявляется изоморфизм графа ( рис. 9 ) . Иными

Рис. 9. Изоморфизм графов

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