Глава 2. Теория графов. Лекция № 1. Введение в теорию графов.

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

Определение 1. Граф – это множество вершин Х, множество , где - множество дуг и - множество ребер, и заданное отношение (инцидентности) R между ними. Ребро обычно изображается в виде неориентированной линии, соединяющей вершины, а дуга – в виде ориентированной линии (на дуге, таким образом, задано направление от начала к концу , а на ребре направления нет и вершины и равноправны):

Рис. 1.

V ребро дуга

х₁ . . х₂ х₁ . . х₂

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

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

В графах на рисунке 1 вершины и – смежные, а в графе на рисунке 2 - нет.

Рис. 2.

Определение 3. Мультиграф – граф, две вершины которого соединены более чем одним ребром (или по крайней мере двумя дугами, идущими в одном направлении). Граф, не являющийся мультиграфом будем называть “просто граф” (простым графом).

Рис. 3. Мультиграф

Определение 4. Степень вершины графа равна числу ребер (дуг) инцидентных .

Заметим, что в графе .

Определение 5. Граф называется ориентированным, если он содержит хотя бы одну дугу и не содержит рёбер..

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

Например, графы и – неориентированные, а – ориентированный.

Определение 7. Полустепенью исхода (захода) называется число дуг исходящих из вершины (заходящих в вершину).

Обозначения: – полустепень захода; – полустепень исхода.

.

Рис. 4. Степени и полустепени вершин.

Г₅

V₁ V₂ х₃

х ₁ х₂ V₅

V₃ V₄

х₄

Определение 8. Петля – дуга (ребро), начало и конец которой совпадают.

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

Утверждение 1. Для ориентированного графа без петель справедливы равенства

и .

Доказательство. Для ориентированного графа без петель . Отсюда следует первое равенство. Второе равенство следует из определений.

Утверждение 2. В графе без петель справедливо равенство: , где -число ребер и дуг.

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

Утверждение 2. Для ориентированного графа без петель справедливы равенства

и .

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

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

Определение 11. Вершина называется узлом, если

Определение 12. Граф называется однородным если все степени его вершин одинаковы.

Определение 13. Граф (простой) называется полным если n – число вершин

Рис. 5. Однородный и полный графы.

Однородный граф

Полный граф

Определение 14. Путь в ориентированном графе – это последовательность дуг

в которой начало следующей дуги совпадает с концом предыдущей.

Определение 15. Цепь в неориентированном графе – последовательность ребер

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

Для Г₅ последовательность – путь, а последовательность – не путь.

Рис 6. Цепи в неориентированном графе .

Г6

V₁

x₂ V₂

x₁ V₃ x₃ V₅

V₆ V₄

x₄

Цепи:

Определение 16. Замкнутая цепь (путь)называется циклом (контуром).

Заметим, что цепь является замкнутой, если ее начало совпадает с концом.

В графе цепь – контур; в графе цепь – цикл, а – цикл (но не контур) !

Замечание. Если в ориентированном графе игнорировать ориентацию, то есть заменить все дуги на ребра, то получаем неориентированный граф, в котором определены цепи и циклы.

Определение 17. Путь (цепь) называется простым (простой), если каждая дуга (ребро) встречается в нем (в ней) не более 1 раза.

Определение 18. Путь (цепь) называется элементарным (элементарной), если каждая вершина встречается не более 1 раза.

Для простого графа дугу (ребро) можно записать как (соответственно, ), где – начало и конец дуги ( концы ребра).

В графе путь можно записать в виде