Маршрут графа. Цепь. Цикл. Простой, сложный и элементарный циклы.

Лекция 1. Элементы графа.  

Элементы графа: висячая или концевая и изолированная вершины.

Определение. Степенью или валентностью вершины p_n графа Г, обозначаемой через d_n , называют число рёбер (дуг), инцидентных этой вершине. Вершина степени 1 называется висячей или концевой. Ребро, инцидентное висячей вершине, называется висячим. Вершина степени 0 называется изолированной.

По определению петля при вершине p_n, добавляет 2 в степень соответствующей вершины.

Рис. 1.1

Сумма степеней вершин графа. В графе Г на рис. 1.1 видно, что сумма степеней вершин графа равна 16 и равна удвоенному числу рёбер 8. Таким образом, сумма степеней вершин графа Г равна удвоенному числу рёбер графа Г и, следовательно, является чётным числом. Пусть граф Г (без петель и изолированных точек) имеет N вершин и M рёбер. Поскольку каждое ребро инцидентно двум вершинам, оно добавляет двойку к сумме степеней вершин графа, поэтому сумма

           Если граф имеет петли и изолированные точки, формула также справедлива, так как изолированная точка добавляет 0 к сумме степеней вершин графа, а петля добавляет двойку.

Число вершин нечётной степени. Лемма о рукопожатиях.

    Более того, можно показать, что число нечётных вершин, т.е. вершин нечётной степени, также чётно. Действительно,

 Итак: число вершин нечётной степени всегда чётно.

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

 Лемма утверждает, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно чётно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях).

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

Примерами однородных графов являются куб и тетраэдр.

Маршрут графа. Цепь. Цикл. Простой, сложный и элементарный циклы.

Определение.  Маршрут в графе Г представляет собой конечную последовательность чередующихся вершин и рёбер.

Определение.  Маршрут называется открытым, если его концевые вершины различны, в противном случае он называется замкнутым.

Определение. Маршрут называется цепью, если все его рёбра различны.

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

 Замкнутый маршрут образует цикл.

Определение. Цикл может быть простым, если он содержит отличные друг от друга рёбра, сложным – в противном случае, элементарным, если при обходе по какому-нибудь направлению каждая вершина цикла встречается только один раз.

    Понятия “простая цепь” или “простой цикл” означают отсутствие повторяющихся рёбер.