Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Определение. Множество 2Л = {«!,...Ли набор 91 неупорядоченных пар объектов а^ из 591 называ-
ется графом Г. Объекты множества 591 называются вершинами графа, а объекты набора 91 — ребрами графа. Про ребра (аи аЛ будем говорить,, что они соединяют вершины И О).
Пример 1. Пусть ЗЛ = {й1, а2, а3, я4) аъ, яя, я7), 91 — “{(«I, а2), (а2, а2), («ч, а5), (а5, аЙ), (а&, я6), (я*, я7), (й5, й7) }. Тогда 591 и 91 определяют граф.
В случае, если множество 501 и набор 91 состоят из конечного числа объектов и пар, то граф Г называется конечным,
ГЛ. 1. ГРАФЫ
223
Пусть а{ и а} — произвольные вершины графа Г.
Определеиие. Система ребер графа Г
^ага} = 1(Я*1’ й*а)’ (а*2’ й*з)’ * • й*в)Ь
где — яч и ач — а^, называется путем, соединяющим вершины а і и а}. Для любого ребра, принадлежащего пути мы будем говорить, что путь Л0.^ проходит через это ребро. Аналогично, если вершина а принадлежит некоторому ребру пути то говорим, что путь Аа{В.
проходит через вершину а.
Определение. Путь А{0^, не проходящий дважды через одно ребро, называется циклом, если а і = Щ. В частности, цикл {(щ, «і)} будем называть петлей.
Определение. Граф Г называется связным, если для любых двух различных вершин щ и а} графа Г существует путь, соединяющий эти вершины.
Легко видеть, что граф из примера 1 является конечным, несвязным и содержащим петли. (Ясно, что связный граф не содержит «изолированных» вершин, т. е. каждая его вершина принадлежит но крайней мере одному его ребру.)
Введенное нами понятие графа является весьма абстрактным. Оно родственно понятию одномерного комплекса в топологии. Для последующих рассмотрений желательно иметь какую-либо наглядную интерпретацию графа. С этой целью будем рассматривать в евклидовом пространстве фигуры определенного вида. Каждая из таких фигур 3 состоит из различных вершин Ь±, Ьг, ... и кривых (являющихся либо дугами окружностей, либо отрезками прямых), каждая из которых соединяет некоторые пары вершин {Ъц Ъз) (возможно и вырождение = Мы предполагаем, что никакая внутренняя точка кривой, принадлежащей фигуре 2, не является вершиной или внутренней точкой другой кривой.
Определение. Фигура 2 называется геометрической реализацией графа Г, если существует взаимно однозначное соответствие между вершинами фигуры & и вершинами графа Г, а также между кривыми фигуры г и ребрами графа Г такое, что если (ЪП{, Ъп-) {а{, а^)(
то а-і, Ъп.} ?*-+аГ (Соответствующие кривые и ребра
соединяют соответствующие вершины.)
224
Ч. III. ГРАФЫ И СЕТИ
Пример 2. Фигура 2 на рис. 1, как нетрудно убедиться, является геометрической реализацией графа Г из примера 1.
Спрашивается, любой ли граф Г можно реализовать в евклидовом пространстве? Если этот вопрос решается
положительно, то интересно знать, существует ли такое число р, чт$ всякий граф допускает реализацию в евклидовом пространстве размерности р? В последнем случае желательно знать минимальное значение р. Ответ на все эти вопросы для случая конечных графов дают теорема 1 и пример 3. Теорема 1 представляет некоторую перефра-вировку известной теоремы из топологии.
Теорема 1. Каждый конечный граф Г можно реализовать в трехмерном евклидовом пространстве.
Доказательство. Пусть граф Г содержит m вершин и h ребер. Возьмем прямую и через нее проведем связку из h плоскостей. На прямой выберем m точек bi, b2, ..., bm) сопоставим их вершинам графа соответственно Qi, а2, ..., ат. Каждому ребру графа Г поставим в соответствие ПЛОСКОСТЬ ИЗ пучка. Пусть (fff, ?j) — ребро графа Г. В плоскости, соответствующей ребру (я,, а;), соединим вершины bi И bj дугой окружности. Выполним такое построение для всех ребер графа Г, получим фигуру 2. Очевидно, что 2 является геометрической реализации й графа Г.
Можно показать, что данная теорема не допускает, усиления в направлении понижения размерности евклидова пространства, в котором может быть реализован любой граф.
II р и мер 3. На рис. 2 изображены два графа. Первый из лих связан с решением известной задачи о трех домах и трех колодцах*). Второй — полный**) граф с пятью
*) Задача о трех домах и трех колодцах состоит в следующем; требуется ог каждого дома проложить тропинку к каждому колидцу и так, чтобы тропинки не пересекались друг с другом.
**) То есть граф, содержащий все ребра вида [аj, а$), 1 ^ ? <
* ч. / М|
Рис. 1 '
вершинами. В топологии доказывается, что данные графы не допускают реализации на плоскости. Доказательства этих фактов мы не приводим.
Интересный результат, выясняющий условия плоской реализуемости, был получен Л. С. Понтрягиным [28] п
независимо, но позже Куратовским. Ниже (теорема 2) приводится без доказательства формулировка этого факта.
Определение. Графы Г и Г' называются изоморф-ными, если существует взаимно однозначное соответствие между их вершинами и ребрами и такое, что соответствующие ребра соединяют соответствующие вершины.
С точки зрснпя этого понятия абстрактный граф и его геометрическая реализация являются пзоморфнымп графами. В силу теоремы 1 вместо абстрактных конечных графов можно рассматривать их реализации. Другими словами, с графами можно обращаться как с геометрическими объектами.
