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

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

1.1.1. История теории графов

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

1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 3.1). Эта задача была решена Эйлером в 1736 году.

Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Про­вести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 3.2). Эта задача была решена Куратовским в 1930 году.

Рис. 3.2. Иллюстрация к задаче о трех домах и трех колодцах

Рекомендуемые материалы

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

1.1.2. Определения

Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов множества V (Е - множество ребер).

G(V,E): ,    EVxV.

Число вершин графа G обозначим р, а число ребер – q.

р(G) = |V|    q(G) = |E|.

Часто рассматриваются следующие родственные графам объекты.

1.  Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).

2.  Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф назы­вается графом с петлями (или псевдографом).

3.  Если Е является не множеством, а набором, содержащим несколько одинако­вых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мультиграфом.

Далее выражение: граф G(V,E) означает неориентированный граф без петель и кратных ребер.

Обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями.

Примеры.

1. . .

Т.о. это неориентированный граф с петлей и кратными ребрами.

Рис. 3.3. Неориентированный граф с петлей и кратными ребрами.

2. . .

Т.о. это ориентированный граф с петлей и кратными ребрами.

Рис. 3.4. Ориентированный граф с петлей и кратными ребрами.

3. . , т.о.

Рис. 3.5. Неориентированный граф с петлей.

1.1.3. Смежность и инцидентность

Пусть v₁, v₂ - вершины, е = (v₁, v₂) - соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .

Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.

Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4  - висячие.

Пример. Для графа, изображенного на рис. 3.3.

Ребро e₁ инцидентно вершинам v₁ и v₂. Вершина v₁ инцидентна ребрам e₁ и e₂. Ребра e₁ и e₂ – смежны. Вершины v₁ и v₂ – смежны.

  . p(G)=3, q(G)=5.

Т.о. можно заметить, что .

Теорема Эйлера: .

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

1.1.4. Изоморфизм графов

Говорят,   что  два   графа   G₁(V₁,E₁)   и   G₂(V₂,E₂)   изоморфны   (обозначается G₁~ G₂), если существует биекция h: V₁ V₂, сохраняющая смежность.

Графы рассматриваются с точностью до изоморфизма.

Пример

Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграм­мами одного и того же графа К_3,3.

Бесплатная лекция: "1.6 Моделирование как метод системного анализа" также доступна.

Рис. 3.6. Диаграммы изоморфных графов

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) - инварианты графа G.

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

Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами