Материал: Ответы на экзаменационные вопросы по дискретной математике

Рисунок 6. Мультиграф

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

По лемме 1 в этом графе есть контур (степень всех вершин больше или равна 2). Если он содержит все рёбра графа, то эйлеров цикл найден (!). Если же этот контур содержит не все рёбра, то удалим все его рёбра из графа. Получим новый граф. Новый граф распадается на компоненты связности, каждая из которых должна иметь общую вершину с удалённым контуром (иначе первоначальный граф не был бы связным), причём степени всех вершин каждой компоненты чётны и число вершин в ней строго меньше , то есть по индуктивному предположению каждая компонента имеет эйлеров цикл. Теперь мы можем построить эйлеров цикл в данном графе следующим образом. Обходим последовательно рёбра удалённого контура. Далее, если мы пришли в вершину, общую для контура и какой-то компоненты связности, то обходим по эйлерову циклу эту компоненту (то есть присоединяем к контуру этот цикл) и идём по этому контуру дальше. Тем самым все рёбра будут пройдены, и каждое ровно один раз. Всё это схематично изображено на следующем рисунке: сначала начинаем обходить контур ; пройдя ребро , проходим «верхний» граф, затем возвращаемся в точку и далее идём по ребру , обходим «правый» граф и так далее. Утверждение Б доказано.

Рисунок 7

В) Необходимость. Пусть граф полуэйлеров. Это значит, что он имеет эйлеров путь, начинающийся в одной вершине и заканчивающийся в другой. Очевидно, что обе эти вершины должны иметь нечётную степень, а степени остальных чётны.

Г) Достаточность. Пусть граф имеет ровно две вершины нечётной степени и . Возможны 2 случая: эти вершины не связаны ребром или связаны. В первом случае, добавляя ребро , получаем граф, все вершины которого чётной степени, следовательно, он имеет эйлеров цикл (по предыдущим доказанным утверждениям) и, удаляя из него это ребро , получаем эйлеров путь. Во втором случае удалим ребро. Получим новый граф. Если он имеет 2 компоненты связности, то пройдём одну из них по эйлерову циклу, начиная и заканчивая в вершине, которая в первоначальном графе имела нечётную степень. Затем добавим удалённое ребро (мост), пройдём его — попадём в другую вершину, которая ранее имела нечётную степень, и пройдём вторую компоненту связности по эйлерову циклу. Во всех разобранных случаях получим эйлеров путь, который начался в одной из вершин с нечётной степенью и закончился в другой.

Теорема доказана.

Примечание. Если граф (или мультиграф без петель) содержит вершин нечётной степени, то его можно разбить на полуэйлеровых графов (то есть нарисовать росчерками пера). Доказательство аналогично доказательству теоремы Эйлера.

