Лекции по дискретке (1021001), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Теорема.

Число протяжённости удовлетворяет неравенству или соответственно для чётного и нечётного .

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

Теорема.

Если – простая цепь из вершины , которую нельзя продолжить за , то лежит на простом цикле, длина которого не меньше чем .

19.Деревья и леса.

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

Деревом называется конечный связный граф без циклов.

Примеры:

Не дерево

Лес из трёх деревьев.

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

Лесом из деревьев называется граф без циклов у которого .

Основная теорема о деревьях.

Для конечного графа следующие 6 утверждений эквивалентны.

1. – дерево, т.е. связный граф без циклов.

2. – не содержит циклов и

3. связен и

4. Связен и каждая его дуга является мостом.

5. Любые две вершины можно соединить, и причём единственной простой цепью.

6. – не содержит циклов, добавление к нему любой дуги приводит к образованию единственного простого цикла.

20.Помеченные графы. Перечисление помеченных деревьев.

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

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

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

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

Замечание.

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

Пример:

изоморфен как помеченный граф, графу и не изоморфен как помеченный графу .

Ясно, что в обычном смысле , , изоморфны.

Задача.

Сколько существует не изоморфных между собой неориентированных помеченных деревьев с вершинами.

Обозначим число неизоморфных помеченных деревьев через . Ясно, что

Теорема Келли.

Свои результат по перечислению деревьев А. Келли успешно применил в жизни для определения количества химических изомеров углеродов C_nH_2n+2.

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

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

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

21.Задача о кратчайшем соединении.

Известны точки, в которых будут расположены населённые пункты (A,B,C,D,E) и известны трасы дорог (I,II,III,IV,V,VI,VII,VIII,IX,X), которые можно построить, а также стоимости из строительства (1,2,3,4,5,6).

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

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

Взвешенным графом будем называть четверку , где — граф, .

Отображение называется весовым отображением.

Если , то называют весом дуги .

Если — путь или цепь на графе , то её весом называют величину: .

Весом графа называют величину .

Аналогично определяется вес подграфа и частичного графа.

Сформулируем задачу о соединении городов на языке теории графов: Дан конечный связный взвешенный граф . Требуется найти связный частичный граф минимального веса.

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

Покрывающим деревом связного графа называется его частичный граф, который является деревом.

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

Теорема.

Решение задачи о соединении городов — покрывающее дерево.

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

Задача о кратчайших путях.

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

1. Какова длина кратчайшего пути, ведущего из одной выделенной вершины к другой? Каков этот путь?

2. Каковы длины кратчайших путей от выделенной вершины до всех остальных вершин графа? Каковы эти пути?

Задачи 1) и 2) очень похожи, и решение задачи 1) получается в результате прерывания в нужном месте решения задачи 2).

Решение поставленных задач даёт алгоритм Дейкстры – один из первых известных динамических алгоритмов.

22.Эйлеровы цепи, критерий Эйлеровости.

Задача о Кёнигсбергских мостах.

Семь мостов города Кёнигсберг расположены на реке Преголи так, как изображено на рисунке, соединяя его части A,B,C,D.

Задача состоит в следующем: «Найти такую точку города, выйдя из которой можно пройти по всем мостам по одному разу и вернуться в неё обратно».

Эйлер показал, что эта задача не имеет решения.

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

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

Лемма:

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

Доказательство:

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

Теорема (критерий Эйлеровости графа).

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

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

Достаточность.

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

Шаг 1. . Единственный граф, удовлетворяющий условиям теоремы изображён на рисунке.

Очевидно, его единственная дуга и образует эйлеров цикл.

Индуктивный переход.

Предположим, что утверждение теоремы (её достаточной части) справедливо для любого графа, у которого .

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

В противном случае рассмотрим граф, полученный из удалением дуг цикла .

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

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

Характеристики

Список файлов лекций