Основы теории графов

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

После путешествия по джунглям бесконечных множеств вернемся к множествам конечным.

Началом рассмотрения графов как самостоятельного объекта считается 1736 год, когда Леонард Эйлер поставил задачу о Кенигсбергских мостах. Примерно через 100 лет (в 1847 году) немецкий физик Густав Роберт Кирхгоф (кстати, уроженец Кенигсберга!) применил подобные конструкции к анализу электрических цепей. Примерно в то же время выдающийся ирландский математик Уильям Роуэн Гамильтон придумал игру, которая по существу сводилась к построению цикла в некотором графе (определения см. далее). Во второй половине 19 века она была столь же популярна, как через век кубик Рубика.

Геометрически граф это семейство точек и соединяющих их линий (или стрелок). Формально граф определяется так.

ОПРЕДЕЛЕНИЕ 16. Графом Г называется пара (V, E), где V – конечное множество, E – антирефлексивное бинарное отношение на V. Элементы множества V называются вершинами графа, множества E – дугамиили ребрами графа. Число вершин обычно обозначается через p, число дуг – через q.

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

Если отношение E симметричное, то граф называется неориентированным, в противном случае – ориентированным. В неориентированном графе стрелки не нужны.

Если бинарное отношение на V не является антирефлексивным, то соответствующий объект называется псевдографом. Иногда полезно считать, что некоторые вершины соединяются несколькими дугами. Такой объект называется мультиграфом. Далее мы не используем эти термины.

Вершины a,b Î V называются смежными, если (a,b)Î E или (b,a)Î E, т.е. если эти вершины на картинке соединяются дугой.

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

Вершина a Î V и дуга (a,b)Î E или (b,a)Î E (т.е. если вершина является одним из концов дуги) называются инцидентными.

Граф называется помеченным, если его вершины различимы. Обычно пометки это номера вершин.

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

ОПРЕДЕЛЕНИЕ 17. Графы Г₁=(V ₁, E ₁) и Г₂=(V ₂, E ₂) называются изоморфными, если существует взаимно однозначное соответствие , переводящее дуги в дуги, т.е. такое, что (a,b)Î E ₁ тогда и только тогда, когда (f (a), f (b))Î E ₂.

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

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

Примеры применения изоморфизма – разные изображения графа K _3,3, известная задача о шахматных конях на доске 3´3.

Каждому ориентированному графу сопоставляется единственный (с точностью до изоморфизма) неориентированный граф: геометрически он получается «стиранием» стрелок на дугах, аналитически – симметризацией бинарного отношения E (т.е. добавлением в E пары (j,i), если (i,j)Î E). В то же время, неориентированному графу соответствует множество ориентированных графов.

Введем следующее понятие.

ОПРЕДЕЛЕНИЕ 18. Граф Г₂=(V ₂, E ₂) называется подграфом графа Г₁=(V ₁, E ₁), если . Подграф называется остовным, если , т.е. Г₂ образован из Г₁ удалением некоторых дуг. Подграф называется порожденным, если из условий a,b Î E ₂, (a,b)Î E ₁ следует, что (a,b)Î E ₂. Это означает, что Г₂ образован из Г₁ удалением некоторых вершин и инцидентных им дуг.

Примеры неориентированных графов.

1. Полный граф K_p.

2. Вполне несвязный граф .

3. Цикл.

4. Цепь.

5. Полный двудольный граф K_m,n.

ОПРЕДЕЛЕНИЕ 19. Степенью вершины неориентированного графа называется число дуг графа, ей инцидентных. Обозначение: deg(a). Для вершины ориентированного графа определены полустепени выхода и входа deg^-(a) и deg⁺(a)–числа дуг соответственно начинающихся и заканчивающихся вершиной a.

Следующее утверждение очень простое, но полезное.

ПРЕДЛОЖЕНИЕ. В неориентированном графе . Здесь, как и выше, p – число вершин, q – число дуг графа.

В ориентированном графе .

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

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

Существует множество красивых и полезных конструкций, которые по данным графам позволяют строить новые графы (сумма, произведение, объединение и т.д.). Приведем две такие конструкции.

ОПРЕДЕЛЕНИЕ 20. Пусть Г – неориентированный граф. Смежным (или реберным)графом называется граф, вершины которого взаимно однозначно сопоставлены ребрам Г, причем они смежные тогда и только тогда, когда смежными являются соответствующие ребра Г.

Еще одна полезная конструкция.

ОПРЕДЕЛЕНИЕ 21. Пусть Г – неориентированный граф. Дополнительным графом называется граф с теми же вершинами, в котором вершины являются смежными тогда и только тогда, когда они не смежные в Г.