Теория графов

Граф - это конечная совокупность вершин, некоторые из которых соединены ребрами. Мы будем рассматривать только такие графы, у которых две вершины могут быть соединены только одним ребром. Иногда возникает необходимость рассматривать конфигурации, когда пара вершин соединена несколькими ребрами, - в этом случае говорят, что задан мультиграф, а ребра, соединяющие одну и ту же пару вершин, называют кратными. Ребро не обязано соединять разные вершины. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.

Две различные вершины графа, соединенные ребром, называют смежными. Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, ребро выходит из вершины дважды. Степень вершины а будем обозначать ¥(а).

Первое свойство, которое мы сформулируем, таково:

Сумма степеней всех вершин графа равна удвоенному числу его ребер.

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

Из этого свойства есть следствие, которое принято называть леммой о рукопожатиях. Вот формулировка этой леммы:

Для любого графа количество вершин нечетной степени всегда четно.

Леммой о рукопожатиях это утверждение называют из-за следующей интерпретации:

В любой момент времени количество людей, сделавших нечетное число рукопожатий, четно.

Действительно, если вершина графа - это люди, а ребра - это рукопожатия, то видно, одно и то же утверждение о получившемся графе. Вот еще одно свойство:

В любом графе есть по крайне мере две вершины, имеющие одинаковую степень.

Докажем это свойство. Пусть в графе n вершин. Степень каждой вершины может иметь значение от 0 до n-1. Если степени всех вершин различны, то каждое из указанных значений должно реализоваться ровно для одной вершины. Рассмотрим вершины степени 0 и степени n-1. Степень 0 означает, что эта вершина не соединен ни с какой другой; степень n-1 означает, что эта вершина соединен со всеми другими вершинами. Но одновременно так быть не может. Свойство доказано.

Маршрутом на графе называется последовательность ребер е₁, е₂, … , е_к, в которой конец одного ребра служит началом следующего. Если при этом конец ребра последовательности совпал с началом первого ребра, то маршрут называется циклическим. Для графа, изображенного на рисунке 1.1, последовательности е₁, е₂, е₄, е₅, е₂, е₃ и е₂, е₄, е₅является маршрутами, причем второй из них циклический. А последовательности е₁, е₂, е₅маршрутом не является.

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

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

Вершины a и b называют связанными, если существует цепь, начинающаяся в вершине a и заканчивающаяся в вершине b. Договариваются так же считать, что каждая вершина связана сама с собой. Граф называется связным, если любые две его вершины связаны. Если же граф несвязен, то в нем можно выделить так называемые связные компоненты, т.е. такие множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом. Но вершины из разных множеств уже не связаны.

Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 1.2 на самом деле тот же что и на рисунке 1.1.