Имеется простой алгоритм (так называемый алгоритм Флери) для нахождения эйлерова цикла (конечно, если этот цикл существует), который состоит в следующем: начинаем с любой вершины и «стираем» пройденные ребра (удаляем также изолированные вершины, которые при этом образуются. При этом по мосту (перешейку) проходим только в случае, когда нет других возможностей.

Рисунок 8. Рёбра пронумерованы в порядке их прохождения. Эйлеров цикл: .

Очевидно, что для того, чтобы построить эйлеров путь достаточно использовать алгоритм Флери, который надо начать с вершины, имеющей нечётную степень.

Рассмотрим некоторые приложения теоремы Эйлера, которые в основном связаны с так называемой задачей китайского почтальона.

Пусть имеется некоторый связный граф, рёбрам которого приписаны некоторые числа, называемые весами рёбер. Требуется найти такой цикл, при котором каждое ребро проходится по крайней мере один раз и суммарный вес всех рёбер, вошедших в цикл, минимален. Заметим, что если граф является эйлеровым, то любой эйлеров цикл решает поставленную задачу (для эйлерова графа веса роли не играют).

Эта задача имеет много приложений, например, поливка улиц одной машиной (здесь ребра графа — дороги, а перекрёстки — вершины; веса — это длины дорог), а также сбор мусора, доставка почты или даже наилучший маршрут для осмотра музея или уборка помещений и коридоров в больших учреждениях.

Заметим, что имеется алгоритм решения задачи китайского почтальона, но он требует достаточно длительного описания.

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

Далее изображены гамильтонов, полугамильтонов и не гамильтонов графы.

Рисунок 9

Несмотря на сходство постановки задач для гамильтоновых графов с эйлеровыми, «хорошего» решения для гамильтоновых графов нет. Вообще, о гамильтоновых графах известно очень мало. В основном — это теоремы типа «если в графе достаточное число рёбер, то он гамильтонов». Ясно, что теоремы такого типа не могут дать критерия гамильтонова графа, поскольку в графах такого типа вершин может быть очень много, а рёбер сравнительно мало.

Приведём без доказательства самую известную теорему.

Теорема (Дирак, 1952). Если в связном графе с вершинами степени всех вершин больше или равны , то граф гамильтонов.

Матрицы

Рисунок 10. Неориентированный мультиграф

Трудно переоценить роль матриц в теории графов. Перечислим наиболее известные.

Матрица смежности. Это квадратная матрица порядка ( — число вершин), в которой нули стоят по главной диагонали (если в графе нет петель, а если петли есть в вершине (и число этих петель равно ), то на главной диагонали в строчке с номером стоит число ). Если вершина связана с вершиной одним ребром, то элемент матрицы смежности равен 1, если эти вершины связаны рёбрами, то . Аналогичным образом строятся матрицы смежности для орграфов и для мультиграфов.

Для предыдущего рисунка матрица смежности такая:

Теорема. Если матрица смежности графа с вершинами есть , то элемент матрицы равен числу маршрутов длины из вершины с номером в вершину с номером (под длиной маршрута понимается число рёбер в этом маршруте).

Доказательство. По правилу перемножения матриц:

Для обычного графа каждый элемент матрицы смежности равен или 0, или 1. Значит, в написанной сумме каждое слагаемое равно или 0, или 1, причём оно равно 1 тогда и только тогда, когда все множители равны 1. Но в этом случае индексы у множителей указывают некоторый путь из -й вершины в -ю, а тогда сумма всех этих единиц равна числу маршрутов из -й вершины в -ю, и теорема доказана. Для мультиграфов доказательство аналогично.

Замечание. В частности, матрица составлена из целых чисел , которые равны числу маршрутов длины 2, соединяющих вершины и . Аналогично составлена из чисел , равных числу маршрутов длины 3 (то есть маршрутов из трёх рёбер) из вершины в вершину и так далее.

Матрица инцидентности. Это матрица размера , где — число вершин, а — число рёбер графа, при этом её элементы равны 1, если вершина с номером инцидентна ребру с номером (если ребро неориентированное), или является начальной (для ориентированного ребра). Заметим, что матрица инцидентности сравнительно редко используется, так как в современных условиях (где число рёбер часто очень велико) она имеет слишком большое число столбцов.

Для предыдущего рисунка матрица инцидентности такая:

Структурная матрица. Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица — это символьная матрица порядка (размера ), где — число вершин графа, причём её элементы — символьные обозначения рёбер. На главной диагонали стоят 1, то есть . Если при вершины и соединены ребром , то элемент , при — отрицание , которое обычно отмечается чертой наверху: . Если же ребра из вершины с номером в вершину с номером нет, то . Структурная матрица может составляться и для орграфа, и для мультиграфа без петель (здесь если два ребра и соединяют две вершины, то соответствующий элемент при равен , а при этот элемент равен .

Для предыдущего рисунка структурная матрица такая:

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

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

Для предыдущего рисунка нахождение всех простых путей из (1) в (4):

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

Понятно, что раскрытие минора методами булевой алгебры предусматривает, что верны следующие соотношения: , (это свойство нужно, для того чтобы не проходить по одному ребру дважды в противоположных направлениях), а также используется правило простого поглощения: . Видно, что если не использовать правило поглощения, то получим все маршруты (без повторения рёбер), связывающие вершины и .