Тема 13.1. Основные определения теории графов

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

Определение: Если две вершины соединены направленным отрезком, то пара называется упорядоченной, а отрезок называется ребром графа. Если вершины соединены ненаправленным отрезком, то вершины называются неупорядоченными, отрезок, их соединяющий, называется дугой.

Определение: Граф, содержащий только рёбра, называется ориентированным.

Определение: Граф, содержащий только дуги, называется неориентированным.

Определение: Пара вершин может соединяться двумя или более рёбрами одного направления, такие рёбра называются кратными.

Определение: Дуга или ребро может начинаться или заканчиваться в одной вершине, такие дуги называются петлями. Считается, что длина петли равна 1.

Определение: Вершины, соединённые ребром или дугой называются смежными.

Определение: Дуги, имеющие общие вершины называются смежными.

Определение: Ребро и любая из двух её вершин называется инцидентными.

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

Определение: Частичным графом графа называется граф, содержащий все вершины графа и только часть дуг графа.

Пример 13.1: Пусть граф – карта шоссейных дорог России, тогда карта шоссейных дорог Приморья – подграф, а карта главных дорог России – частичный граф.

Определение: Путём в графе называется такая последовательность дуг, в которой конец каждой предыдущей дуги является началом следующей дуги.

Определение: Длиной пути называется число , равное числу дуг, составляющих путь.

Путь может быть конечным и бесконечным. В случае бесконечного пути полагаем .

Определение: Путь, в котором ни одна дуга не встречается дважды, называется простым.

Определение: Путь, в котором ни одна вершина не встречается дважды, называется элементарным.

Определение: Контур – это конечный путь, у которого начальная и конечная вершина совпадают. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной вершины).

Для неориентированного графа аналогичными понятиями являются понятия цепи и цикла. С понятием неориентированного графа связано понятие связности графа.

Определение: Граф связен, если любые две его вершины можно соединить цепью.

Определение: Если граф не связен, то его можно разбить на такие подграфы, что все вершины в каждом подграфе связны, а вершины из различных подграфов не связны. Такие подграфы называются компонентами связности графа.

Для того чтобы определить связность ориентированного графа, не нужно обращать внимание на ориентацию дуг. Для ориентированного графа существует понятие сильной связности.

Определение: Ориентированный граф сильно связен, если для любых вершин и существует путь, идущий из в .

Определение: Степенью вершины графа называется число рёбер, инцидентных этой вершине.

Теорема: Если граф без петель имеет вершин и дуг, то сумма степеней всех вершин .

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

Определение: Граф, у которого все вершины имеют одинаковые степени (равные ), называется регулярным (степени ).

В полном графе нет петель, и каждая пара вершин соединена в точности одним ребром.

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

Граф дополнительный к полному, состоит из изолированных вершин. Такой граф называется пустым, или вырожденным.

Дата добавления: 2015-10-28